Abstract
Tiling is an important loop optimization for exposing coarse-grained parallelism and enhancing data locality. Tiled loop generation from an arbitrarily shaped polyhedron is a well studied problem. Except for the special case of a rectangular iteration space, the tiled loop generation problem has been long believed to require heavy machinery such as Fourier-Motzkin elimination and projection, and hence to have an exponential complexity. In this paper we propose a simple and efficient tiled loop generation technique similar to that for a rectangular iteration space. In our technique, each loop bound is adjusted only once, syntactically and independently. Therefore, our algorithm runs linearly with the number of loop bounds. Despite its simplicity, we retain several advantages of recent tiled code generation schemes—unified generation for fixed, parameterized and hybrid tiled loops, scalability for multi-level tiled loop generation with the ability to separate full tiles at any levels, and compact code. We also explore various schemes for multi-level tiled loop generation. We formally prove the correctness of our scheme and experimentally validate that the efficiency of our technique is comparable to existing parameterized tiled loop generation approaches. Our experimental results also show that multi-level tiled loop generation schemes have an impact on performance of generated code. The fact that our scheme can be implemented without sophisticated machinery makes it well suited for autotuners and production compilers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. In: PLDI 2008, pp. 101–113. ACM, New York (2008)
Ahmed, N., Mateev, N., Pingali, K.: Tiling imperfectly-nested loop nests. In: Supercomputing 2000, Washington, DC, USA, p. 31. IEEE Computer Society, Los Alamitos (2000)
Lim, A.W., Liao, S.W., Lam, M.S.: Blocking and array contraction across arbitrarily nested loops using affine partitioning. In: PPoPP 2001, pp. 103–112. ACM Press, New York (2001)
Xue, J.: Loop Tiling For Parallelism. Kluwer Academic Publishers, Dordrecht (2000)
Lam, M.S., Wolf, M.E.: A data locality optimizing algorithm (with retrospective). In: Best of PLDI, pp. 442–459 (1991)
Wolfe, M.: Iteration space tiling for memory hierarchies. In: Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, Philadelphia, PA, USA, pp. 357–361. Society for Industrial and Applied Mathematics (1989)
Wolfe, M.: More iteration space tiling. In: Supercomputing 1989, pp. 655–664. ACM, New York (1989)
Irigoin, F., Triolet, R.: Supernode partitioning. In: 15th ACM Symposium on Principles of Programming Languages, pp. 319–328. ACM, New York (1988)
Goumas, G., Athanasaki, M., Koziris, N.: An efficient code generation technique for tiled iteration spaces. IEEE Transactions on Parallel and Distributed Systems 14(10) (2003)
Renganarayanan, L., Kim, D., Rajopadhye, S., Strout, M.M.: Parameterized tiled loops for free. In: PLDI 2007, pp. 405–414. ACM Press, New York (2007)
Ancourt, C., Irigoin, F.: Scanning polyhedra with DO loops. In: PPoPP 1991, pp. 39–50 (1991)
Le Verge, H., Van Dongen, V., Wilde, D.: La synthèse de nids de boucles avec la bibliothèque polyédrique. In: RenPar‘6, Lyon, France (1994); English version, Loop Nest Synthesis Using the Polyhedral Library in IRISA TR 830 (May 1994)
Le Verge, H., Van Dongen, V., Wilde, D.: Loop nest synthesis using the polyhedral library. Technical Report PI 830, IRISA, Rennes, France (1994)
Kelly, W., Pugh, W., Rosser, E.: Code generation for multiple mappings. In: Frontiers 1995: The 5th Symposium on the Frontiers of Massively Parallel Computation, McLean, VA (1995)
Pugh, W.: Omega test: A practical algorithm for exact array dependency analysis. Comm. of the ACM 35(8), 102 (1992)
Wilson, R.P., French, R.S., Wilson, C.S., Amarasinghe, S.P., Anderson, J.M., Tjiang, S.W.K., Liao, S.W., Tseng, C.W., Hall, M.W., Lam, M.S., Hennessy, J.L.: SUIF: An infrastructure for research on parallelizing and optimizing compilers. SIGPLAN Notices 29(12), 31–37 (1994)
Quilleré, F., Rajopadhye, S., Wilde, D.: Generation of efficient nested loops from polyhedra. International Journal Parallel Programming 28(5), 469–498 (2000)
Bastoul, C.: Code generation in the polyhedral model is easier than you think. In: PACT 2004, Juan-les-Pins, 7–16 (2004)
Amarasinghe, S.P., Lam, M.S.: Communication optimization and code generation for distributed memory machines. In: PLDI 1993, pp. 126–138. ACM Press, New York (1993)
Größlinger, A., Griebl, M., Lengauer, C.: Introducing non-linear parameters to the polyhedron model. In: Gerndt, M., Kereku, E. (eds.) Proc. 11th Workshop on Compilers for Parallel Computers (CPC 2004). Research Report Series, LRR-TUM, Technische Universität München, pp. 1–12 (2004)
Jiménez, M., Llabería, J.M., Fernández, A.: Register tiling in nonrectangular iteration spaces. ACM Trans. Program. Lang. Syst. 24(4), 409–453 (2002)
Kim, D., Renganarayanan, L., Rostron, D., Rajopadhye, S., Strout, M.M.: Multi-level tiling: M for the price of one. In: SC 2007, pp. 1–12. ACM, New York (2007)
Hartono, A., Baskaran, M.M., Bastoul, C., Cohen, A., Krishnamoorthy, S., Norris, B., Ramanujam, J., Sadayappan, P.: Parametric multi-level tiling of imperfectly nested loops. In: ICS 2009: Proceedings of the 23rd international conference on Supercomputing, pp. 147–157. ACM, New York (2009)
Gagnon, E., Hendren, L.: An object-oriented compiler framework. In: Proceedings of TOOLS, pp. 140–154 (1998)
Kim, D., Rajopadhye, S.: Parameterized tiling for imperfectly nested loops. Technical Report 09-101, Colorado State University (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, D., Rajopadhye, S. (2010). Efficient Tiled Loop Generation: D-Tiling. In: Gao, G.R., Pollock, L.L., Cavazos, J., Li, X. (eds) Languages and Compilers for Parallel Computing. LCPC 2009. Lecture Notes in Computer Science, vol 5898. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13374-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-13374-9_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13373-2
Online ISBN: 978-3-642-13374-9
eBook Packages: Computer ScienceComputer Science (R0)