A family of parallel prefix algorithms embedded in networks

This paper presents a family of algorithms for producing, from (υ₀, υ₁, ..., υ_n-1), all initial prefixes x_i=υ₀θυ₁ θ···θυ_i (i=0, 1, ..., n-1) in parallel in interconnection networks such as the omega network and the hypercube, where θ is an associative binary operator. Each algorithm can be embedded in the switches and interconnections of the network, and can be executed in O((log₂ r+1) log_r n) time steps provided that the network connecting n processors is constructed by using an r×r switch, and that parallelism within as well as among individual switches is exploited. The objective of these algorithms is to attain a communication pattern that fits the topology of the network. One type of network can be made equivalent to, or can be embedded in, another type of network, so a family of algorithms can be derived from one basic algorithm. In the basic algorithm, every processor p_i upward multicasts υ_i to processors p_k (k=i+1, i+2, ..., n - 1). En route to p_i, υ_j (j=0, 1, ..., i - 1) are combined in the switches to produce the (i - 1)th initial prefix x_i-1 that is received by p_i, which can then compute the ith initial prefix x_i=x_i-1θυ_i