The B-network: a multistage interconnection network with backward links

Abstract

A multistage interconnection network (MIN) for multiprocessor systems is proposed. The proposed MIN, called the B-network, uses backward links to provide backward paths for the requests blocked at switches or memory due to contentions. The gamma network is known to contain a cube network (specifically, the inverse omega network) as a substructure. The B-network is obtained from the gamma network by preserving the cube structure but reversing the direction of all other links. These backward links are used as alternate paths for requests blocked due to path or memory contentions. The B-network can be controlled by the simple destination tag control algorithm; packets navigating through the B-network, using both regular forward links and backward links, can reach their destinations under the destination tag control. The performance of the B-network is analyzed under the uniform traffic model and compared to various networks of interest. It is shown that the B-network surpasses the performance of the gamma network, the crossbar switch, and single-buffered MINs based on (2*2) switches, while having the same hardware complexity as the gamma network.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>