| Abstract |
|---|
| Iteration space tiling is a common strategy used by parallelizing compilers and in performance tuning of parallel codes. We address the problem of determining the tile size that minimizes the total execution time. We restrict our attention to orthogonal tiling --- uniform dependency programs with (hyper) parallelepiped shaped iteration domains which can be tiled with hyperplanes parallel to the domain boundaries. Our model is developed in two steps. We first formulate and partially resolve an abstract optimization problem which is based on two simple parameters --- tile period, P_t and inter-tile latency, L. Next, we refine the model with realistic machine and program parameters, yielding a discrete nonlinear optimization problem. This formulation includes many machine and program models used in the literature, notably the bsp programming model. We resolve the optimization problem analytically, yielding a closed form solution. |
| Contact |
| Sanjay Rajopadhye Irisa,,Campus de Beaulieu,35042 Rennes cedex,France Sanjay.Rajopadhye@irisa.fr |