Towards execution time estimation in abstract machine-based languages

ABSTRACT

Abstract machines provide a certain separation between platform-dependent and platform-independent concerns in compilation. Many of the differences between architectures are encapsulated in the specific abstract machine implementation and the bytecode is left largely architecture independent. Taking advantage of this fact, we present a framework for estimating upper and lower bounds on the execution times of logic programs running on a bytecode-based abstract machine. Our approach includes a one-time, program-independent profiling stage which calculates constants or functions bounding the execution time of each abstract machine instruction. Then, a compile-time cost estimation phase, using the instruction timing information, infers expressions giving platform-dependent upper and lower bounds on actual execution time as functions of input data sizes for each program. Working at the abstract machine level makes it possible to take into account low-level issues in new architectures and platforms by just reexecuting the calibration stage instead of having to tailor the analysis for each architecture and platform. Applications of such predicted execution times include debugging/verification of time properties, certification of time properties in mobile code, granularity control in parallel/distributed computing, and resource-oriented specialization

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: E. Albert, P. Arenas, S. Genaim, and G. Puebla. Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis. In Proc. of Static Analysis Symposium (SAS), LNCS. Springer-Verlag, July 2008. To appear.
• 3: E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. Cost analysis of java bytecode. In R. D. Nicola, editor, 16th European Symposium on Programming, ESOP'07, volume 4421 of Lecture Notes in Computer Science, pages 157--172. Springer, March 2007.
• 4: R. Bagnara, A. Pescetti, A. Zaccagnini, E. Zaffanella, and T. Zolo. Purrs: The Parma University's Recurrence Relation Solver. http://www.cs.unipr.it/purrs.
• 5: I. Bate , G. Bernat , G. Murphy , P. Puschner, Low-level analysis of a portable Java byte code WCET analysis framework, Proceedings of the Seventh International Conference on Real-Time Systems and Applications (RTCSA'00), p.39, December 12-14, 2000
• 6: Java Virtual-Machine Support for Portable Worst-Case Execution-Time Analysis, Proceedings of the Fifth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.83, April 29-May 01, 2002
• 7: Ralph Benzinger, Automated higher-order complexity analysis, Theoretical Computer Science, v.318 n.1-2, p.79-103, June 2004 [doi>10.1016/j.tcs.2003.10.022]
• 8: F. Bueno, P. López-García, and M. Hermenegildo. Multivariant Non-Failure Analysis via Standard Abstract Interpretation. In 7th International Symposium on Functional and Logic Programming (FLOPS 2004), number 2998 in LNCS, pages 100--116, Heidelberg, Germany, April 2004. Springer-Verlag.
• 9: S. Buettcher. Warren's Abstract Machine - A Java Implementation. http://www.stefan.buettcher.org/cs/wam/index.html.
• 10: Stephen-John Craig , Michael Leuschel, Self-tuning resource aware specialisation for prolog, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.23-34, July 11-13, 2005, Lisbon, Portugal [doi>10.1145/1069774.1069777]
• 11: Saumya K. Debray , Nai-Wei Lin, Cost analysis of logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.826-875, Nov. 1993 [doi>10.1145/161468.161472]
• 12: Saumya K. Debray , Nai-Wei Lin , Manuel Hermnegildo, Task granularity analysis in logic programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.174-188, June 1990, White Plains, New York, United States
• 13: Saumya Debray , Pedro López-García , Manuel Hermenegildo , Nai-Wei Lin, Lower bound cost estimation for logic programs, Proceedings of the 1997 international symposium on Logic programming, p.291-305, November 1997, Port Washington, New York, United States
• 14: Stephan Diehl , Peter Sestoft, Abstract machines for programming language implementation, Future Generation Computer Systems, v.16 n.7, p.739-751, May 2000 [doi>10.1016/S0167-739X(99)00088-6]
• 15: A. Ermedahl, J. Gustafsson, and B. Lisper. Experiences from Industrial WCET Analysis Case Studies. In R. Wilhelm, editor, Proc. Fifth International Workshop on Worst-Case Execution Time (WCET) Analysis, Palma de Mallorca, July 2005.
• 16: Gustavo Gómez , Yanhong A. Liu, Automatic time-bound analysis for a higher-order language, Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.75-86, January 14-15, 2002, Portland, Oregon
• 17: Manuel V. Hermenegildo , Germán Puebla , Francisco Bueno , Pedro López-García, Integrated program debugging, verification, and optimization using abstract interpretation (and the Ciao system preprocessor), Science of Computer Programming, v.58 n.1-2, p.115-140, October 2005 [doi>10.1016/j.scico.2005.02.006]
• 18: E. Y.-S. Hu, A. J. Wellings, and G. Bernat. Deriving java virtual machine timing models for portable worst-case execution time analysis. In On The Move to Meaningful Internet Systems 2003: OTM 2003 Workshops, volume 2889 of LNCS, pages 411--424. Springer, October 2003.
• 19: E. Mera, P. López-García, G. Puebla, M. Carro, and M. Hermenegildo. Combining Static Analysis and Profiling for Estimating Execution Times. In Ninth International Symposium on Practical Aspects of Declarative Languages, number 4354 in LNCS, pages 140--154. Springer-Verlag, January 2007.
• 20: J. Navas, M. Méndez-Lojo, and M. Hermenegildo. Customizable Resource Usage Analysis for Java Bytecode. Technical report, University of New Mexico, Department of Computer Science, UNM, January 2008. Submitted for publication.
• 21: J. Navas, E. Mera, P. López-García, and M. Hermenegildo. User-Definable Resource Bounds Analysis for Logic Programs. In 23rd International Conference on Logic Programming (ICLP 2007), volume 4670 of LNCS, pages 348--363. Springer-Verlag, September 2007.
• 22: G. Román-Díez and G. Puebla. Java bytecode timing cost models. Technical Report CLIP12/2007.0, Technical University of Madrid, School of Computer Science, UPM, December 2007.
• 23: D. Warren. An Abstract Prolog Instruction Set. Technical Report 309, Artificial Intelligence Center, SRI International, 333 Ravenswood Ave, Menlo Park CA 94025, 1983.
• 24: R. Wilhelm. Timing analysis and timing predictability. In F. S. de Boer, M. M. Bonsangue, S. Graf, and W. P. de Roever, editors, Formal Methods for Components and Objects, Third International Symposium, FMCO 2004, Leiden, The Netherlands, November 2 - 5, 2004, Revised Lectures, volume 3657 of Lecture Notes in Computer Science, pages 317--323. Springer, 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Languages, Performance

Keywords:
cost analysis, cost models, execution time estimation, logic programming, profiling, resource awareness