research-article

Task-level analysis for a language with async/finish parallelism

Authors:

Elvira Albert,

Puri Arenas,

Samir Genaim,

Damiano ZanardiniAuthors Info & Claims

LCTES '11: Proceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Pages 21 - 30

https://doi.org/10.1145/1967677.1967681

Published: 11 April 2011 Publication History

Get Access

Abstract

The task level of a program is the maximum number of tasks that can be available (i.e., not finished nor suspended) simultaneously during its execution for any input data. Static knowledge of the task level is of utmost importance for understanding and debugging parallel programs as well as for guiding task schedulers. We present, to the best of our knowledge, the first static analysis which infers safe and precise approximations on the task level for a language with async-finish parallelism. In parallel languages, async and finish are basic constructs for, respectively, spawning tasks and waiting until they terminate. They are the core of modern, parallel, distributed languages like X10. Given a (parallel) program, our analysis returns a task-level upper bound, i.e., a function on the program's input arguments that guarantees that the task level of the program will never exceed its value along any execution. Our analysis provides a series of useful (over)-approximations, going from the total number of tasks spawned in the execution up to an accurate estimation of the task level.

References

[1]

M. Abadi and G. D. Plotkin. A model of cooperative threads. In Proc. of POPL'09, pages 29--40. ACM, 2009.

Digital Library

Google Scholar

[2]

E. Albert, P. Arenas, S. Genaim, and G. Puebla. Closed-Form Upper Bounds in Static Cost Analysis. Journal of Automated Reasoning, 46(2):161--203, 2011.

Digital Library

Google Scholar

[3]

E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. Cost Analysis of Java Bytecode. In Proc. of ESOP'07, volume 4421 of LNCS, pages 157--172. Springer, 2007.

Digital Library

Google Scholar

[4]

E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. COSTA: Design and Implementation of a Cost and Termination Analyzer for Java Bytecode. In Proc. of FMCO'07, volume 5382 of LNCS, pages 113--133. Springer, 2008.

Digital Library

Google Scholar

[5]

E. Albert, S. Genaim, and M. G&#243;mez-Zamalloa. Parametric Inference of Memory Requirements for Garbage Collected Languages. In Proc. of ISMM'10, pages 121--130. ACM Press, 2010.

Digital Library

Google Scholar

[6]

A. W. Appel. Ssa is Functional Programming. SIGPLAN Notices, 33(4):17--20, 1998.

Digital Library

Google Scholar

[7]

V. Braberman, F. Fern&#225;ndez, D. Garbervetsky, and S. Yovine. Parametric Prediction of Heap Memory Requirements. In Proc. of ISMM'08, pages 141--150. ACM Press, 2008.

Digital Library

Google Scholar

[8]

P. Charles, C. Grothoff, V. A. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, C. von Praun, and V. Sarkar. X10: An Object-Oriented Approach to Non-Uniform Cluster computing. In Proc. of OOPSLA'05, pages 519--538. ACM, 2005.

Digital Library

Google Scholar

[9]

W-N. Chin, H.H. Nguyen, C. Popeea, and S. Qin. Analysing Memory Resource Bounds for Low-Level Programs. In Proc. of ISMM'08, pages 151--160. ACM Press, 2008.

Digital Library

Google Scholar

[10]

R. DeLine and K.R.M. Leino. BoogiePL: A typed procedural language for checking object-oriented programs. Technical Report MSR-TR-2005--70, Microsoft Research, 2005.

Google Scholar

[11]

M. F\"ahndrich. Static Verification for Code Contracts. In Proc. of SAS'10, volume 6337 of LNCS, pages 2--5. Springer, 2010.

Digital Library

Google Scholar

[12]

S. Gulwani, K. K. Mehra, and T. M. Chilimbi. Speed: precise and efficient static estimation of program computational complexity. In Proc. of POPL'09, pages 127--139. ACM, 2009.

Digital Library

Google Scholar

[13]

J. Hoffmann and M. Hofmann. Amortized Resource Analysis with Polynomial Potential. In Proc. of ESOP'10, volume 6012 of LNCS, pages 287--306. Springer, 2010.

Digital Library

Google Scholar

[14]

M. Hofmann and S. Jost. Type-Based Amortised Heap-Space Analysis. In Proc. of ESOP'06, volume 3924 of LNCS, pages 22--37. Springer, 2006.

Digital Library

Google Scholar

[15]

N.D. Jones, C.K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, New York, 1993.

Digital Library

Google Scholar

