Zwiększenie zbieżności iteracyjnego algorytmu obliczania tranzytywnego domknięcia unii sparametryzowanych relacji zależności

• Autorzy: Bielecki W. , Klimek T.
• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono udoskonalony algorytm mający na celu poprawienie zbieżności iteracyjnego obliczania tranzytywnego domknięcia sparametryzowanych relacji zależności, których ograniczenia składają się z wielu koniunkcji. Opisane podejście zostało zaimplementowane i przebadane pod kątem skuteczności na zbiorze pętli testowych NAS [13] i UTDSP [14]. Pozwala ono na rozszerzenie możliwości uzyskania dokładnego wyniku w porównaniu z algorytmami zaproponowanymi w [8], [10] i [15]. W dalszych badaniach planowane jest przetestowanie proponowanego algorytmu z innymi zbiorami pętli testowych oraz dalsze jego udoskonalanie. W ogólnym przypadku dla relacji opisującej zależności afiniczne, obliczenie tranzytywnego domknięcia złożonych, sparametryzowanych relacji zależności może być niemożliwe ze względu na nieafiniczne ograniczenia [8], co w konsekwencji utrudnia nam wyznaczenie całkowitej równoległości niewymagającej synchronizacji. Istotne zatem staje się opracowanie algorytmów umożliwiających obliczenie dokładnego tranzytywnego domknięcia dla szerszego spektrum pętli programowych i tym samym zwiększenia ich stopnia równoległości i lokalności.

EN

A novel algorithm for calculating the transitive closure of a multiple conjunct relation (union of single conjunct relations) is presented. It is based on both non-iterative and iterative techniques. Non-iterative techniques are to calculate transitive closure for particular subsets while iterative techniques are to produce final result - the transitive closure for whole space being the union of the range and the domain of an input relation. The advantage of the algorithm is its larger scope of applicability in comparison with known iterative and non-iterative techniques. The algorithm is implemented by means of the Omega Library and applied to NAS and UTDSP benchmarks. Experimental results demonstrate the algorithm effectiveness.

Słowa kluczowe

PL

relacja zależności; przechodnie zamknięcie stosunku zależności; zrównoleglenie

EN

tuple relation; transitive closure of dependence relation; parallelization

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 2 (23)
• Strony: 37--47
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Bielecki W.

autor

Klimek T.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] 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.
• [2] Feautrier P., Some efficient solutions to the affine scheduling problem, part i, one dimensional time, International Journal of Parallel Programming 21. (1992), pp. 313-348
• [3] Feautrier P., Some efficient solutions to the affine scheduling problem, part ii, multidimensional time, International Journal of Parallel Programming 21. (1992), pp. 389- 420
• [4] Pugh W., Wonnacott D. An exact method for analysis of value-based array data dependences. In Sixth Annual Workshop on Programming Languages and Compilers for Parallel Computing. Springer-Verlag, 1993.
• [5] Kelly W., Maslov V., Pugh W., Rosser E., Shpeisman T., Wonnacott D. The omega library interface guide. Technical report, USA, 1995.
• [6] Bielecki W., Klimek T., Trifunovič K., Calculating Exact Transitive Closure for a Normalized Affine Integer Tuple Relation, Electronic Notes in Discrete Mathematics 33 (2009) 7–14
• [7] Bielecki W., Klimek T., Pietrasik M., Obliczenie tranzytywnego domknięcia sparametryzowanych relacji zależności nie należących do klasy d-form, Metody Informatyki Stosowanej Nr 2/2009 (Tom 19)
• [8] Kelly W., Pugh W., Rosser E., Shpeisman T., Transitive clousure of infinite graphs and its applications, Languages and Compilers for Parallel Computing, 1995
• [9] Bielecki W., Klimek T., Pietrasik M., An experimental study on recognizing classes of dependence relations, Measurement Automation and Monitoring Nr 10/2009 vol. 55.
• [10] Beletska A., Barthou D., Bielecki W., Cohen A. Computing the Transitive Closure of a Union of Affine Integer Tuple Relations, In COCOA 2009, volume 5573 of Lecture Notes in Computer Science, pp. 98-109. Springer, 2009.
• [11] Bielecki W., Klimek T., Pałkowski M. An iterative algorithm of computing the transitive closure of a union of parameterized affine integer tuple relations. (wysłano na konferencję COCOA 2010)
• [12] http://www.wolfram.com [online] [dostęp : 2010]
• [13] http://www.nas.nasa.gov/Software/NPB/ [online] [dostęp : 2008]
• [14] http://www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html [online] [dostęp : 2008]