GRAPH for PVM: Graph Reduction for Distributed Hardware

Hans Wolfgang-Loidl and Kevin Hammond
International Workshop on the Implementation of Functional Languages, Norwich, England, September 1994.

We describe a version of the GRAPH system (Graph Reduction for an Assortment of Parallel Hardware) designed to execute parallel functional programs on a range of distributed-memory MIMD machines running the PVM communications harness. GRAPH was developed from the runtime system for the novel GRIP multiprocessor. Although this system has proved highly successful, being a novel architecture it is hard to compare results with other architectures or implementations. The CPUs used in the GRIP design are also rather old.

The principal extensions from GRAPH for GRIP to GRAPH for PVM are intended to handle high latencies more efficiently, by exploiting asynchronous communication, multi-threaded scheduling, and by grouping packets into larger entities where possible. The main innovation is the development of new, sophisticated packet flushing and packet fetching algorithms whose purpose is to allow graphs to be exported to and fetched from global memory without inter-processor synchronisation. As communication and reduction can be interleaved, a new form of synchronising communication and reduction is necessary.

We also give a short outlook on the design of a new portable distributed graph reduction system, GRAPH for UMM, that adepts the ideas and techniques originally developed for the GRIP system to a distributed memory environment.

GRAPH for PVM has been implemented on a network of SUN workstations and it is currently being tested and debugged. Although no extensive performance measurements have been performed yet, the available data shows a significant decrease in the overall communication and thus an improvement in the overall performance of the system.

  author = 	 {Hans-Wolfgang Loidl and Kevin Hammond},
  title = 	 {GRAPH for PVM: Graph Reduction for Distributed Hardware},
  booktitle = 	 {International Workshop on the Implementation of Functional Languages},
  year = 	 {1994},
  address =      {Norwich, England},
  month = 	 sep

Available in: ps, ps.gz

GPH Papers | GPH