Extracting representative loop statement instances of synchronization-free slices

• Autorzy: Bielecki W. , Palkowski M. , Beletska A.

Warianty tytułu

PL

Ekstrakcja instancji instrukcji fragmentów kodu pozbawionych synchronizacji w pętlach programowych

• Języki publikacji: EN

Abstrakty

EN

Extracting synchronization-free parallelism by means of the Iteration Space Slicing Framework consists of two steps. First, representative loop statement instances of slices are extracted. Next, slices are reconstructed from their representatives and parallel code scanning slices and elements of each slice is generated. In this paper, we present how to benefit from this technique in practice. We explain how to extract representative loop statement instances of slices by means of the Omega Library enlarged by four new functions allowing us to simplify the process of extracting slice representatives. Results of experiments with the NAS and UTDSP benchmarks are presented.

PL

Rozwój architektur wielordzeniowych wymusza poszukiwanie algorytmów automatycznego zrównoleglenia aplikacji. W artykule opisano zrównoleglenie pętli programowych za pomocą ekstrakcji niezależnych fragmentów kodu. Ekstrakcja równoległości w pętlach programowych pozbawionych synchronizacji za pomocą podziału przestrzeni iteracji składa się z dwóch kroków. Najpierw znajdowane są instancje instrukcji będące początkami fragmentów kodu. Następnie fragmenty kodu uzupełniane są o wszystkie instrukcje i generowany jest kod równoległy. W artykule przedstawiono korzyści wynikające z takiego podejścia. Wyjaśniono sposób poszukiwania instancji instrukcji fragmentów kodu za pomocą biblioteki Omega rozszerzonej o nowe funkcje upraszczające poszukiwanie instrukcji należących do fragmentów kodu. Opis proponowanego podejścia uzupełniono o zbiór eksperymentów na pętlach testowych NAS i UTDSP.

Słowa kluczowe

EN

synchronization-free slices; parallelism; representative loop statement instances

PL

fragmenty kodu pozbawione synchronizacji; równoległość; instancje instrukcji pętli programowych

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 10
• Strony: 807--810
• Opis fizyczny: Bibliogr. 12 poz., rys., tab., wzory

Twórcy

autor

Bielecki W.

autor

Palkowski M.

autor

Beletska A.

• Department of Computer Science and Information technology, West Pomeranian University of Technology,

Bibliografia

• [1] Bastoul C.: Code generation in the polyhedral model is easier than you think. In PACT’2004, pp. 7-16, Juan-les-Pins, September 2004.
• [2] 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.
• [3] Bielecki W., Beletska A., Palkowski M., and San Pietro P.: Extracting synchronization-free chains of dependent iterations in non-uniform loops. In ACS’07: Proceedings of International Conference on Advanced Computer Systems, 2007.
• [4] Bielecki W., Beletska A., Palkowski M., and San Pietro P.: Finding synchronization-free parallelism represented with trees of dependent operations. In ICA3PP, volume 5022 of LNCS, pp. 185-195. Springer, 2008.
• [5] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., and Wonnacott D.: The omega library interface guide. Technical report, USA, 1995.
• [6] 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.
• [7] Pugh W. and Rosser E.: Iteration space slicing and its application to communication optimization. In International Conference on Super-computing, pp. 221-228, 1997.
• [8] Pugh W. and 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.
• [9] Vasilache N., Bastoul C., Cohen A..: Polyhedral code generation in the real world. In ETAPS CC’06), LNCS 3923, pp 185-201, Vienna, Austria, March 2006. Springer-Verlag.
• [10] NAS benchmark suite. http://www.nas.nasa.gov.
• [11] The Omega project. http://www.cs.umd.edu/projects/omega.
• [12] UTDSP benchmark suite. http://eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html.