An improved generalization of mesh-connected computers with multiple buses

Yi Pan, S. Q. Zheng, Keqin Li, Hong Shen

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


Mesh-connected computers (MCCs) are a class of important parallel architectures due to their simple and regular interconnections. However, their performances are restricted by their large diameters. Various augmenting mechanisms have been proposed to enhance the communication efficiency of MCCs. One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). We propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). We compare IMMBs with MMBs and a class of previously proposed generalized MMBs (GMMBs). We show the power of IMMBs by considering semigroup and prefix computations. Specifically, as our main result we show that for any constant O < ε < 1, one can construct an N1/2 × N1/2 square IMMB using which semigroup an prefix computations on N operands can be carried out in O(Nε) time, while maintaining O(1) broadcasting time. Compared with the previous best complexitie O(N1/8) and O(N1/16) achieved on a rectangular MMB and GMMB, respectively, for the same computations, our results show that IMMBs are more powerful than MMBs and GMMBs.

Original languageEnglish
Pages (from-to)293-305
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
Publication statusPublished - Mar 2001
Externally publishedYes


  • Bus
  • Mesh-connected computer
  • Mesh-connected computer with multiple buses
  • Parallel algorithm
  • Parallel architecture
  • Parallel computing
  • Processor array


Dive into the research topics of 'An improved generalization of mesh-connected computers with multiple buses'. Together they form a unique fingerprint.

Cite this