Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Metody Informatyki Stosowanej

1 2010

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: przechodnie zamknięcie stosunku zależności

Sortuj według:

Ogranicz wyniki do:

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

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.

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.