Problem Based Benchmark Suite

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 500 lines of code, but not trivial microbencharks
• Have outputs that can be easily tested for correctness and possibly quality

This is currently work in early progress, and these pages are preliminary. The plan is to supply:

1. The definition of the problems in terms of their function specification (the input they take and the required output given the input).
2. For each problem a weighted set of input distributions on which to test and time implementations.
3. Input generators for each of the input distributions.
4. Output testers for testing the correctness and/or quality of the output
5. A sequential and a parallel base implementation for each problem
6. A set of criteria for measuring the quality of code
7. A repository of submitted implementations.

Currently the benchmarks include the following:

• Comparison sort (SORT)
• Integer sort (ISORT)
• Remove Duplicates (RDUPS)
• Dictionary (RDUPS)
• Suffix Array (SA)
• Breadth First Search Tree (BFS)
• Maximal Independent Set (MIS)
• Maximal Matching (MIS)
• Minimum Spanning Tree (MST)
• Spanning Tree (MST)
• Convex Hull (CH)
• Delaunay Triangulation (DT)
• Delaunay Refinement (DR)
• K-Nearest Neighbors (KNN)
• Ray-Triangle Intersection (RAY)
• Nbody Forces (NBODY)

These are described on the Benchmarks Page.