Automatic Parallelization of Divide and Conquer Algorithms

Technische Universität München, Germany
Author: Thomas Erlebach
© 1995 All Rights Reserved

APERITIF (formerly called APRIL) is the name of a new programming language designed for the automatic parallelization of divide and conquer algorithms. A compiler, called april, translates APERITIF programs into C programs which can be run on parallel computers (e.g., networks of workstations) and which contain explicit message passing calls. The aim in the development of APERITIF was to provide an easy-to-use programming model which allows the efficient exploitation of available parallel computing power.

APERITIF is similar to PASCAL but (among other differences) has the additional keywords "parbegin" and "parend" which allow you to tell the compiler that certain recursive procedure calls (typical for divide and conquer algorithms) can be executed in parallel on separate processors.

If you are interested in looking at an implementation of parallel Quicksort using APERITIF, look at the file qsA.pr. This implementation was contributed by Francesco de Sande.

The APERITIF compiler package and documentation is now available via anonymous ftp at ftp://flop.informatik.tu-muenchen.de/pub/april/. There are two files: april.tar.gz (tar'ed and gzip'ed, 122,596 bytes) and april_manual.ps.gz (gzip'ed PostScript: 84,896 bytes). Note that in this distribution the language and the compiler are still called APRIL. Any future releases and announcements will use the new name, APERITIF.

Contents of the archive april.tar.gz:

Contents of april_manual.ps.gz:


The APERITIF programming system (compiler and libraries) was developed and tested on networks of HP 9000/720 workstations running HP-UX and SUN SparcStations running SunOS 4.1. In principle, APERITIF should work on any target system provided that PVM can be installed on it. During the development of APERITIF we used PVM version 3.2.6 and 3.3.7, but any version up from 3.2 should work fine.

PVM is a Parallel Virtual Machine System which enables a collection of heterogeneous computers to be used as a coherent and flexible concurrent computational resource. It can be obtained via anonymous ftp from netlib2.cs.utk.edu. For discussions related to PVM there is a newsgroup called comp.parallel.pvm.

Besides PVM you only need the gcc C compiler to build the april compiler and support libraries.


Please direct any e-mail (questions, bug reports, comments, suggestions, etc.) to: erlebach@informatik.tu-muenchen.de
Thomas Erlebach, 1995-06-16, 1998-07-01