Dependence analysis and extraction of coarse-grained parallelism for parameterized perfectly-nested loops

• Autorzy: Bielecki W. , Kraska K. , Poliwoda M.

Warianty tytułu

PL

Analiza zależności oraz ekstrakcja gruboziarnistej równoległości sparametryzowanych pętli idealnie zagnieżdżonych

• Języki publikacji: EN

Abstrakty

EN

This paper expands an approach presented in [1] to extraction of coarse-grained parallelism available in parameterized uniform and quasi-uniform perfectly-nested loops. It introduces a dependence analysis that is characterized by a polynomial time complexity and enables computing dependence distance vectors when the Petit dependence analyser fails to produce dependences. It permits to examine the performance of the approach for all parameterized perfectly-nested loops from the NAS Parallel Benchmark Suite.

PL

W artykule przedstawiono rozwinięcie zaprezentowanego we wcześniejszej pracy [1] podejścia do ekstrakcji gruboziarnistej równoległości w jednorodnych oraz quasi-jednorodnych pętlach programowych idealnie zagnieżdżonych. Rozwinięcie uprzednich wyników zostało osiągnięte poprzez wprowadzenie analizy zależności o wielomianowej złożoności obliczeniowej jednocześnie umożliwiającej obliczenie wektorów zależności w tych przypadkach, w których uprzednio wykorzystany analizator zależności Petit sygnalizował brak możliwości analizy źródła. Stworzyło to ostatecznie warunki do oceny skuteczności działania proponowanego podejścia dla wszystkich sparametryzowanych pętli idealnie zagnieżdżonych zawartych w zestawie testowym NAS Parallel Benchmark Suite.

Słowa kluczowe

EN

parallelizing compilers; dependence analysis; quasi-uniform dependences; loop transformation

PL

kompilatory zrównoleglające; analiza zależności; zależności quasi-jednorodne; transformacja pętli

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 10b
• Strony: 231--234
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Bielecki W.

autor

Kraska K.

autor

Poliwoda M.

• Zachodniopomorski Uniwersytet Technologiczny, Wydział Informatyki, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Bielecki, W., Kraska, K., Extracting coarse-grained parallelism for affine perfectly nested quasi-uniform loops. 9th International Conference on Parallel Processing and Applied Mathematics, proceedings: R. Wyrzykowski et al. (Eds.): PPAM 2011, Part I, LNCS 7203 (2012), 307-316
• [2] Lim, A.W., Lam M.S., Maximizing Parallelism and Minimizing Synchronization with Affine Partitions, Parallel Computing, (1998), Vol 24, Issue 3-4, 445-475
• [3] Griebl, M., Automatic Parallelization of Loop Programs for Distributed Memory Achitectures. Habilitation, Fakultät für Mathematik und Informatik Universität Passau (2004)
• [4] Beletska, A., Bielecki, W., Pietro, P.S., Extracting Coarse-Grained Parallelism in Program Loops with the Slicing Framework, In ISPDC (2007), 203-210
• [5] NASA Advanced Supercomputing Division, http://www.nas.nasa.gov
• [6] Kelly, W., Maslov, V., Pugh, W., Rosser, E., Shpeisman, T., Wonnacott, D., The Omega Library Interface Guide, Technical Report CS-TR-3445, Dept. of Computer Science, University of Maryland College Park (1995)
• [7] Schrijver, A., Theory of Linear and Integer Programming, Series in Discrete Mathematics (1999)
• [8] Nookala, P.K.V.V, Risset, T., A Library for Z-Polyhedral Operations, Publication interne n.1330, Institut de Recherche en Informatique et Systemes Aléatoires (2000)
• [9] Hofting, F., Wanke, E., Polynomial-Time Analysis of Toroidal Periodic Graphs, Journal of Algorithms 34 (2000), 14-39
• [10] Bondhugula, U.K.R.,Effective Automatic Parallelization and Locality Optimization Using the Polyhedral Model. Dissertation, The Ohio State University (2010)
• [11] Skiena, S., The Algorithm Design Manual. 2nd Edition, Springer (2008)
• [12] Quinton, P., Rajopadhye, S., Risset, T., On Manipulating Z-Polyhedra. Publication interne n.1016, Institut de Recherche en Informatique et Systemes Aléatoires (1996)
• [13] Cohen, E., Megiddo, N., Recognizing Properties of Periodic Graphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4 (1991), 135-146
• [14] Bastoul, C., Code Generation in the Polyhedral Model Is Easier Than You Think, PACT'13 IEEE International Conference on Parallel Architecture and Compilation Techniques (2004), 7-16