Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 2009

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pętle afiniczne

Sortuj według:

Ogranicz wyniki do:

An experimental study on recognizing classes of dependence relations

Bielecki W., Klimek T., Pietrasik M.

Pomiary Automatyka Kontrola

2009

R. 55, nr 10

799-802

A classification of dependence relations representing exact dependences in program loops is presented. The class of a relation causes the choice of techniques for program loop parallelization. Techniques to recognize the class of a relation are presented. The implementation of these techniques by means of the Omega library is discussed. Results of an experimental study aimed at recognizing classes of dependence relations extracted for popular benchmarks (Livermore Loops, NAS, and UTDSP) are outlined.

W artykule dokonano podziału relacji zależności występujących w pętlach programowych. Na podstawie przeprowadzonych obserwacji wyodrębniono sześć podstawowych klas takich relacji. Trafne rozpoznanie danej klasy relacji opisującej zależności, determinuje dobór odpowiedniej techniki transformacji pętli programowej i tym samym pozwala na uzyskanie znacznie większego jej stopnia równoległości w porównaniu z metodami bazującymi na rozwiązaniach przybliżonych. Rozwiązania takie, zawierają zdecydowanie większą liczbę zależności, aniżeli ich faktyczna liczba wystąpień. W celu ułatwienia procesu identyfikacji poszczególnych klas relacji zależności, przedstawiono szereg formalnych metod ich rozpoznania wykorzystujących szeroki wachlarz mechanizmów zawartych w bibliotece Omega. Na potrzeby przeprowadzonych badań zaimplementowano narzędzie, w ramach którego przeanalizowano zestawy pętli trzech popularnych benchmarków : Livermoore, NAS i UTDSP. Uzyskane wyniki pozwoliły wyciągnąć wnioski odnośnie procentowego udziału relacji zależności w zaproponowanych przez autorów klasach.

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

Bielecki W., Klimek T., Pietrasik M.

Metody Informatyki Stosowanej

2009

nr 2 (19)

5-15

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.

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.