Node placement optimization in ShuffleNets

Abstract

Node placement problem in ShuffleNets is a combinatorial optimization problem. In this paper an efficient node placement algorithm, called the gradient algorithm, is proposed. A communication cost function between a node pair is defined and the gradient algorithm places the node pairs one by one, based on the gradient of the cost function. Then two lower bounds on the traffic weighted mean internodal distance h are proposed. The performance of the gradient algorithm is compared to the lower bounds as well as to some algorithms in the literature. Significant reduction of h̄ is obtained with the use of the gradient algorithm, especially for highly skewed traffic distributions. For a ShuffleNet with N = 64 nodes, the h̄ found is only 22% above the lower bound for the uniform random traffic distribution, and 14.7% for a highly skewed traffic distribution with skew factor γ = 100. © 1998 IEEE.