Overview
The problem based benchmark suite (PBBS) is designed to be an open
source repository to compare different parallel programming
methodologies in terms of performance and code quality. The
benchmarks define problems in terms of the function they implement and
not the particular algorithm or code they use. We encourage people to
implement the benchmarks using any algorithm, with any programming
language, with any form of parallelism (or sequentially), and for any
machine. The problems are selected so they:
- Are representative of a reasonably wide variety of real-world tasks
- The problem can be defined concisely
- Are simple enough that reasonably efficient solutions
can be implemented in around 500 lines of code, but not trivial microbencharks
- Have outputs that can be easily tested for correctness and possibly quality
Each problem supplies:
- The definition of the problems in terms of their function specification (the input they take and the required output given the input).
-
A set of input distributions on which to test and time implementations.
-
Input generators for each of the input distributions.
-
Output testers for testing the correctness and/or quality of the output
-
A sequential and a parallel base implementation for each problem (in some cases the sequential implementation is just the parallel one on a single processor).
-
A repository of implementations.
Currently the benchmarks include the following:
- Comparison sort (SORT)
- Integer sort (ISORT)
- Suffix Array (SA)
- Breadth First Search Tree (BFS)
- Maximal Independent Set (MIS)
- Maximal Matching (MIS)
- Minimum Spanning Forest (MSF)
- Spanning Forest (SF)
- Convex Hull (CH)
- Delaunay Triangulation (DT)
- Delaunay Refinement (DR)
- K-Nearest Neighbors (KNN)
- Nbody Forces (NBODY)
These are described on the
benchmarks Page.
The benchmark codebase were updated in 2020 to use the
library.
This project has been funded by the following sources:
Intel Labs Academic Research Office for the Parallel Algorithms for Non-Numeric Computing Program,
National Science Foundation, and
IBM Research.