Solving large, irregular graph problems using adaptive work-stealing

Guojing Cong, Sreedhar Kodali, Sriram Krishnamoorthy, Doug Lea, Vijay Saraswat, Tong Wen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

80 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - 37th International Conference on Parallel Processing, ICPP 2008
Pages536-545
Number of pages10
DOIs
StatePublished - 2008
Externally publishedYes
Event37th International Conference on Parallel Processing, ICPP 2008 - Portland, OR, United States
Duration: Sep 9 2008Sep 12 2008

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Conference

Conference37th International Conference on Parallel Processing, ICPP 2008
Country/TerritoryUnited States
CityPortland, OR
Period09/9/0809/12/08

Fingerprint

Dive into the research topics of 'Solving large, irregular graph problems using adaptive work-stealing'. Together they form a unique fingerprint.

Cite this