An experimental study on recognizing classes of dependence relations

• Autorzy: Bielecki W. , Klimek T. , Pietrasik M.

Warianty tytułu

PL

Techniki identyfikacji klas relacji zależności w pętlach programowych

• Języki publikacji: EN

Abstrakty

EN

A classification of dependence relations representing exact dependences in program loops is presented. The class of a relation causes the choice of techniques for program loop parallelization. Techniques to recognize the class of a relation are presented. The implementation of these techniques by means of the Omega library is discussed. Results of an experimental study aimed at recognizing classes of dependence relations extracted for popular benchmarks (Livermore Loops, NAS, and UTDSP) are outlined.

PL

W artykule dokonano podziału relacji zależności występujących w pętlach programowych. Na podstawie przeprowadzonych obserwacji wyodrębniono sześć podstawowych klas takich relacji. Trafne rozpoznanie danej klasy relacji opisującej zależności, determinuje dobór odpowiedniej techniki transformacji pętli programowej i tym samym pozwala na uzyskanie znacznie większego jej stopnia równoległości w porównaniu z metodami bazującymi na rozwiązaniach przybliżonych. Rozwiązania takie, zawierają zdecydowanie większą liczbę zależności, aniżeli ich faktyczna liczba wystąpień. W celu ułatwienia procesu identyfikacji poszczególnych klas relacji zależności, przedstawiono szereg formalnych metod ich rozpoznania wykorzystujących szeroki wachlarz mechanizmów zawartych w bibliotece Omega. Na potrzeby przeprowadzonych badań zaimplementowano narzędzie, w ramach którego przeanalizowano zestawy pętli trzech popularnych benchmarków : Livermoore, NAS i UTDSP. Uzyskane wyniki pozwoliły wyciągnąć wnioski odnośnie procentowego udziału relacji zależności w zaproponowanych przez autorów klasach.

Słowa kluczowe

EN

affine loops; dependence relations; program transformation; parallelization

PL

pętle afiniczne; relacja zależności; transformacje pętli; przetwarzanie równoległe

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 10
• Strony: 799--802
• Opis fizyczny: Bibliogr. 9 poz., tab., wzory

Twórcy

autor

Bielecki W.

autor

Klimek T.

autor

Pietrasik M.

• Wydział Informatyki, Zachodniopomorski Uniwersytet Technologiczny,

Bibliografia

• [1] Bielecki W., Klimek T., Trifunovič K.: Calculating Exact Transitive Closure for a Normalized Affine Integer Tuple Relation, Electronic Notes in Discrete Mathematics, 33 (2009), pp. 7-14.
• [2] Bielecki W., Klimek T., Trifunovič K.: Obliczenie potęgi k znormalizowanej afinicznej relacji, Metody Informatyki Stosowanej Nr 2/2008 (Tom 15).
• [3] 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, March 1995.
• [4] Kelly W., Pugh W., Rosser E., Shpeisman T.: Transitive clousure of infinite graphs and its applications, Languages and Compilers for Parallel Computing, 1995.
• [5] Kennedy K., Allen John R.: Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., 2001.
• [6] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D.: New User Interface for Petit and other Extensions, Technical Report, Dept. of Computer Science, University of Maryland, College Park, December 1996.
• [7] http://www.netlib.org/benchmark/livermoore.
• [8] http://www.nas.nasa.gov/Software/NPB/.
• [9] http://www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html.