Embedding Algorithm Between the Macro-star.pdf

Embedding Algorithm Between the Macro-star Graph and the Matrix-star Graph *Kim jeong-suk 1, Seo jung-hyun 2, Sim Hyun 3, Lee HyeongOk 4, 1 Department of Computer Science, Oklahoma State University, USA rockhee@hanmail.net 2,3 Department of Computer Science, Sunchon National University, 315 Maegok-dong, Sunchon, Chonnam, 540-742, Korea {jhseo@sunchon.ac.kr, simhyun@sunchon.ac.kr}, 82-61-752-3625 4 Department of Computer Education, Sunchon National University, 315 Maegok-dong, Sunchon, Chonnam, 540-742, Korea oklee@sunchon.ac.kr, 82-61-750-3345 Index Term – Interconnection Network, Macro-star, Matrix-star, Embedding Algorithm, Star Graph Abstract The Macro-star graph which has the star graph as a basic module has node symmetry, maximum fault tolerance, and hierarchical decomposition property. And, it is an interconnection network which improves a network cost against the star graph. A Matrix-star graph also has such a good properties of the Macro-star graph and is an interconnection network which has a lower network cost than the Macro- star graph. In this paper, we propose a method to embed between the Macro-star graph and a Matrix-star graph. We show that the Macro-star graph MS(k,n) can be embedded into a Matrix-star graph MSk,n+1 with dilation 2. In addition, we show that a Matrix-star graph MSk,n can be embedded into the Macro-star graph MS(k,n+1) with dilation 4 and average dilation 3 or less as well. This result means that several algorithms developed in the star graph can be simulated in a Matrix-star graph at a lower cost. 1. Introduction Parallel processing computer is classified multiprocessor which has shared-memory and multi- computer which uses distributed-memory. In the multi-computer system, each processor has its own local memory and is connecting by an interconnection network. * This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Researc