Continuous message routing on fixed-connection networks
Yukon Chang · University Microfilms International eBooks · 1986
Message routing is known to be an important problem in parallel computation; besides its intrinsic interest it is often used as a subroutine in parallel algorithms to transmit the results of subcomputations to the processors that will use them. In this thesis we study the problem of continuous routing in which, unlike commonly studied one-wave routing, messages are allowed to be generated at arbitrary times. Thus, continuous routing can more realistically model the interprocessor communication appearing in a long parallel computation. We study the feasibility problem of continuously routing a set of messages with individual deadlines on mesh-connected processor arrays. In the feasibility problem we are to determine whether every message can be at its destination by the deadline. These problems are in general very hard--testing feasibility is NP-hard on the linear array. In fact, it is NP-hard on almost all interconnection networks that have appeared in the literature. However, certain restricted versions are shown solvable in polynomial time. The reduction technique is applied to problems in other areas such as VLSI wire routing and multiprocessor scheduling. We also study continuous broadcasting in which broadcast messages replace point-to-point messages. We give a distributed broadcasting algorithm on the 2-dimensional mesh and show that its feasibility testing can be done in polynomial time. Next we search for efficient probabilisitic routing algorithms for periodic continuous routing. In this problem we assume that one permutation becomes available every constant number of time steps and has to be routed as fast as possible. We prove that on the n-dimensional hypercube the periodic continuous routing process can be carried out indefinitely long with the following performance guarantee: with overwhelming probability for any permutation, regardless of how late it is generated, we can show that it will finish in O(n) time steps after it became available. As a preparation step of proving this main result, we improve Valiant's classical 2-phase probabilistic routing result when routing n permutations at the same time from an O(n('2)) running time to O(n).