|
Mathematic
methods for analysis and transformation of programs
|
Precise analysis of
programs allows to develop efficient optimization methods subject to hardware
and/or software constraints. For nested loop programs, the iteration spaces
can be modeled by polyhedra and systems of rational linear constraints. Using
this model, important program analysis such as computing:
-
The number of
flops executed by a loop,
-
The number of
memory locations or cache lines touched by a loop,
-
The amount of
processor to processor communication needed during the execution of a loop,
-
The maximum parallelism
induced by a loop from a given time-schedule,
-
The number of
processors needed from a given mapping function,
-
The amount of
communications from a given loop and data partitioning,
-
The number of
cache misses from a given loop and data partitioning,
-
The execution
step of an iteration according to the lexicographic order,
-
The last iteration
updating an array element before a given use of it (exact symbolic array
dataflow analysis),
-
...
all reduce to geometrical and arithmetical
algorithms on polyhedra.
The resulting information can be
used to:
-
Estimate the execution
time of a code segment,
-
Compare the memory
bandwidth requirements vs. the flop counts of a code segment,
-
Determine which
loops will flush the cache, and then calculate the cache miss rate,
-
Determine if a
loop is load balanced (i.e., performs the same amount of computation in
each iteration), or if not balanced,
-
Determine number
of iterations to assign each processor in order to balance the work load
(balanced chunk-scheduling),
-
Exploit maximum
parallelism,
-
Optimize the number
of needed processors,
-
Optimize loop
and data partitioning,
-
Improve parallelism,
-
....
We have developed several mathematic
algorithms handling parameterized fundamental problems which are :
-
Computing the
parametric coordinates of the vertices of any polyhedra,
-
Computing a symbolic
expression of the number of integer points contained in a polytope,
-
Computing a symbolic
expression of the number of integer points contained in the affine transformation
of a polytope.
-
Sven Verdoolaege, Rachid Seghir, Kristof Beyls, Vincent Loechner and Maurice
Bruynooghe,
Analytical computation of Ehrhart
polynomials: enabling more compiler analyses and optimizations, Proceedings of International Conference on Compilers, Architectures, and Synthesis for Embedded Systems,
CASES 2004, pages 248--258, Washington D.C., September 2004.
-
-
-
Benoît Meister,
Periodic
Polyhedra, 13th
International Conference on Compiler Construction, CC 2004, Barcelona,
Spain, April 2004.
-
-
-
-
-
-
-
-
-