Constant congestion embedding of node balanced trees into optimal-sized grids

摘要

The problem of efficiently implementing parallel algorithms on message passing parallel computer systems and the problem of efficiently simulating networks by other networks have been studied for many years as the graph embedding problem. In particular it is known that the minimal congestion embedding is very important for a parallel system which adopts cut-through switching techniques, which are well used in recent architectures for node-to-node communication. In this paper, we show that every binary tree such that for each vertex u, the ratio of the number of vertices of the subtrees rooted by children of u is bounded by a constant can be embedded with constant congestion into a grid with the same number of vertices as that of the tree.