On the Parallel Implementation of a Generalized Broadcast

Abstract. We prove the correctness of optimized parallel implementations of a generalized broadcast, in which a value b is distributed to a sequence of processors, indexed from 0 upwards, such that processor i receives g i b (i.e., some function g applied i times to b). Its straight-forward implementation is of linear time complexity in the number of processors. This type of broadcast occurs when combining scans with an ordinary broadcast. The optimized parallel implementations we describe is based on an odd-even tree and has logarithmic time complexity