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 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.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
R. Andonov, H. Bourzoufi, and S. Rajopadhye. Two-dimensional orthogonal tiling: from theory to practice. In International Conference on High Performance Computing, pages 225–231, Tiruvananthapuram, India, December 1996. IEEE.
R. Andonov and S. Rajopadhye. Optimal orthogonal tiling of 2-d iterations. Journal of Parallel and Distributed Computing, 45(2):159–165, September 1997.
R. Andonov, N. Yanev, and H. Bourzoufi. Three-dimensional orthogonal tile sizing problem: Mathematical programming approach. In ASAP 97: International Conference on Application-Specific Systems, Architectures and Processors, pages 209–218, Zurich, Switzerland, July 1997. IEEE, Computer Society Press.
S. Bokhari. Communication overheads on the Intel iPSC-860 Hypercube. Technical Report Interim Report 10, NASA ICASE, May 1990.
P. Boulet, A. Darte, T. Risset, and Y. Robert, (pen)-ultimate tiling? INTEGRATION, the VLSI journal, 17:33–51, Nov? 1994.
S. Hiranandani, K. Kennedy, and C-W. Tseng. Evaluating compiler optimizations for Fortran D. Journal Of Parallel and Distributed Computing, 21:27–45, 1994.
F. Irigoin and R. Triolet. Supernode partitioning. In 15th ACM Symposium on Principles of Programming Languages, pages 319–328. ACM, Jan 1988.
R. M. Karp, R. E. Miller, and S. V. Winograd. The organization of computations for uniform recurrence equations. JACM, 14(3):563–590, July 1967.
C-T. King, W-H. Chou, and L. Ni. Pipelined data-parallel algorithms: Part I-concept and modelling. IEEE Transactions on Parallel and Distributed Systems, 1(4):470–485, October 1990.
C-T. King, W-H. Chou, and L. Ni. Pipelined data-parallel algorithms: Part II-design. IEEE Transactions on Parallel and Distributed Systems, 1(4):486–499, October 1990.
W. F. McColl. Scalable computing. In J. van Leeuwen, editor, Computer Science Today: Recent Trends and Developments, volume 1000, pages 46–61. Springer Verlag, 1995.
H. Ohta, Y. Saito, M. Kainaga, and H. Ono. Optimal tile size adjsutment in compiling general DOACROSS loop nests. In International Conference on Supercomputing, pages 270–279, Barcelona, Spain, July 1995. ACM.
D. Palermo, E. Su, J. Chandy, and P. Banerjee. Communication optimizations used in the PARADIGM compiler for distributed memory multicomputers. In International Conference on Parallel Processing, pages xx–yy, St. Charles, IL, August 1994. IEEE.
J. Ramanujam and P. Sadayappan. Tiling multidimensional iteration spaces for non shared-memory machines. In Supercomputing 91, pages 111–120, 1991.
R. Schreiber and J. Dongarra. Automatic blocking of nested loops. Technical Report 90.38, RIACS, NASA Ames Research Center, Aug 1990.
L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8): 103–111, August 1990.
M. J. Wolfe. Iteration space tiling for memory hierarchies. Parallel Processing for Scientific Computing (SIAM), pages 357–361, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Andonov, R., Rajopadhye, S., Yanev, N. (1998). Optimal orthogonal tiling. In: Pritchard, D., Reeve, J. (eds) Euro-Par’98 Parallel Processing. Euro-Par 1998. Lecture Notes in Computer Science, vol 1470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057891
Download citation
DOI: https://doi.org/10.1007/BFb0057891
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64952-6
Online ISBN: 978-3-540-49920-6
eBook Packages: Springer Book Archive