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:
[Sort] Sorting and Merging
[Sparse] Sparse Matrix Operations
[CC] Connected Components
[Scan] Scans and Linear Recurrences
[Listrank] List Ranking
[Separator] Graph Separators
[Nbody] N-body Simulation
[SCTG] Preconditioned Conjugate Gradient
[Treaps] Set Operations using Treaps
marcoz@cs.cmu.edu. Last updated 17 July 1994