(A) multiple ring network for large scale multiprocessors

Abstract

Unidirectional point-to-point ring based networks are currently popular choices for high performance multiprocessors. Their simple hardware interfaces can make them run at very high clock rates and provide wider data paths. And their simple interconnections can make it easy to use the raw bandwidth of the links to the fullest extent. In addition, a ring construction allows easy addition and removal of extra nodes. However, the fixed bandwidth of a ring, independent of ring size, limits the size of a ring within small ranges. To accommodate a large number of nodes, rings must be interconnected to a multiple ring network. There are two main approaches to interconnect rings; synthesizing general topologies such as k-ary n-cube and multistage networks, and connecting rings in a hierarchical form. Synthesizing general topologies can be constructed with switches having large fan-out. The switches having large fan-out can reduce the distance between nodes but their complex hardware architecture causes a performance bottleneck. This type of networks has no considerations for the communication locality, often exhibited in many parallel applications, and requires relatively high construction cost. The hierarchical ring networks as a natural extension of a single ring use simple hardware interfaces and thus retain the advantages of unidirectional ring connections. But the hierarchical ring networks have been suffered from the limited scalability because the bandwidth of the network decreases as one moves toward the top of the hierarchy. In this thesis, we propose a new multiple ring interconnection scheme, called the Multistage Ring Network (MRN). The MRN has a 2-level hierarchy of register insertion rings. The interconnection of global rings forms a type of the multistage network. The architecture of the MRN can reduce network complexities and increases communication efficiency by supporting effectively the communication locality of many parallel programs. Moreover, th...