Optimal all-To-All personalized communication on Butterfly networks through a reduced Latin square

Information exchange has a key role both in distributed systems and in Data Centers. The all-To-All personalized communication (or complete exchange) is a relevant communication pattern in multiprocessor applications, such as matrix transposition, fast Fourier transform and distributed table lookup, and in Data Center applications, such as MapReduce and Spark. All-To-All personalized communication problem has been extensively studied in the past for many networks topologies. Interesting results are on Multistage Interconnection Networks (MINs) with log N stages (N is the size of the network), and are based on the realization of a sequence of permutations forming a Latin square, i.e. a matrix whose elements occur once in each row and each column. If a particular Latin square is desired, MINs with log N stage are not adequate, since they cannot realize all possible permutations. On the contrary, the use of double MINs, having 2log N-1 stages, can allow in principle the realization of any Latin square, the use of which could make possible particular applications.In this work, we consider the Butterfly-Butterfly network to realize the Latin square consisting of the identity permutation and its N-1 rotations, 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 in O(N) time, that is optimal. Our method can also be applied in systems that use a single Butterfly simply passing through the network twice, and in Data Centers using the flattened butterfly as network.