Abstract
Two-dimensional mesh-connected computers with multiple broadcasting (2-MCCMBs) are studied. Previously, only square 2-MCCMBs with N processing elements (PEs) were considered for semigroup computations of N data items, and O(N 1/6 ) time was required. The authors propose three approaches to achieve a better performance. With fewer PEs, first, an O(N 1/7 ) time algorithm is derived on a square 2-MCCMB. Then it is found that square machines are not the best form for semigroup computations, and an O(N 1/8 ) time algorithm is thus derived on a rectangular 2-MCCMB with N PEs. This time complexity can be further reduced to O(N 1/9 ) if fewer PEs are used. Semigroup computations on k-dimensional MCCMBs are discussed.