PLI: The Periodic-Linear Model of Program Behavior Capture

Philippe Clauss, Bénédicte Kenmei

Understanding and controlling program behavior is a challenging objective for the design of advanced compilers and critical system development. We propose an analysis and modeling strategy of program behavior characteristics by considering traces generated from opportune code instrumentations. The proposed models consist in periodic and linear interpolations separated into adjacent program phases. It is shown that these models exhibit apparent and useful information on program behavior. Moreover they can directly be used to guide static optimizations or to build dynamic optimization processes.

Periodic interpolation allows to extract periodic behavior information of the observed program as well as reduce the complexity of the interpolation function. For example, the sequence [3, 3, 7, 13, 11, 23, 15, 33, 19, 43, 23] where each element is respectively indexed by 0,1,2,... is interpolated classically by the polynomial:


which is a quite high degree polynomial exhibiting no apparent information about periodicity. Instead, periodic interpolation would give the following interpolation function:

[2,5] x + [3,-2]

which is equal to 2x + 3 if x mod 2 = 0 and 5x - 2 if x mod 2 = 1. It shows clearly a periodic behavior of period 2 and a linear relation between 2-spaced elements.

Our model defines as one program phase a set of successive intervals that are linearly and periodically dependent. So it expresses behavior characteristics based on linear and periodic evolution of program runs. We associate each interval of a program phase a chronological time index, defining the time space of the model. Since each periodic coefficient of the periodic interpolation function can itself be interpreted as a trace, we recursively apply our model to the coefficients. This approach yields the definition of a multi-dimensional time space and a granularity hierarchy of the program behavior.

This multi-dimensionnal time model onto a phase can be fully represented as a loop nest of depth d of the following general form, where the instruction of the innermost loop serves to output the element value associated to a time instant (t1,t2,...,td):

 

where f(t1,t2,...,td) is the final multi-variable function resulting from the d-depth recursive application of the model.

Our periodic-linear interpolation approach is being implemented. The last version of the software is available here.

Application example : retrieving array accesses from pointer accesses in program fir2dim (DSPstone benchmark)

References:

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.