Prywatyzacja zmiennych skalarnych dla wyznaczania równoległości w pętlach programowych

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

Warianty tytułu

EN

Automatic privatization of scalar variables for coarse-grained parallelism extraction

• Języki publikacji: PL

Abstrakty

PL

Wynikiem automatycznego zrównoleglenia pętli programowych jest kod tożsamy z sekwencyjnym odpowiednikiem, który honoruje wszystkie zależności. Zastosowanie prywatyzacji określonych zmiennych programu pozwala na wyeliminowanie zależności danych, co zmniejsza złożoność obliczeniową wyznaczania równoległości w pętlach programowych a także pozwala zwiększyć stopień wyznaczanej równoległości. W artykule zaprezentowano zastosowanie technikę prywatyzacji zmiennych operującej na zależnościach zapisanych w postaci relacji. Zbadano stosowalność proponowanego rozwiązania na pętlach programowych z benchmarku NAS.

EN

Extracting synchronization-free slices allows us to automatically generate parallel loops. The code can be executed on multi-processors machines in a reduced period of time. Privatization of data is an important technique used by compilers to parallelize loops by eliminating storage-related dependences. A scalar variable defined within a loop is said to be privatizable with respect to that loop if and only if every path from the beginning of the loop body to a use of X within that body must pass through a definition of X before reaching that use. In this paper there is presented an approach to automatic privatization of variables involved in data dependences that permits for extracting loop parallelism. The algorithm input is a set of relation dependences, the output is a parallel loop when appropriate. The scope of the approach applicability is illustrated by means of the NAS Parallel Benchmark suite. The obtained results are compared with another automatic parallelizer and locality optimizer for multicores - Pluto. The future work is considered.

Słowa kluczowe

PL

prywatyzacja; równoległość gruboziarnista; zrównoleglanie pętli programowych

EN

privatization; coarse-grained parallelism; parallelizing loops

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 2
• Strony: 180--183
• Opis fizyczny: Bibliogr. 14 poz., tab., wzory

Twórcy

autor

Pałkowski M.

autor

Bielecki W.

• Katedra Inżynierii Oprogramowania, Wydział Informatyki, Zachodniopomorski Uniwersytet Technologiczny, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Allen R., Kennedy K.: Optimizing compilers for modern architectures: A Dependence based Approach, Morgan Kaufmann Publish., Inc, 2001.
• [2] Kelly W., Pugh W., Maslov V., Rosser E., Shpeisman T., Wonnacott D.: New User Interface for Petit and Other Extensions. User Guide, 1996.
• [3] Moldovan D.: Parallel Processing: From Applications to Systems, Morgan Kaufmann Publishers, Inc., 1993.
• [4] Pugh W., Wonnacott D.: 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.
• [5] Beletska A., Bielecki W., Cohen A., Palkowski M., Siedlecki K.: Coarse-grained loop parallelization: Iteration space slicing vs affine transformations. Parallel Computing, 37, s. 479-497, 2011.
• [6] Pugh W., Rosser E.: Iteration Space Slicing and Its Application to Communication Optimization. Proceedings of the International Conference on Supercomputing. s. 221-228, 1997.
• [7] Bielecki W., Beletska A., Palkowski M., San Pietro P.: Extracting synchronization-free trees composed of non-uniform loop operations, Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science Volume 5022/2008, Springer Berlin / Heidelberg, s. 185-195, 2008.
• [8] 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, s. 145-153, 2008.
• [9] NAS Parallel Benchmarks v.3.2, 2010. http://www.nas.nasa.gov/Resources/Software/npb.html
• [10] PLUTO - An automatic parallelizer and locality optimizer for multicores, http://pluto-compiler.sourceforge.net/, 2011.
• [11] Lim A. W., Lam M., Cheong G.: An affine partitioning algorithm to maximize parallelism and minimize communication. In ICS’99, s. 228-237, ACM Press, 1999.
• [12] Feautrier P.: Some efficient solutions to the affine scheduling problem, part I, II, one dimensional time, International Journal of Parallel Programming 21, s. 313-348, 389-420, 1992.
• [13] Gupta M.: On Privatization of Variables for Data-Parallel Execution, In Proceedings of the 11th International Parallel Processing Symposium, 1997.
• [14] Padua D., Peng T.: Automatic Array Privatization, Proc. 6th Workshop on languages and compilers for Parallel Computing, 1993.