Reducing time complexities of semigroup computations on mesh-connected computers with multiple broadcasting

[[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(N1/6) time was required. The authors propose three approaches to achieve a better performance. With fewer PEs, first, an O(N1/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(N1/8) time algorithm is thus derived on a rectangular 2-MCCMB with N PEs. This time complexity can be further reduced to O(N1/9) if fewer PEs are used. Semigroup computations on k-dimensional MCCMBs are discussed.[[department]]資訊工程學