Solving Large, Irregular Graph Problems Using Adaptive Work-Stealing Export

@inproceedings{citeulike:6021474, abstract = {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.}, author = {Cong, Guojing and Kodali, S. and Krishnamoorthy, S. and Lea, D. and Saraswat, V. and Wen, Tong}, citeulike-article-id = {6021474}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/ICPP.2008.88}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4625891}, day = {16}, doi = {10.1109/ICPP.2008.88}, journal = {Parallel Processing, 2008. ICPP '08. 37th International Conference on}, keywords = {graph-algorithms, parallelism, work-stealing}, month = {September}, pages = {536--545}, posted-at = {2009-10-28 17:51:57}, priority = {2}, title = {Solving Large, Irregular Graph Problems Using Adaptive Work-Stealing}, url = {http://dx.doi.org/10.1109/ICPP.2008.88}, year = {2008} }

TY - CONF ID - citeulike:6021474 L3 - citeulike-article-id:6021474 N2 - 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. JF - Parallel Processing, 2008. ICPP '08. 37th International Conference on EP - 545 TI - Solving Large, Irregular Graph Problems Using Adaptive Work-Stealing SP - 536 KW - graph-algorithms KW - parallelism KW - work-stealing AU - Cong, Guojing AU - Kodali, S AU - Krishnamoorthy, S AU - Lea, D AU - Saraswat, V AU - Wen, Tong PY - 2008/09/16/ UR - http://dx.doi.org/10.1109/ICPP.2008.88 ER -