Generalized Connection Networks for Parallel Processor Intercommunication.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 papers 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 papers GCN has 6N log N switches, providing an alternative to banyan networks with ON log N switches but incomplete functionality.
- Computer Hardware
- Computer Systems
- Non-Radio Communications