22n-k×2k 토러스와 HFN(n,n), HCN(n,n) 사이의 임베딩 알고리즘
Embedding Algorithm between 22n-k？2k Torus and HFN(n,n), HCN(n,n)
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 22n-k×2k 토러스 연결망과 상호연결망 HFN(n,n)과 HCN(n,n) 사이의 임베딩을 분석한다. 먼저, 22n-k×2k 토러스를 HFN(n,n)에 연장율 3과 밀집율 4로 임베딩 가능함을 보이며, 평균연장율이 2 이하임을 증명한다. 그리고 22n-k×2k 토러스를 HCN(n,n)에 연장율 3으로 임베딩 가능함을 보이며, 평균 연장율이 2 이하임을 증명한다. 또한 HFN(n,n)과 HCN(n,n)이 22n-k×2k 토러스에 임베딩하는 연장율이 O(n)임을 보인다. 이러한 결과는 토러스에서 개발된 여러 가지 알고리즘을 HCN(n,n)과 HFN(n,n)에서 효율적으로 이용할 수 있음을 의미한다.
Abstract
In this paper, we will analysis embedding between 22n-k×2k torus and interconnection networks HFN(n,n), HCN(n,n). First, we will prove that 22n-k×2k torus can be embedded into HFN(n,n) with dilation 3, congestion 4 and the average dilation is less than 2. And we will show that 22n-k×2k torus can be embedded into HCN(n,n) with dilation 3 and the average dilation is less than 2. Also, we will prove that interconnection networks HFN(n,n) and HCN(n,n) can be embedded into 22n-k×2k torus with dilation O(n). These results mean so many developed algorithms in torus can be used efficiently in HFN(n,n) and HCN(n,n).
참고문헌 (16)
- S. B. Akers, "A Group-Theoretic Model for Symmertric Interconnection Network", pp.555~565 (1989)
- L. Bjorneborn, "Fault-tolerant cycle embedding in hierarchical cubic networks", 43(1), pp.28~38 (2004)
- J. Bruck, "Wildcard Dimensions, Coding Theory and Fault-Tolerant Meshes and Hypercubes", 44(1), pp.150~155 (1995)
- D. R. Duh, "Algorithms and Properties of a New Two-Level Network with Folded Hypercubes as Basic Modules", 6(7), pp.714~723 (1995)
- T-Y, "A Survey of Interconnection Networks", pp.12~27
- J.-S. Fu, "Cycle embedding in faulty hierarchical cubic networks", pp.860~864 (2002)
- J.-S. Fu, "Hamiltonicity of the hierarchical cubic network", 35, pp.59~79 (2002)
- J.-S. Fu, "Node-disjoint paths and related problems on hierarchical cubic networks", 40(3), pp.142~154 (2002)
- K. Ghose, "Hierarchical Cubic Networks", 6(4), pp.427~436 (1995)
- J.-S. Kim, "Embedding among HCN(n,n), HFN(n,n) and hypercube", pp.533~540 (2001)
- E. Oh, "Double-Link Failure Recovery in WDM Optical Torus Networks", pp.708~717 (2004)
- E. Oh, "Fault-tolerant routing in mesh-connected 2D tori", 2659, pp.527~536 (2003)
- R. Pranav, "Fast and efficient submesh determination in faulty tori", 3296, pp.474~483 (2004)
- A, "Embedding of Tree Networks into Hypercubes", pp.238~249 (1985)
- S-K. Yun, "Comments on 'Hierarchical Cubic Networks", 9(4), pp.410~414 (1998)
- 김종석, "하이퍼큐브와 HCN(n,n), HFN(n,n) 사이의 임베딩", 정보처리학회논문지. 컴퓨터 및 통신시스템, 9(2), pp.191~196 (2002), 한국정보처리학회