4-Systolic Broadcasting in a Wrapped Butterfly Network

摘要

In this paper we present a 4-systolic algorithm for broadcasting, in the one-port model, in an undirected d-dimensional (d even) wrapped butterfly. We prove that the broadcast time for the algorithm is no more than 5d/2-2, hence making it the fastest known algorithm of this nature for broadcasting in a wrapped butterfly.