Concurrent Start Tiling of Stencil Computations based on the Transitive Closure of a Data Dependence Graph

• Autorzy: Bielecki W. , Skotnicki P.

Warianty tytułu

PL

Transformacja pe˛ tli programowych przez blokowanie z równoczesnym rozpoczęciem obliczeń za pomocą domknięcia przechodniego grafu zależności danych

• Języki publikacji: EN

Abstrakty

EN

Stencil computations stand at the core of a wide range of scientific and engineering solutions. Load-balanced execution of stencil kernels, allowing for full utilization of processing units from the very beginning, is therefore the subject of a considerable amount of research. This paper presents a novel approach to generating parallel tiled code of stencil loops, based on the application of the transitive closure of a data dependence graph and a combination of the polyhedral model and the iteration space slicing framework.

PL

Iteracyjne obliczenia, będące funkcja wartości punktów pewnej przestrzeni w czasie, stanowią podstawe˛ szerokiego zakresu rozwiązań naukowych i inżynieryjnych. Efektywne wykonanie realizujących je pętli programowych, poprzez pełne i zrównowaz˙one wykorzystanie dostępnych jednostek obliczeniowych od samego początku, jest przedmiotem znacznej liczby badań. Artykuł prezentuje nowe podejście do blokowania omawianych pętli, bazujące na zastosowaniu domknięcia przechodniego grafu zależności danych oraz technice podziału przestrzeni iteracji.

Słowa kluczowe

EN

optimizing compilers; tiling; transitive closure; paraller computing; dependence graph

PL

kompilator; blokowanie pętli; domknięcie przechodnie; obliczenia równoległe; graf zależności

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2015
• Tom: R. 91, nr 11
• Strony: 167--170
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Bielecki W.

• West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, ul. Z˙ołnierska 49, 70-210 Szczecin, Poland

autor

Skotnicki P.

• West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, ul. Z˙ołnierska 49, 70-210 Szczecin, Poland

Bibliografia

• [1] Bandishti V., Pananilath I., Bondhugula U.: Tiling Stencil Computations to Maximize Parallelism, In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, IEEE Computer Society Press, (2012).
• [2] Bastoul C.: Code Generation in the Polyhedral Model Is Easier Than You Think, In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, pp. 7–16, IEEE Computer Society, (2004).
• [3] Benabderrahmane M. W., Pouchet L. N., Cohen A., Bastoul C.: The Polyhedral Model Is More Widely Applicable Than You Think, Compiler Construction, Springer Berlin Heidelberg, pp. 283–303, (2010).
• [4] Bielecki W., Klimek T., Pałkowski M., Beletska A.: An Iterative Algorithm of Computing the Transitive Closure of a Union of Parameterized Affine Integer Tuple Relations, In COCOA 2010: Fourth International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol. 6508/2010, pp. 104–113, (2010).
• [5] Bielecki W., Pałkowski M.: Perfectly Nested Loop Tiling Transformations Based on the Transitive Closure of the Program Dependence Graph, Soft Computing in Computer and Information Science, vol. 342, pp. 309–320, Springer International Publishing, (2015).
• [6] Grosser T., Cohen A., Holewinski J., Sadayappan P., Verdoolaege S.: Hybrid Hexagonal/Classical Tiling for GPUs, In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, p. 66, ACM, (2014).
• [7] Grosser T., Cohen A., Kelly P. H., Ramanujam J., Sadayappan P., Verdoolaege S.: Split Tiling for GPUs: Automatic Parallelization Using Trapezoidal Tiles, In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, pp. 24–31, ACM, (2013).
• [8] Krishnamoorthy S., Baskaran M., Bondhugula U., Ramanujam J., Rountev A., Sadayappan P.: Effective Automatic Parallelization of Stencil Computations, ACM SIGPLAN Notices, vol. 42, no. 6, pp. 235–244, ACM, (2007).
• [9] OpenMP Architecture Review Board: OpenMP Application Program Interface Version 3.0, www.openmp.org/mp-documents/spec30.pdf, (2008).
• [10] Pugh W., Rosser E.: Iteration Space Slicing and Its Application to Communication Optimization, In Proceedings of the 11th International Conference on Supercomputing, pp. 221–228, ACM, (1997).
• [11] Verdoolaege S., Grosser T.: Polyhedral Extraction Tool, Second International Workshop on Polyhedral Compilation Techniques (IMPACT’12), Paris, France, (2012).
• [12] Verdoolaege S.: Barvinok – User Guide, Version: barvinok-0.37, compsys-tools.ens-lyon.fr/iscc/barvinok.pdf, (2014).
• [13] Verdoolaege S.: Integer Set Library – Manual, Version: isl- 0.14, isl.gforge.inria.fr/manual.pdf, (2014).
• [14] Weiser M.: Program Slicing, In IEEE Transactions on Software Engineering, pp. 352–357, (1984).