----+-------------------------------------------------------------------------
    #           Ample                                             v2.0 |.$$...
    #           A        M           P        L    E                   |......
--- #           Abstract Machine for Parallel Lazy Evaluation          ---+---
..| @                                                                     #   
d.+##      Ben Lippmeier                 ben.lippmeier@cs.anu.edu.au      # 
?.|        Clem Baker-Finch           clem.baker-finch@cs.anu.edu.au      #
--------------------------------------------------------------------------+---


Overview

Ample is an experimental environment that can be used to study the behavior of parallel programs in terms of an abstract machine, without needing to worry about details particular to a native implementation. Ample is based on Sestoft's Mark-3 machine [1] and the Operational Semantics for Parallel Lazy Evaluation given by Clem Baker-Finch, David J. King and Phil Trinder [2].

Ample accepts programs written in a spartan, no-nonsense functional language which includes support for constructed types, basic IO and integer math. Ample presents three separate machine models - single threaded, fully speculative and semi-implicit. In the semi-implicit model parallelism is introduced with the par and seq combinators in the same way as in programs written for GpH.

The operation of the abstract machine is highly tuneable. Tunability extends to include the maximum number of active threads, the latency of communication between the threads and the methods used for sparking and unblocking.

Ample includes a prelude of common functions and presents an interactive prompt where expressions are reduced and the machine state queried. Profiling information can also be generated interactively, including graphs of thread activity similar to the ones provided by GranSim.

Ample has been written entirely in Haskell and uses Happy for parsing and Gnuplot to generate the graphs.

Screenshots


 An Ample session showing the machine state after evaulation of the treeSize function.
  • treeSize counts the elements in a binary tree.
  • This evaulation was performed in fully speculative mode, with a new thread created for each function application. This leads to many fine grain threads which rapidly become blocked (shown in red)

An Ample session showing the machine state after evaulation of the parTreeSize function.
  • parTreeSize also counts the elements in a binary tree, though it does it using the par and seq combinators to introduce parallelism.
  • Compared to the previous evaulation a smaller number of threads are created and the total time spent blocked is much less.

Download

Software
 Paper
  • An AMPLE Implementation
    Ben Lippmeier and Clem Baker-Finch
    15th International Workshop on the Implementation of Functional Languages (draft proceedings)
    Edinburgh, September 2003, pages 161-176.
    [pdf] [ps.gz]

References

[1]
 Deriving a Lazy Abstract Machine, Peter Sestoft, Journal of Functional Programming vol 7 number 3, May 1997
[2]
 An Operational Semantics for Parallel Lazy Evaulation, Clem Baker-Finch, David King and Phil Trinder, September 2000
[GpH]
 Glasgow Parallel Haskell.
[GranSim]
 GranSim, a simulator for Glasgow Parallel Haskell programs.
[Gnuplot]
 Gnuplot, a useful plotting tool.
[Happy]
 Happy, The Parser Generator for Haskell.
[Haskell]
 Haskell, a purely functional language.

Last update: 5/4/2005