A FAMILY OF PARALLEL PREFIX ALGORITHMS EMBEDDED IN NETWORKS

This paper presents a family of algorithms for producing, from (v0, v1 ,..., v(n - 1), all initial prefixes x(i) = v0thetav1theta...thetav(i) (i = 0, 1,..., n - 1 in parallel in interconnection networks such as the omega network and the hypercube, where theta is an associative bin ary operator. Each algorithm can be embedded in the switches and inter connections of the network, and can be executed in the O(log2 r + 1) l og(r)n) time steps provided that the network connecting n processors i s constructed by using an r x r switch, and that parallelism within as well as among individual switches is exploited. The objective of thes e algorithms is to attain a communication pattern that fits the topolo gy of the network. One type of network can be made equivalent to, or c an 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 v(i) to processors p(k) (k = i + 1, i + 2,..., n - 1). En route to p(i), n(j) (j = 0, 1..., i - 1) are com bined in the switches to produce the (i - 1)th initial prefix x(i-1) t hat is received by p(i), which can then compute the ith initial prefix x(i) = x(i-1)thetav(i).