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

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-98-981

, 1998

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-981.pdf

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.

---

BibTeX citation:

@techreport{Wang:CSD-98-981,
    Author= {Wang, Randolph Y. and Krishnamurthy, Arvind and Martin, Richard P. and Anderson, Thomas E. and Culler, David E.},
    Title= {Towards a Theory of Optimal Communication Pipelines},
    Year= {1998},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/5435.html},
    Number= {UCB/CSD-98-981},
    Abstract= {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.},
}

EndNote citation:

%0 Report
%A Wang, Randolph Y. 
%A Krishnamurthy, Arvind 
%A Martin, Richard P. 
%A Anderson, Thomas E. 
%A Culler, David E. 
%T Towards a Theory of Optimal Communication Pipelines
%I EECS Department, University of California, Berkeley
%D 1998
%@ UCB/CSD-98-981
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/5435.html
%F Wang:CSD-98-981