Barrel shifter-a close approximation to the completely connected network in supporting dynamic tree structured computations

摘要

High performance computing requires high quality load distribution of processes of a parallel application over processors in a parallel computer at runtime such that both maximum load and dilation are minimized. The performance of a simple randomized tree growing algorithm on the barrel shifter and the Illiac networks is studied in this paper. The algorithm spreads tree nodes by letting them to take random walks to neighboring processors. We develop recurrence relations that characterize expected loads on all processors. We find that the performance ratio of probabilistic dilation-1 tree embedding in the barrel shifter network with N processors (a network with node degree O(log N)) is very close to that in the completely connected network of the same size. However, the hypercube network, which also has node degree log N, does not have such a capability. As a matter of factor, even the Illiac network, which is a subnetwork of the barrel shifter, has an optimal asymptotic performance ratio.