Semigroup and prefix computations on improved generalized mesh-connected computers with multiple buses

Various augmenting mechanisms have been proposed to enhance the communication efficiency of mesh-connected computers (MCC's). One major approach is to add non-configurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). In this paper, we propose a new class of generalized MMB's, the improved generalized MMB's (IMMB's). Each processor in an IMMB is connected to exactly two buses. We show the power of IMMB's by considering semi-group and prefix computations. Specifically, we show that semigroup and prefix computations on N operands, and data broadcasting all take O(log N) time on IMMB's. This is the first O(log N) time algorithm for these problems on arrays with fixed broadcasting buses.