Abstract
Semigroup and prefix computations on two-dimensional mesh-connected computers with multiple broadcasting (2-MCCMB's) are studied in this paper. Previously, only square 2-MCCMB's with N processing elements were considered for semigroup computations of N data items, and O(N1/6) time was required. It is found that square machines are not the best form for semigroup computations, and an O(N1/8) time algorithm is thus derived on an N5/8 x N3/8 rectangular 2-MCCMB. This time complexity can be further reduced to O(N1/9) if fewer PE's are used. Following the same way, parallel algorithms for prefix computations are also derived with the same time complexities. © 1990 IEEE