Design and implementation of the banyan interconnection network in TRAC
U. V. Premkumar, Rajan N. Kapur, Miroslaw Malek, G. Jack Lipovski, P. Horne · 1980
Over the past few years, owing to technological breakthroughs in building cheap, reliable and powerful microprocessors and relatively cheap LSI memories, interconnection networks have become the major hardware cost in design and implementation of the multiprocessor systems. This situation occurs from the fact that many more functions may be expected from the interconnection network (switch) than the establishment of simple bus connections. Even if only the communication links were considered, the complexity of some networks make their implementation prohibitive. An example of such a network is a crossbar whose complexity is 0(n**2) where n represents a number of resources which may be connected to another set of n resources. This switch provides a separate connection between each pair of resources (Figure 1). It has been empirically shown that implementation of a crossbar switch for a large n is very difficult and with a state-of-the-art technology practically infeasible for n>50.