n-Dimensional Orthogonal Tile Sizing Problem

this paper how to execute a class of n + 1-dimensional uniform recurrences in SPMD (Single Program Multiple Data) fashion on a n-dimensional torus/grid of DMM (distributed memory multicomputers) general-purpose machines. We focus on the class 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 non-linear integer optimization problem. This approach guarantees exploration of the entire solution space and for any value of the iteration space and for any torus configuration this ensures choosing the optimal task granulaty that balances the available parallelism with the cost of communication. We study which is the best direction of projection and we give analytic criterion if the optimal behavior is achieved by one or by multiple passes strategy. By revealing new and useful properties of the execution time function and its relationship with the tile volume function we derive an O(n log n) algorithm for solving the corresponding minimization problem. Such result is real-time usable for very large values of n and can be used in the parallelizing compilers optimization techniques