On embedding between 2D meshes of the same size

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₁×t₁ mesh into an s₂×t₂ mesh, where s_i⩽t_i (i=1, 2), s₁⩽t₁=s₂t₂, 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₁ /s₂]+2 and congestion [s₁/s₂]+4 for the case s₂⩾s₂, both of which almost match the lower bound [s₁/s₂]. Finally, for the case s ₁<s₂, we present an embedding which has a dilation less than or equal to 2√s₁