research-article

Public Access

Real-Time Program-Specific Phase Change Detection for Java Programs

Authors:

Meng-Chieh Chiu,

Benjamin Marlin,

Eliot MossAuthors Info & Claims

PPPJ '16: Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools

Article No.: 12, Pages 1 - 11

https://doi.org/10.1145/2972206.2972221

Published: 29 August 2016 Publication History

Abstract

It is well-known that programs tend to have multiple phases in their execution. Because phases have impact on micro-architectural features such as caches and branch predictors, they are relevant to program performance Xian et al. [2007], Roh et al. [2009], Gu and Verbrugge [2008] and energy consumption. They are also relevant to detecting whether a program is executing as expected or is encountering unusual or exceptional conditions, a software engineering and program monitoring concern Peleg and Mendelson [2007], Singer and Kirkham [2008], Pirzadeh et al. [2011], Benomar et al. [2014]. We offer here a method for real-time phase change detection in Java programs. After applying a training protocol to a program of interest, our method can detect phase changes at run time for that program with good precision and recall (compared with a "ground truth" definition of phases) and with small performance impact (average less than 2%). We also offer improved methodology for evaluating phase change detection mechanisms. In sum, our approach offers the first known implementation of real-time phase detection for Java programs.

References

[1]

O. Benomar, H. Sahraoui, and P. Poulin. Detecting program execution phases using heuristic search. In Search-Based Software Engineering, pages 16--30. Springer, 2014.

[2]

S. M. Blackburn, R. Garner, C. Hoffman, A. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, S. Z. Guyer, A. Hosking, M. Jump, J. E. B. Moss, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Widerman. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 2006 ACM International Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA 2006), pages 169--190, Portland, OR, October 2006.

Digital Library

[3]

C.-B. Cho and T. Li. Complexity-based program phase analysis and classification. In Proceedings of the 15th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2006, pages 105--113. ACM, 2006.

Digital Library

[4]

A. S. Dhodapkar and J. E. Smith. Comparing program phase detection techniques. In Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 36, page 217. IEEE Computer Society, 2003.

Digital Library

[5]

S. Dieckmann and U. Hölzle. A study of the allocation behavior of the SPECjvm98 Java benchmark. In Proceedings of the 13th European Conference on Object-Oriented Programming, ECOOP '99, pages 92--115, London, UK, 1999. Springer-Verlag. ISBN 3-540-66156-5. URL http://dl.acm.org/citation.cfm?id=646156.679838.

Digital Library

[6]

E. Duesterwald, C. Caşcaval, and S. Dwarkadas. Characterizing and predicting program behavior and its variability. In Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2003, pages 220--231. IEEE, 2003.

Digital Library

[7]

A. Georges, D. Buytaert, L. Eeckhout, and K. De Bosschere. Method-level phase behavior in Java workloads. In Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '04, pages 270--287, New York, NY, USA, 2004. ACM. ISBN 1-58113-831-8. URL http://doi.acm.org/10.1145/1028976.1028999.

Digital Library

[8]

D. Gu and C. Verbrugge. Phase-based adaptive recompilation in a JVM. In Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization, pages 24--34. ACM, 2008.

Digital Library

[9]

W. ke Chen, S. Bhansali, T. Chilimbi, X. Gao, and W. Chuang. Profile-guided proactive garbage collection for locality optimization. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, PLDI '06, pages 332--340. ACM, 2006.

Digital Library

[10]

J. Lau, E. Perelman, G. Hamerly, T. Sherwood, and B. Calder. Motivation for variable length intervals and hierarchical phase behavior. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 2005, pages 135--146. IEEE, 2005.

Digital Library

[11]

G. McLachlan and D. Peel. Finite mixture models. John Wiley & Sons, 2004.

[12]

P. Nagpurkar and C. Krintz. Visualization and analysis of phased behavior in Java programs. In Proceedings of the 3rd International Symposium on Principles and Practice of Programming in Java, pages 27--33. Trinity College Dublin, 2004.

Digital Library

[13]

P. Nagpurkar, C. Krintz, M. Hind, P. F. Sweeney, and V. T. Rajan. Online phase detection algorithms. In Proceedings of the International Symposium on Code Generation and Optimization, pages 111--123. IEEE Computer Society, 2006.

Digital Library

[14]

M. Otte and S. Richardson. An HMM applied to semi-online program phase analysis (CU-CS-1034-07). Technical report, Univ. of Colorado Boulder, 2007.

[15]

N. Peleg and B. Mendelson. Detecting change in program behavior for adaptive optimization. In Parallel Architecture and Compilation Techniques, 2007. PACT 2007. 16th International Conference on, pages 150--162. IEEE, 2007.

Digital Library

[16]

H. Pirzadeh, A. Agarwal, and A. Hamou-Lhadj. An approach for detecting execution phases of a system for the purpose of program comprehension. In Eighth ACIS International Conference on Software Engineering Research, Management, and Applications (SERA), 2010, pages 207--214. IEEE, 2010.

Digital Library

[17]

H. Pirzadeh, A. Hamou-Lhadj, and M. Shah. Exploiting text mining techniques in the analysis of execution traces. In 2011 27th IEEE International Conference on Software Maintenance (ICSM), pages 223--232. IEEE, 2011.

Digital Library

[18]

