ONE-TO-ALL PERSONALIZED COMMUNICATION IN TORUS NETWORKS

摘要

Given a multicomputer system of parallel processors connected in a torus network, the one-to-all personalized communication 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 network into disjoint subnetworks. We also present a heuristic 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.