Brian Reistad
Abstract
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.
- ADGHSS85 Applegate, J.F., Douglas, M.R., Giirsel, Y., Hunter, P., Seitz, C., and Sussman, G.J. A Digital Orrery. IEEE Computer, September 1985. Google Scholar
Digital Library
- A90 Apt, K.R. Logic Programming. Handbook of TGS, Vol B, Formal Models and Semantics, Jan Van Leeuwen (editor), Elsevier, 1990, 491-574. Google ScholarDigital Library
- B78 Backus, J. Can Programming Be Liberated from the yon Neumann Style? A Functional Style and Its Algebra of Programs. GACM, 21(8), 1978, 613-641. Google ScholarDigital Library
- CBF91 Chatterjee, S., BleUoch, G.E., and Fisher, A.L. Size and Access Inference for Data-Parallel Programs. PLDI 199i, 130-144. Google ScholarDigital Library
- C82 Cohen, J. Computer-Assisted Microanalysis of Programs. CA CM, 25(10), 1982, 724-733. Google ScholarDigital Library
- D92 Dornic, V. Analyse de Complexit4 des Programmes: V4rification et In/drence. Ph.D. Thesis, Ecole des Mines, Paris, France, CRI/A/212, June 1992.Google Scholar
- D93 Dornic, V. Ordering Times. Yale University, Research Report YALEU/DCS/RR-956, April 1993.Google Scholar
- DJG92 Dornic, V., Jouvelot, P., and Gifford, D.K. Polymorphic Time Systems for Estimating Program Complexity. LoPLaS, 1(1), 1992, 33-45. Google ScholarDigital Library
- GJSO92 Gifford, D.K., Jouvelot, P., Sheldon, M.A., and O'Toole, J.W. Report on the FX-91 Programming Language. MIT/LCS/TR-531, February 1992.Google Scholar
- G88 Goldberg, B. Multiprocessor Execution of Functional Programs. International Journal of Parallel Programming, 17(5), 1988, 425-473. Google ScholarDigital Library
- G86 Gray, S.L. Using Futures to Exploit Parallelism in Lisp. M.S. Thesis, MIT, February 1986.Google Scholar
- GSO92 Grundman, D., Stata, R., and O'Toole, J. t~FX/DLX- A Pedagogic Compiler. MIT/LCS/TR- 538, March 1992.Google Scholar
- HG88 Hammel, R.T., and Gifford, D.K. FX-87 Performance Measurements: Dataflow Implementation. MIT/LCS/TR-421, November 1988. Google ScholarDigital Library
- H77 Harrison, W.H. Compiler Analysis of the Value Ranges of Variables. IEEE Transactions on Software Engineering, SE-3(3), 1977, 243-250.Google ScholarDigital Library
- HP90 t{ennessy, J.L., and Patterson, D.A. Computer Architecture - A Quantitative Approach. Morgan Kaufmann Publishers, Inc., San Mateo, California, 1990. Google ScholarDigital Library
- HL92 Huelsbergen, L., and Larus, J. Dynamic Program Parallelization. LFP 1992, 311-323. Google ScholarDigital Library
- HLA94 Huelsbergen, L., Larus, J., and Aiken, A. Using the Run-Time Sizes of Data Structures to Guide Parallel-Thread Creation. LFP 199d. Google ScholarDigital Library
- JG89 Jouvelot, P., and Gifford, D.K. Parallel Functional Programming: The FX Project. Parallel and Distributed Algorithms, M. Cosnard et al. (editors), Elsevier Science Publishers B.V. (North-Holland), 1989, 257-267.Google Scholar
- JG91 Jouvelot, P., and Gifford, D.K. Algebraic Reconstruction of Types and Effects. POPL 1991, 303- 310. Google ScholarDigital Library
- K68 Knuth, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, 1968. Google ScholarDigital Library
- L88 Le M~tayer, D. ACE: An Automatic Complexity Evaluator. ToPLaS, 10(2), 1988, 248-266. Google ScholarDigital Library
- L92 Lim, B. Instructions for Obtaining and Installing ASIM~ MIT/LCS, Alewife Systems Memo #30, September 1992.Google Scholar
- LG88 Lucassen, J.M., and Gifford, D.K. Polymorphic Effect Systems. POPL 1988, 47-57. Google ScholarDigital Library
- M87 Miller, J.S. MultiScheme: A Parallel Processing System Based on MIT Scheme. Ph.D. Thesis, MIT/LCS/TR-402, September 1987.Google Scholar
- MKH90 Mohr, E., Kranz, D.A., and Halstead, R.H. Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs. LFP 1990, 197- 185. Google ScholarDigital Library
- MT92 Morrisett, J.G., and Tolmach, A. A Portable Multiprocessor Interface for Standard ML of New Jersey. Carnegie Mellon University, CMU-CS-92-155, June 1992. Google ScholarDigital Library
- R65 Robinson, J.A. A Machine Oriented Logic Based on the Resolution Principle. JACM, 12(1), 1965, 23-41. Google ScholarDigital Library
- R89 Rosendahl, M. Automatic Complexity Analysis. Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, 1989, 144-156. Google ScholarDigital Library
- S88 Sands, D. Complexity Analysis for Higher Order Languages. Imperial College, London, Research Report DOC 88/14, October 1988.Google Scholar
- S90 Sands, D. Calculi for Time Analysis of Functional Programs. Ph.D. Thesis, University of London, September 1990.Google Scholar
- SH86 Sarkar, V., and Hennessy, J. Compile-Time Partitioning and Scheduling of Parallel Programs. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, 1986, 17-26. Google ScholarDigital Library
- SC93 Skillicorn, D.B., and Cai, W. A Cost Calculus for Parallel Functional Programming. Queen's University, Kingston, Canada, ISSN-0836-0227-93-348, March 1993.Google Scholar
- SML/NJ93 Standard ML of New Jersey Reference Manual (Vers,on 0.93). February 1993.Google Scholar
- T93 Talpin, J.P. Aspects Th4oriques et Pratiques de l'Infdrence de Type et d'Effets. Ph.D. Thesis, Paris University VI, May 1993.Google Scholar
- TJ92 Talpin, J., and Jouvelot, P. Polymorphic Type, Region and Effect Inference. Journal of Functional Programm,ng, 2(3), 1992, 245-271.Google Scholar
- TJ93 Talpin, J., and Jouvelot, P. Compiling FX on the CM-2. Proceedings of the Third Workshop on Static Analysis, LNCS 724, September 1993, 87-98. Google ScholarDigital Library
- T87 Tofte, M. Operational Semantics and Polymorphic Type Inference. Ph.D. Thesis, University of Edinburgh, 1987.Google Scholar
- W91 Wall, D. Predicting Program Behavior Using Real or Estimated Profiles. PLDI 1991, 59-70. Google ScholarDigital Library
- W75 Wegbreit, B. Mechanical Program Analysis. CA CM, is(9), 1975, s2s-sag. Google ScholarDigital Library
Index Terms
- Static dependent costs for estimating execution time
Recommendations
Static dependent costs for estimating execution time
LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programmingWe 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 ...
Dynamic Economic Lot Size Models with Period-Pair-Dependent Backorder and Inventory Costs
Inventory and backorder cost functions in the classical Wagner-Whitin economic lot size ELS models are typically period-pair-independent pp-independent in the sense that inventoried units carried or backorders in existence in a given period are treated ...
Time and quantity dependent waiting costs in a newsvendor problem with backlogged shortages
Upon demand realization in the newsvendor problem, it is often assumed that shortages result in lost sales penalties. However, in some practical situations, shortages are backlogged and the inventory manager is penalized based on the magnitude and ...
Reviews
Ronald Thomas House
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.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments