Solving Large, Irregular Graph Problems Using Adaptive Work-Stealing
Guojing Cong, Sreedhar B. Kodali, Sriram Krishnamoorthy et al. · Proceedings of the International Conference on Parallel Processing · 2008
Solving large, irregular graph problems efficiently is challenging. Current software systems and commodity multiprocessors do not support fine-grained, irregular parallelism well. We present XWS, the X10 Work Stealing framework, an open-source runtime for the parallel programming language X10 and a library to be used directly by application writers. XWS extends the Cilk work-stealing framework with several features necessary to efficiently implement graph algorithms, viz., support for improperly nested procedures, global termination detection, and phased computation. We also present a strategy to adaptively control the granularity of parallel tasks in the work-stealing scheme, depending on the instantaneous size of the work queue. We compare the performance of the XWS implementations of spanning tree algorithms with that of the hand-written C and Cilk implementations using various graph inputs. We show that XWS programs (written in Java) scale and exhibit comparable or better performance.
Cited by 104 works. doi:10.1109/icpp.2008.88
Authors
References
- Cilk
- The implementation of the Cilk-5 multithreaded language
- R-MAT: A Recursive Model for Graph Mining
- Cilk: An Efficient Multithreaded Runtime System
- A comparison of parallel algorithms for connected components
- An efficient parallel algorithm for planarity
- A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
- Non-blocking steal-half work queues
- A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)(extended abstract )
- Parallel implementation of algorithms for finding connected components in graphs