Contention and Achieved Performance in Multicomputer Wormhole
Routing Networks
Stephen Tweedie
Graduated Ph.D. December 1999
Abstract
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.
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.
