An Optimal Routing Algorithm for Mesh-Connected Parallel Computers

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

85 Scopus citations


An opUmal algorithm to route data in a mesh-connected parallel computer is presented This algorithm can be used to perform any data routing that can be specified by the permutation and complementing of the bits in a PE address Matrix transpose, bit reversal, vector reversal, and perfect shuffle are examples of data permutations that can be specified in this way The algorithm presented uses the minimum number of unit distance routing steps for every data permutation that can be specified as above.

Original languageEnglish (US)
Pages (from-to)6-29
Number of pages24
JournalJournal of the ACM (JACM)
Issue number1
StatePublished - Jan 1 1980
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • complexity
  • data routing
  • mesh-connected computer
  • parallel algorithm
  • permutation


Dive into the research topics of 'An Optimal Routing Algorithm for Mesh-Connected Parallel Computers'. Together they form a unique fingerprint.

Cite this