Consult the book page
PAD: A Library of basic PRAM Algorithms and Data Structures
Last update of this page: 12.01.01. SOFTWARE NOT AVAILABLE FOR DOWNLOAD -
contact instead the author,
Jesper Larsson Träff.
PAD is a small library of PRAM Algorithms and Data structures.
The motivation of PAD is to study the PRAM as a
practical programming model, and to provide a collection of
efficiently implemented basic PRAM algorithms. In PAD you will find
- Data types for arrays, range query trees, lists, trees, graphs, and
dictionaries
- Various prefix-sums operations for both generic and integer arrays
- Search, merge, sort operations for generic and integer arrays
- List ranking and other operations on lists
- Lowest common ancestors, generic tree contraction
- Connected components
- Dictionary operations
This page gives access to the complete PAD software, including several
smaller example programs. PAD is described in
the book Practical PRAM Programming
- which we suggest you buy! - but can also be used without the book.
A short manual can also be found on this page.
How to get the library
Download a complete gzipped tar-file with all of the below
mentioned material (library, makefile, example programs).
Or download the components separately:
-
The PAD header file,
pad.h
-
The complete code of the PAD library,
pad.c
-
A
Makefile
How to install the library
Example Programs
-
prefix_example.c
-
sort_example.c
-
list_example.c
-
tree_example.c
-
graph_example.c
-
dict_example.c
The PAD manual
Current version, 18.8.00. See also Appendix F of the book.
Revision history
Version 1 of PAD was done between 1995 and 1998 at the
Max-Planck-Institut für Informatik in Saarbrücken, Germany,
as part of the SFB-124 project.
Version 2 of PAD was completed in July-August 2000,
with some revisions January 2001.
Wish list
A parallel generator for random permutations.
Matererial relevant to the projects in Chapter 8 of
Practical PRAM Programming
Publications
Master's theses
Two Master's Theses (German: Diplomarbeiten) describe and evaluate
implementations of PRAM algorithms from the literature in FORK and use
routines from PAD:
-
Peter Dickert:
Berechnung von Einfach- und Zweifachzusammenhangskomponenten auf
einer PRAM.
Max-Planck-Institut für Informatik, 1999.
-
Anastasios Semeloglou:
Kürzeste Wege in planare Graphen.
Max-Planck-Institut für Informatik, 2000.
Older TR's
The technical reports listed below describe version 1 of the
PAD library. They are now obsolete, as is this version.
-
Jesper Larsson Träff.
Explicit implementation of a parallel dictionary.
Technical Report SFB 124-D6 10/95, Universität des Saarlandes,
Sonderforschungsbereich 124, VLSI Entwurfsmethoden und Parallelität,
1995.
53 Pages.
-
Jesper Larsson Träff.
Parallel searching, merging and sorting.
Technical Report SFB 124-D6 1/96, Universität des Saarlandes,
Sonderforschungsbereich 124, VLSI Entwurfsmethoden und Parallelität,
1996.
45 Pages.
-
Jesper Larsson Träff.
Prefix sums and other operations on parallel arrays.
Technical Report SFB 124-D6 6/96, Universität des Saarlandes,
Sonderforschungsbereich 124, VLSI Entwurfsmethoden und Parallelität,
1996.
49 Pages.
-
Jesper Larsson Träff.
Parallel List Ranking and other Operations on Lists.
Technical Report SFB 124-D6 3/97, Universität des Saarlandes,
Sonderforschungsbereich 124, VLSI Entwurfsmethoden und Parallelität,
1997.
69 Pages.
-
Jesper Larsson Träff.
Parallel Tree Operations.
Technical Report SFB 124-D6 4/97, Universität des Saarlandes,
Sonderforschungsbereich 124, VLSI Entwurfsmethoden und Parallelität,
1997.
40 Pages.