An Optimal Routing Algorithm for Mesh-Connected Parallel Computers

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

84 Scopus citations

Abstract

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)
Volume27
Issue number1
DOIs
StatePublished - Jan 1 1980
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

Cite this