Graph-based Communication in Eden

Thomas Horstmeyer and Rita Loogen

Category: Research

Abstract: We present a new approach to the definition and creation of process topologies in the parallel functional Haskell extension Eden. Grace (Graph-based communication in Eden) allows a programmer to specify a network of processes as a graph, where the graph nodes represent processes and the edges represent communication channels. This simplifies the specification and creation of complex communication topologies a lot. The main benefit of the new approach is the clean separation between coordination and computation. Runtime experiments show that Grace has a marginal overhead in comparison with traditional Eden code.

1.1 INTRODUCTION

The parallel functional language Eden [8] enables programmers to define process networks with arbitrary topologies. However, the creation of a non-tree-like topology had up to now to be done on a low level of abstraction, using so-called 'dynamic channels'. These channels are created by receiver processes and must be passed to the corresponding sender processes to establish a direct channel connection between those processes. This is a rather tedious and error-prone task.

In this paper, we present a new approach to the definition and creation of process topologies in Eden. Grace (Graph-based communication in Eden) allows a programmer to specify a network of processes as a graph, where the graph nodes represent processes and the edges represent communication channels. The graph is described as a Haskell data structure ProcessNetwork a, where a is the result type of the network computation. A function start will instantiate the network and automatically set up the corresponding process topology, i.e. the processes are created and the necessary communication channels are installed. The main benefit of the new approach is the clean separation between coordination and computation. The network specification encapsulates the coordinational aspects. The graph nodes are annotated with functions describing the computations of the corresponding processes.

Generally, a user defines the process network by placing functions on nodes and connecting the nodes with edges. For every parameter that a function takes, the corresponding node must have an incoming edge. An ordering on incoming edges maps them unambiguously to the parameters. The result computed on a node will be transmitted over every outgoing edge to other nodes. Since not every successor node might need the whole result, an optional transformation function can be placed on edges that filters the data to be transmitted before the transfer. No filtering is expressed using nothing. A small extension to the base system allows the definition of multiple incoming edges for a parameter of list type, which then will be received element-wise over those edges.

An Introductory Example

Let us take a look at a simple network that computes the sequence (xn/n ≥ 1) with x1 = 1 and xi = 2xi + 1 for all i > 1. Here, xn gives you the sum of the elements in the Pascal's triangle with n levels. We use two separate processes to compute the multiplication and the addition. Figure 1.1 visualizes the network.

Listing 1.1 shows how to describe this network with the help of Grace. It uses the data types and functions of the Grace package shown in Listing 1.2. The network is specified as a graph structure that is passed to the Grace function build. It consists of the node for the main process where the sums function is evaluated, two nodes labelled "mult" and "add" for the separate processes, and edges connecting the nodes. The third and fourth parameter of the edge constructor E are not of interest in this small example. Applying the function start to the network will instantiate its processes, build the communication channels and compute the result.

Plan of Paper. The next section contains a short introduction to Eden. Basic constructs of Grace are explained in Section 1.3. Advanced constructs follow in Section 1.4. Implementation details are discussed in Section 1.5, while an experimental evaluation is presented in Section 1.6. Section 1.7 gives an implementation of the hyperquicksort algorithm that uses all of Grace's features. The paper finishes with a discussion of related work in Section 1.8 and conclusions in Section 1.9.

1.2 EDEN

The parallel Haskell dialect Eden [8] extends Haskell [9] with an explicit notion of processes (function applications evaluated remotely in parallel). The programmer has direct control over evaluation site, process granularity, data distribution and communication topology, but does not have to manage synchronization and data exchange between processes. The latter are performed by the parallel runtime system through implicit communication channels, transparent to the programmer.

The essential two coordination constructs of Eden are process abstraction and instantiation:

process : : (Trans a, Trans b) [??] (a -> b) -> P

# : : (Trans a, Trans b) [??] Process a b) ->

The function process embeds functions of type a [right arrow] b into process abstractions of type Process a b where the context (Trans a, Trans b) states that both a and b must be types belonging to the Trans class of transmissible values. Evaluation of an expression (process funct) # arg leads...