skip to main content
10.1145/1248377.1248416acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
Article

Deadlock-free scheduling of X10 computations with bounded resources

Published: 09 June 2007 Publication History

Abstract

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.

References

[1]
Eric Allan, David Chase, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, Guy L. Steele Jr., and Sam Tobin-Hochstadt. The Fortress language specification version 0. 618. Technical report, Sun Microsystems, April 2005.
[2]
Robert D. Blumofe. Executing multithreaded programs efficiently . PhD thesis, Cambridge, MA, USA, 1995.
[3]
Robert D. Blumofe and Charles E. Leiserson. Scheduling multithreaded computations by work stealing. J. ACM, 46(5):720--748, 1999.
[4]
Dan Bonachea. GASNet specification. Technical Report CSD-02-1207, University of California, Berkeley, October 2002.
[5]
Luca Cardelli. A language with distributed scope. In Proceedings of the Symposium on Principles of Programming Languages (POPL '95), pages 286--297, January 1995.
[6]
Philippe Charles, Christopher Donawa, Kemal Ebcioglu, Christian Grotho ., Allan Kielstra, Christoph von Praun, Vijay Saraswat, and Vivek Sarkar. X10: An object-oriented approach to non-uniform cluster computing. In OOPSLA 2005 Onward! Track, 2005.
[7]
Cilk-5. 3 reference manual. Technical report, Supercomputing Technologies Group, June 2000.
[8]
William J. Dally and Charles L. Seitz. Deadlock-free message routing in multiprocessor interconnection networks. IEEE Trans. Comput., 36(5):547--553, 1987.
[9]
Frederica Darema, David A. George, V. Alan Norton, and Gregory F. Pfister. A Single-Program-Multiple-Data Computational model for EPEX/FORTRAN. Parallel Computing, 7(1):11--24, 1988.
[10]
Paul Hilfinger, Dan Bonachea, David Gay, Susan Graham, Ben Liblit, Geo . Pike, and Katherine Yelick. Titanium language reference manual. Tech Report UCB/CSD-01-1163, U. C. Berkeley, November 2001.
[11]
Cray Inc. The Chapel language specification version 0.4. Technical report, Cray Inc., February 2005.
[12]
Alan Mainwaring and David Culler. Active message applications programming interface and communication subsystem organization. Tech Report UCB/CSD-96-918, U. C. Berkeley, 1995.
[13]
Lionel M. Ni and Philip K. McKinley. A survey of wormhole routing techniques in direct networks. IEEE Computer, 26:62--76, 1993.
[14]
Robert W. Numrich and John Reid. Co-array Fortran for parallel programming. In ACM Fortran Forum 17, 2, 1--31., 1998.
[15]
Vijay Saraswat and Radha Jagadeesan. Concurrent clustered programming. In Proceedings of the International Conference on Concurrency Theory (CONCUR '05), August 2005.
[16]
UPC language specifications, v1. 2. Technical Report LBNL-59208, Berkeley National Lab, 2005.
[17]
Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, and Klaus Erik Schauser. Active messages: A mechanism for integrated communication and computation. In 19th International Symposium on Computer Architecture, pages 256--266, Gold Coast, Australia, 1992.

Cited By

View all
  • (2023)Distributed Work Stealing in a Task-Based Dataflow RuntimeParallel Processing and Applied Mathematics10.1007/978-3-031-30442-2_17(225-236)Online publication date: 28-Apr-2023
  • (2021)Provably space-efficient parallel functional programmingProceedings of the ACM on Programming Languages10.1145/34342995:POPL(1-33)Online publication date: 4-Jan-2021
  • (2020)An Efficient Work-Stealing Scheduler for Task Dependency Graph2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS51040.2020.00018(64-71)Online publication date: Dec-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures
June 2007
376 pages
ISBN:9781595936677
DOI:10.1145/1248377
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. X10
  2. active messages
  3. deadlock-free scheduling

Qualifiers

  • Article

Conference

SPAA07

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25
37th ACM Symposium on Parallelism in Algorithms and Architectures
July 28 - August 1, 2025
Portland , OR , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Distributed Work Stealing in a Task-Based Dataflow RuntimeParallel Processing and Applied Mathematics10.1007/978-3-031-30442-2_17(225-236)Online publication date: 28-Apr-2023
  • (2021)Provably space-efficient parallel functional programmingProceedings of the ACM on Programming Languages10.1145/34342995:POPL(1-33)Online publication date: 4-Jan-2021
  • (2020)An Efficient Work-Stealing Scheduler for Task Dependency Graph2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS51040.2020.00018(64-71)Online publication date: Dec-2020
  • (2019)FunctionFlowFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6286-813:1(73-85)Online publication date: 1-Feb-2019
  • (2018)Heartbeat scheduling: provable efficiency for nested parallelismACM SIGPLAN Notices10.1145/3296979.319239153:4(769-782)Online publication date: 11-Jun-2018
  • (2018)Heartbeat scheduling: provable efficiency for nested parallelismProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192391(769-782)Online publication date: 11-Jun-2018
  • (2018)Reducing Message Latency and CPU Utilization in the CAF Actor Framework2018 26th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)10.1109/PDP2018.2018.00028(145-153)Online publication date: Mar-2018
  • (2018)Scheduling Parallel Computations by Work StealingInternational Journal of Parallel Programming10.1007/s10766-016-0484-846:2(173-197)Online publication date: 1-Apr-2018
  • (2016)Data-centric execution of speculative parallel programsThe 49th Annual IEEE/ACM International Symposium on Microarchitecture10.5555/3195638.3195644(1-13)Online publication date: 15-Oct-2016
  • (2016)Data-centric execution of speculative parallel programs2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO.2016.7783708(1-13)Online publication date: Oct-2016
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media