Look-ahead routing switches for multistage interconnection networks

Multistage interconnection networks have been implemented in several prototype parallel systems as well as marketed products. One major performance drawback of this type network is due to link contention. This contention may occur when messages share part of their routes with each other. Especially, under hot-spot traffic, the network can be easily saturated and provides a drastically degraded performance. To remedy this problem, we propose a switch design which uses two independent routes between each input port and each output port within a switch. With proper routing control mechanisms, the adverse effect on link conflicts can be greatly reduced. The design needs neither additional connection between switches nor message resequencing for maintaining serialization. Various simulations are used to illustrate the performance improvement of this new design under both uniform and hot-spot traffic patterns. © 1993 Academic Press, Inc.