Title
Automatic Static Cost Analysis for Parallel Programs
Abstract
Static analysis of the evaluation cost of programs is an extensively studied problem that has many important applications. However, most automatic methods for static cost analysis are limited to sequential evaluation while programs are increasingly evaluated on modern multicore and multiprocessor hardware. This article introduces the first automatic analysis for deriving bounds on the worst-case evaluation cost of parallel first-order functional programs. The analysis is performed by a novel type system for amortized resource analysis. The main innovation is a technique that separates the reasoning about sizes of data structures and evaluation cost within the same framework. The cost semantics of parallel programs is based on call-by-value evaluation and the standard cost measures work and depth. A soundness proof of the type system establishes the correctness of the derived cost bounds with respect to the cost semantics. The derived bounds are multivariate resource polynomials which depend on the sizes of the arguments of a function. Type inference can be reduced to linear programming and is fully automatic. A prototype implementation of the analysis system has been developed to experimentally evaluate the effectiveness of the approach. The experiments show that the analysis infers bounds for realistic example programs such as quick sort for lists of lists, matrix multiplication, and an implementation of sets with lists. The derived bounds are often asymptotically tight and the constant factors are close to the optimal ones.
Year
DOI
Venue
2015
10.1007/978-3-662-46669-8_6
ESOP
Keywords
Field
DocType
Functional Programming,Static Analysis,Resource Consumption,Amortized Analysis
Data structure,Programming language,Functional programming,Computer science,sort,Amortized analysis,Correctness,Static analysis,Type inference,Theoretical computer science,Soundness
Conference
Volume
ISSN
Citations 
9032
0302-9743
14
PageRank 
References 
Authors
0.61
26
2
Name
Order
Citations
PageRank
Jan Hoffmannand120316.61
Zhong Shao289768.80