Modeling communication pipeline latency

Randolph Y. Wang, Arvind Krishnamurthy, Richard P. Martin, Thomas E. Anderson, David E. Culler

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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 systems that employ dedicated processing elements for protocol processing. We develop an abstract pipeline model that reveals a crucial performance tradeoff involving the effects of the overhead of the bottleneck stage and the bandwidth of the remaining stages. We exploit this tradeoff to develop a suite of fragmentation algorithms designed to minimize message latency. We also provide an experimental methodology that enables the construction of customized pipeline algorithms that can adapt to the specific system characteristics and application workloads. By applying this methodology to the Myrinet-GAM system, we have improved its latency by up to 51%. Our theoretical framework is also applicable to pipelined systems beyond the context of high speed networks.

Original languageEnglish (US)
Pages (from-to)22-32
Number of pages11
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Modeling communication pipeline latency'. Together they form a unique fingerprint.

Cite this