Simon Roodhouse was the editor of the Creative Industries Journal. His research focused on the relationship between the arts and industry.

Trends in Functional Programming

Intellect Ltd

Contents

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 to the creation of a new process for evaluating the application of the function funct to the argument arg. The type class Trans provides overloaded communication functions for lists, which are transmitted as streams, element by element, and for tuples, which are evaluated component-wise by concurrent threads in the same process. An Eden process can thus contain a variable number of threads during its lifetime.

Two additional non-functional features of Eden are essential for performance optimizations and the creation of non-hierarchical process networks: non-deterministic stream merging and explicit communication. Eden's non-deterministic function merge :: Trans a [??] [[a]] [right arrow] [a] merges a list of streams into a single stream and thus provides many-to-one communication. Communication channels may be created implicitly during process creation – in this case we call them static channels – or explicitly during process evaluation. In the latter case we call them dynamic channels. The following functions provide the interface to create and use dynamic channels:

new :: Trans a [??] (ChanName a -> a -> b) -> b

parfill :: Trans a [??] ChanName a -> a -> b -> b

Evaluating new (λ name val [right arrow] e), a process creates a dynamic channel name of type ChanName a in order to receive a value val of type a. After creation, the channel should be passed to another process (just like normal data) inside the expression result e, which will also use the eventually received value val. Evaluating (parfill name e1 e2) in the other process has the side effect that a new thread is forked to evaluate concurrently and send the value e1 via the channel. The overall result of the expression is e2.

Listing 1.3 shows a definition of the introductory example in Eden. The main process pascalSums creates process addOne, which in turn creates process multTwo. Process multTwo creates a dynamic channel chan, which it returns to its creator addOne. The latter simply passes this channel to the main process, which uses the channel to pass the result list (1:result) directly to the process multTwo. Thus the channels from multTwo to addOne and from addOne to the main process are implicitly created static channels, while the channel connection from the main process to multTwo is dynamically created.

1.3 BASIC CONSTRUCTS

With Grace the desired network topology is specified through a directed graph structure where nodes represent the processes and edges the communication between them. On every node a function must be placed which will receive each of its arguments through an incoming edge. The function's result will be sent to every successor node. To unambiguously map incoming edges to function parameters the edges must have a weight, i.e. a label with a type for which an ordering is defined.

The graph itself is specified as a list of nodes, a list of edges and a separate root node, whose result is considered to be the result of the whole network. In the following we will refer to this special node as the main node. A node has a label and a function placed on it.

data Node l = forall f a g r p. (placeable f a g r p) [??] N l f

This construct uses multi-parameter classes with functional dependencies [13] and explicit quantification to introduce the type variables a, g, r and p, which are dependent on f. The class Placeable in the type context is used by the implementation. However, the user need not declare a suitable instance – an instance will be derived automatically for every possible function. The only constraint is that the function may not have allquantified type variables. Note that the type variable f that represents the placed function is existentially quantified [6] and does not appear in the type of the node. This allows us to declare a list of nodes as a standard Haskell list [Node l], even if the functions placed on the nodes have different types.

Edges consist of two nodes (from and to), a label and an optional function. The use of the latter will be explained in Section 1.4.

data edge n l = for all a b p.

(Trans a, Trans b, placeable f a g r p) (a -> b) a b b p) [??] E n n l (Maybe (a ? b))

When nodes and edges have been specified they can be passed to the function build, which combines them into an abstraction of a process network.

In the type context, Ord e and Eq n ensure that edges can be ordered by their label and that nodes can be identified by their label. The main node is not of type Node n but a pair of its label and function. This is because the existential quantification would hide f, which is needed to determine the result type r of the network's computation. Placeable f a g r p relates f to r, such that r is a constant and f is a type τ1 [right arrow] ... [right arrow] τk [right arrow] r for k ≥ 0.

The instantiation of the network and the computation of its result is executed by passing the process network to the function start.

start :: (Trans a) [??] ProcessNetwork a -> a

The introductory example given in Listing 1.1 shows the clear distinction between computation logic and topology specification. Due to the usage of strings as node labels the intended interrelations between the processes are even perceptible in the edge declarations.

1.4 ADVANCED CONSTRUCTS

Parameterized Number of Edges

With the basic constructs each node has exactly as many incoming edges as its function takes parameters. This is not very practical for processes that need to communicate with an arbitrary (possibly high) number of other processes. Without Grace one would store the incoming data as elements in a list. An example is the master-worker skeleton [8, 7], where the master has a list of incoming streams that is merged with the Eden-function merge. In Grace we have allowed not only for the receipt of a list as a stream, but also element-wise from different communication partners. This is implemented by introducing a new type Lister f, that can be placed on a node like an ordinary function. It is created using the function lister:

