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 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.