Computing Reviews

Static dependent costs for estimating execution time
Reistad B., Gifford D. ACM SIGPLAN Lisp PointersVII(3):65-78,1994.Type:Article
Date Reviewed: 11/01/95

Reistad presents a method for statically estimating program execution time in this excellent and readable paper. It can be added to any statically typed polymorphic programming language, and thereby provides yet another illustration of the benefits of static typing. Cost expressions are added to the type information in the compiler and used to deduce upper bounds on execution time. The weakness is the theoretical impossibility of predicting execution paths statically. For example, the cost for an if is the maximum cost of the two branches. From experimental tests, however, the authors find a useful adjustment factor to apply to the maximum costs to obtain expected costs. They then apply their method with great success to the problem of dynamically predicting the optimal number of processors to use in a multiprocessor system for problems of various sizes. This one useful application must surely provide ample justification for the method. For other purposes, it might be worth considering interactive querying of the programmer to obtain better estimates for the unpredictable elements such as conditionals.

Reviewer:  R. House Review #: CR118658 (9511-0879)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy