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

摘要

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 Wonnacotfa. 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ń.