Embedding tree structures in massively parallel computers
Jaafar Gaber, Bernard Toursel, Gilles Gonçalves, T. Hsu · 1995
Trees are an important class of computational structures due to their favoumble property of logarithmic path from the root to any leaf element.Since simple and regular interconnections among nodes are needed, they are easily manipulated.Mapping problems arise when the tree structure differs from the processor interconnection of the pamllel computer.The MasPar's MP-2 is a massively parallel computer where processors are interconnected via the X-Net neighborhood two-dimensional mesh and the globul multistage crossbar router network.We present novel mapping schemes for trees on the MasPar's MP-2 twodimensional mesh and on the two-dimensional mesh together with the MasPar's MP-2 multistage crossbar network.Appropriate algorithms of the mapping scheme on the two-dimensional mesh (or grid) are presented and are shown to be superior over known mappings on square arrays (or grids).