More Web Proxy on the site http://driver.im/

research-article

JIT-Based Cost Analysis for Dynamic Program Transformations

Authors:

John Magnus Morton,

Phil TrinderAuthors Info & Claims

Electronic Notes in Theoretical Computer Science (ENTCS), Volume 330, Issue C

Pages 5 - 25

https://doi.org/10.1016/j.entcs.2016.12.012

Published: 10 December 2016 Publication History

Abstract

Tracing JIT compilation generates units of compilation that are easy to analyse and are known to execute frequently. The AJITPar project investigates whether the information in JIT traces can be used to dynamically transform programs for a specific parallel architecture. Hence a lightweight cost model is required for JIT traces.This paper presents the design and implementation of a system for extracting JIT trace information from the Pycket JIT compiler. We define three increasingly parametric cost models for Pycket traces. We determine the best weights for the cost model parameters using linear regression. We evaluate the effectiveness of the cost models for predicting the relative costs of transformed programs.

References

[1]

Jaume Abella, Damien Hardy, Isabelle Puaut, Eduardo Quinones, Francisco J. Cazorla, On the comparison of deterministic and probabilistic WCET estimation techniques, in: 2014 26th Euromicro Conference on Real-Time Systems (ECRTS), IEEE, 2014, pp. 266-275.

[2]

AJITPar project. http://www.dcs.gla.ac.uk/~pmaier/AJITPar/

[3]

Elvira Albert, Puri Arenas, Jesús Correas, Samir Genaim, Miguel Gómez-Zamalloa, Enrique Martin-Martin, Germán Puebla, Guillermo Román-Díez, Resource analysis: From sequential to concurrent and distributed programs, FM 2015: Formal Methods (2015) 3-17.

[4]

Elvira Albert, Puri Arenas, Samir Genaim, German Puebla, Damiano Zanardini, Cost analysis of object-oriented bytecode programs, Theoretical Computer Science, 413 (2012) 142-159.

Digital Library

[5]

Elvira Albert, Jesús Correas, Germán Puebla, Guillermo Román-Díez, Incremental resource usage analysis, in: Proceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation, ACM, 2012, pp. 25-34.

Digital Library

[6]

David Aspinall, Robert Atkey, Kenneth MacKenzie, Donald Sannella, Symbolic and analytic techniques for resource analysis of Java bytecode, in: Trustworthly Global Computing, Springer, 2010, pp. 1-22.

[7]

Marco Autili, Paolo Di Benedetto, Paola Inverardi, A hybrid approach for resource-based comparison of adaptable Java applications, Science of Computer Programming, 78 (2013) 987-1009.

Digital Library

[8]

John Aycock, A brief history of just-in-time, ACM Computing Surveys (CSUR), 35 (2003) 97-113.

[9]

Gilles Barthe, Pierre Crégut, Benjamin Grégoire, Thomas Jensen, David Pichardie, The MOBIUS proof carrying code infrastructure, in: Formal Methods for Components and Objects, Springer, 2008, pp. 1-24.

Digital Library

[10]

Spenser Bauman, Carl Friedrich Bolz, Robert Hirschfeld, Vasily Krilichev, Tobias Pape, Jeremy G. Siek, Sam Tobin-Hochstadt, Pycket: A tracing JIT for a functional language, in: ICFP '15, 2015.

[11]

Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, Armin Rigo, Tracing the meta-level: PyPy's tracing JIT compiler, in: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, ACM, 2009, pp. 18-25.

Digital Library

[12]

Carl Friedrich Bolz, Adrian Kuhn, Adrian Lienhard, Nicholas D. Matsakis, Oscar Nierstrasz, Lukas Renggli, Armin Rigo, Toon Verwaest, Back to the future in one week - implementing a Smalltalk VM in PyPy, in: Self-Sustaining Systems, Springer, 2008, pp. 123-139.

Digital Library

[13]

Carl Friedrich Bolz, Tobias Pape, Jeremy Siek, Sam Tobin-Hochstadt, Meta-tracing makes a fast Racket, 2014.

[14]

István Bozó, Viktoria Fordós, Zoltán Horvath, Melinda Tóth, Dániel Horpácsi, Tamás Kozsik, Judit Köszegi, Adam Barwell, Christopher Brown, Kevin Hammond, Discovering parallel pattern candidates in Erlang, in: Proceedings of the Thirteenth ACM SIGPLAN workshop on Erlang, ACM, 2014, pp. 13-23.

Digital Library

[15]

Carlo Brandolese, William Fornaciari, Fabio Salice, Donatella Sciuto, Source-level execution time estimation of C programs, in: Proceedings of the ninth international symposium on Hardware/software codesign, ACM, 2001, pp. 98-103.

Digital Library

[16]

Christopher Brown, Marco Danelutto, Kevin Hammond, Peter Kilpatrick, Archibald Elliott, Cost-directed refactoring for parallel Erlang programs, International Journal of Parallel Programming, 42 (2014) 564-582.

Digital Library

[17]

Murray I. Cole, Algorithmic skeletons: structured management of parallel computation, Pitman, London, 1989.

[18]

Computer languages benchmark game. http://benchmarksgame.alioth.debian.org/

[19]

Ugo Dal Lago, Ricardo Peña, Foundational and Practical Aspects of Resource Analysis: Third International Workshop, FOPARA 2013, in: Revised Selected Papers, vol. 8552, Springer, 2014.

