Isomorphic Routing on a Toroidal Mesh
INFORMS Journal on Computing · 1996 · Volume 8 · Issue 1
Abstract
We study a routing problem that arises on SIMD parallel architectures whose communication network forms a toroidal mesh. We assume there exists a set of k message descriptors {( x i , y i ) ∣ i = 1, 2, …, k }, where ( x i , y i ) indicates that the i th message's recipient is offset from its sender by x i hops in one mesh dimension, and y i hops in the other. Every processor has k messages to send, and all processors use the same set of message descriptors. The SIMD constraint implies that at any routing step, every processor is actively routing messages with the same descriptors as any other processor. We call this Isomorphic Routing . Our objective is to find the isomorphic routing schedule with the minimum makespan. We consider a number of variations on the problem, yielding complexity results from O ( k ) to NP-complete. Most of our results follow after we transform the problem into a scheduling problem, where it is related to other well-known scheduling problems.
Keywords
analysis of algorithms, computational complexity, networks/graphs, message routing, production/scheduling, open shop scheduling
Enable JavaScript for citation tools and additional paper interactions.