Wyniki wyszukiwania - BazTech

1

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

Bielecki W., Klimek T.

Metody Informatyki Stosowanej

|

2010

|

nr 2 (23)

37-47

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.

2

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

EN

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.

PL

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.

3

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

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.

4

Rozszerzenie biblioteki Omega Calculator do celów zrównoleglania pętli programowych

Pałkowski M.

Metody Informatyki Stosowanej

|

2007

|

nr 2(Tom 12)

103-112

PL

W niniejszym artykule przedstawiono zestaw funkcji poszerzających możliwości generowania relacji w pakiecie Omega Calculator. Funkcje umożliwiają dowolne kopiowanie ograniczeń z podmianą zmiennych w zbiorach i relacjach oraz dodawanie specjalnych ograniczeń np. porządku leksykograficznego.

EN

The extended mathematical representation of dependence relations and sets, used in algorithms for automatic parallelization, is presented. The article describes functions and implementation details of computing relations with examples. The project uses of the Omega Calculator library in Pressburger arithmetic operations on relations and sets. The extended library allows easy constructing sets and relations with additional mathematical constraints.