[20]

Christian Ferdinand, Reinhold Heckmann, aiT: Worst-case execution time prediction by static program analysis, in: Building the Information Society, Springer, 2004, pp. 377-383.

[21]

Khronos OpenCL Working Group et al. The OpenCL specification. version, 1(29):8, 2008.

[22]

Shuai Hao, Ding Li, William GJ Halfond, Ramesh Govindan, Estimating mobile application energy consumption using program analysis, in: 2013 35th International Conference on Software Engineering (ICSE), IEEE, 2013, pp. 92-101.

Digital Library

[23]

Martin Hofmann, Automatic amortized analysis, in: Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming, ACM, 2015, pp. 5.

Digital Library

[24]

Simon L. Peyton Jones, Compiling Haskell by program transformation: A report from the trenches, in: Programming Languages and Systems - ESOP'96, Springer, 1996, pp. 18-44.

[25]

Simon Peyton Jones, Andrew Tolmach, Tony Hoare, Playing by the rules: rewriting as a practical optimisation technique in GHC, in: Haskell workshop, vol. 1, 2001, pp. 203-233.

[26]

Rody W.J. Kersten, Bernard E. Gastel, Olha Shkaravska, Manuel Montenegro, Marko C.J.D. Eekelen, ResAna: a resource analysis toolset for (real-time) JAVA, Concurrency and Computation: Practice and Experience, 26 (2014) 2432-2455.

Digital Library

[27]

Patrick Maier, John Magnus Morton, Phil Trinder, Towards an adaptive framework for performance portability, in: Pre-proceedings of IFL 2015, 2015.

[28]

Patrick Maier, Rob Stewart, Philip W. Trinder, Reliable scalable symbolic computation: The design of SymGridPar2, Computer Languages, Systems & Structures, 40 (2014) 19-35.

[29]

John Magnus Morton, Pycket fork. https://github.com/magnusmorton/pycket

[30]

John Magnus Morton, Trace analysis utilities. https://github.com/magnusmorton/trace-analysis

[31]

Tobias Pape, Benchmarking pycket against some Schemes. https://github.com/krono/pycket-bench

[32]

Pypy. http://pypy.org

[33]

Python. http://python.org

[34]

Vítor Rodrigues, Benny Akesson, Mário Florido, Simão Melo de Sousa, João Pedro Pedroso, Pedro Vasconcelos, Certifying execution time in multicores, Science of Computer Programming, 111 (2015) 505-534.

Digital Library

[35]

Norman Scaife, Susumi Horiguchi, Greg Michaelson, Paul Bristow, A parallel SML compiler based on algorithmic skeletons, Journal of Functional Programming, 15 (2005) 615-650.

Digital Library

[36]

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons, Space profiling for parallel functional programs, ACM Sigplan Notices, 43 (2008) 253-264.

Digital Library

[37]

Guy Lewis Steele, Gerald Jay Sussman, The revised report on SCHEME: A dialect of LISP, 1978.

[38]

Timing analyis on code-level (TACLe). http://www.tacle.eu

[39]

Topaz. https://github.com/topazproject/topaz

[40]

W.Philip Trinder, Murray I. Cole, Kevin Hammond, H-W. Loidl, Greg J. Michaelson, Resource analyses for parallel and distributed coordination, Concurrency and Computation: Practice and Experience, 25 (2013) 309-348.

[41]

Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, The worst-case execution-time problem - overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS), 7 (2008) 36.

Cited By

Maier PMorton JTrinder PDuke DKameyama Y(2016)JIT costing adaptive skeletons for performance portabilityProceedings of the 5th International Workshop on Functional High-Performance Computing10.1145/2975991.2975995(23-30)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2975991.2975995

JIT-Based Cost Analysis for Dynamic Program Transformations
1. Software and its engineering
  1. Software notations and tools

Recommendations

Amalgamating different JIT compilations in a meta-tracing JIT compiler framework
DLS 2020: Proceedings of the 16th ACM SIGPLAN International Symposium on Dynamic Languages

Most virtual machines employ just-in-time (JIT) compilers to achieve high-performance. Trace-based compilation and method-based compilation are two major compilation strategies in JIT compilers. In general, the former excels in compiling programs with ...
Adaptive multi-level compilation in a trace-based Java JIT compiler
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

This paper describes our multi-level compilation techniques implemented in a trace-based Java JIT compiler (trace-JIT). Like existing multi-level compilation for method-based compilers, we start JIT compilation with a small compilation scope and a low ...
A trace-based Java JIT compiler for large-scale applications
VMIL '12: Proceedings of the sixth ACM workshop on Virtual machines and intermediate languages

Trace-based compilation uses dynamically-identified frequently-executed code sequences (traces) as units for compilation. We explore trace-based compilation in Java to see if a trace-based JIT compiler (trace-JIT) can address a limitation of method-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Electronic Notes in Theoretical Computer Science (ENTCS)

Electronic Notes in Theoretical Computer Science (ENTCS) Volume 330, Issue C

December 2016

44 pages

ISSN:1571-0661

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 10 December 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Maier PMorton JTrinder PDuke DKameyama Y(2016)JIT costing adaptive skeletons for performance portabilityProceedings of the 5th International Workshop on Functional High-Performance Computing10.1145/2975991.2975995(23-30)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2975991.2975995

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents