Implementations of Irregular Parallel Algorithms
One of the goals of the SCANDAL project is
to develop fast implementations of parallel algorithms for irregular
problems.
We have or are working on the following machines: the
Thinking Machines Connection
Machines CM2 and
CM5,
the Cray Research
C90, and
T3D,
the IBM
SP1,
the SUN
Ultra
Enterprise 3000, and
the SGI
Power Challenge.
When developing algorithms for irregular problems we often write
prototypes in NESL and then write
machine-specific code to study how algorithm and architecture
interact. Here are some problems we have worked on:
- Sorting and Merging
- Sparse Matrix Operations
- Connected Components
- Scans and Linear Recurrences
- List Ranking
- Graph Separators
- N-body Simulation
- Preconditioned Conjugate Gradient
- Set Operations using Treaps
marcoz@cs.cmu.edu.
Last updated 17 July 1994