R. Y. Wang, A. Krishnamurthy, R. P. Martin, T. E. Anderson, D. E. Culler.
Modeling and Optimizing Communication Pipelines. To Appear.
Proc. 1998 ACM SIGMETRICS Conference on Measurement and Modeling
of Computer Systems.
Also appeared as University of California Technical Report CSD-98-981.
In this paper, we study how to minimize the latency of a message
through a network that consists of a number of store-and-forward
stages. This research is especially relevant for today's low overhead
communication subsystems that employ dedicated processing elements for
protocol processing. We develop an abstract pipeline model that
reveals a crucial performance tradeoff. We subsequently exploit this
tradeoff and present a series of fragmentation algorithms designed to
minimize message latency. We provide an experimental methodology that
enables the construction of customized pipeline algorithms that can
adapt to the specific pipeline characteristics and application
workloads. By applying this methodology to the Myrinet-GAM system, we
have improved its latency by up to 51%. We also study the
effectiveness of this technique for other realistic cases.
Paper |
Slides |