A Conflict-Free Routing Scheme on Multistage Interconnection Networks

Woei Lin, Tsang Ling Sheu, Chita R. Das, Tseyun Feng, Chuan Lin Wu

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this paper, we present a conflict-free routing scheme for a class of parallel and distributed computing systems. The core of the proposed routing scheme is a quadtree communication structure. The quadtree structure suggests a general approach to mapping a class of parallel algorithms with intensive communication requirements for selecting data from many different sources and distributing data from a single source. By properly merging messages and efficiently replicating data, the quadtree structure can complete required communications in O(log4 M) parallel steps, where M is the network size. We also consider contraction and stretch of the quadtree structure, while retaining its conflict-free property. Contracted and stretched tree structures allow us to adaptively balance off computation and communication requirements for various parallel algorithms.

Original languageEnglish (US)
Pages (from-to)1086-1097
Number of pages12
JournalIEEE Transactions on Computers
Issue number8
StatePublished - Aug 1989

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A Conflict-Free Routing Scheme on Multistage Interconnection Networks'. Together they form a unique fingerprint.

Cite this