Using interconnection-processor combining to reduce hot spots and tree saturation in multistage interconnection networks

Multistage interconnection networks are very promising for shared-memory multiprocessor systems. These networks offer flexibility, scalability, and good performance-cost ratio. However, under a non-uniform traffic pattern, the performance of multistage interconnection networks suffers greatly because of hot spot traffic contention. The potential performance degradation due to even moderate hot spot traffic was found to be very significant, severely reducing all memory access, not just to shared locations. This phenomenon is called a tree saturation effect. Prior studies have outlined several techniques to reduce the effects of hot spot and tree saturation contentions in multistage interconnection networks. These include multibuffer switching nodes, multipath networks, and request combining. Request combining strategy was found to be an effective method of reducing the tree saturation problem. Some request combining approaches have been proposed in the literature. These approaches have one or more of the following limitations: requirements for prior knowledge of messages in the network, restrictions on the routing of the messages in the network, and the use of sophisticated interconnection network nodes. The interconnection-processor combining protocol which does not have the limitations of the other combining methods was an unexplored area of the design space. This study pioneers the interconnection-processor combining protocol with two original approaches. This research defines the operational characteristics, and analyzes these two approaches for performance measures and limitations on Omega networks and Serial Link Interconnection Networks (SLIN). The first approach is the interconnection-processor combining using a common bus to distribute the results (IP-BD). CSMA/CD and Token bus access methods were studied for the distribution bus under the hot spot traffic. In the second method, the interconnection network combines the similar memory request packets and the memory Front-End unit distributes the results of combined memory access (IN-FEC). These proposed approaches suggest higher performance measures while reducing implementation cost. Analytical and simulation models are designed to provide numerical analysis for the proposed combining approaches. The results show considerable throughput enhancement under IN-FEC for Omega and IP-BD (Token) for SLIN