Prev Up Next
Go backward to Writing Parallel Programs
Go up to Top
Go forward to Strategies Separate Algorithm from Dynamic Behaviour

Introducing Parallelism

GpH is available free with the Glasgow Haskell compiler and is supported by GUM, a robust, portable runtime system [Trinder et al., 1996]. GUM is message-based, and portability is facilitated by using the PVM communications harness that is available on many multi-processors. As a result, GUM is available for both shared-memory (Sun SPARCserver multi-processors) and distributed-memory (networks of workstations, and CM5) architectures. The high message-latency of distributed machines is ameliorated by sending messages asynchronously, and by sending large packets of related data in each message. GUM delivers wall-clock speedups relative to the best sequential compiler technology for real programs [Trinder et al., 1996]. Most of the example programs below are run on shared-memory architectures. Parallelism is introduced in GpH by the par combinator, which takes two arguments that are to be evaluated in parallel. The expression p `par` e (here we use Haskell's infix operator notation) has the same value as e, and is not strict in its first argument, i.e. bottom `par` e has the value of e. Its dynamic behaviour is to indicate that p could be evaluated by a new parallel thread, with the parent thread continuing evaluation of e. We say that p has been sparked, and a thread may subsequently be created to evaluate it if a processor becomes idle. There is no global priority ordering between sparks on different processors, although the sparks on a single processor are scheduled in first-in first-out (FIFO) order. Since the thread is not necessarily created, p is similar to a lazy future [Mohr et al., 1991]. Note that par differs from parallel composition in process algebras such as CSP [Hoare, 1985] or CCS [Milner, 1989] by being an asymmetric operation - at most one new parallel task will be created.

Since control of sequencing can be important in a parallel language [Roe, 1991], we introduce a sequential composition operator, seq. If e1 is not bottom, the expression e1 `seq` e2 has the value of e2; otherwise it is bottom. The corresponding dynamic behaviour is to evaluate e1 to weak head normal form (WHNF) before returning e2. Since both par and seq are projection functions, they are vulnerable to being altered by optimising transformations, and care is taken in the compiler to protect them. A more detailed description of the implementation of par and seq is given in [Trinder et al., 1996].

  • Simple Divide-and-Conquer Functions
  • Data-Oriented Parallelism
  • Dynamic Behaviour

  • {trinder,hwloidl,simonpj},

    Prev Up Next