N. P. Ricci, S. Z. Guyer, and J. E. B. Moss. Tool demonstration: Elephant Tracks---generating program traces with object death records. In Proceedings of the 9th International Conference on the Principles and Practice of Programming in Java, pages 39--43, Kongens Lyngby, Denmark, Aug. 2011. ACM.

Digital Library

[19]

N. P. Ricci, S. Z. Guyer, and J. E. B. Moss. Elephant Tracks: Portable production of complete and precise GC traces. In P. Cheng and E. Petrank, editors, International Symposium on Memory Management, ISMM '13, Seattle, WA, USA - June 20-20, 2013, pages 109--118. ACM, 2013. ISBN 978-1-4503-2100-6. URL http://doi.acm.org/10.1145/2464157.2466484.

Digital Library

[20]

Y. Roh, J. Kim, and K. H. Park. A phase-adaptive garbage collector using dynamic heap partitioning and opportunistic collection. IEICE TRANSACTIONS on Information and Systems, 92(10):2053--2063, 2009.

[21]

X. Shen, Y. Zhong, and C. Ding. Locality phase prediction. In Proceedings of the 11th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XI, pages 165--176, New York, NY, USA, 2004. ACM. ISBN 1-58113-804-0. URL http://doi.acm.org/10.1145/1024393.1024414.

Digital Library

[22]

T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically characterizing large scale program behavior. ACM SIGOPS Operating Systems Review, 36(5):45--57, 2002.

Digital Library

[23]

J. Singer and C. Kirkham. Dynamic analysis of Java program concepts for visualization and profiling. Science of Computer Programming, 70(2):111--126, 2008.

Digital Library

[24]

C. Wang, X. Li, D. Dai, G. Jia, and X. Zhou. Phase detection for loop-based programs on multicore architectures. In 2012 IEEE International Conference on Cluster Computing (CLUSTER), pages 584--587. IEEE, 2012.

Digital Library

[25]

Y. Watanabe, T. Ishio, and K. Inoue. Feature-level phase detection for execution trace using object cache. In Proceedings of the 2008 International Workshop on Dynamic Analysis; held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2008), pages 8--14. ACM, 2008.

Digital Library

[26]

C. Wimmer, M. S. Cintra, M. Bebenita, M. Chang, A. Gal, and M. Franz. Phase detection using trace compilation. In Proceedings of the 7th International Conference on Principles and Practice of Programming in Java (PPPJ), pages 172--181. ACM, 2009.

Digital Library

[27]

F. Xian, W. Srisa-an, and H. Jiang. Microphase: An approach to proactively invoking garbage collection for improved performance. In Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications, OOPSLA '07, pages 77--96, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-786-5. URL http://doi.acm.org/10.1145/1297027.1297034.

Digital Library

[28]

C. Zhang, K. Kelsey, X. Shen, C. Ding, M. Hertz, and M. Ogihara. Program-level adaptive memory management. In Proceedings of the 5th International Symposium on Memory Management, ISMM 2006, pages 174--183. ACM, 2006.

Digital Library

[29]

W. Zhang, J. Li, Y. Li, and H. Chen. Multilevel phase analysis. ACM Transactions on Embedded Computing Systems (TECS), 14(2):31, 2015.

Digital Library

Cited By

Chiu MMoss ETilevich EMössenböck H(2018)Run-time program-specific phase prediction for python programsProceedings of the 15th International Conference on Managed Languages & Runtimes10.1145/3237009.3237011(1-10)Online publication date: 12-Sep-2018
https://dl.acm.org/doi/10.1145/3237009.3237011

Recommendations

Run-time program-specific phase prediction for python programs
ManLang '18: Proceedings of the 15th International Conference on Managed Languages & Runtimes

It is well-known that a program's execution can be partitioned into different phases. Because of their impact on micro-architectural components such as caches and branch predictors, phases are an important aspect of dynamic program behavior that is ...
Accurate and Low-Overhead Dynamic Detection and Prediction of Program Phases Using Branch Signatures
SBAC-PAD '08: Proceedings of the 2008 20th International Symposium on Computer Architecture and High Performance Computing

We introduce a hardware-only program phase detection and prediction architecture, which improves on the existing proposal by forming the execution footprints using simple bit-vectors called "branch signatures" to capture the set of branches touched ...
Online Phase Detection Algorithms
CGO '06: Proceedings of the International Symposium on Code Generation and Optimization

Today's virtual machines (VMs) dynamically optimize an application as it is executing, often employing optimizations that are specialized for the current execution profile. An online phase detector determines when an executing program is in a stable ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

PPPJ '16: Proceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools

August 2016

186 pages

ISBN:9781450341356

DOI:10.1145/2972206

Conference Chair:
Yudi Zheng
University of Lugano
,
General Chair:
Walter Binder,
Program Chair:
Petr Tůma

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 August 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Science Foundation

Conference

PPPJ '16

PPPJ '16: Virtual Machines, Languages, and Tools

August 29 - September 2, 2016

Lugano, Switzerland

Acceptance Rates

PPPJ '16 Paper Acceptance Rate 14 of 31 submissions, 45%;

Overall Acceptance Rate 29 of 58 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
423
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)15

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chiu MMoss ETilevich EMössenböck H(2018)Run-time program-specific phase prediction for python programsProceedings of the 15th International Conference on Managed Languages & Runtimes10.1145/3237009.3237011(1-10)Online publication date: 12-Sep-2018
https://dl.acm.org/doi/10.1145/3237009.3237011

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten