Realizing Optimal All-to-All Personalized Communication Using Butterfly-Based Networks

Abstract

The communication network is a key component in parallel and distributed systems, high-performance computing (HPC) systems and Data Centers, as information exchange has a key role in communication-intensive applications. The all-to-all personalized exchange is a relevant communication pattern and has been extensively studied for many network topologies. When considering a Multistage Interconnection Network (MIN) with $\log N$ stages, the realization of all-to-all communication is obtained through a sequence of admissible permutations forming a Latin square. If a particular Latin square is desired, double MINs consisting of $2 \log N$ -1 stages are required. In this work, we consider the Butterfly-Butterfly network to realize the Latin square consisting of the identity permutation and its $N-1$ rotations, $\mathcal {RLS}$ , and we show how to obtain the sequence of rotations forming such a Latin square, without storing it. We propose a method to realize the $N$ permutations in pipeline fashion taking optimal $O(N)$ time, and we analyze the energy consumption according to the order of realization of the permutations, both on Butterfly-Butterfly network and on a single Butterfly used twice. We also show how to generate a Latin Square starting from any realizable permutation exploiting the switch configurations of the $\mathcal {RLS}$ .

Keywords

• All-to-all personalized communication
• butterfly network
• latin squares
• MINs