Making a Packet:
Cost-Effective Communication for a Parallel Graph Reducer
Hans-Wolfgang Loidl 1 and Kevin Hammond 2

1 Department of Computing Science, University of Glasgow, Scotland, U.K.
E-mail: hwloidl@dcs.glasgow.ac.uk
2 Division of Computer Science, University of St. Andrews, Scotland, U.K.
E-mail: kh@dcs.st-and.ac.uk

Abstract. This paper studies critical runtime-system issues encoun-
tered when packing data for transmission in a lazy, parallel graph re-
duction system. In particular, we aim to answer two questions:
-- How much graph should go into a packet?
-- How aggressively should a processor look for work after requesting
remote data?
In order to answer the first question, we compare various packing schemes,
of which one extreme packs just the node that is demanded (``incremen-
tal fetching''), and the other packs all the graph that is reachable from
that node (``bulk fetching''). The second question is addressed by con-
sidering various mechanisms for latency hiding during communication,
ranging from fully synchronous communication with no attempt to mask
latency, to full thread migration during asynchronous communication.
In order to make our results as general as possible, we have used the
GranSim simulator to study a wide variety of parallel machine configu-
rations. Based on these measurements we propose concrete improvements
for parallel graph reducers such as the GUM implementation of Glasgow
Parallel Haskell.