Paper Info
Title
On measuring the performance of adaptive wormhole routing.
Abstract
Adaptive routing is widely regarded as a promising approachto improving interconnection network performance.Many designers of adaptive routing algorithms have usedsynthetic communication patterns, such as uniform andtranspose traffic, to compare the performance of variousadaptive routing algorithms with each other and withoblivious routing. These comparisons have shown that theaverage message latency is usually lower with adaptiverouting. On the other hand, when a parallel program is executedon a multiprocessor, the goal is to reduce the totalexecution time. In this paper, we explain why improvingthe average message latency of a routing algorithm doesnot necessarily lead to a lower execution time for real applications.We support this observation by reporting simulationresults for both adaptive and oblivious routing usingcommunication derived from real applications. Specifically,we report the performance of various routing algorithmsfor directed acyclic graphs (DAGs) derived fromthe Cholesky factorization of sparse matrices. Our resultsshow that there is little correlation between average messagelatency and the total execution time of a parallel program.Hence, average message latency does not seem tobe a useful measure of the performance of a routing algorithm.This strongly suggests that current comparisons ofrouting algorithms do not provide a reliable indication ofthe performance improvements to be realized by executingprograms on a multiprocessor with such a routing algorithm.We interpret these results and suggest several alternativesfor further research.
Year
DOI
Venue
1997
10.1109/HIPC.1997.634512
HiPC
Keywords
Field
DocType
parallel program,withoblivious routing,routing algorithm doesnot,routing algorithm,adaptive routing algorithm,variousadaptive routing algorithm,adaptive routing,adaptive wormhole routing,real application,oblivious routing usingcommunication,various routing algorithmsfor,cholesky factorization,directed acyclic graphs,routing,multiprocessor,hardware,parallel programming,message switching,simulation,algorithm design and analysis,matrix decomposition,directed acyclic graph,network routing,information science,sparse matrices,directed graphs
Link-state routing protocol,Multipath routing,Dynamic Source Routing,Static routing,Policy-based routing,Computer science,Enhanced Interior Gateway Routing Protocol,Parallel computing,Destination-Sequenced Distance Vector routing,Wireless Routing Protocol,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-8186-8067-9
2
0.41
References 
Authors
11
2
Name
Order
Citations
PageRank
Loren Schwiebert187190.17
D. N. Jayasimha215816.02