Logo: lash (lambda hash)
 
  Main  
 

Eden Main Constructs

Eden gives the programmer explicit high-level control over the parallel behaviour of a program by introducing the concept of processes into the functional language Haskell.

Process Abstraction and Instantiation

Eden provides the high-level constructs:
process :: (Trans a, Trans b) => (a -> b) -> Process a b
to transform a function into a process abstraction and
( # ) :: (Trans a, Trans b) => Process a b -> a -> b
to create a process by instantiating a process abstraction with input. The programmer can concentrate on partitioning the algorithm into parallel sub-tasks, thereby taking into account issues like task granularity, topology, and data distribution. Evaluation of the 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 argument arg is evaluated locally and sent to the new process.

Eden processes produce their output even if it is not demanded. This deviation from lazy evaluation aims at increasing the parallelism degree. In general, a process is implemented by several threads concurrently running in the same processor, so that different values can be produced independently.

In the current implementation process instantiation takes place lazily (unlike the specification in publications past 2005). Eager instantiation of a list of processes supplied with a list of corresponding inputs can easily be achieved using function

spawn :: (Trans a, Trans b) => [Process a b] -> [a] -> [b]
spawn corresponds to zipWith ( # ) but with eager process creation.

Communication

Processes communicate via unidirectional channels which connect one writer to exactly one reader. When trying to access input which is not available yet threads are temporarily suspended. The type class Trans (short for transmissible) comprises all types which can be communicated and provides overloaded, implicitly used functions for sending values. All primitive types like Int, Bool, Char etc., pre- and user-defined algebraic types belong to Trans.

System information

noPe :: Int
selfPe :: Int
The number of virtual process elements (Eden machines) is provided by the constant class="tt">noPe. The constant selfPE defines the own machine ID. Machine IDs range from 1 to noPe.

Process Placement

Processes are instantiated in turn across the available machines (round robin placement). This default behaviour can be set to random placement by a run-time option.
Manual process placement can be achieved using function
spawnAt :: (Trans a, Trans b) => [Int] -> [Process a b] -> [a] -> [b]
spawnAt pos ps is 
to instantiate processes ps!i on machines pos!i (machine IDs range from 1 to noPe, 0 means default placement) with input is!i. Note that the shortest of the three input lists determines the number of processes which will be instantiated, thus the use of infinite lists is possible.

Non determinism

Function merge :: [[a]] -> [a] does a fair merging of inputs into a single (non-deterministic) output stream.

Implementation

The above language constructs are implemented in the Eden module. It is part of the Eden compiler (available at the download section), which is based on GHC.
See also the Haddock documentation of the Eden module.

Example: Hamming process network

The hamming process network calculates the hamming numbers with 5 processes, a root processes evaluating the function hamming and four newly created child processes. picture of the hamming process network
hamming :: [Int]
hamming = 1:
  sm (sMerge # ((multp 2) # hamming,
                     (multp 3) # hamming)) 
           ((multp 5) # hamming)

multp :: Int -> Process [Int] [Int]
multp n= process (map (*n))

sMerge:: Process ([Int], [Int]) [Int]
sMerge = process (uncurry sm)

sm :: [Int] -> [Int] -> [Int]
sm [ ] ys = ys
sm xs [ ] = xs
sm (x:xs)(y:ys)
        | x < y = x : sm xs (y:ys)
        | x == y = x : sm xs ys
        | otherwise = y : sm (x:xs) ys
This is an inefficient toy example to demonstrate the basic Eden features. The message size as well as the amount of work for each process are too small for the network to be efficient. Even more, all communication is passed through the root process (which evaluates hamming and sm), i.e. the results of processes (*2) and (*3) are first sent to the root process and from there to the spawn process. This indirection is not shown in the picture. Such indirections cannot completely be avoided using the main Eden constructs only because these constructs always lead to tree-shaped process networks, i.e. direct communication takes place between parent and child processes only. Advanced language features like remote data must be used to create non-hierarchical process networks. We will show a second version of this network using Remote Data.
 
 
Philipps-Universität Marburg

Eden - Parallel Functional Programming. E-Mail
Fb. 12 - Mathematik und Informatik, Hans-Meerwein-Straße, D-35032 Marburg

This page: http://www.mathematik.uni-marburg.de/~eden

Last change: 14/06/12