Randy Wang, Arvind Krishnamurthy, Richard Martin, Thomas
Anderson, and David Culler. Modeling and Optimizing Communication Pipelines. Proc.
1998 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems,
June 1998, pages 22 - 32.
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.