Interconnection Network Congestion Analysis And High-performance Adaptive Routing Technology Research

The performance of the interconnection network determines the overall efficiency of the MPP system to a great degree. Among many factors affecting the performance of the interconnection network, message blocking is a crucial one. In this paper we focus our study on the blocking analysis of the interconnection network, and investigate adaptive routing schemes to reduce the blocking effect. It contributes mainly in the following aspects:1. A performance analysis model for the wormhole routed networks. The model avoids the difficulty met in prior work, and predicts the network performance well.2. Blocking analysis of the network using the blocking ratio, a new performance metric exactly measuring the blocking effect in the network. We also use this metric for network scalability analysis and the scalability analysis of the routing technique.3. Design of a family of low-cost adaptive routing algorithms - the virutual net routing algorithm family including SVAR, NMVAR and MVAR. These algorithms adopting the virtual net and the turn model try to compete the deterministic routing algorithm by the cost while providing much higher performance.4. Design and simulation of a wormhole router for the MVAR algorithm. The router adpots data and control pipelines inside, and supports concurrent routing of multiple messages. Simulations show that it is a competitive scheme.