Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Identyfikatory
Warianty tytułu
Wyznaczenie harmonogramu instancji instrukcji dla pętli dowolnie zagnieżdżonych
Języki publikacji
Abstrakty
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.
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ń.
Wydawca
Czasopismo
Rocznik
Tom
Strony
1186--1189
Opis fizyczny
Bibliogr. 12 poz., rys., tab., wzor
Twórcy
autor
autor
autor
- West pomeranian University of Technology, Department of Computer Science and Information Technology, ul. Żołnierska 49, 71-210 Szczecin, wbielecki@wi.zut.edu.pl
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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSW4-0086-0019