Generalized Connection Networks for Parallel Processor Intercommunication.
Abstract
A generalized connection network (GCN) is a switching network with N inputs and N outputs that can be set to pass any of the N to the Nth power mappings of inputs onto outputs. This paper demonstrates an intimate connection between the problems of GCN construction, message routing on SIMD computers, and resource partitioning. A previous GCN is here improved to use less than 8N log N contact pairs, making it the minimal known construction. Any GCN construction leads to a new algorithm for the broadcast of messages among processing elements of an SIMD computer, when each processing element is to receive one message. Previous approaches to message broadcasting have not handled the problem in its full generality. The algorithm arising from this paper's GCN takes 8 log N (or 13 sq.rt. N) routing steps on an N element processor of the perfect shuffle (or mesh-type) variety. If each resource in a multiprocessing environment is assigned one output of a GCN, private buses may be provided for any number of disjoint subsets of the resources. The partitioning construction derived from this paper's GCN has 6N log N switches, providing an alternative to banyan networks with O(N log N) switches but incomplete functionality.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1977
- Accession Number
- ADA046859
Entities
People
- C. D. Thompson
Organizations
- Carnegie Mellon University