Zastosowanie bibliotek Omega i ISL do ekstrakcji niezależnych fragmentów kodu w pętlach programowych

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

Abstrakty

PL

Prezentowane wyniki badań wskazują na zbliżoną skuteczność obu bibliotek w implementacji algorytmów ekstrakcji niezależnych fragmentów kodu. Dla badanego zestawu pętli testowych operacje tranzytywnego domknięcia unii relacji zależności oraz ekstrakcji punktów reprezentatywnych fragmentów kodu zostały policzone dla podobnych zbiorów pętli z zestawu testowego NAS. Biblioteka Omega Calculator wydaje się być projektem bardziej kompletnym, oprócz funkcji do przeprowadzania obliczeń z zakresu arytmetyki Presburgera, zawiera także analizator zależności Petit oraz funkcje generującą kod na podstawie zbioru krotek. Biblioteka ISL nie zawiera własnego analizatora zależności. Wprowadzenie do niej relacji zależności wymaga opracowania dodatkowych konwerterów. Do generowania kodu także należy wykorzystać inne narzędzia, np. Cloog [6]. Zaletami biblioteki ISL jest ciągły rozwój i częste aktualizacje oraz zgodność z najnowszymi wersjami kompilatora języka C. Wpływa to na szybkość wykonywania algorytmów (potwierdzonych w powyższych badaniach), co jest głównym plusem tego narzędzia w przeprowadzonym porównaniu. Algorytmy wyznaczania niezależnych fragmentów kodu nie narzucają zastosowania konkretnego środowiska i narzędzi, co świadczy także o ich uniwersalności. Wymagana jest dokładna reprezentacja zależności w postaci relacji oraz zdolność do przeprowadzania operacji arytmetyki Presburgera na nich. Umiejętna implementacja i dobór narzędzi stanowi o praktycznej użyteczności opracowywanych algorytmów do ekstrakcji równoległości. W przyszłych badaniach zamierzona jest dalsza weryfikacja możliwości omawianych narzędzi z wykorzystaniem innych zestawów pętli testowych.

EN

Finding synchronization-free slices is a technique of extracting parallelism available in loops. In this paper, two implementations of slicing algorithms are compared using the two polyhedral model libraries: the Omega Calculator and the Integer Set Library (ISL). These tools allow us to execute calculations using Presburger arithmetic. Results of experiments with the NASA Parallel Benchmark Suite are presented. The goal of experiments was to examine whether these both tools are able to calculate the transitive closure of a union of dependence relations, slice representatives, and synchronization-free slices.

Słowa kluczowe

PL

wydobycie równoległości w pętlach; cięcie; plastry bez synchronizacji

EN

extracting parallelism in loops; slicing; synchronization-free slices; Omega Calulator; Integer Set Library

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 3 (23)
• Strony: 49--56
• Opis fizyczny: Bibliogr. 14., rys., tab.

Twórcy

autor

Bielecki W.

autor

Pałkowski M.

autor

Sierbin M.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki, Katedra Inżynierii i Oprogramowania

Bibliografia

• [1] Pugh W., Wonnacott D. An exact method for analysis of value-based array data dependences. In Sixth Annual Workshop on Programming Languages and Compilers for Parallel Computing. Springer-Verlag, 1993.
• [2] Beletska A., Bielecki W., Siedlecki K., San Pietro P. Finding synchronization-free slices of operations in arbitrarily nested loops. In ICCSA (2), volume 5073 of Lecture Notes in Computer Science, s. 871-886. Springer, 2008.
• [3] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D. The omega library interface guide. Technical report, USA, 1995.
• [4] The Omega project. http://www.cs.umd.edu/projects/omega.
• [5] Verdoolaege S. Integer Set Library Manual, Version isl-0.0.3, http://www.kotnet.org/~skimo//isl/manual.pdf, 2010.
• [6] Bastoul C. Generating Loops for Scanning Polyhedra: CLooG User’s Guide, http://www.prism.uvsq.fr/~cedb/bastools/download/cloog.pdf, 2004.
• [7] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D. New User Interface for Petit and Other Extensions. User Guide. December 5, 1996.
• [8] Beletska A., Barthou D., Bielecki W., Cohen A. Computing the transitive closure of a union of affine integer tuple relations. In COCOA ’09: Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications, Berlin, Heidelberg, pp. 98–109. Springer-Verlag, 2009
• [9] Kelly W., Pugh W., Rosser E., Shpeisman T. Transitive Closure of Infinite Graphs and its Applications. International Journal of Parallel Programming. Tomy 24, n. 6, s. 579-598, 1996.
• [10] Bielecki W., Klimek T., Palkowski M. A modified version of iterative algorithm to computing the transitive closure of a union of affine integer tuple relations, artykuł wysłany na konferencję COCOA’10, International Conference on Combinatorial Optimization and Applications, 2010.
• [11] NAS benchmark suite. http://www.nas.nasa.gov.
• [12] The Polylib Team, Polylib User’s Manual, http://www.irisa.fr/polylib/DOC/index.html,2002
• [13] Bielecki W., Pałkowski M. Using message passing for developing coarse-grained applications in OpenMP, Proceedings of Third International Conference on Software and Data – ICSOFT 2008, Porto, Portugalia 2008, s. 145-153.
• [14] Repozytorium najnowszej wersji biblioteki Omega Calculator, 2.1, http://github.com/davewathaverford/the-omega-project/