TY - GEN
T1 - Solving large, irregular graph problems using adaptive work-stealing
AU - Cong, Guojing
AU - Kodali, Sreedhar
AU - Krishnamoorthy, Sriram
AU - Lea, Doug
AU - Saraswat, Vijay
AU - Wen, Tong
PY - 2008
Y1 - 2008
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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=55849100059&partnerID=8YFLogxK
U2 - 10.1109/ICPP.2008.88
DO - 10.1109/ICPP.2008.88
M3 - Conference contribution
AN - SCOPUS:55849100059
SN - 9780769533742
T3 - Proceedings of the International Conference on Parallel Processing
SP - 536
EP - 545
BT - Proceedings - 37th International Conference on Parallel Processing, ICPP 2008
T2 - 37th International Conference on Parallel Processing, ICPP 2008
Y2 - 9 September 2008 through 12 September 2008
ER -