Efficient submesh permutations in wormhole-routed meshes

Ching Tien Ho, Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies how to concurrently permute related logical or physical submeshes in a d-dimensional n x ⋯ x n physical mesh via wormhole and dimension-ordered routing. Our objective is to minimize the congestion for realizing the permutations, while maximizing the number and dimensionality of permuted submeshes. We show that for d ≤ 2α - β, concurrent independent permutations of nβ related physical submeshes, each of α dimensions, can be performed in two routing steps without congestion. If the permuted submeshes are logical ones, they can be permuted in one, instead of two, routing step. In addition, any shift operation along any axis of the logical mesh can be performed in the physical mesh without congestion. We also show that if all nodes know the permutation function, any permutation within a submesh of dimensions [2(d - 1)/3] can be realized in three routing steps without congestion.

Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalInformation Sciences
Volume107
Issue number1-4
DOIs
StatePublished - Jun 1998

Funding

This paper studies how to concurrently permute related logica/ or physical submeshes in a d-dimensional physical mesh via wormhole and * Corresponding author. E-mail: [email protected]. E-mail: [email protected]. 2 Research supported in part by NSF Grant CCR-9531028.

Keywords

  • Meshes
  • Permutations
  • Wormhole routing

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Efficient submesh permutations in wormhole-routed meshes'. Together they form a unique fingerprint.

Cite this