Partial Connection : A New Approach To Improving The Bandwidth Of Banyan Networks

Abstract

Banyan networks have been proposed as interconnection networks for large multiprocessors, those containing hundreds or even thousands of processors. Their attractiveness is attributed to two features : low manufacturing cost and self routing. However, these networks have a serious problem, low bandwidth. Unfortuntely, this problem gets worse as the size and/or the load of the network increases. In this paper we introduce a novel approach to solve this problem, partial connection. The idea is that when some of the network terminals arc left unconnected, less blocking takes place, and therefore the bandwidth of the network improves. We explore this approach using an exact analytical model. The resits obtained from the model, which have been validated by extensive simulation studies, arc very promising. An arbitrary bandwidth improvement can be obtained. We have found that the exact amount of improvement depends not only on the amount of unconnected terminals, but also on their side and their arrangement with respect to the connected ones. It depends also on the network original size and the load. The partial connection approach has three primary advantages. First, it works better as the size and / or the load of the network increases. Second, it preserves the same routing procedure of the normal network. Third, it is extremely easy to implement. The last advantage is due to the fact that the approach preserves the architectural structure of the normal network, and docs not require any alteration in the design of its original components. The approach can be a convenient option in situations where performance is more important than cost. It can also be applied only around very active terminals, e.g. hot spots, if cost is a concern.