GranSim Home Page

This page describes GranSim, a simulator for the parallel execution of Glasgow Parallel Haskell (GPH) programs. Haskell is a non-strict, purely-functional programming language. GPH extends Haskell with annotations for sequential (seq) and parallel (par) composition.

GranSim is based on the Glasgow Haskell Compiler (GHC) and available from the anonymous FTP server (Version 0.29 of GHC). Basically, GranSim is just a special setup of GHC, similar to the parallel setup (GUM). In the GranSim setup the compiler instruments the generated code. This information is used by the runtime-system to perform an event driven simulation. The actual graph reduction code is the same as for sequential compilation with GHC. Therefore, all optimisations in GHC can be used for GranSim, too. For now, GranSim only been tested with the Haskell 1.2 front-end of GHC.

Index:

• How to Get GranSim
• The Main Features of GranSim
• An Example Program
• Parallelism Profiles
• Documentation about GranSim and Publications

How to Get GranSim

GranSim is available by anonymous FTP from Glasgow, in the directory pub/haskell/glasgow:

ftp.dcs.glasgow.ac.uk (130.209.240.50)

The Glasgow site is mirrored by src.doc.ic.ac.uk (146.169.43.1), in computing/programming/languages/haskell/glasgow.

A description of the contents of the Glasgow FTP server can be found in

ftp://ftp.dcs.gla.ac.uk/pub/haskell/glasgow/README.html

GranSim is part of GHC, actually it is a special setup of GHC 0.29. To install it you have to download a GranSim bundle of GHC for the architecture you are using. Then download a GranSim friendly version of hsc and replace the hsc in the bundle with it:

gransim.ANNOUNCE		This file

gransim-guide{.ps,.info.tar,.html.tar}.gz	GranSim User's Guide

ghc-0.29-gransim->platform<.tar.gz  Binary distribution of GranSim.
				This bundle and a GranSim friendly hsc are all
				you need to compile (ghc -gransim) and run
				parallel Haskell programs.

	>platform< ==<	alpha-dec-osf2
			sparc-sun-sunos4
			sparc-sun-solaris2

ghc-0.29-gran-hsc->platform<.gz  The GranSim friendly hsc.
			 Replace the hsc in the GranSim bundle with this one
			 before you start using GranSim.

ghc-0.29-gran-hc-files.tar.gz Basic set of intermediate C (.hc) files for 
			 the compiler proper, and the prelude in GranSim setup.
			 Used for bootstrapping the system.

The Main Features of GranSim

The main features of GranSim are:

• Event driven simulation: GranSim uses events to model parallel execution on a set of processors. For example communication between processors.
• Accuracy: GranSim is based on GHC, an optimising compiler for Haskell. Therefore, it accurately models the execution of sequential code. Furthermore, the implementation is closely related to a real parallel system for Haskell (GUM). Overall, the execution time is measured in machine cycles (based on the assembler code generated by GHC) rather than in abstract graph reduction steps.
• Flexibility: GranSim offers a wide range of parameters to tune the simulation to a specific machine. In the GranSim-Light mode an infinite number of processors can be modelled. In the normal mode the number of processors is limited, but the communication between the processors is measured accurately.
• Efficiency: The bookkeeping overhead for simulating a parallel execution of a program slows down the execution of the program. Comparing the execution time with an optimised sequential execution of the program, the GranSim version is typically 5 to 15 times slower (depending on the length of the time slice used in the simulation).
• Visualisation: A set of visualisation tools allows to show overall activity, per-processor activity and per-thread activity of a simulation. Another set of tools allows to focus on the granularity of the generated threads. These tools a very useful for tuning the performance of a parallel program.
• Integration into GHC: Being a part of an optimising compiler allows to study the interaction of a large set of sequential optimisations (like deforestation) with the parallel execution of the program. Furthermore, GHC's ccall mechanism can be used to call C code in the parallel system, too.
• Large scale parallel programming: GranSim is currently being used in the parallelisation of several large Haskell programs. The largest is the LOLITA natural language processing system, which consists of about 60.000 lines of Haskell and some 1000 lines of C code.

An Example Program

This section discusses a very simple parallel example program to convey the main idea of how to express parallelism in GPH.

We use the well-known nfib function as an example. Here is the sequential version:

