Parallel Graph Reduction

Ulrike Thomas

\overline{1}

Overview

• Sequential Graph Reduction

• Alfalfa: Parallel implementation of Alfl

• GAML: Parallel Implementation of lazy ML

• GUM: A Portable Parallel Implementation of Haskell

• other approaches are: GRIP, < ν,G>-machine, MaRs, ALICE etc.

\overline{2}

Structure of the G-Machine Compiler Supercombinators and Lambda-lifting

A supercombinator S is a lambda expression of the form

λx_{1}, x_{2}, ..., x_{n}. E

• S has no free variables

• any lambda abstraction in E is a supercombinator

• n ≥ 0 there need be no lambdas at all

Transforming lambda abstractions into supercombinators using lambda-lifing for each function where free variables occur:

• 1.Choose any abstraction which has no inner lambda

• 2.Abstract all free variables ( make each free variable into an extra paramter) To obtain full lazyness: Use the maximal free expression

• 3.Replace the occurence of the lambda abstraction by the name applied to the free variable

Example for Lambda-lifting

The original program may look like:

(λx.(λy.y + x)x)4

after lambda-lifting:

comb Y w y= y + w comb X z = combY z z comb X 4

at the end we obtain:

• a set of supercombinators

• an application

An other program in supercombinator form:

comb from n = CONS n (comb from (comb suc n)) comb suc n = n + 1 comb prog = comb from (comb suc 0 )

Graph Reduction and the Spine-stack

\overline{Alfalfa 6}

Alfalfa

• the source language is Alfl, designed at Yale.

• use a heterogenous evaluation model

– Parallel Graph Reduction

– Sequential Stack-based Evaluation

• provide synchronization by using serial combinators

• suspending and resuming tasks (function invocations)

• each processor has

– graph reducer

– message handler

– task queue

– diffusion scheduler

– storage manager

• send nodes to other processors

• no spine stack is needed

Serial Combinators

• each supercombinator is translated into a serial combinator.

• serial combinator’s body is sequential and can be executed on a singel processor

• a serial combinator consist of the original supercombinator extended with function for synchronisation. These are the following four functions:

– (demand (v_{1}...v_{n}))

body-exp)

– (wait(v_{1}...v_{n}))

body-exp)

– (spawn ((v_{1} exp_{1})...(v_{n} exp_{n})) body-exp)

– (let ((v_{1} exp_{1})...(v_{n} exp_{n})) body-exp)

Example for a Serial Combinator

The original program may look following:

   pfac (l, h) = if l==h then 1
                 else
                  let mid = (1+h)/2
                  in pfac(l mid)
                     * pfac( (mid+1) h)

as a serial combinator:

pfac l h ==
  (demand (l h)
     (wait (l h)
       (if (= l h) l
         (let ((mid (/ (+ l h))) (v1 (+ mid 1)))
            (spawn ((v2 (pfac l mid))
                    (v3 (pfac v1 h)))
               (wait (v2 v3)
                 (* v2 v3)))))))

Alfalfa Run-time System

How does it work ?

1. each processor takes a task of his own task queue

2. if it is a:

• evaltask, then evaluation proceeds by a jump to the code pointed by n’s value field

• buildtask, a subgraph is created in the local graph space and execution proceeds as through an evaltask was encountered

• returntask, for returning a value which may be needed by a node of this proceccor and which has been evaluated by an other one

3. evaluation for this node proceeds until a value which occures in a wait is not evaluated yet. Then the active task is suspended and will be awakened when an other processor has finished its evaluation and has sent a returntask

\overline{GAML 11}

Parallel Implementation of lazy ML

• lazy runtime system is implemented on a parallel shared-memory system

• several G-machines reduce the same graph concurrently

• each of these G-machines consist of an 6-tuple <C,S,D,G,R,F> where G,R and F are shared

• the V and S stacks are implemented in one stack

• using strictness annotation to find expression which can be evaluated eagerly

Scheduling

• one processor takes a redex to evaluate and all others are waiting for the initiating machine to put something in the fork pool

• suspending and awaking processes; suspend a process, when it will be awakened it goes into the fork pool where one of the idle processors can pick it up

• scheduler in the fork pool is LIFO

• evaluation of forked expression should not be delayed too much

• divide up the spine with a fixed granularity constant T (8...16)

\overline{GUM 13}

Parallel Implementation of Haskell

• message based; implemented on both sharedmemory and distributed memory

• each processor has a local heap

• runable nodes are never exported to another processor to try to balance the load

• once a processor has sent a message it can forget all about it

• messages are sent asynchronously and contain larger parts of the graph

• a spark pool is used for expressions which might be useful to evaluate in parallel

Scheduling

• one processor creates a manager task whose job is to control startup and termination; this processor begins executing the main redex of the Haskell program

• this manager task spawns other tasks

• each processor executes the following scheduling loop until it receives a finish message Main Scheduler:

1. Perform local garbage collection, if necessary 2. Process any incoming messages from other processors, possibly sending messages in response 3. If there are runnable threads, run one of them 4. Otherwise look for work

Load Distribution

• FIFO; good results for divide and conquer programs

Each processor seeks for work by sending a FISH message to other processors

• if the processor that receives a FISH has a usefull spark, it sends a Schedule message to the processor that originated the FISH, containing the sparked thunk packaged with nearby graph

• if the processor does not have work it sends this message at random to some other processor

References

• S.L. Peyton Jones, The Implementation of Functional Programming Languages, Prentice-Hall, 1987

• Hudak/Goldberg Alfalfa: Distributed Graph Reduction on a Hypercube Multiprocessor, Proceedings of Santa Fe Graph Reduction Workshop, Sept. 1986

• Luce Maranget, GAML: a Parallel Implementation of Lazy ML, Prceedings of Functional Programming Languages and Computer Architecture 1991

• Trinder/Hammond/Mattson/Partridge/Peyton Jones GUM: a portable parallel implementation of Haskell, Proceedings of Programming Language Design and Implementation, Philadelphia, USA, May 1996