Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Metody Informatyki Stosowanej

2 2010

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: plastry bez synchronizacji

Sortuj według:

Ogranicz wyniki do:

Zastosowanie bibliotek Omega i ISL do ekstrakcji niezależnych fragmentów kodu w pętlach programowych

Bielecki W., Pałkowski M., Sierbin M.

Metody Informatyki Stosowanej

2010

nr 3 (23)

49-56

Prezentowane wyniki badań wskazują na zbliżoną skuteczność obu bibliotek w implementacji algorytmów ekstrakcji niezależnych fragmentów kodu. Dla badanego zestawu pętli testowych operacje tranzytywnego domknięcia unii relacji zależności oraz ekstrakcji punktów reprezentatywnych fragmentów kodu zostały policzone dla podobnych zbiorów pętli z zestawu testowego NAS. Biblioteka Omega Calculator wydaje się być projektem bardziej kompletnym, oprócz funkcji do przeprowadzania obliczeń z zakresu arytmetyki Presburgera, zawiera także analizator zależności Petit oraz funkcje generującą kod na podstawie zbioru krotek. Biblioteka ISL nie zawiera własnego analizatora zależności. Wprowadzenie do niej relacji zależności wymaga opracowania dodatkowych konwerterów. Do generowania kodu także należy wykorzystać inne narzędzia, np. Cloog [6]. Zaletami biblioteki ISL jest ciągły rozwój i częste aktualizacje oraz zgodność z najnowszymi wersjami kompilatora języka C. Wpływa to na szybkość wykonywania algorytmów (potwierdzonych w powyższych badaniach), co jest głównym plusem tego narzędzia w przeprowadzonym porównaniu. Algorytmy wyznaczania niezależnych fragmentów kodu nie narzucają zastosowania konkretnego środowiska i narzędzi, co świadczy także o ich uniwersalności. Wymagana jest dokładna reprezentacja zależności w postaci relacji oraz zdolność do przeprowadzania operacji arytmetyki Presburgera na nich. Umiejętna implementacja i dobór narzędzi stanowi o praktycznej użyteczności opracowywanych algorytmów do ekstrakcji równoległości. W przyszłych badaniach zamierzona jest dalsza weryfikacja możliwości omawianych narzędzi z wykorzystaniem innych zestawów pętli testowych.

Finding synchronization-free slices is a technique of extracting parallelism available in loops. In this paper, two implementations of slicing algorithms are compared using the two polyhedral model libraries: the Omega Calculator and the Integer Set Library (ISL). These tools allow us to execute calculations using Presburger arithmetic. Results of experiments with the NASA Parallel Benchmark Suite are presented. The goal of experiments was to examine whether these both tools are able to calculate the transitive closure of a union of dependence relations, slice representatives, and synchronization-free slices.

Wyznaczenie punktów reprezentatywnych niezależnych fragmentów kodu w grafie zależności pętli programowych

Bielecki W., Pałkowski M., Klimek T.

Metody Informatyki Stosowanej

2010

nr 1 (22)

13-20

W artykule przedstawiono nowy algorytm wyznaczania punktów reprezentatywnych cechujacy się mniejszą złożonością obliczeń w porównaniu do rozwiazania [6-7]. Powodzenie wyznaczania punktów jest zależne tylko od obliczenia dokładnego tranzytywnego domknięcia unii relacji zależności pętli. Oprócz tego należy wykonać szereg podstawowych operacji, jak: część wspólna, iloczyn skalarny, unia, aplikacja relacji na zbiorze, inwersja, projekcja. Relacja RUSC budowana jest wieloetapowo dzięki czemu można dokonywać pośrednich uproszczeń jej postaci. Opisane podejście zostało zaimplementowane i przetestowane pod kątem skuteczności na zbiorze pętli testowych NAS. W dalszych badaniach planowane jest zbadanie proponowanego algorytmu z innymi zbiorami pętli testowych oraz dalsze udoskonalanie algorytmów do wyznaczania fragmentów dla dowolnej topologii zależności pod kątem generowania wydajnego kodu równoległego.

An algorithm of finding representatives of synchronization-free slices available in program loops is presented. It based on the transitive closure of a union of dependence relations describing all the dependences in program loops. An algorithm to calculate transitive closure is studied. Both the algorithms are implemented by means of the Omega library. The results of experiments with the NAS Parallel Benchmark are discussed.