Performance analysis of multiprocessor interconnection networks using a burst-traffic model
Turner, Stephen Wilson
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/23307
Description
Title
Performance analysis of multiprocessor interconnection networks using a burst-traffic model
Author(s)
Turner, Stephen Wilson
Issue Date
1995
Doctoral Committee Chair(s)
Veidenbaum, Alexander V.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Computer Science
Language
eng
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
