×

\(n\)-dimensional orthogonal tile size problem. (English) Zbl 0944.68199

We discuss in this paper the problem of generating highly efficient code when a \(n+1\)-dimensional nested loop program is executed on \(n\)-dimensional torus/grid of distributed-memory general-purpose machines. We focus on a class of uniform recurrences with non-negative components of the dependency matrix. Using tiling the iteration space strategy we show that minimizing the total running time reduces to solving a nontrivial nonlinear integer optimization problem. For the later we present a mathematical framework that enables us to derive an \(O(n/\log n)\) algorithm for finding a good approximate solution. The theoretical evaluations and the experimental results show that the obtained solution approximates the original minimum sufficiently well in the context of the considered problem. Such algorithm is real-time usable for very large values of \(n\) and can be used as optimization techniques in parallelizing compilers as well as in performance tuning of parallel codes by hand.
Reviewer: N.I.Yanev (Sofia)

MSC:

68W15 Distributed algorithms
90C90 Applications of mathematical programming