The acronym APSET stands for A Parallel Software Engineering Tool, and is a one year project funded by The Open University and carried out by:

David King Jon Hall	Research Fellow Lecturer	}	The Open University
Phil Trinder	Lecturer		Heriot-Watt University

Background

seq x y	=	_|_				if x = _|_
	=	y				otherwise
par x y	=	y

Adding par and seq to programs can mix up the algorithmic structure with the description of how it should be evaluated in parallel. Because of this higher-order functions were introduced that allow the original algorithm to remain unchanged, but with a suffix called a strategy that describes its parallel behaviour. For example, mapping the function f over the list [x0, x1, ...,xn] may be parallelised by using:

map f [x0, x1, ...,xn] `using` strategy

The compiler for GpH that we are working with is an extension of GHC, i.e. the Glasgow Haskell compiler with two extra components in the runtime system, namely:

• GUM - which allows parallel Haskell to be executed on several parallel architectures;
• GranSim - which can simulate the behaviour of running parallel Haskell on a variety of architectures whilst only running on a single processor.

Objective

map f [x0, x1, ...,xn] `using` markStrat "map strategy" strategy

As well as adding markStrat to GpH, we are also interested in better way of visually displaying profiles.

Motivating examples for a strategic profiler

• Evaluation scoping instead of lexical scoping

  In the expression

  map f xs `using` markStrat "A" strat

  the cost of evaluating map f xs would be attributed to an enclosing label with lexical scoping, and to the label "A" with evaluation scoping. With sequential Haskell a hybrid of lexical scoping was found to be the most suitable approach (see [1]), but for our purposes evaluation scoping is essential, as the above example demonstrates.

• Thread call graphs

  In the profiles below of a simple program, function h is called from both f and g. But it is only by looking at the strategic profile, that the two calls to h can be distinguished. Cost centre stack profiling could be used to distinguish the two calls to h. But distinguish them in the strategic profiles by labeling threads with their parent's thread id.

  GranSim profile	GranCC profile	Strategic profile	Per thread strategic profile

• Only mark strategies and not computation

  When optimising the strategies used for parallelism, we are not especially interested in the cost of every individual function. The profile on the left distinguishes the cost of three functions, although the program it was generated from only had one strategy. So we are more interested in marking the strategies rather than computation.

Some example strategic profiles

• Colin Runciman's soda example (26/7/98)

  The soda program of Runciman does a word search in parallel, and below are three different visualisations of it. Several different parallel versions of the soda program are discussed in the book Applications of Functional Programming by Colin Runciman and David Wakeling (1995). The version that is profiled here is a strategic version based on the final version give in the afore mentioned book.

  GranSim profile	Strategic profile	Per thread strategic profile

• Hans-Wolfgang Loidl's parallel tic-tac-toe (28/7/98)

  

  This is parallel version of tic-tac-toe by Hans-Wolfgang Loidl. It's based on a sequential version of tic-tac-toe by John Hughes which is discussed in the paper Why Functional Programming Matters, (1989).

Papers

• An operational semantics for parallel call-by-need.
  Clem Baker-Finch, David J. King, Jon G. Hall, and Phil Trinder.
  Technical Report, Faculty of Maths and Computing, The Open University, Milton Keynes, March, 1998.

  Version dated (30/03/99): ps (400K), ps.gz (143K).

• An operational semantics for parallel call-by-need.
  Clem Baker-Finch, David J. King, Jon G. Hall, and Phil Trinder.
  Submitted for publication.

  Version dated (10/03/99): ps (249K), ps.gz (94K).

• A strategic profiler for Glasgow Parallel Haskell.
  David J. King, Jon G. Hall, and Phil Trinder,
  Presented at IFL'98, London, 9-11th September, 1998.

  Version dated (29/01/99): ps (1313K), ps.gz (205K).

• Towards an operational semantics for a parallel non-strict functional language.
  Jon G. Hall, Clem Baker-Finch, Phil Trinder, and David J. King,
  Presented at IFL'98, London, 9-11th September, 1998.

  Version dated (29/01/99): ps (399K), ps.gz (88K).

Talks

• An operational semantics for parallel call-by-need.
  Talk given to SCOFPIG group at Edinburgh University on 17th December, 1998. (ps, ps.gz).

• SCOFPIG challenge applications.
  Talk given to SCOFPIG group at Edinburgh University on 17th December, 1998. (ps, ps.gz).
  • Ray tracer for spheres (lhs)
  • Digital circuit simulator (lhs)

Code

• An interpreter written in literate Haskell that reduces GPH-core terms (i.e. lambda-calculus with par and seq) with respect to the operational semantics given in the above paper.

  Version dated (03/12/98): sem.lhs (16K).

Related work

[1] Cost centre profiling

Patrick Sansom provided an execution profiler for the sequential Glasgow Haskell compiler. This provided a primitive scc that allowed costs to be attributed to labels.

[2] Cost centre stack profiling

Stephen Jarvis's work extended Sansom's to record not just the immediate enclosing cost centre but all enclosing cost centres.

[3] Parallel cost centre profiling

Kevin Hammond, Hans-Wolfgang Loidl, and Phil Trinder's work combines cost centre profiling with GpH.

[4] GranSim & GUM

Kevin Hammond, Hans-Wolfgang Loidl, Simon Peyton Jones, and Phil Trinder have written several papers about the GranSim and GUM projects.

[5] An interactive approach to profiling parallel functional programs

Nathan Charles and Colin Runciman are working on a graphical user interface that allows a log-file in a database format to be queried and graphically displayed interactively.

[6] A grammar for self-describing documents

Stephen Jarvis, Simon Marlow, Simon Peyton Jones, and Eric Wilcox have been working on a log file format which is self defining.