Resource-bounded partial evaluation

ABSTRACT

Most partial evaluators do not take the availability of machine-level resources, such as registers or cache, into consideration when making their specialization decisions. The resulting resource contention can lead to severe performance degradation---causing, in extreme cases, the specialized code to run slower than the unspecialized code. In this paper we consider how resource considerations can be incorporated within a partial evaluator. We develop an abstract formulation of the problem, show that optimal resource-bounded partial evaluation is NP-complete, and discuss simple heuristics that can be used to address the problem in practice.

REFERENCES

• 1: L. O. Anderson, "Program Analysis and Specialization for the C Programming Language", DIKU Report No. 94/19, I)ept. of Computer Science, University of Copenhagen, 1994.
• 2: L. O. Andersen and C. K. Gomard, "Speedup Analysis in Partial Evaluation (Preliminary Results)", Proc. A CM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, June 1992, pp. 1-7. (Also available as Technical Report YALEU/DCS/RR-909, Department of Computer Science, Yale University, New Haven, CT.)
• 3: Peter Holst Andersen , Carsten Kehler Holst, Termination Analysis for Offline Partial Evaluation of a Higher Order Functional Language, Proceedings of the Third International Symposium on Static Analysis, p.67-82, September 24-26, 1996
• 4: R. Baler, R. Gliick, and R. ZSchling, "Partial Evaluation of Numerical Programs in Fortran", Proc. A CM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, 1994, pp. 119-132. Report 94/9, Dept. of Computer Science, University of Melbourne.
• 5: L. Birkedal and M. Welinder, "Partial Evaluation of Standard ML", DIKU Report No. 93/22, Dept. of Computer Science, University of Copenhagen, 1993.
• 6: A. Bondorf, Sirnilix 5.0 Manual, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, May 1993.
• 7: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 8: C. Castelluccia, "Automating Header Prediction", Proc. Workshop on Compiler Support for System Software, Tucson, Feb. 1996, pp. 44-53.
• 9: W. Y. Chen , P. P. Chang , T. M. Conte , W. W. Hwu, The Effect of Code Expanding Optimizations on Instruction Cache Design, IEEE Transactions on Computers, v.42 n.9, p.1045-1057, September 1993 [doi>10.1109/12.241594]
• 10: Charles Consel, Binding time analysis for high order untyped functional languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.264-272, June 27-29, 1990, Nice, France [doi>10.1145/91556.91668]
• 11: Olivier Danvy , Nevin Hentze , Karoline Malmkjær, Resource-bounded partial evaluation, ACM Computing Surveys (CSUR), v.28 n.2, p.329-332, June 1996 [doi>10.1145/234528.234741]
• 12: Jack W. Davidson , Anne M. Holler, Subprogram Inlining: A Study of its Effects on Program Execution Time, IEEE Transactions on Software Engineering, v.18 n.2, p.89-102, February 1992 [doi>10.1109/32.121752]
• 13: J. W. Davidson and S. Jinturkar, "An Aggressive Approach to Loop Unrolling", Proc. Compiler Construction '96.
• 14: Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
• 15: Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.93-102, June 18-21, 1995, La Jolla, California, United States
• 16: J. Dongarra and A. R. Hinds, "Unrolling Loops in FORTRAN", Software Practice and Experience vol. 9 no. 3, March 1979, pp. 219-226.
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Arne J. Glenstrup , Neil D. Jones, BTA Algorithms to Ensure Termination of Off-Line Partial Evaluation, Proceedings of the Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics, p.273-284, June 25-28, 1996
• 19: Robert Glück , Jesper Jørgensen, Efficient Multi-level Generating Extensions for Program Specialization, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.259-278, September 20-22, 1995
• 20: C. Gurr, A Self-Applicable Partial Evaluator for the Logic Programming Language GSdel, Ph.D. Thesis, University of Bristol, 1994.
• 21: Carsten Kehler Holst, Finiteness analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.473-495, June 1991, Cambridge, Massachusetts, United States
• 22: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 23: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.246-257, June 19-23, 1989, Portland, Oregon, United States
• 24: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 25: Scott Arthur McFarling, Program analysis and optimization for machines with instruction cache, Stanford University, Stanford, CA, 1992
• 26: D. Mosberger, L. L. Peterson, P. G. Bridges, and S. O'Malley, "Improving the I-Cache Effectiveness of Network Software", Proc. Workshop on Compiler Support for System Software, Tucson, Feb. 1996, pp. 29-36.
• 27: David Mosberger , Larry L. Peterson , Patrick G. Bridges , Sean O'Malley, Analysis of techniques to improve protocol processing latency, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.73-84, August 28-30, 1996, Palo Alto, California, United States
• 28: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 29: D. Sahlin, An Automatic Partial Evaluator for Full Prolog, Ph.D. Thesis, Kungliga Tekniska HSgskolan, Stockholm, Sweden, 1991. Report TRITA-TCS-9101.
• 30: Manuel Serrano , Pierre Weis, Bigloo: A Portable and Optimizing Compiler for Strict Functional Languages, Proceedings of the Second International Symposium on Static Analysis, p.366-381, September 25-27, 1995
• 31: Shlomo Weiss , James E. Smith, A study of scalar compilation techniques for pipelined supercomputers, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.105-109, October 1987, Palo Alto, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory