The space-time mapping methods we study are based on the polytope model of nested loops, and on some extensions of it.
The polytope model is a useful model of computation for the static
parallelization of nested [Len93]. The model represents the
atomic iteration steps of d perfectly nested as the points of a
polytope in ; each loop defines the extent of the polytope in one
dimension. The faces of the polytope correspond to the bounds of the
loops; they are all known at compile time. This enables the compile-time
discovery of maximal parallelism--relative to the choices available within the
method, which are limited by the data dependences of the source program
and by the requirement that the space-time mapping defining the parallelism
be affine.