메쉬 부류 네트워크를 피터슨-토러스(PT) 네트워크에 임베딩
Embedding Mesh-Like Networks into Petersen-Torus(PT) Networks
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문은 분지수가 상수인 네트워크들을 피터슨-토러스(PT) 네트워크에 임베딩 가능함을 보인다. 상호연결망 G가 H에 임베딩 되면 G에서 설계된 병렬 알고리즘을 상호연결망 H에 적용할 수 있다. 토러스(메쉬)를 PT에 연장율 5, 밀집율 5 그리고 확장율 1에 일대일 임베딩 하였고, 허니컴브 메쉬를 PT에 연장율 5, 밀집율 2 그리고 확장율 5/3에 일대일 임베딩 하였다. 추가로 평균 연장율을 분석하였다. 널리 알려진 토러스와 허니컴브 메쉬 네트워크를 연장율과 밀집율을 5이하에 PT에 임베딩 함으로써 웜홀 라우팅 방식과 store-and-forward 방식 모두에서 임베딩 알고리즘이 사용 가능하고, 일대일 임베딩을 함으로써 시뮬레이션시 프로세서 작업 처리량을 최소화 하였다.
Abstract
In this paper, we prove mesh-like networks can be embedded into Petersen-Torus(PT) networks. Once interconnection network G is embedded in H, the parallel algorithm designed in Gcan be applied to interconnection network H. The torus is embedded into PT with dilation 5, link congestion 5 and expansion 1 using one-to-one embedding. The honeycomb mesh is embedded into PT with dilation 5, link congestion 2 and expansion 5/3 using one-to-one embedding. Additional, We derive average dilation. The embedding algorithm could be available in both wormhole routing system and store-and-forward routing system by embedding the generally known Torus and honeycomb mesh networks into PT at 5 or less of dilation and congestion, and the processor throughput could be minimized at simulation through one-to-one.
참고문헌 (23)
- S. Bettayeb, "Embedding Star Networks into Hypercubes", IEEE trans. comput, 45(2), pp.186~194 (1996)
- M. Hamdi, "Embedding Hierarchical Hypercube Networks into the Hypercube", IEEE trans. on Parallel and Distributed Systems, 8(9), pp.987~902 (1997)
- X. Shen, "On Embedding Between 2D Meshes of the Same Size", IEEE trans. comput, 46(8), pp.880~889 (1997)
- I. Stojmenovic, "Honeycomb Network: Topological Properties and Commnication Algorithms", IEEE trans. on Parallel and Distributed Systems, 8(10), pp.1036~1042 (1997)
- S. K. Das, "Embeddings into Hyper Petersen networks: yet another hypercube-like interconnection Topology", VLSI Design, 2(4), pp.335~351 (1995)
- C. H Kim, "Embedding Full Ternary Trees into Recursive Circulants", EurAsia- ICT2002, pp.874~882 (2002)
- S. Y. Hsieh, "Embedding of Cycles in the Faulty Hypercube", ACSAC2005, pp.229~235 (2005)
- S. Y. Hsieh, "Embed longest rings onto star graphs with vertex fault", Proceedings of the International Conference on Parallel Processing, pp.140~147 (1998)
- P. F. Cortese, "On Embedding a Cycle in a Plane Graph", GD2005, pp.49~60 (2005)
- S. Bezrukov, "Embedding complete trees into the Hypercube", Discrete Applied Mathematics, 100(2-3), pp.101~119 (2001)
- J. H. Park, "Embedding Starlike Trees into Hypercube-Like Interconnection Networks", ISPA 2006 Ws LNCS 4331, pp.301~310 (2006)
- K. Li, "On the Performance of Randomized Embedding of Reproduction Trees in Static Networks", International Journal of Parallel Programming, 31(5), pp.393~406 (2003)
- K. Li, "Comparative Performance Evaluation of a Random-Walk-Based Algorithm for Embedding Dynamically Evolving Trees in Hypercubic Networks", Computation and Concurrency:Practice and Experience, 15 (2003)
- D. K. Saikia, "Embedding Torus on the Star Graph", IEEE Transactions on Parallel and Distributed Systems, 9(7), pp.650~663 (1998)
- Z. Miller, "Near Embeddings of Hypercubes into Cayley Graphs on the Symmetric Group", IEEE Transactions on Computers, 43(1), pp.13~22 (1994)
- M. Y. Chan, "On Embedding Rectangular Grids in Hypercubes", IEEE Transactions on Computers, 37(10), pp.1285~1288 (1988)
- K. W. Tang, "Diagonal and toroidal Mesh Networks", IEEE trans. comput, 43(7), pp.815~826 (1994)
- J. A. Ellis, "Embedding Rectangular Grids into Square Grids", IEEE Transactions on Computers, 40(1), pp.46~52 (1991)
- J. A. Ellis, "Embedding grids into grids: techniques for large compression ratios", Networks, 27, pp.1~17 (1996)
- S. H. S. Huang, "On embedding rectangular meshes into rectangular meshes of smaller aspect ratio", Information Processing Letters, 63, pp.123~129 (1997)
- S. Y. Kim, "An Approach for Torus Embedding", proc of international conference on parallel processing, pp.301~306 (1999)
- X. Yang, "Embedding torus in hexagonal honeycomb torus", IET Computers & Digital Techniques, 2, pp.86~93 (2008)
- 서정현, "멀티컴퓨팅 시스템을 위한 피터슨-토러스(PT) 네트워크", 정보과학회논문지 : 시스템 및 이론, 35(6), pp.263~272 (2008), 한국정보과학회