[16]

J. K. Lee and J. Palsberg. Featherweight X10: A Core Calculus for Async-Finish Parallelism. In Proc. of PPoPP'10, pages 25--36. ACM, 2010.

Digital Library

Google Scholar

[17]

Antoine Min&#233;. Field-sensitive value analysis of embedded c programs with union types and pointer arithmetics. In Proc. of LCTES'06, pages 54--63. ACM, 2006.

Digital Library

Google Scholar

[18]

C. Otto, M. Brockschmidt, C. von Essen, and J. Giesl. Automated Termination Analysis of Java Bytecode by Term Rewriting. In Proc. of RTA'10, volume 6 of LIPIcs, pages 259--276, 2010.

Google Scholar

[19]

R. Raman, J. Zhao, V. Sarkar, M. T. Vechev, and E. Yahav. Efficient data race detection for async-finish parallelism. In Proc. of RV'10, volume 6418 of LNCS, pages 368--383. Springer, 2010.

Digital Library

Google Scholar

[20]

V. A. Saraswat and R. Jagadeesan. Concurrent Clustered Programming. In Proc. of CONCUR'05, volume 3653 of LNCS, pages 353--367. Springer, 2005.

Digital Library

Google Scholar

[21]

F. Spoto, F. Mesnard, and &#201;. Payet. A Termination Analyser for Java Bytecode based on Path-Length. Transactions on Programming Languages and Systems, 32(3), 2010.

Digital Library

Google Scholar

[22]

W. Zou T. Wei, J. Mao and Y. Chen. A new algorithm for identifying loops in decompilation. In Proc. of SAS'07, volume 4634 of LNCS, pages 170--183, 2007.

Digital Library

Google Scholar

[23]

L. Unnikrishnan and S. Stoller. Parametric heap usage analysis for functional programs. In Proc. of ISMM'09, pages 139--148. ACM Press, 2009.

Digital Library

Google Scholar

[24]

L. Unnikrishnan, S. D. Stoller, and Y. A. Liu. Optimized Live Heap Bound Analysis. In Proc. of VMCAI'03, volume 2575 of LNCS, pages 70--85. Springer, 2003.

Digital Library

Google Scholar

[25]

R. Vallee-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java Optimization Framework. In Proc. of CASCON'99, pages 125--135. IBM, 1999.

Digital Library

Google Scholar

[26]

M. T. Vechev, E. Yahav, R. Raman, and V. Sarkar. Automatic Verification of Determinism for Structured Parallel Programs. In Proc. of SAS'10, volume 6337 of LNCS, pages 455--471. Springer, 2010.

Digital Library

Google Scholar

[27]

B. Wegbreit. Mechanical Program Analysis. Communications of the ACM, 18(9), 1975.

Digital Library

Google Scholar

Cited By

View all

Baudon TFuhs CGonnord L(2022)Analysing Parallel Complexity of Term RewritingLogic-Based Program Synthesis and Transformation10.1007/978-3-031-16767-6_1(3-23)Online publication date: 11-Sep-2022
https://doi.org/10.1007/978-3-031-16767-6_1
Albert ECorreas JRomán-Díez G(2014)Peak Cost Analysis of Distributed SystemsStatic Analysis10.1007/978-3-319-10936-7_2(18-33)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10936-7_2
Albert EGenaim SMasud A(2013)On the Inference of Resource Usage Upper and Lower BoundsACM Transactions on Computational Logic10.1145/2499937.249994314:3(1-35)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1145/2499937.2499943
Show More Cited By

Index Terms

Task-level analysis for a language with async/finish parallelism

Recommendations

Task-level analysis for a language with async/finish parallelism
LCTES '10

The task level of a program is the maximum number of tasks that can be available (i.e., not finished nor suspended) simultaneously during its execution for any input data. Static knowledge of the task level is of utmost importance for understanding and ...
Work-first and help-first scheduling policies for async-finish task parallelism
IPDPS '09: Proceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing

Multiple programming models are emerging to address an increased need for dynamic task parallelism in applications for multicore processors and shared-address-space parallel computing. Examples include OpenMP 3.0, Java Concurrency Utilities, Microsoft ...
A work-stealing scheduler for X10's task parallelism with suspension
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

The X10 programming language is intended to ease the programming of scalable concurrent and distributed applications. X10 augments a familiar imperative object-oriented programming model with constructs to support light-weight asynchronous tasks as well ...

Reviews

Reviewer: Rafael Corchuelo

