Three-dimensional orthogonal tile sizing problem : mathematical programming approach
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 209-218
- https://doi.org/10.1109/asap.1997.606827
Abstract
We discuss in this paper the problem of finding the optimal tiling transformation of three-dimensional uniform recurrences on a two-dimensional torus/grid of distributed-memory general-purpose machines. We show that even for the simplest case of recurrences which allows for such transformation, the corresponding problem of minimizing the total running time is a non-trivial non-linear integer programming problem. For the later we derive an O(1) algorithm for finding a good approximation 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 analytical results are of obvious interest and can be successfully used in parallelizing compilers as well as in performance tuning of parallel codes.Keywords
This publication has 14 references indexed in Scilit:
- Two-dimensional orthogonal tiling: from theory to practicePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Precise tiling for uniform loop nestsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- (Pen)-ultimate tiling?Integration, 1994
- Communication Optimizations Used in the Paradigm Compiler for Distributed-Memory MulticomputersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- Evaluating Compiler Optimizations for Fortran DJournal of Parallel and Distributed Computing, 1994
- A loop transformation theory and an algorithm to maximize parallelismIEEE Transactions on Parallel and Distributed Systems, 1991
- Tiling multidimensional iteration spaces for nonshared memory machinesPublished by Association for Computing Machinery (ACM) ,1991
- Path planning on a ring of processors∗∗International Journal of Computer Mathematics, 1990
- Pipelined data parallel algorithms-I: concept and modelingIEEE Transactions on Parallel and Distributed Systems, 1990
- Partitioning and Mapping Algorithms into Fixed Size Systolic ArraysIEEE Transactions on Computers, 1986