Paper Info
Title
Task-level analysis for a language with async/finish parallelism
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.
Year
DOI
Venue
2011
10.1145/1967677.1967681
LCTES
Keywords
Field
DocType
static knowledge,input data,task-level analysis,input argument,parallel language,guiding task schedulers,maximum number,parallel program,task level,spawning task,static analysis,java,upper bound
Resource consumption,Asynchronous communication,Programming language,Computer science,Task parallelism,Upper and lower bounds,Parallel computing,Static analysis,Real-time computing,Data parallelism,Java,Debugging
Conference
Volume
Issue
ISSN
46
5
0362-1340
Citations 
PageRank 
References 
10
0.55
19
Authors
4
Name
Order
Citations
PageRank
Elvira Albert1110068.19
Puri Arenas244522.76
Samir Genaim389144.31
Damiano Zanardini432416.83