Multistage Ring Network: A New Multiple Ring Network for Large Scale Multiprocessors

We present a new multiple ring network for multiprocessors, called the Multistage Ring Net-work(MRN). The MRN has a 2-level hierarchy of register insertion rings, and its interconnection of global rings forms a type of the multistage net-work. The architecture of the MRN is effective at diffusing the global traffic to all global rings and the bandwidth of the network increases propor-tionally with increases in the system size. At the same time, the MRN retains the economic design and high speed communication advantages of the ring network. We develop a deadlock-free routing algorithm for the MRN. We also present a per-formance analysis of the MRN and compare the results with those of a hierarchical ring network. 1