Accession Number:

ADA263152

Title:

Isomorphic Routing on a Toroidal Mesh

Descriptive Note:

Contractor rept.,

Corporate Author:

INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s):

Report Date:

1993-02-01

Pagination or Media Count:

25.0

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 xi, yi , where xi, yi indicates that the ith messages recipient is offset from its sender by xi hops in one mesh dimension, and yi hops in the other. Every processor has k messages to send, and all processors use the same set of message routing 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 least makespan. We consider a number of variations on the problem, yielding complexity results from Ok 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.... Message routing, Network, Scheduling, Complexity, Algorithms.

Subject Categories:

  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE