This paper studies critical runtime-system issues encountered when packing data for transmission in a lazy, parallel graph reduction system. In particular, we aim to answer two questions:
In order to answer the first question, we compare various packing schemes, of which one extreme packs just the node that is demanded (``incremental fetching''), and the other packs all the graph that is reachable from that node (``bulk fetching''). The second question is addressed by considering 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 configurations. Based on these measurements we propose concrete improvements for parallel graph reducers such as the GUM implementation of Glasgow Parallel Haskell.
@InProceedings{gum-packet,
author = {Hans-Wolfgang Loidl and Kevin Hammond},
title = {Making a Packet: Cost-Effective Communication for a Parallel Graph Reducer},
booktitle = {International Workshop on the Implementation of Functional Languages},
pages = {184--199},
month = sep,
year = {1996},
series = {LNCS 1268},
address = {Bonn/Bad-Godesberg, Germany},
publisher = {Springer-Verlag}
}