Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Static dependent costs for estimating execution time
Reistad B., Gifford D. ACM SIGPLAN Lisp PointersVII (3):65-78,1994.Type:Article
Date Reviewed: Nov 1 1995

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)
Bookmark and Share
 
Optimization (D.3.4 ... )
 
 
Data Types And Structures (D.3.3 ... )
 
 
Type Structure (F.3.3 ... )
 
 
Language Constructs and Features (D.3.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Optimization": Date
Finite constants
Steffen B., Knoop J. Theoretical Computer Science 80(2): 303-318, 1991. Type: Article
May 1 1992
Optimizing schemes for structured programming language processors
Tsuji T., Ellis Horwood, Upper Saddle River, NJ, 1990. Type: Book (9780138551230)
Apr 1 1992
Optimizing compilers for parallel computers (videotape)
Allen F., University Video Communications, Stanford, CA, 1991. Type: Book
Aug 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy