크기 2n×2m 인 메쉬의 꼬인 큐브에 대한 임베딩
Embedding a Mesh of Size 2n×2m Into a Twisted Cube
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m에 대하여 크기가 2n×2n 인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 4×2m인 메쉬가 연장율 과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 이 짝수일 경우엔 크기 2n×2m 인 메쉬가 꼬인 큐브에 연장율1 , 확장율 2n-1로 임베딩됨을 보이고 이 홀수일 경우엔 연장율1 , 확장율2n 로 임베딩됨을 보인다 (1≤n≤m).
Abstract
The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even , a mesh of size 2×2m can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size 2×2m with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size 2n×2m can be embedded into a twisted cube with dilation 1 and expansion 2n-1 for even m and with dilation 1 and expansion 2n for odd where 1≤n≤m.
참고문헌 (18)
- S. Abraham, "The twisted cube topology for multiprocessors: a study in network asymmetry", J. Parallel Distrib. Comput., 13(1), pp.104~110 (1991)
- E. Abuelrub, "Embedding complete binary trees into twisted hypercubes", Proc. of the Int. Conf. on Computer Applications in Design, Simulation and Analysis, pp.1~4 (1992)
- F. Berman, "On mapping parallel algorithms into parallel architectures", J. Parallel Distrib. Comput., 4(5), pp.439~458 (1987)
- S.L. Bezrukov, "The congestion of n-cube layout on a rectangular grid", Discrete Math, 213(1), pp.13~19 (2000)
- C.-P. Chang, "Topological properties of twisted cube", Information Sciences, 113, pp.147~167 (1999)
- V. Chaudhary, "Generalized mapping of parallel algorithms onto parallel architectures", Proc. Int’l Conf. Parallel Processing, pp.137~141 (1990)
- J. Fan, "The t", k-diagnosability of the BC Graphs, 2005, pp.54(2), 176~184
- J. Fan, "Edge-pancyclicity of twisted cubes", Lecture Notes in Comput. Sci., 3827, pp.1090~1099 (2005)
- J. Fan, "Optimal fault-tolerant embedding of paths in twisted cubes", J. Parallel Distrib. Comput, 67(2), pp.205~214 (2007)
- J.-S. Fu, "Fault-free Hamiltonian cycles in twisted cubes with conditional link faults", Theoretical Computer Science, 407(1), pp.318~329 (2008)
- P. A. J. Hilbers, "The twisted cube. in: PARLE:Parallel Architectures and Languages Europe, Parallel Architectures, Vol.1", pp.152~158 (1987), Springer
- W.-T. Huang, "Fault-tolerant hamiltonicity of twisted cubes", J. Parallel Distrib. Comput., 62(4), pp.591~604 (2002)
- C.-J. Lai, "Embedding a family of meshes into twisted cubes", Information Processing Letters, 108(5), pp.326~330 (2008)
- A. Matsubayashi, "VLSI layout of trees into grids of minimum width", IEICE Trans. Fundamentals, E87-A(5), pp.1059~1069 (2004)
- B. Monien, "Embedding one interconnection network in another", Computing Supplementum, 7, pp.257~282 (1990)
- A. Patel, "Area-efficient VLSI layouts for binary hypercubes", IEEE Trans. Computers, 49(2), pp.160~169 (2000)
- A. Rosenberg, "Issues in the study of graph embeddings", Lecture Notes in Computer Science, 100, pp.150~176 (1981), Springer-Verlag
- M.-C. Yang, "On embedding cycles into faulty twisted cubes", Information Sciences, 176(6), pp.676~690 (2006)