Mapping computation structures onto sw-banyan networks
Richard Douglas Degroot · 1981
There is an urgent need for very powerful computer systems whose processing powers exceed the capabilities of present day computers by several orders of magnitude. With the recent flourish of advances in microelectronics and LSI technology, it is becoming increasingly feasible to build such supersystems. General purpose computer systems containing hundreds, thousands, and even tens of thousands of processors, memories, and I/O devices are being proposed by many researchers. The interconnection networks used in these systems constitute a significant architectural component. Effective use of the interconnection network is a prerequisite to effective use of the interconnected resources. Many types of interconnection networks have been studied, including partitioning and permuting networks. One large class of networks, SW-banyans, has been studied extensively with respect to both their partitioning and permuting capabilities. Studies of interprocessor communication schemes have generally been limited to intrapartition bus-based communication or packet or message based interpartition communication and have included only one-to-one, one-to-many, and many-to-one interconnections. A method for allocating permanent circuit switched communication paths of arbitrary complexity between a set of processors, including many-to-many interconnections, in a tightly-coupled multimicroprocessor system is presented. This form of communication is applicable to a large number of process-structured computational models. A graph theoretic approach to the problem is used. The class of networks onto which the communication paths are mapped is the class of regular SW-banyan networks. Previous partitioning studies of SW-banyans are reviewed and the particular mapping problem studied is compared to other mapping problems. The mapping solutions presented are of two forms: (1) given a specific type of process-structured computation, such as a binary tree of pipeline, and a specific SW-banyan, what is the size of the largest such structure that can be mapped onto the given SW-banyan, and (2) given an SW-banyan an arbitrarily complex process-structured computation, is it possible to map this structure onto the SW-banyan? Several solutions of each type are presented.