On Measuring the Performance of Adaptive Wormhole Routing
Abstract
Adaptive routing is widely regarded as a promising approach to
improving interconnection network performance. Many designers of
adaptive routing algorithms have used synthetic communication
patterns, such as uniform and transpose traffic, to compare the
performance of various adaptive routing algorithms with each other and
with oblivious routing. These comparisons have shown that the average
message latency is usually lower with adaptive routing. On the other
hand, when a parallel program is executed on a multiprocessor, the
goal is to reduce the total execution time. In this paper, we
explain why improving the average message latency of a routing
algorithm does not necessarily lead to a lower execution time for real
applications. We support this observation by reporting simulation
results for both adaptive and oblivious routing using communication
derived from real applications. Specifically, we report the
performance of various routing algorithms for directed acyclic graphs
(DAGs) derived from the Cholesky factorization of sparse matrices.
Our results show that there is little correlation between average
message latency and the total execution time of a parallel program.
Hence, average message latency does not seem to be a useful measure of
the performance of a routing algorithm. This strongly suggests that
current comparisons of routing algorithms do not provide a reliable
indication of the performance improvements to be realized by executing
programs on a multiprocessor with such a routing algorithm. We
interpret these results and suggest several alternatives for further
research.
Return to the Publication list.
Last updated by Loren Schwiebert Email: 
on Jun-06-2001