Design and analysis of buffered Multistage Interconnection Networks

Abstract

Multistage Interconnection Network (MIN) has gained widespread popularity in both multiprocessor and ATM switching applications because of its cost-effectiveness structure. Thus, design and analysis of high performance MIN architecture have become very important. This dissertation addresses the following issues relating to the design and analysis of buffered multistage interconnection networks (MINs): (1) Design of a novel synchronization clock and analysis of its performance in comparison to the existing clock design, (2) Design of a new multi-queue buffer allocation scheme and development of a unified analytical model for analyzing various multi-queue buffer allocation schemes, (3) Performance evaluation of nonuniform traffic load for various buffering strategies, and (4) Performance analysis of adaptive buffer splitting, and priority-based selection strategies in MINs. Traditional MIN design used a big synchronization clock to transfer a package from one stage to the next. This design is difficult to scale because the clock cycle length depends on the network size. We propose a small synchronization clock cycle design that is independent of the network size and thus is easy to implement. Its performance is also shown to be better than the big cycle design. Buffer design and allocations have significant effects on the system performance. We propose a new Dynamically Allocated Fully Connected (DAFC) scheme and show that it performs better than the existing schemes by developing a unified analytical model. Most performance evaluation of interconnection networks focuses on uniform analysis. In reality, applications involve many nonuniform traffic patterns. Nonuniform traffic can further be classified into symmetric and arbitrary patterns. We first develop an analytical model to evaluate various buffer allocation schemes under arbitrary traffic patterns and show that the DAFC scheme we have proposed has the best performance over the existing buffer schemes under both uniform and nonuniform load. We also develop an analytical model to evaluate a typical symmetric nonuniform pattern--favorite load which has applications in both multiprocessor systems and ATM switches. By using this analytical model, we investigate performance features under different priority-based selection policies and buffer splitting strategies.