Ordered vs. unordered
Authors:
Open Access
- 12 February 2011
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 46 (8) , 3-12
Abstract
Outside of computational science, most problems are formulated in terms of irregular data structures such as graphs, trees and sets. Unfortunately, we understand relatively little about the structure of parallelism and locality in irregular algorithms. In this paper, we study multiple algorithms for four such problems: discrete-event simulation, single-source shortest path, breadth-first search, and minimal spanning trees. We show that the algorithms can be classified into two categories that we call unordered and ordered, and demonstrate experimentally that there is a trade-off between parallelism and work efficiency: unordered algorithms usually have more parallelism than their ordered counterparts for the same problem, but they may also perform more work. Nevertheless, our experimental results show that unordered algorithms typically lead to more scalable implementations, demonstrating that less work-efficient irregular algorithms may be better for parallel execution.Keywords
This publication has 23 references indexed in Scilit:
- Fpga-based prototype of a pram-on-chip processor2008
- Optimistic parallelism requires abstractionsACM SIGPLAN Notices, 2007
- Transactional collection classes2007
- Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphsJournal of Parallel and Distributed Computing, 2006
- Δ-stepping: a parallelizable shortest path algorithmJournal of Algorithms, 2003
- The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelizationIEEE Transactions on Parallel and Distributed Systems, 1999
- Transactional memory1993
- Some efficient solutions to the affine scheduling problem. I. One-dimensional timeInternational Journal of Parallel Programming, 1992
- Virtual timeACM Transactions on Programming Languages and Systems, 1985
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982