All-to-All Scatter in de Bruijn and Kautz Networks

Abstract

In this paper, we describe algorithms for all-to-all scatter in all-port de Bruijn and Kautz networks. The algorithms are memory-optimal and asymptotically time- and transmission-optimal. We give algorithms for the noncombining model and their modifications for the limited combining model. The algorithms achieve asymptotic optimality on both store-and-forward and wormhole switched networks.