The PRAM Programming Language Fork

A Programming Environment for Practical Experimentation with the Theory of Parallel Computing

New: PRAM simulator pramsim and system tools now available for Linux!

Contents:

• Introduction
  • The PRAM model and its realizations in hardware; SB-PRAM
  • The Fork language for the PRAM model
  • Example programs in Fork
• Software package: compiler, tools, simulator
  • Download
  • Hardware platforms
  • Known bugs
  • Visualization tool
• Documentation:
  • Book: Practical PRAM Programming
  • Quick Reference Card; Tutorial
  • Other publications on Fork
  • Projects

Page last updated 19 Apr 2010 by Christoph W. Kessler

PRAM model and SB-PRAM hardware emulation

The PRAM (Parallel Random Access Machine) is a strictly synchronous MIMD multiprocessor with a sequentially consistent shared memory that can be accessed in unit time. Hence, it completely abstracts from data locality, memory consistency, and communication cost and focuses on pure parallelism instead. Because of its simplicity, it is a very popular model of parallel computation in the theory of parallel algorithms.
Although criticized for being unrealistic, a PRAM has actually been realized in hardware in the 1990s by the SB-PRAM project of Wolfgang Paul's group at the University of Saarbrücken. Drawing upon hardware design techniques such as massive multithreading with cycle-by-cycle interleaving and a pipelined, combining interconnection network between processors and memory modules, it is a physical realization of a Combining Concurrent Read, Concurrent Write PRAM, the strongest PRAM model known in theory. The largest operational SB-PRAM prototype (finished 2001) has 2048 (virtual) processors (corresponding to 64 processor boards). The architecture is scalable.

Today, superscalar, VLIW and other monolithic processor architectures are hitting the limits of their performance spectrum, and leakage currents, heat dissipation and energy consumption problems put another limit on the maximum clock frequency. As a consequence, multithreaded chip multiprocessors are becoming more and more mainstream architecture. In order to obtain speed-up on such an architecture, applications must be parallelized - not only at the instruction level, but also at loop and task level, which is a notoriously complex and time-consuming task with today's parallel supercomputers. This complexity is largely caused by the need to adapt to the hardware idiosyncracies of clusters, constellations, and CC-NUMA architectures, and to worry about message passing, prefetching, data distribution, cache behavior, or memory consistency. Hence, a simple parallel programming model (and the PRAM is the simplest one) could be a realistic option for a future general-purpose programming model.
This trend is supported by recent developments in computer architecture, such as simultaneous multithreading, thread-level speculation, optical interconnects, and network-on-chip technology. Here are some more recent projects on how to realize PRAMs in hardware:

• ECLIPSE network-on-chip architecture for PRAM emulation, VTT Electronics, Oulo, Finland
• Explicit Multi-Threading (XMT) PRAM-on-Chip, at Univ. of Maryland

The PRAM programming language Fork

Fork is a programming language for the PRAM model; it has been implemented for the SB-PRAM.
Fork is based on ANSI C with extensions for the management of shared and private address subspaces and variables, and for static and dynamic nesting parallelism by processor group splitting constructs. The groups establish the scope of sharing and of synchronous execution. Fork offers full expressibility for many known parallel algorithmic paradigms like data parallelism, semaphore-coordinated asynchronous processes, pipelining and systolic algorithms, parallel task queue, multiprefix, parallel divide-and-conquer, and even message passing.
The language design of Fork has been developed since 1994 by Christoph W. Kessler and Helmut Seidl, starting with an initial version called Fork95 that was partially based on an earlier proposal (FORK) by Hagerup, Schmitt, and Seidl from 1989. Fork95 was extended several times from 1995 to 1999. In 1999, the language design has reached a final state, and from then on, it is just called Fork.

Example programs in Fork

Some selected Fork example programs. Their source codes are part of the Fork compiler package.

