Grace

Grace is a library that lets you specify a network of Eden-processes as a graph. You define a list of nodes and a list of directed edges between the nodes. This is passed to the function

build :: forall f a g r p n e. (Placeable f a g r p, Ord e, Eq n) => 
         (n, f) -> [Node n] -> [Edge n e] -> ProcessNetwork r

that creates an abstraction of the process network. Applying the function

start :: (Trans a) => ProcessNetwork a -> a

to this abtraction will instantiate the processes and create the specified communication channels. A deeper introduction can be found in the paper.

To be able to derive instances of the Placeable class automatically for a given function that is to be put on a node, its parameters may not be (pure) type variables. It best be monomorphic. However, it seems to be sufficient to have at least one type constructor in each parameter. This means that, e.g., [a] is ok.

The Grace library is available in our download section.

Example

The core of the master-worker-skeleton implemented with Grace.

mwGrace :: forall t r. (Trans t, Trans r) =>
       Int -> Int        -- #workers, prefetch
       -> ([t] -> [r])   -- worker function
       -> [t] -> [[r]]   -- what to do
mwGrace np prefetch wf tasks =  fst $ (start $ build (0, master) (number workers) edges)
    where
        master :: Lister ([[(Int, r)]] -> ([[r]], [(Int, t)]))
        master = lister (\xs -> (map (map snd) xs, zip (initReqs ++ map fst (merge xs)) tasks)) [np]

        initReqs = concat (replicate prefetch [0..np-1])

        -- worker specifications
        worker :: Int -> [t] -> [(Int, r)]
        worker n ts = zip [n, n..] $ wf ts

        workers :: [Function]
        workers = toFL [worker i | i <- [0..np-1]]

        -- edge definitions
        edges :: [Edge Int Int]
        edges = zipWith4 E [1..np] [0,0..] [1,1..] nothings
                ++ zipWith4 E [0,0..] [1..np] [1,1..] [Just (toWorkerSelect i) | i <- [0..np-1]]

        toWorkerSelect :: Int -> ([r], [(Int, t)]) -> [t]
        toWorkerSelect n (_, xs) = map snd $ filter ((==n) . fst) xs

In this example we have two types of nodes: One master process and several worker processes. A worker node gets as input a stream of tasks and computes a list of results. Each of the results is tagged with the worker's id so that the master knows its origin. The worker functions are grouped in a FunctionList workers. Nodes are then defined by applying the function number to this list, which labels the nodes with numbers starting at 1. Note that this labels the node with id i with the label (i+1).

The master node is special int two ways. First, it is the main node of the process network. This means that its result is the overall result the network computes. As main node, it is not included in the node list but passed to the build-function separately as pair of its label and function.
Second, it is using Grace's Lister-construct. The Lister is a deviation from the Grace principle, that each node has exactly as many incoming edges as its function takes parameters. With the Lister you can receive a parameter of list type element-wise over different channels. Then, each channel contributes exactly one element to the list. A Lister is constructed by applying lister to the function-to-be-placed and a list, that defines for each of the functions's parameters, how many edges/channels are to be used. A 0 in this list means default behaviour. In the example, the master gets one stream from each of the np workers.
The master's result is a pair consisting of the overall result and the tasks tagged with the id of the responsible worker.

For this network, the edges have the type Edge Int Int, meaning that they connect nodes with Int-labels and that the edges' labels are of type Int, too. We have two groups of edges, both of which are defined by zipping four lists with the edge-constructor E. The first group of edges connects each of the workers (1 to np) with the master node (0). Each edge is equally labeled with the value 1. Edge labels are used to define an ordering on a node's incoming edges. Here, we do not care about their order. The pre-defined list nothings effects that no selection is taking place: the worker node's result is completely (and unchanged) transmitted.
The edges from the master to each of the workers, on the other hand, filter the main node's result using the function toWorkerSelect such that only the tasks for the connected worker are transmitted.

Download the source code of this example.