Home News People Research Study Search

Institute for Computing Systems Architecture

Contention and Achieved Performance in Multicomputer Wormhole Routing Networks

Stephen Tweedie

Graduated Ph.D. December 1999


In modern wormhole-routed multicomputer interconnection networks, contention plays an increasingly significant role in limiting performance at high loads, especially if there is poor communication locality in the workload or if the communication load is non-uniform.

However, the relationship between the level of contention in the communication network and performance degradation in a running workload is complex. At high loads, the communication network may be affecting the rate of injection of new packets into the network just as much as the workload's packet injection rate is affecting performance in the network.

In this thesis we will aim to provide a way of untangling this relationship. We will present a methodology based on discrete event simulation which will allow us to separately identify the cost of contention to a running program, and the amount of contention actually occurring.

We describe a dedicated discrete event simulator used to host performance evaluations of a set of workloads on a 2-D mesh of wormhole routing elements based on the T9000 transputer and its associated C104 routing device. Our simulator is capable of selectively running without contention effects, allowing us to observe not only the amount of contention taking place in the network but also the performance degradation it is causing relative to an ideal, contention-free environment.

We describe a set of metrics which can be used to measure these contention effects. We make a strong distinction between contention internal to the communication network and contention taking place at or before the injection buffers into the network: these are shown to have very different implications for performance.

We also describe a method of classifying synchronisation properties of workloads for which packet injections are not necessarily independent. If there is a feedback loop between network performance and workload performance, then we need to understand if and how the workload may react to changes in the network's performance before we can predict the impact of contention.

Finally we show that the workload classifications and contention metrics we have identified do allow us to distinguish between different levels of workload sensitivity to contention in our networks.

Home : Postgrad : Graduates 

Last modified: Fri Dec 10 10:41:26 GMT 1999

Please contact our webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh.