Wyznaczenie punktów reprezentatywnych niezależnych fragmentów kodu w grafie zależności pętli programowych

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

Abstrakty

PL

W artykule przedstawiono nowy algorytm wyznaczania punktów reprezentatywnych cechujacy się mniejszą złożonością obliczeń w porównaniu do rozwiazania [6-7]. Powodzenie wyznaczania punktów jest zależne tylko od obliczenia dokładnego tranzytywnego domknięcia unii relacji zależności pętli. Oprócz tego należy wykonać szereg podstawowych operacji, jak: część wspólna, iloczyn skalarny, unia, aplikacja relacji na zbiorze, inwersja, projekcja. Relacja RUSC budowana jest wieloetapowo dzięki czemu można dokonywać pośrednich uproszczeń jej postaci. Opisane podejście zostało zaimplementowane i przetestowane pod kątem skuteczności na zbiorze pętli testowych NAS. W dalszych badaniach planowane jest zbadanie proponowanego algorytmu z innymi zbiorami pętli testowych oraz dalsze udoskonalanie algorytmów do wyznaczania fragmentów dla dowolnej topologii zależności pod kątem generowania wydajnego kodu równoległego.

EN

An algorithm of finding representatives of synchronization-free slices available in program loops is presented. It based on the transitive closure of a union of dependence relations describing all the dependences in program loops. An algorithm to calculate transitive closure is studied. Both the algorithms are implemented by means of the Omega library. The results of experiments with the NAS Parallel Benchmark are discussed.

Słowa kluczowe

PL

program pętli; stosunki i zestawy; równoległość; zamknięcia przechodnie; plastry bez synchronizacji

EN

program loops; relations and sets; parallelism; transitive closure; synchronization-free slices

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 1 (22)
• Strony: 13--20
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Bielecki W.

autor

Pałkowski M.

autor

Klimek T.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki, Katedra Inynierii i Oprogramowania

Bibliografia

• [1] A. W. Lim, G. I. Cheong, M. S. Lam. An affine partitioning algorithm to maximize parallelism and minimize communication. In ICS'99, pp.228-237. ACM Press, 1999.
• [2] A. Beletska, W. Bielecki, A. Cohen, M. Palkowski. Synchronization-free automatic parallelization: Beyond affine iteration-space slicing. In Languages and Compilers for Parallel Computing (LCPC'09), LNCS. Springer-Verlag, 2009.
• [3] Feautrier P., Some efficient solutions to the affine scheduling problem, part i, ii, one dimensional time, International Journal of Parallel Programming 21. (1992), s. 313-348, 389- 420.
• [4] W. Pugh, D. Wonnacott. 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.
• [5] W. Pugh, E. Rosser. Iteration space slicing and its application to communication optimization. In International Conference on Supercomputing, s. 221-228, 1997.
• [6] A. Beletska, W. Bielecki, K. Siedlecki, P. San Pietro. 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.
• [7] W. Bielecki, A. Beletska, M. Palkowski. Extracting representative loop statement instances of synchronization-free slices. In ACS '09: Proceedings of International Conference on Advanced Computer Systems, 2009.
• [8] W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, D. Wonnacott. The omega library interface guide. Technical report, USA, 1995.
• [9] The Omega project. http://www.cs.umd.edu/projects/omega.
• [10] NAS benchmark suite. http://www.nas.nasa.gov.
• [11] C. Bastoul. Code generation in the polyhedral model is easier than you think. In PACT'2004, s. 7-16, Juan-les-Pins, september 2004.
• [12] F. Bancilhon, R. Ramakrishnan. An amateur’s introduction to recursive query processing strategies. In ACM-SIGMOD 1986 Conference on Management of Data, s. 16-52, 1986.
• [13] W. Bielecki, T. Klimek, K. Trifunovic, Calculating Exact Transitive Closure for a Normalized Affine Integer Tuple Relation, Electronic Notes in Discrete Mathematics 33 (2009) 7–14.
• [14] W. Bielecki, T. Klimek, M. Pietrasik, Obliczenie tranzytywnego domknięcia sparametryzowanych relacji zależności nie należących do klasy d-form, Metody Informatyki Stosowanej Nr 2/2009 (Tom 19).
• [15] W. Bielecki, T. Klimek, M. Pietrasik, An experimental study on recognizing classes of dependence relations , Measurement Automation and Monitoring Nr 10/2009 vol 55.
• [16] W. Bielecki, T. Klimek, M. Pałkowski, An iterative algorithm of computing the transitive closure of a union parameterized affine integer tuple relations artykuł wysłany na konferencje TAMC2010.