Embedding complete k-ary trees into k-square 2-D meshes with optimal edge congestion
Wormhole switching is distance insensitive but suffers from blocking in the case of communication conflicts. Embeddings of process graphs into interconnection networks of parallel machines with wormhole switching can ignore dilation, but should minimize edge congestion for a given load or expansion. In this paper, we present an algorithm for embedding complete k-ary trees into k-square 2-D meshes with load 1, asymptotically optimal expansion, and nearly optimal edge congestion. (C) 2000 Elsevier Science B.V. All rights reserved.
2-d mesh edge congestion load expansion embedding problem complete tree divide & conquer computation