Trends in Functional Programming Volume 10

Zoltán Horváth, Viktória Zsók, Zoltán Horváth, Viktória Zsók, Zoltan Horvath, Viktoria Zsok

• Publisher: Intellect Books
• Year: 2014
• Print ISBN: 9781841504056
• eBook ISBN: 9781841504421
• Edition: 1
• Topic: Art
• Subtopic: Art General

Volume 10 in the Trends in Functional Programming (TFP) series presents some of the latest research results in the implementation of functional programming languages and the practice of functional programming. It contains a peer-reviewed selection of the best articles presented at the 2009 Tenth Symposium on Trends in Functional Programming held in Komárno, Slovakia. TFP 2009 was co-located with the Third Central European Functional Programming School (CEFP 2009) and organized by the Department of Programming Languages and Compilers, Faculty of Informatics, Eötvös Loránd University, Budapest and the Selye János University, Komárno.

Chapter 1

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.

FIGURE 1.1. Network Topology for the Sums of Elements in the Pascal’s Triangle

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

with x₁ = 1 and x_i = 2x_i−1 + 1 for all i > 1. Here, x_n 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.

Listing 1.1. Element Sums in the Pascal’s Triangle with Grace

Listing 1.2. Some Data Types and Functions of the Grace Package

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) → Process a b ( # ) :: (Trans a, Trans b) ⇒ Process a b → a → b

The function process embeds functions of type a → 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]] → [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 → e), a process creates a dynamic channel name of type ChanName a in order to receive a value val o...

Table of contents

• Cover
• Title Page
• Copyright
• Preface
• Organization
• Contents
• Chapter 1 Graph-based Communication in Eden
• Chapter 2 Compiling Concurrency Correctly: Cutting Out the Middle Man
• Chapter 3Towards Compiling Sac to Cuda
• Chapter 4 Low Pain vs No Pain Multi-core Haskells
• Chapter 5 An Operational Semantics for Distributed Lazy Evaluation
• Chapter 6 On Graph Rewriting, Reduction and Evaluation
• Chapter 7 A Reflection-based Proof Tactic for Lattices in Coq
• Chapter 8 Generic Programming for Domain Reasoners
• Chapter 9 Haskell Module Tools for Liberating Type Class Design
• Chapter 10 Signals, Not Generators!
• Chapter 11 Braincurry: A Domain- specific Language for Integrative Neuroscience
• Author Index