계층적 폴디드 하이퍼스타 네트워크의 임베딩 알고리즘
Embedding Algorithms of Hierarchical Folded HyperStar Network
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
계층적 폴디드 하이퍼스타 네트워크는 동일한 노드 개수를 갖는 계층적 네트워크인 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)에서 효율적으로 활용 가능함을 의미한다.
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).
참고문헌 (17)
- S. Abraham, "The Twisted Cube Topology for Multiprocessor: A Study in Network Asymmetry", Journal of Parallel and Distributed Computer, 13, pp.104~110 (1991)
- M. M. Azevedo, "Low Expansion Packing and Embeddings of Hypercubes into Star Graphs: A Performance-Oriented Approach", IEEE Parallel and Distributed Systems, 9(3), pp.261~274 (1998)
- D-R. Duh, "Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules", IEEE Trans. Parallel and Distributed Systems, 6(7), pp.714~723 (1995)
- A. H. Esfahanian, "The Twisted N-Cube with Application to Multiprocessing", IEEE Trans. Computer, 40(1), pp.88~93 (1991)
- A. K. Gupta, "Multiple Network Embeddings into Hypercubes", J. Parallel and Distributed Computing, 19, pp.73~82 (1993)
- S. L. Johnsson, "Communication Efficient Basic Linear Algebra Computations on Hypercube Architectures", Journal of Parallel Distributed Computer, 4, pp.133~172 (1987)
- J. Kim, "Operationally Enhanced Folded Hypercubes", IEEE Trans. Parallel and Distributed Systems, 5(12), pp.1310~1316 (1994)
- J.-S. Kim, "Topological and Communication aspects of Hyper-star Graphs", LNCS, 2869, pp.51~58 (2003)
- H.-O. Lee, "Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube", LNCS, 2510, pp.858~865 (2002)
- F. T. Leighton, "Introduction to Parallel Algorithms and Architectures : Arrays, Hypercubes" (1992), Morgan Kaufmann Publishers
- S. Ranka, "Embedding Meshes on the Star Graph", J. parallel and Distributed Computing, 19, pp.131~135 (1993)
- A. S. Vaidya, "A Class of Hypercube_like Networks", Proc. of the 5th IEEE Symp. Parallel and Distributed Processing, pp.800~803 (1993)
- A. Y. Wu, "Embedding of Tree Networks into Hypercubes", J. Parallel and Distributed Computing, 2, pp.238~249 (1985)
- S.-K. Yun, "Comments on Hierarchical Cubic Networks", IEEE Trans. Parallel Distributed systems, 9(4), pp.410~414 (1998)
- 김종석, "PMC 모델과 비교진단 모델을 이용한 하이퍼-스타 연결망의 진단도 분석", 정보처리학회논문지A, 13(1), pp.19~26 (2006), 한국정보처리학회
- 김종석, "Folded 하이퍼-스타 FHS(2n,n)의 위상적 성질 분석", 정보처리학회논문지A, 14(5), pp.263~268 (2007), 한국정보처리학회
- 김종석, "계층적 Folded 하이퍼-스타 연결망(HFH): Folded 하이퍼-스타 연결망을 기반으로 하는 새로운 상호연결망", 정보처리학회논문지A, 15(2), pp.95~100 (2008), 한국정보처리학회