On embedding between 2D meshes of the same size
Xiaojun Shen, Weifa Liang, Qing‐Miao Hu · IEEE Transactions on Computers · 1997
Mesh is one of the most commonly used interconnection networks and, therefore, embedding between different meshes becomes a basic embedding problem. Not only does an efficient embedding between meshes allow one mesh-connected computing system to efficiently simulate another, but it also provides a useful tool for solving other embedding problems. The authors study how to embed an s/sub 1//spl times/t/sub 1/ mesh into an s/sub 2//spl times/t/sub 2/ mesh, where s/sub i//spl les/t/sub i/ (i=1, 2), s/sub 1//spl les/t/sub 1/=s/sub 2/t/sub 2/, such that the minimum dilation and congestion can be achieved. First, they present a lower bound on the dilations and congestions of such embeddings for different cases. Then, they propose an embedding with dilation [s/sub 1//s/sub 2/]+2 and congestion [s/sub 1//s/sub 2/]+4 for the case s/sub 2//spl ges/s/sub 2/, both of which almost match the lower bound [s/sub 1//s/sub 2/]. Finally, for the case s/sub 1/