Performance analysis of multiprocessor interconnection networks using a burst-traffic model

This thesis presents the development and use of a performance analysis methodology suitable for use in the evaluation of multiprocessor interconnection networks. The study is grounded in a detailed evaluation of the Cedar multiprocessor. Using characteristics of the behavior exhibited by the benchmarks studied on that system, a burst-traffic model is developed. The performance predictions of the model for adaptive and oblivious virtual-channel routers used in a 2D torus are compared to those of an open-loop random-traffic model, and significant differences are shown to exist.The design of a novel adaptive router, the Shunt router, is proposed. Proofs of its freedom from deadlock and livelock are provided, showing its suitability for use in the construction of a shared-memory multiprocessor. The burst traffic model is used to drive simple versions of the Shunt router and compare its performance to those of the virtual-channel routers discussed previously. The Shunt router is shown to provide a suitable base for explorations of alterations to the routing algorithms and size of buffers within the router, due to its simplicity of structure.The Shunt router is then augmented with a variety of adaptive routing algorithms. The performance of these algorithms, as well as two oblivious routing algorithms, is evaluated. The results show that structure in oblivious routing is important, and several adaptive routing schemes perform equally well. The Shunt router is also used to evaluate the impact of queue sizes on performance, as well as the interaction between queue lengths and adaptivity. Finally, a traffic-throttling network interface is used, with results that show it is primarily useful in cases of limited router buffering.Analytic performance bounds are developed, and used to place the improvements due to adaptive routing into perspective. These bounds are derived from considerations of the systems topology and the structure of the burst-traffic model. Minimum latency, bisection-width, and a complex mean value analysis model are developed, and each is shown to have utility in different areas of performance prediction and comparison. Given the context of the performance bounds, the adaptive routers are shown to achieve a significant percentage of the potential performance improvement.U of I OnlyETDs are only available to UIUC Users without author permissio