On the maximal dimensionality of tiles in tiled code generated by means of Affine Transformations

• Autorzy: Bielecki W. , Pałkowski M.
• Języki publikacji: EN

Abstrakty

EN

Tiling(blocking) is a very important iteration reordering transformation for both improving data locality and extracting loop nest parallelism. Affine transformations are one of the most power approach to generate tiled code. Tile dimensionality has a strong impact on tiled code performance. This paper presents a way allowing one to discover before tiling what is the maximal dimensionality of tiles in code generated by means of affine transformations.

Blokowanie jest bardzo ważną transformacja reorganizacji iteracji zarówno dla poprawy lokalności pętli jak i dla ekstrakcji równoległości w gniezdzie pętli programowej. Przekształcenia afiniczne są jednym z najbardziej mocnych podejść do implementacji techniki blokowania. W artykule przedstawiono sposób, za pomocą którego można odkryć przed zastosowaniem blokowania jaki jest maksymalny wymiar bloków w kodzie generowanym za pomocą przekształceń afinicznych, który ma silny wpływ na wydajność kodu.

Słowa kluczowe

EN

optimizing compilers; tiling; affine transformation; parallelism

PL

kompilator; transformacja afiniczna; równoległość

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2015
• Tom: R. 91, nr 11
• Strony: 158--161
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Bielecki W.

• West Pomeranian University of Technology Szczecin, Faculty of Computer Science, 71-210 Szczecin, ul. Żołnierska 49

autor

Pałkowski M.

• West Pomeranian University of Technology Szczecin, Faculty of Computer Science, 71-210 Szczecin, ul. Żołnierska 49

Bibliografia

• [1] Wolf, M.: Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, pp. 357–361, 1987.
• [2] Irigoin, F. and Triolet, R.: Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 319–329,1988.
• [3] C King, C., Ni, L.: Grouping in nested loops for parallel execution on multicomputers, In Proc. of Int. Conf. on Parallel Processing, 1989.
• [4] Wolf, M., Lam, S.: Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Trans. Parallel Distrib. Syst., 2(4), pp. 452–471, 1991.
• [5] Feautrier, P.: Some efficient solutions to the affine scheduling problem: II. Multidimensional time, Int. J. Parallel Program., 21(5), pp. 389–420, 1992.
• [6] Ramanujam, J., Sadayappan, P.: Tiling Multidimensional Iteration Spaces for Multicomputer, Proceedings of the 1990 International Conference on Parallel Processing 1992.
• [7] Lim, A., and Gerald I. Cheong,G., Lam, M.: An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication, In Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing, pp. 228–237, 1999.
• [8] Xue, J.: Loop Tiling for Parallelism, Kluwer Academic Publishers, 43, pp. 101–113, 2000.
• [9] Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer, SIGPLAN, 43, pp. 101–113, 2008.
• [10] Pouchet, L-N., Bondhugula, U.,Bastoul,C., Cohen A., Ramanujam, J., Sadayappan, P., Vasilache, N.: Loop transformations: convexity, pruning and optimization, Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 43, pp. 549–562, 2011.
• [11] Lenstra, H.W.: Integer programming with a fixed number of variables., Mathematics of Operations Research, 8(4), pp. 538–548, 1983.
• [12] The Polyhedral Benchmark suite, http://www.cse.ohiostate.edu/ pouchet/software/polybench/, 2012.
• [13] "The Livermore Fortran Kernels: A Computer Test Of The Numerical Performance Range", Techn. report, UCRL-53745, 1986.
• [14] PughW.,Wonnacott D.: An exact method for analysis of valuebased array data dependences, Sixth Annual Workshop on Programming Languages and Compilers for Parallel Computing, 1983.
• [15] Bielecki W., Palkowski M.: Perfectly nested loop tiling transformations based on the transitive closure of the program dependence graph, Soft Computing in Computer and Information Science, 342, 2015.