static dependent costs for estimating execution time
We present the first system for estimating and using data-dependent expression execution times in a language with first-class procedures and imperative constructs. The presence of first-class procedures and imperative constructs makes cost estimation a global problem that can benefit from type information. We estimate expression costs with the aid of an algebraic type reconstruction system that assigns every procedure a type that includes a static dependent cost. A static dependent cost describes the execution time of a procedure in terms of its inputs. In particular, a procedure's static dependent cost can depend on the size of input data structures and the cost of input first-class procedures. Our cost system produces symbolic cost expressions that contain free variables describing the size and cost of the procedure's inputs. At run-time, a cost estimate is dynamically computed from the statically determined cost expression and run-time cost and size information. We present experimental results that validate our cost system on three compilers and architectures. We experimentally demonstrate the utility of cost estimates in making dynamic parallelization decisions. In our experience, dynamic parallelization meets or exceeds the parallel performance of any fixed number of processors.
dependencies cost estimates timing systems data express language procedure presence cost estimates global informal reconstruction input size data structures variability dynamic experience experimentation compilation architecture demonstrate utility parallel performance processor class