• queens.c: A parallel implementation of the N-Queens-Problem, using join for parallel graphical output.
• parprefix.c: Parallel prefix sums computation exploiting Fork's powerful built-in mpadd operator.
• mergesort.c: Parallel mergesort, based on the parallel divide-and-conquer paradigm.
• quickhull.c: The parallel version of the Quickhull algorithm to compute the convex hull of N points in the plane, based on the parallel divide-and-conquer paradigm.
• koch.c: Parallel drawing of Koch fractal curves, based on the parallel divide-and-conquer paradigm.
• nbody.c: Hierarchical N-Body simulation. Parallelization of the standard O(n*n) method as well as the O(n log n) tree-based algorithm of Barnes/Hut'86. Features: Concurrent dynamic insertion of particles in the quad-/octtree, fully parallel computation of mass centers, fully parallel computation of forces, graphical output, arbitrary numbers of particles and of processors. Here is a sample output picture generated by the program with 32 processors for 32 particles in 2D space. Particles are drawn red, mass centers violet, and force vectors white. Some performance measurements are available here.

Current releases of the software packages

Recent releases are available here for download.
You need to download and install
(1) the SBPRAM simulator pramsim and the system software tools, and
(2) the Fork compiler framework.

Terms of usage: The Fork implementation is free, but we appreciate that you cite our book Practical PRAM Programming when publishing results that are based on using it. The distribution comes with complete source code, examples, and documentation. We have extensively used this compiler for several years now, but, as with all complex software, there are some known bugs and probably some unknown bugs left; please report if you have found one. Anyway, we assume no liability for any damage or problems that may occur when using this software. For some components that we borrowed from other software packages (lcc 1.9 and some routines from the GNU C library, see comments in the source code) the corresponding terms of usage apply.

Fork compiler releases

• Download the current version of the compiler package:
  

  Current version (Linux and Solaris, Feb. 2009):
  Fork compiler git repository, click on snapshot to get it in .tar.gz format

