A Practical Method For Quickly Evaluating Program OptimizationsOutlineBackgroundThe problem of Iterative evaluationCan we do better?What’s does phase mean?The stability of execution time of subroutine residMore examplesThe Main IdeaAdd monitor codeDetect stabilityEvaluating Optimization OptionsResultData StructureConclusion and Future workQuestions?A Practical Method For A Practical Method For Quickly Evaluating Program Quickly Evaluating Program OptimizationsOptimizationsGrigori Fursin, Albert Cohen, Michael O’Boyle Grigori Fursin, Albert Cohen, Michael O’Boyle and Olivier Temamand Olivier TemamALCHEMY Group, INRIA Futurs and LRI, Paris-Sud ALCHEMY Group, INRIA Futurs and LRI, Paris-Sud Universit, FranceUniversit, FranceInstitute for Computing Systems Architecture, Institute for Computing Systems Architecture, University of Edinburgh, UKUniversity of Edinburgh, UKPresented by Shaofeng LiuOutlineOutlineShort backgroundShort backgroundWhat’s problem we want to solve?What’s problem we want to solve?How to solve the problem?How to solve the problem?The main challengesThe main challengesResultResultConclusionConclusionBackgroundBackgroundIterative optimization has great Iterative optimization has great potential for a large range of potential for a large range of optimization techniques;optimization techniques;By running the program repeatedly, a By running the program repeatedly, a new optimization technique is tested new optimization technique is tested at each execution;at each execution;What’s the problem of this evaluation What’s the problem of this evaluation approach?approach?The problem of Iterative evaluationThe problem of Iterative evaluationProblem:Problem:•Optimization option space could be huge.Optimization option space could be huge.•An naïve iterative search could be very time-An naïve iterative search could be very time-consuming.consuming.•e.g. The mgrid SpecFP2000 benchmark, it’s e.g. The mgrid SpecFP2000 benchmark, it’s original execution time is 290s, if we have 32 original execution time is 290s, if we have 32 optimization options, the total evaluation time optimization options, the total evaluation time will be 290x32=9280s. will be 290x32=9280s. [Note: An optimization option is not necessarily a single [Note: An optimization option is not necessarily a single optimization technique, it could be a combined set of techniques. ]optimization technique, it could be a combined set of techniques. ]Few work provides a practical approach for Few work provides a practical approach for effectively applying iterative optimization.effectively applying iterative optimization.Can we do better?Can we do better?The idea is:The idea is:•Can we evaluate multiple optimization options in a single Can we evaluate multiple optimization options in a single run of the program?run of the program?To do this:To do this:•This paper does some research on the programs. Other This paper does some research on the programs. Other than knowing nothing about the programs as last two than knowing nothing about the programs as last two iterative papers said, this work takes advantage of an iterative papers said, this work takes advantage of an interesting property of many programs.interesting property of many programs.The interesting thing is: The interesting thing is: •The programs (scientific applications) tend to have some The programs (scientific applications) tend to have some performance stability. performance stability. Some papers has shown that many programs exhibit Some papers has shown that many programs exhibit phases, i.e. program trace intervals of several millions phases, i.e. program trace intervals of several millions instructions where performance is similar.instructions where performance is similar.What’s does phase mean?What’s does phase mean?Phase is actually the stable consecutive Phase is actually the stable consecutive periodic runs of the same piece of code. periodic runs of the same piece of code. (e.g. time-consuming function calls, or big (e.g. time-consuming function calls, or big loop).loop).•A phase only corresponds to one piece of code;A phase only corresponds to one piece of code;•But one piece of code may have multiple But one piece of code may have multiple phases;phases;For example, if we monitor the subroutines For example, if we monitor the subroutines “resid” & “psinv” in mgrid, we can see “resid” & “psinv” in mgrid, we can see their behaviors are quite stable and their behaviors are quite stable and predictable.predictable.The stability of execution time of The stability of execution time of subroutine residsubroutine residWe can see that the execution time of resid is quite stable with We can see that the execution time of resid is quite stable with a period of 7.a period of 7.Can we take advantage of this stability?Can we take advantage of this stability?More examplesMore examplesThe Main IdeaThe Main IdeaFind some time-consuming functions and big loops Find some time-consuming functions and big loops to optimize;to optimize;(I think this is done by the EKOPath compiler and (I think this is done by the EKOPath compiler and users).users).Insert the codes optimized with different Insert the codes optimized with different optimization options into the original code, i.e, optimization options into the original code, i.e, multi-version code;multi-version code;Detect the phases of the program;Detect the phases of the program;Apply different optimization options within one Apply different optimization options within one phase and measure the execution time. Since phase and measure the execution time. Since these executions are supposed to have same these executions are supposed to have same execution time without optimization, so the execution time without optimization, so the changes of execution time is the effect of the changes of execution time is the effect of the optimization techniques. optimization techniques.Add monitor codeAdd monitor codeCompiler instrumentationCompiler instrumentation•Two monitoring routines Two monitoring routines timer_start and timer_start and timer_stop are added timer_stop are added before and after each before and after each monitored code section;monitored code section;timer_start: select one timer_start: select one piece of code from the piece of code from the multi-version, and record