One-to-All Personalized Communication in Torus Networks

W. Mao, J. Chen, and W. Watson, III (USA)


One-to-all personalized communication, scatter and gather, parallel computing, torus network, algorithm, optimization.


Given a multicomputer system of parallel processors con nected in a torus network, the one-to-all personalized com munication is to send from the root processor unique data to each of the other processors in the network. Under the assumptions of same-size data to each processor, store and-forward routing, and all-port processors, we formulate the one-to-all personalized communication problem as an optimization problem with the goal to minimize the total elapsed time (measured in the number of time steps) for all data to reach their respective destinations. We design an optimal algorithm based on partitioning the torus net work into disjoint subnetworks. We also present a heuris tic algorithm based on a greedy strategy. We implement the algorithms on two Linux clusters with Gigabit Ethernet torus connection, currently in use at the Jefferson National Lab and configured as a 2-dimensional 8 × 8 torus and a 3-dimensional 4 × 8 × 8 torus, respectively. We analyze the performance of the algorithms using data collected in experiments.

Important Links:

Go Back