• Earlier version (Solaris only, 2000):
  Compiler version 2.0 (beta2) (750 KB gzip'ed tar file)

  First release Aug. 20, 1999, last updated Jan. 20, 2000.
  Many new language features, such as
  - automatic group rank $$, group size #
  - straight function synchronicity,
  - improved type checking and casting
  - deprecated old stuff removed (JOIN macro, async_groupsize)
  - new macros for parallel loops
  - several bugs fixed
  - new string library functions: strcat, itoa
  - fcc documentation updated
  

• List of known bugs

SB-PRAM simulator and system software package

In addition to the Fork Compiler distribution (see above), you need the following SB-PRAM system software tools to be able to compile and execute Fork programs.

• SB-PRAM assembler prass,
• SB-PRAM linker ld,
• SB-PRAM loader loader, and the
• SB-PRAM simulator pramsim.

• Download the SBPRAM system software tools package, the current version (both Linux and Solaris) is sbp_pramutils-v0.10.rc9.git of Oct. 2008,
  (a .tar.gz packaged version can be obtained under shortlog by clicking on snapshot).
  Unpack it and follow the instructions in the README file.
  See also Appendix B of Practical PRAM Programming for further description and installation guide.

  Note: With the snapshot version of 2009-03-12, the files config.h.in and configure are missing in the pramsim directory, and the configure tool is not available on all Linux versions, such as Ubuntu 9.10. Linux kernel version 2.6.31-23-generic. In that case, download the two files separately and make all/install as indicated in the README file.
  An alternative can be to retry installation from a fresh directory and run autoreconf > --install from the pramsim directory. That should generate these files.

• [Older version (Solaris only): v0.9 of 2000]

Hardware platforms and compatibility problems

The Fork compiler fcc and the SB-PRAM system tools run under Solaris (and other Unix-based systems) and Linux (only v10 of the system tools). Simulating large numbers of processors requires sufficient main memory.
Please notify us if you manage to install fcc and/or the system tools on a platform different from these listed above.
For the installation of fcc and the SB-PRAM system tools you need an ANSI C compiler such as the GNU C compiler.

The trv tool for the visualization of execution traces of Fork programs

Graphical trace file visualization of Fork program traces is obtained by adding four tracing routine calls to the program, compiling/linking it with the -T option, running the instrumented version, and submitting the generated trace file to the trv tool (here is the man page of trv in groff and in postscript format).
In the default setup, group split phases are drawn in black, wait phases at barriers are red. Processor working phases are blue/green combinations where processors belonging to the same group have the same color. Delays due to spinning on locks are drawn in yellow. Waiting phases for join entry are shown in black. join working phases are drawn in light green.
Recently, trv has been generalized to allow for fully user-specified graphics output and easy insertion of user-defined trace events. Sample configurations for color and greyscale printers are provided. Fork programs containing MPI calls for message passing result in a processor-time diagram augmented by arrows for messages. This new version of trv is available in the compiler version 2.1.

Examples for trace images:

• a simple divide-and-conquer program
  
• an example program for nested skeletons (Map2 over map2;reduce) applied to nested parallel matrix-vector multiplication
  
• a test of the parallel skip list implementation.
  
• a test of the parallel random search tree implementation
  
• execution traces of a synchronous N-Queens program with parallel output of the results,
  - with 16 processors and N=8.
  - with 4 processors and N=4
  - with 8 processors and N=6.
  
• execution traces of an asynchronous N-Queens program based on a shared task queue, with parallel output of the results,
  - for N=6 and 8 processors
  - for N=8 and 16 processors - (here as postscript)
  
• execution trace of the tree construction phase of a CRCW-Quicksort implementation: for N=16 processors
  
• More execution traces for the CRCW-Quicksort implementation: countDescendants (bottom-up phase) and findOrder (top-down phase), for N=16 processors
  
• Visualization of an execution trace with 4 processors for a message passing example program (MPI broadcast followed by 3 MPI send-recv pairs), a demonstration for user-defined trace events. Tracing for message passing events will be publically available in the next compiler release.
  

Publications

Textbook:

• Practical PRAM Programming by J. Keller, C. Kessler, and J. Träff.
  Textbook on PRAM theory and practice, emulation techniques, SB-PRAM architecture, Fork language description, Fork compilation, parallel algorithmic paradigms and programming techniques, the PAD library of PRAM algorithms and data structures, and the implementation of FView, a larger parallel application in Fork.
  596 pages, Wiley, New York, Dec. 2000.

Quick Reference Cards:

• Fork Quick Reference Card
• SB-PRAM Quick Reference Card
  

Slides:

• Fork tutorial slides: postscript, pdf
  
• Fork research talk slides: postscript, pdf

Fork95 Tutorial:

• Christoph W. Kessler: "Practical PRAM Programming in Fork95 - A Tutorial".
  Forschungsbericht Nr. 97-12, Universität Trier, Mathematik / Informatik, ISSN 0944 0488, 62 pages, May 1997. Updated Sept. 1997.
  Now slightly outdated, replaced by:
• Chapter 5 of Practical PRAM Programming.

Research Papers:

Projects based on Fork

• ForkLight, a programming language for the Asynchronous PRAM model.

• NestStep, a programming language for the BSP model, inspired by Fork and the SBPRAM's combining network.

• PAD - Library of basic parallel algorithms and data structures written in Fork by Jesper L. Träff at MPI Saarbrücken, TU Munich and NEC C&C Research Center St. Augustin, Germany. Comprehensive collection of mainly synchronous parallel routines for PRAM algorithms like multiprefix computations, list ranking, searching, merging, sorting, etc., as e.g.\ occurring in PRAM algorithm textbooks like JaJa's An Introduction to Parallel Algorithms. PAD is described in "Practical PRAM Programming".

• APPEND (Asynchronous Parallel Programming Environment for Non-static Data structures), by Oliver Fritzen at the University of Trier.
  APPEND is a library of basic asynchronous parallel data structures written in Fork95, i.e. an asynchronous complement to PAD. It offers some useful parallel data structures that are not part of the Fork95 compiler's standard library and have no direct equivalent in PAD. Nevertheless, this util package will be distributed with future releases of the Fork95 compiler. APPEND offers a pseudo-object-oriented interface for the Fork95 programmer. Right now, two variants of a parallel hash table are available, as well as a parallel dictionary and a parallel priority queue based on a parallel skip list, and a parallel FIFO queue. Also operational is a parallel quadtree / octree developed for the n-body example program.
  For more information see the documentation. These data structures are also described in "Practical PRAM Programming".
  

• Implementation of the MPI core routines in Fork95, done by Oliver Fritzen at the University of Trier. Included in the util directory of v.2.0 of the compiler and described in "Practical PRAM Programming".

• FVIEW, a parallel implementation of fish-eye views of layouted graphs, implemented in Fork by Jörg Keller at FU Hagen. The application is described in "Practical PRAM Programming".

• Hierarchical Skeleton Model (HSM), a platform-independent programming model based on skeletons with one of its basis languages, Fork95++, being based on Fork95; developed by Marcus Marr at the University of Edinburgh, UK.

• Other projects: If you would like your Fork-based project to be listed here, please send me an email to chrke \at ida.liu.se. Thanks!