계층적 폴디드 하이퍼스타 네트워크의 임베딩 알고리즘 = Embedding Algorithms of Hierarchical Folded HyperStar Network

다국어 초록 (Multilingual Abstract)

Hierarchical Folded HyperStar Network has lower network cost than HCN(n,n) and HFN(n,n) which are hierarchical networks with the same number of nodes. In this paper, we analyze embedding between Hierarchical Folded HyperStar HFH(Cn,Cn) and Hypercube, HCN(n,n), HFN(n,n). The results of embedding are that HCN(n,n), HFN(n,n) and Hypercube Q2n can be embedded into HFH(Cn,Cn) with expansion and dilation 2, 3, and 4, respectively. Also, HFH(Cn,Cn) can be embedded into HFN(2n,2n) with dilation 1. These results mean so many developed algorithms in Hypercube, HCN(n,n), HFN(n,n) can be used efficiently in HFH(Cn,Cn).

국문 초록 (Abstract)

계층적 폴디드 하이퍼스타 네트워크는 동일한 노드 개수를 갖는 계층적 네트워크인 HCN(n,n)과 HFN(n,n)보다 망비용이 우수한 연결망이다. 본 연구에서는 하이퍼큐브, HCN(n,n), HFN(n,n)과 계층적 폴디드 하이퍼스타 HFH(Cn,Cn) 사이의 임베딩을 분석한다.
임베딩 결과는 HCN(n,n), HFN(n,n), 하이퍼큐브 Q2n은 계층적 폴디드 하이퍼스타 HFH(Cn,Cn)에 확장율 과 연장율 2, 3, 4로 각각 임베딩 가능하다. 또한, 계층적 폴디드 하이퍼스타 HFH(Cn,Cn)는 계층적 네트워크인 HFN(2n,2n)에 연장율 1에 임베딩 가능하다. 이러한 임베딩 결과는 하이퍼큐브, HCN(n,n), HFN(n,n)에서 개발된 알고리즘을 계층적 폴디드 하이퍼스타 HFH(Cn,Cn)에서 효율적으로 활용 가능함을 의미한다.

참고문헌 (Reference)

1 김종석, "계층적 Folded 하이퍼-스타 연결망(HFH): Folded 하이퍼-스타 연결망을 기반으로 하는 새로운 상호연결망" 한국정보처리학회 15 (15): 95-100, 2008

2 J.-S. Kim, "Topological and Communication aspects of Hyper-star Graphs" 2869 : 51-58, 2003

3 A. H. Esfahanian, "The Twisted N-Cube with Application to Multiprocessing" 40 (40): 88-93, 1991

4 S. Abraham, "The Twisted Cube Topology for Multiprocessor: A Study in Network Asymmetry" 13 : 104-110, 1991

5 김종석, "PMC 모델과 비교진단 모델을 이용한 하이퍼-스타 연결망의 진단도 분석" 한국정보처리학회 13 (13): 19-26, 2006

6 J. Kim, "Operationally Enhanced Folded Hypercubes" 5 (5): 1310-1316, 1994

7 A. K. Gupta, "Multiple Network Embeddings into Hypercubes" 19 : 73-82, 1993

8 M. M. Azevedo, "Low Expansion Packing and Embeddings of Hypercubes into Star Graphs: A Performance-Oriented Approach" 9 (9): 261-274, 1998

9 F. T. Leighton, "Introduction to Parallel Algorithms and Architectures : Arrays, Hypercubes" Morgan Kaufmann Publishers 1992

10 H.-O. Lee, "Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube" 2510 : 858-865, 2002

11 김종석, "Folded 하이퍼-스타 FHS(2n,n)의 위상적 성질 분석" 한국정보처리학회 14 (14): 263-268, 2007

12 A. Y. Wu, "Embedding of Tree Networks into Hypercubes" 2 : 238-249, 1985

13 S. Ranka, "Embedding Meshes on the Star Graph" 19 : 131-135, 1993

14 S. L. Johnsson, "Communication Efficient Basic Linear Algebra Computations on Hypercube Architectures" 4 : 133-172, 1987

15 S.-K. Yun, "Comments on Hierarchical Cubic Networks" 9 (9): 410-414, 1998

16 D-R. Duh, "Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules" 6 (6): 714-723, 1995

17 A. S. Vaidya, "A Class of Hypercube_like Networks" 800-803, 1993