Generalized Connection Networks for Parallel Processor Intercommunication

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^Nmappings 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 GCN due to Ofman [7] is here improved to use less than 7.6N log N contact pairs, making it the minimal known construction.