Personal tools
You are here: Home Publications Deadlock-Free Scheduling of X10 Computations with Bounded Resources
Document Actions

Shivali Agarwal, Rajkishore Barik, Dan Bonachea, Vivek Sarkar, Rudrapatna Shyamasundar, and Katherine Yelick (2007)

Deadlock-Free Scheduling of X10 Computations with Bounded Resources

In: Symposium on Parallel Algorithms and Architecture (SPAA), pp. 229–240, San Diego, California, ACM.

In this paper,we address the problem of guaranteeing the absence of physical deadlock in the execution of a parallel program using the async, finish, atomic, and place constructs from the X10 language. First, we extend previous work-stealing memory bound results for fully strict multi-threaded computations to terminally strict multithreaded computations in which one activity may wait for completion of a descendant activity (as in X10's async and finish constructs), not just an immediate child (as in Cilk 's spawn and sync constructs). This result establishes physical dead-lock freedom for SMP deployments.Second,we introduce a new class of X10 deployments for clusters, which builds on an underlying Active Message network and the new concept of Doppelgänger mode execution of X10 activities. Third, we use this new class of deployments to establish physical deadlock freedom for deployments on clusters of uniprocessors. Together these results give the user the ability to execute a rich set of programs written with async finish atomic and place constructs without worrying about the possibility of physical deadlock due to computation, memory and communication resources. A major open topic for future work is to extend these results to deployments on clusters of SMPs.

by admin last modified 2008-02-15 04:36
« November 2017 »
Su Mo Tu We Th Fr Sa

Powered by Plone

CScADS Collaborators include:

Rice University ANL UCB UTK WISC