An approach to form affine time partitioning for statement instances of arbitrarily nested loops

• Autorzy: Bielecki W. , Siedlecki K. , Wernikowski S.

Warianty tytułu

PL

Wyznaczenie harmonogramu instancji instrukcji dla pętli dowolnie zagnieżdżonych

• Języki publikacji: EN

Abstrakty

EN

A novel approach to form affine time partitioning for statement instances of arbitrary nested loops is presented. It is based on extracting free-scheduling which next is used to form a system of equations to produce legal time partitioning. The approach requires an exact dependence analysis. To carry out experiments, the dependence analysis by Pugh and Wonnacott was chosen. Examples illustrating the approach and the results of experiments are presented.

PL

Przedstawiona została nowa metoda do tworzenia afinicznych odwzorowań czasowych instancji instrukcji dla pętli dowolnie zagnieżdżonych. Metoda bazuje na ekstrakcji harmonogramu swobodnego, wykorzystywanego do tworzenia legalnego odwzorowania czasowego. Metoda wymaga dokładnej analizy zależności. Do przeprowadzenia eksperymentów, wybrana została analiza zależności zaproponowana przez Pugh'a and Wonnacott'a. W analizie tej zależności reprezentowane są przez relacje zależności, natomiast przestrzeń iteracji przez zbiory. Do tworzenie zbiorów i relacji zależności wykorzystywana jest arytmetyka Presburgera. Zostały przedstawione przykłady ilustrujące działanie metody dla pętli idealnie zagnieżdżonej, jak i dla pętli nieidealnie zagnieżdżonej. Eksperymenty przeprowadzone zostały na procesorach graficznych firmy nVidia z wykorzystaniem technologii CUDA w trybie zgodności z wersją 1.1. Wyniki zostały przedstawione w formie tabelarycznej. Zostały przedstawione prace pokrewne oraz kierunek dalszych badań.

Słowa kluczowe

EN

loop parallelization; free schedule; affine time partitioning

PL

zrównoleglenie pętli; harmonogram swobodny; afiniczne odwzorowanie czasowe

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 10
• Strony: 1186--1189
• Opis fizyczny: Bibliogr. 12 poz., rys., tab., wzor

Twórcy

autor

Bielecki W.

autor

Siedlecki K.

autor

Wernikowski S.

• West pomeranian University of Technology, Department of Computer Science and Information Technology, ul. Żołnierska 49, 71-210 Szczecin,

Bibliografia

• [1] Bielecki W., Siedlecki K.: Finding free schedules for non-uniform loops. Euro-Par 2003, 26-29.08, Klagenfurt, Austria, LNCS, vol. 2790, pp. 297-302.
• [2] Vivien F.: On the optimality of Feautrier's scheduling algorithm. In Proceedings of the EUROPAR’2002, 2002.
• [3] Pugh W., Wonnacott D.: An Exact Method for Analysis of Value-based Array Data Dependences. Workshop on Languages and Compilers for Parallel Computing, 1993.
• [4] Darte A., Robert Y., Vivien F.: Scheduling and Automatic Parallelization. Birkhäuser Boston, 2000.
• [5] The Omega project. http://www.cs.umd.edu/projects/omega
• [6] Pugh W., Wonnacott D.: An Exact Method for Analysis of Value-based Array Data Dependences. Workshop on Languages and Compilers for Parallel Computing, 1993.
• [7] Darte A., Robert Y., Vivien F.: Scheduling and Automatic Parallelization, Birkhaser, 2000.
• [8] Lim A. W., Cheong G. I., Lam M. S.: An affine partitioning algorithm to maximize parallelism and minimize communication. In: Proc. of the 13th ACM SIGARCH Int. Conf. on Supercomputing. ACM Press, 1999, pp. 228-237.
• [9] www.wolfram.com/mathematica.
• [10] Alfred V. Aho, Lam M. S., Sethi R., Ullman J D.: Compilers: Principles, Techniques, and Tools. Addison Wesley, 2006.
• [11] Bondhugula U., Hartono A., Ramanujam J., Sadayappan P.: A practical automatic polyhedral parallelizer and locality optimizer. In Conf. on Programming Language Design and Implementation, pp. 101–113, ACM, 2008.
• [12] www.nvidia.com