Using transitive closure and transitive reduction to extract coarse-grained parallelism in program loops

• Autorzy: Bielecki W. , Pałkowski M. , Siedlecki K.

Warianty tytułu

PL

Redukcja nadmiarowej synchronizacji w ekstrakcji równoległości gruboziarnistej

• Języki publikacji: EN

Abstrakty

EN

A technique for extracting coarse-grained parallelism available in loops is presented. It is based on splitting a set of dependence relations into two sets. The first one is to be used for generating code scanning slices while the second one permits us to insert send and receive functions to synchronize the slices execution. The paper presents a way demonstrating how to remove redundant synchronization in generated code by means of the transitive reduction operation. Results of experiments - how many synchronization points can be removed, speed-up and efficiency of examined parallel loops are discussed.

PL

W artykule zaprezentowano technikę ekstrakcji równoległości grubo-ziarnistej w pętlach programowych. Bazuje ona na podziale relacji zależności na dwa zbiory: na podstawie pierwszego generowany jest kod skanujący niezależne fragmenty, natomiast drugi służy do wstawienia funkcji send i receive (wyślij i odbierz) służących do synchronizacji tych fragmentów. Operacje te zrealizowano za pomocą semaforów, możliwe jest jednak wykorzystanie innej konstrukcji, bardziej wydajnej dla danego środowiska. Algorytm generuje kod z zaznaczonymi punktami synchronizacji, nie narzuca jednak ich implementacji. W artykule przeanalizowano technikę wyszukiwania i eliminacji zbędnych punktów synchronizacji. Ekstrakcja równoległości za pomocą fragmentów kodu bazuje na operacji tranzytywnego domknięcia, znanej także z teorii grafów. Operacja ta jest również wykorzystana do obliczenia tranzytywnej redukcji, za pomocą której eliminowana jest nadmiarowa synchronizacja. Usuwanie zbędnej komunikacji pomiędzy wątkami obliczeń jest istotne, ponieważ ich obsługa zwłaszcza dla komputerów z pamięcią dzieloną, w których ich koszt obsługi jest istotny. Docelowe jest zatem uzyskanie gruboziarnistego kodu równoległego. Zbadano także wyniki przeprowa-dzonych eksperymentów pod kątem przyspieszenia i efektywności obliczeń.

Słowa kluczowe

EN

synchronization; slices; parallelism; transitive closure and reduction

PL

fragmenty kodu; synchronizacja; równoległość; tranzytywne domknięcie i redukcja

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 8
• Strony: 976--979
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wzory

Twórcy

autor

Bielecki W.

autor

Pałkowski M.

autor

Siedlecki K.

• West Pomeranian University of technology, Department of Computer and Information Technology, ul. Zołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Kelly W., Pugh W., Rosser E., Shpeisman T.: Transitive Closure of Infinite Graphs and its Applications. International Journal of Parallel Programming. 1996, Tomy 24, n. 6, s. 579-598.
• [2] Bielecki W., Pałkowski M.: Extracting coarse-grained parallelism in computer simulation applications, Advanced Computer Systems, 13th International Multi-Conference, Vol. II, Szczecin 2006, s. 237-246.
• [3] 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.
• [4] Beletska A., Bielecki W., Siedlecki K., and San Pietro P.: Finding synchronization-free slices of operations in arbitrarily nested loops. In ICCSA (2), volume 5073 of Lecture Notes in Computer Science, pp. 871-886, Springer, 2008.
• [5] W. Pugh and D. Wonnacott.: An exact method for analysis of value-based array data dependences. In In Sixth Annual Workshop on Programming Languages and Compilers for Parallel Computing. Springer-Verlag, 1993.
• [6] The Omega project. http://www.cs.umd.edu/projects/omega
• [7] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T. and Wonnacott D.: The omega library interface guide. Technical report, USA, 1995.
• [8] Lim A. W., Cheong G. I., Lam M. S.: An affine partitioning algorithm to maximize parallelism and minimize communication. In ICS’99, pp. 228-237. ACM Press, 1999.
• [9] Banerjee U.: 1990. Unimodular transformations of double loops. In Proceedings of the Third Workshop on Languages and Compilers for Parallel Computing, pp. 192-219.
• [10] Feautrier P., 1994. Toward automatic distribution. Journal of Parallel Processing Letters 4, pp. 233-244.
• [11] www.openmp.org