lister :: (IsFunctionType f flag, Placeable' f flag, Placeable f a g r p) ? f ? [Int] ? Lister f

Again, for the user the type context is not really important. Appropriate instances will be derived for any given function. The list parameter specifies the behaviour for each of the function's arguments. If the i-th element of the list is 0 the corresponding parameter of the function will be treated normally. However, if it is k > 0 and the i-th parameter of the function is a list then exactly k channels will be created for this parameter when building the network. A single list element will be received over each of these channels.

In Section 1.6 the lister function is used in a Grace version of the master-worker skeleton.

Selection on Edges

In most of the cases where a node has multiple outgoing edges not all successors are really interested in the whole result that is computed on the node. It is quite common that the result, e.g. a tuple, is supposed to be distributed component-wise. Eden's eager communication forces us to address this problem on the sender's side. We allow for the placing of a function on an edge that is used to transform the node's result before it is communicated over that edge. The edge data type given in Section 1.3 already takes this possibility into account. This will typically be used for selection or filtering, but technically arbitrary transformations are possible.

1.5 BEHIND THE SCENES – GRACE IMPLEMENTATION DETAILS

The implementation faces a few challenges, most of which can be solved using common language extensions like multi-parameter classes, functional dependencies and relaxations in type-checking.

The easiest task is how to specify the graph. A list of nodes (and edges) that carry functions of different types must be made possible. Since the number of functions is not fixed, we cannot use an algebraic data type. The use of the HList-library [5] would be possible, but we do not really need its advanced features. The user has to define the graph, which should therefore be as easy as possible. By declaring the node data type as existential type that hides the type of the placed function, ordinary Haskell lists can be used.

A more complicated problem is how to partition the user-supplied function type into its parts, i.e. parameter types and result type, so that individual channels for these can be created. Here we use techniques developed in the context of generic programming. We define a multi-parameter class with dependent types to make the parts of the function type accessible.

class (Trans argtype, Trans restype) [??] Placeable ftype argtype remtype restype plisttype | ftype -> argtype remtype restype plisttype where ...

The function's type ftype determines all the other types. The type of the function's first argument is argtype; remtype is the remaining part of the function's type without the first argument. The final result type of the function, which you get after applying all parameters, is restype. Finally, plisttype is a type level list of all the parameters. This list uses the type constructors:

data PNilType = PNil

data PConsType a b = PCons a b

For a function of type Int [right arrow] Char [right arrow] Bool we would get the instance:

Placeable

(Int -> Char -> Bool) -- ftype

Int -- argtype

(Char -> Bool) -- remtype

Bool -- restype

(PCons Int (Pcons Char(Pcons Bool PNil))) -- plisttype

The type context (Trans argtype, Trans restype) ensures that both first argument and result can be transported over Eden-channels. For the other parameters we will ensure this via recursive instance declarations.

Let us now take a look at these instance declarations. We do not show the (not so interesting) class methods, but it is important for these (and for the recursive structure of the instance declarations as well) to be able to distinguish between constants and functions that take parameters. To decide this, we follow the technique described by Kiselyov on his website [4], based on the class TypeCast from the HList-library.

We declare a class IsFunctionType a b that relates a given type to one of the types HFuncListParam, HFuncConstParam or HConst, depending on whether the type is a function type that takes a list as first parameter, a one that takes a non-list first parameter, or is a constant, respectively. The distinction between list and non-list parameters is needed to support the Lister-construct.

Originally, we had intended to give only one instance declaration for the class Placeable:

instance (IsFunctionType ftype, flag,
Placeable' flag ftype argtype
remtype restype plisttype) [??]
Placeable ftype argtype remtype
restype plisttype
where ...

Any method in this class would redirect its call to a corresponding method in the class Placeable'. For Placeable', we give instances for any of the three possible flags, as shown in Listing 1.4. You can see that for the constant function the result type is the same as the function type.

In the end the Lister data type got its own, second instance declaration. This ensures that Lister can only be 'wrapped' around a function and not be another part of a function type, e.g. Lister ([Int] -> Int) has an instance, but Int [right arrow] Lister ([Int] -> Int) does not.

While the aforementioned challenges all could be addressed, a serious chicken-and-egg problem is as yet only partly solved. The dynamic channels specified by the edges must be created by the receiving process and be communicated – via other channels – to the sender. We chose a star network to accomplish this: every node sends its channels to the main node that distributes them to where they belong. The problem is the typing: a channel's type is determined by the communicated data's type. A channel of our building network transports an arbitrary number of channels with user-defined types.

Since we do not want to pass this problem on to the user, we do not see any other solution than to cheat by hiding the channel's type for transport using unsafeCoerce and re-establishing the type afterwards with the same operation. However, the reapplied type could be a different one if the process network was erroneous. The channel is created with the type of data that is expected on the receiver's side. The sender later casts it to a type for the data it intends to send. If these do not match the computation may lead to unexpected results and even deadlocks.