nfib :: Int -> Int
nfib 0 = 1
nfib 1 = 1
nfib n = nf1+nf2+1
         where nf1  = nfib (n-1)
               nf2  = nfib (n-2)

The straightforward idea for parallelising nfib is to start parallel processes for computing both recursive calls. This is expressed with the par annotation, which `sparks' a parallel process for computing its first argument and whose result is its second argument. This gives the following parallel program:

parfib :: Int -> Int
parfib 0 = 1
parfib 1 = 1
parfib n = nf2 `par` (nf1 `par` (nf1+nf2+1))
           where nf1 = parfib (n-1)
                 nf2 = parfib (n-2)

The drawback of this program is the blocking of the main task on the two created child-tasks. Only when both child tasks have returned a result, the main task can continue. It is more efficient to have one of the recursive calls computed by the main task and to spark only one parallel process for the other recursive call. In order to guarantee that the main expression is evaluated in the right order (i.e. without blocking the main task on the child task) the seq annotation is used:

parfib :: Int -> Int
parfib 0 = 1
parfib 1 = 1
parfib n = nf2 `par` (nf1 `seq` (nf1+nf2+1))
           where nf1 = parfib (n-1)
                 nf2 = parfib (n-2)

The operational reading of this function is as follows: First spark a parallel process for computing the expression parfib (n-2). Then evaluate the expression parfib (n-1). Finally, evaluate the main expression. If the parallel process has not finished by this time the main task will be blocked on nf2. Otherwise it will just pick up the result.

This simple example already shows several basic aspects of parallel, lazy functional programming:

• For adding parallelism to the program par annotations on local variables (that appear in the main expression) are used.
• To specify evaluation order of the program seq annotations are used. It reduces the first argument (usually a variable occurring in the definition of the second argument) to weak head normal form (WHNF).
• For the efficiency of the parallel program it is important to avoid unnecessary blocking during the execution.

Parallelism Profiles

This section shows some activity profiles generated by GranSim's visualisation tools. See the appropriate section in the GranSim User's Guide for a more detailed discussion of the visualisation tools and for more examples.

The first example is a PostScript picture showing the overall activity during the execution of a simple parallel example program (searching for a list of words in a grid of letters). The overall activity profile separates the threads into five different classes:

• running threads (i.e. threads that are currently performing a reduction) are shown in green,
• runnable threads (i.e. threads that could be executed but that have not found an idle processor) are shown in amber,
• blocked threads (i.e. threads that wait for a result that is being computed by another thread) are shown in red,
• fetching threads (i.e. threads that are currently fetching data from a remote processor) are shown in light blue,
• migrating threads (i.e. threads that are currently being transferred from a busy processor to an idle processor) are shown in dark blue.

The second example shows the per-processor activity profile for the same program. It shows one strip for each of the simulated processors. Each of these strips encodes three pieces of information:

• Is the processor active at a certain point? If it is active the strip appears in some shade of green (gray in the monochrome version). If it is idle it appears in red (white in the monochrome version).
• How high is the load of the processor? The load is measured by the number of runnable threads on this processor. A high load is shown by a dark shade of green (or grey).
• How many blocked threads are on the processor? This information is shown by the thickness of blue (black) bar at to bottom of each strip. This bar may cover up to 80 percent of the strip. Thus, the load information is always visible `in the background'.

The third example shows a per-thread activity profile for a part of the same program. In this profile active (running) periods of a thread are shown as a thick green line. Periods of fetching remote data are shown as a blue line. Periods of suspension, because another thread is running on that processor, are shown as a red line. Finally, periods in which a thread is blocked because it needs data that is being evaluated by another thread are shown as gaps in the profile.

We also have an experimental Java script to generate a dynamic visualisation of the program execution. The idea is to represent the parallel machine as a sequqence of processors and to show for each processor its state (as color) and its load (as the height of the associated bar). Here is a demo.

Documentation about GranSim and Publications

A more detailed description of GranSim with more example programs, a discussion of available options and of visualisation tools and an introduction to parallel non-strict functional programming in the large can be found in the GranSim User's Guide (PostScript, PostScript 2-up, Info).

Finally, here is a list of our publications about parallel, non-strict functional programming. This covers both GranSim and GUM.

This page is currently under construction!