A Conflict-Free Routing Scheme on Multistage Interconnection Networks

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.