Obliczenie tranzytywnego domknięcia sparametryzowanych relacji zależności nie należących do klasy d-form

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

Abstrakty

PL

Przedstawiliśmy w artykule sposoby obliczenia domknięcia przechodniego sparametryzowanych relacji nie należących do klasy relacji d-form. Do takich relacji należą relacje, których ograniczenia tranzytywnego domknięcia mają nieliniowe wyrażenia oraz relacje hybrydowe czyli takie, których część odpowiadających sobie składowych krotki wejściowej i wyjściowej jest charakterystyczna dla relacji d-form [9], a pozostała pozwala na zastosowanie techniki opartej na utworzeniu i rozwiązaniu układu równań rekurencyjnych [7]. Przedstawione podejścia pozwalają na rozszerzenie możliwości obliczania tranzytywnego domknięcia relacji, a znaczy znajdowanie równoległości dla większego spektrum pętli programowych.

EN

Approaches for calculating the exact transitive closure of a single dependence relation are presented. These approaches are based on calculating firstly the power k of a relation, then transitive closure is easily formed by making k in the formula received to be existentially quantified. Supposed approaches permit for enlarging the scope of dependence relations for which it is possible to calculale exact transitive closure. This enlarges the scope of program loops for which it is possible to extract both fine- and coarse-grained paralIelism. Results of experiments with popular benchmarks are presented.

Słowa kluczowe

PL

pętle afiniczne; relacja zależności; domknięcie przechodnie; transformacje pętli; przetwarzanie równoległe

EN

affine loops; dependence; transitive closure; program transformation; parallelization

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

Twórcy

autor

Bielecki W.

autor

Klimek T.

autor

Pietrasik M.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] B. Boigelot. Symbolic Methods for Exploring Infnite State Spaces. PhD thesis, Universite de Liμege, 1998.
• [2] E. Nuutila. Efficient Transitive Closure Computation in Large Digraphs, Mathematics and Computing in Engineering Series No. 74 PhD thesis Helsinki University of Technology
• [3] P. Feautrier, Some Efficient Solutions to the Affine Scheduling Problem, Part I. One-Dimensional Time, International Journal of Parallel Programing, Vol 21(5), 1992
• [4] P. Feautrier, Some Efficient Solution to the Affine Scheduling Problem, Part II, Multi-Dimensional Time, International Journal of Parallel Programing, Vol 21(6), 1992
• [5] T. Cormen, C. E. Leiserson, R. Rivest, Introduction to Algorithms, The MIT Press, 2001
• [6] W. Bielecki, R. Drążkowski, Approach to building free schedules for loops with affine dependences represented with a single dependence relation, WSEAS Transactions on Computers, Issue 11, Volume 4, 2005
• [7] W. Bielecki, T. Klimek, K. Trifunovič, Calculating Exact Transitive Closure for a Normalized Affine Integer Tuple Relation, Electronic Notes in Discrete Mathematics 33 (2009) 7–14
• [8] W. Bielecki, T. Klimek, K. Trifunovič, Obliczenie potęgi k znormalizowanej afinicznej relacji, Metody Informatyki Stosowanej Nr 2/2008 (Tom 15)
• [9] W.Kelly, W. Pugh, E. Rosser, T. Shpeisman, Transitive clousure of infinite graphs and its applications, Languages and Compilers for Parallel Computing, 1995
• [10] W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, D. Wonnacott, The Omega library interface guide, Technical Report CS-TR-3445, Dept. of Computer Science, University of Maryland, College Park, March 1995
• [11] http://mathworld.wolfram.com/RecurrenceEquation.html [online] [Dostęp 15.04.2009]
• [12] http://www.netlib.org/benchmark/livermore [online] [Dostęp 30.03.2009]
• [13] http://www.nas.nasa.gov/Software/NPB [online] [Dostęp 03.04.2009]
• [14] http://www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html [online] [Dostęp 10.04.2009]