메쉬의 교차큐브에 대한 임베딩
Embedding a Mesh into a Crossed Cube
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
교차큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지므로 각광 받아 왔다. 크기가 2X2m이거나 4X2m인 메쉬를 연장율 1로 교차큐브에 임베딩하는 연구 결과는 이미 발표된 바 있다. 그러나 양변의 길이가 모두 8 이상인 메쉬가 교차큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 크기 2nX2m인 메쉬가 교차큐브에 연장율 1, 확장율 (수식)로 임베딩될 수 있음을 보인다, (수식)
Abstract
The crossed cube has received great attention because it has equal or superior properties to the hypercube that is widely known as a versatile parallel processing system. It has been known that a mesh of size 2X2m can be embedded into a crossed cube with dilation 1 and expansion 1 and a mesh of size 4X2m with dilation 1 and expansion 2. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a crossed cube with dilation 1. In this paper, we show that a mesh of size 2nX2m can be embedded into a crossed cube with dilation 1 and expansion (수식) where and (수식).
참고문헌 (19)
- F. Berman, "On mapping parallel algorithms into parallel architectures", J. Parallel Distrib. Comput, 4, pp.439~458 (1987)
- S.L. Bezrukov, "The congestion of n-cube layout on a rectangular grid", Discrete Math, 213(1-3), pp.13~19 (2000)
- C.-P. Chang, "Edge congestion and topological properties of crossed cubes", IEEE Trans. Parallel and Distributed Systems, 11(1), pp.64~80 (2000)
- V. Chaudhary, "mapping of parallel algorithms onto parallel architectures", Proc. Int’l Conf. Parallel Processing, pp.137~141 (1990)
- Q. Dong, "Embedding a family of disjoint 3D meshes into a crossed cube", Information Sciences, 178(11), pp.2396~2405 (2008)
- K. Efe, "A variation on the hypercube with lower diameter", IEEE Trans. Computers, 40(11), pp.1312~1316 (1991)
- K. Efe, "The crossed cube architecture for parallel computing", IEEE Trans. Parallel and Distributed Systems, 3(5), pp.513~524 (1992)
- K. Efe, "Topological properties of the crossed cube architecture", Parallel Computing, 20, pp.1763~1775 (1994)
- J. Fan, "Diagnosability of crossed cubes under the comparison diagnosis model", IEEE Trans. Parallel and Distributed Systems, 13(10), pp.1099~1104 (2002)
- J. Fan, "Embedding meshes into crossed cubes", Information Sciences, 177(15), pp.3151~3160 (2007)
- J. Fan, "The t", k-diagnosability of the BC graphs, 2005, pp.53(2), 176~184
- W.-T. Huang, "On the fault-tolerant hamiltonicity of faulty crossed cubes", IEICE Trans. Fundamentals, E85-A(6), pp.1359~1370 (2002)
- P. Kulasinghe, "Connectivity of the crossed cube", Information Processing Letters, 61, pp.221~226 (1997)
- P. Kulasinghe, "Embedding binary trees into crossed cubes", IEEE Trans. Computers, 44(7), pp.923~929 (1995)
- 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", pp.1990, Springer-Verlag
- 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)
- M.-C. Yang, "Fault-tolerant cycle-embedding of crossed cubes", Information Processing Letters, 88(4), pp.149~154 (2003)