|
Collaborative
Static and Dynamic analysis for feedback-directed optimisations
|
HATRIA DOLCEVITAProfiling a program consists in collecting opportune informations
during its execution in order to guide efficient optimizations (dead code
elimination, prefetching, instruction scheduling, memory layout transformation,
...). Those optimisations can be applied either by transforming the initial
source code or by re-compiling it guided by the collected informations.
Profiling is essential when optimizing codes where dynamic control
structures occur and for which static analysis is inadequate. But this approach
has several drawbacks :
-
Preliminary executions can be very time-consumable. Moreover
initial versions of programs have not been optimized yet.
-
The computation volume during profiling is often small compared
to real executions for the above reason. Hence collected informations can
lead to program transformations that would be inadequate for larger computations.
-
Interactions between optimizations of the initial code are
often not considered although some transformations applied on some parts
can have bad effects on some other parts.
-
Existing profiling tools collect global informations that
can be slightly refined. Static analysis should be used in order to guide
the profiling process in order to eliminate any useless tracing and to refine
useful observations.
Our objective is to develop some automatic methods for collaborative static
and dynamic analysis of programs :
-
Static analysis adaptation and extensions allowing to focus
the profiling process on presumed expensive parts of the initial code and
allowing to identify some possible interactions,
-
Automatic generation of entries guiding the profiling process,
-
Development of a customizable profiling software,
-
Validation of the approach by applying some optimizations
guided by the static/dynamic analysis results.
We recently proposed a model of program
behavior capture called the periodic-linear model
(PLI). Program profiling traces are analyzed and represented as
periodic-linear functions that exhibit useful information about
periodicity and repetitive behaviors of the analyzed program. Moreover,
the whole trace is represented as a sequence of loop nests that
constitutes a rich analysis and optimization framework. More details and
the current software implementation can be found here.
- Ph. Clauss, B. Kenmei and J.C. Beyler, The Periodic-Linear Model of Program Behavior
Capture, Euro-Par 2005, LNCS 3648, pages 325-335, Springer, Lisboa, Portugal, September 2005.
- Ph. Clauss, Bénédicte
Kenmei Youta and Odile Rousselet, Modeling
Program Traces with Nested Loops, Workshop on Exploring the Trace Space
for Dynamic Optimization Techniques, held in conjunction with ICS'03, San
Francisco, USA, june 2003.
| |