Multicore hardware platforms are sprouting up at an increasing pace, which makes it more important than ever before to schedule parallel programs efficiently. Having an a priori estimation of the maximum number of tasks a program can spawn at runtime (also referred to as a task level) would help schedulers to be more effective; unfortunately, having such estimations has not been possible so far. Albert, Arenas, Genaim, and Zanardini have devised a technique to calculate a precise upper bound to the task level, which seems to be the first such result in the literature. Their focus is on an X10-like language that supports async-finish parallelism. (This kind of parallelism is appealing because the results in the literature prove that it may not lead to deadlocking situations.) The technique is based on generating symbolic recurrence equations that accurately represent the resources a program consumes along theoretical parallel executions; the solution to these equations provides a precise upper bound to the task level. Furthermore, the authors argue that if this upper bound exists, then the program is guaranteed to terminate for all input data. The experimental results seem to suggest that this technique is promising. A lot of work must be done, however, with regard to extending it to the full X10 language and considering specific scheduling characteristics. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

LCTES '11: Proceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

April 2011

182 pages

ISBN:9781450305556

DOI:10.1145/1967677

General Chair:
Jan Vitek
Purdue University, USA
,
Program Chair:
Bjorn De Sutter
Ghent University, Belgium

ACM SIGPLAN Notices Volume 46, Issue 5
LCTES '10
May 2011
170 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2016603
Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 April 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '11

Sponsor:

LCTES '11: SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems

April 11 - 14, 2011

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
210
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Baudon TFuhs CGonnord L(2022)Analysing Parallel Complexity of Term RewritingLogic-Based Program Synthesis and Transformation10.1007/978-3-031-16767-6_1(3-23)Online publication date: 11-Sep-2022
https://doi.org/10.1007/978-3-031-16767-6_1
Albert ECorreas JRomán-Díez G(2014)Peak Cost Analysis of Distributed SystemsStatic Analysis10.1007/978-3-319-10936-7_2(18-33)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10936-7_2
Albert EGenaim SMasud A(2013)On the Inference of Resource Usage Upper and Lower BoundsACM Transactions on Computational Logic10.1145/2499937.249994314:3(1-35)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1145/2499937.2499943
Albert ECorreas JPuebla GRomán-Díez GKiselyov OThompson S(2012)Incremental resource usage analysisProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103754(25-34)Online publication date: 23-Jan-2012
https://dl.acm.org/doi/10.1145/2103746.2103754
Albert EAlonso-Blas DArenas PCorreas JFlores-Montoya AGenaim SGómez-Zamalloa MMasud APuebla GRojas JRomán-Díez GZanardini D(2012)Automatic Inference of Bounds on Resource ConsumptionRevised Lectures of the 11th International Symposium on Formal Methods for Components and Objects - Volume 786610.1007/978-3-642-40615-7_4(119-144)Online publication date: 24-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-40615-7_4
Albert EArenas PGenaim SGómez-Zamalloa MPuebla G(2012)Automatic inference of resource consumption boundsProceedings of the 18th international conference on Logic for Programming, Artificial Intelligence, and Reasoning10.1007/978-3-642-28717-6_1(1-11)Online publication date: 11-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28717-6_1
Albert EGenaim SGómez-Zamalloa MJohnsen ESchlatte RTarifa S(2011)Simulating concurrent behaviors with worst-case cost boundsProceedings of the 17th international conference on Formal methods10.5555/2021296.2021333(353-368)Online publication date: 20-Jun-2011
https://dl.acm.org/doi/10.5555/2021296.2021333
Albert EArenas PGenaim SGómez-Zamalloa MPuebla G(2011)Cost analysis of concurrent OO programsProceedings of the 9th Asian conference on Programming Languages and Systems10.1007/978-3-642-25318-8_19(238-254)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25318-8_19
Klemen MLópez-García PGallagher JMorales JHermenegildo M(2020)A General Framework for Static Cost Analysis of Parallel Logic ProgramsLogic-Based Program Synthesis and Transformation10.1007/978-3-030-45260-5_2(19-35)Online publication date: 22-Apr-2020
https://doi.org/10.1007/978-3-030-45260-5_2
Albert EArenas PCorreas JGenaim SGómez-Zamalloa MPuebla GRomán-Díez G(2015)Object-sensitive cost analysis for concurrent objectsSoftware Testing, Verification and Reliability10.1002/stvr.156925:3(218-271)Online publication date: 4-Mar-2015
https://doi.org/10.1002/stvr.1569

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations