PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 6

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  transitive closure
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs
Bielecki W., Pałkowski M.
International Journal of Applied Mathematics and Computer Science
|
2016
|
Vol. 26, no. 4
919--939
EN
A novel approach to generation of tiled code for arbitrarily nested loops is presented. It is derived via a combination of the polyhedral and iteration space slicing frameworks. Instead of program transformations represented by a set of affine functions, one for each statement, it uses the transitive closure of a loop nest dependence graph to carry out corrections of original rectangular tiles so that all dependences of the original loop nest are preserved under the lexicographic order of target tiles. Parallel tiled code can be generated on the basis of valid serial tiled code by means of applying affine transformations or transitive closure using on input an inter-tile dependence graph whose vertices are represented by target tiles while edges connect dependent target tiles. We demonstrate how a relation describing such a graph can be formed. The main merit of the presented approach in comparison with the well-known ones is that it does not require full permutability of loops to generate both serial and parallel tiled codes; this increases the scope of loop nests to be tiled.
2
Content available remote Concurrent Start Tiling of Stencil Computations based on the Transitive Closure of a Data Dependence Graph
Bielecki W., Skotnicki P.
Przegląd Elektrotechniczny
|
2015
|
R. 91, nr 11
167-170
EN
Stencil computations stand at the core of a wide range of scientific and engineering solutions. Load-balanced execution of stencil kernels, allowing for full utilization of processing units from the very beginning, is therefore the subject of a considerable amount of research. This paper presents a novel approach to generating parallel tiled code of stencil loops, based on the application of the transitive closure of a data dependence graph and a combination of the polyhedral model and the iteration space slicing framework.
PL
Iteracyjne obliczenia, będące funkcja wartości punktów pewnej przestrzeni w czasie, stanowią podstawe˛ szerokiego zakresu rozwiązań naukowych i inżynieryjnych. Efektywne wykonanie realizujących je pętli programowych, poprzez pełne i zrównowaz˙one wykorzystanie dostępnych jednostek obliczeniowych od samego początku, jest przedmiotem znacznej liczby badań. Artykuł prezentuje nowe podejście do blokowania omawianych pętli, bazujące na zastosowaniu domknięcia przechodniego grafu zależności danych oraz technice podziału przestrzeni iteracji.
3
Content available Wpływ redukcji zależności na możliwość obliczenia tranzytywnego domknięcia grafu zależności
Siedlecki K., Pałkowski M.
Pomiary Automatyka Kontrola
|
2012
|
R. 58, nr 2
188-192
PL
W artykule zaprezentowano wpływ redukcji zależności na możliwość obliczenia tranzytywnego domknięcia grafu zależności. Redukcje zależności wykonano przy pomocy znanych technik (redukcja zmiennych skalarnych i indukcyjnych, przekoszenie pętli, podział i łączenie pętli, rozszerzenie zmiennych skalarnych). Przedstawiono problemy związane z obliczeniem tranzytywnego domknięcia grafu zależności. Dla zbioru pętli testowych z benchmarku NAS przedstawiono wyniki statystyczne z przeprowadzonych badań. Dla wybranej pętli zaprezentowano wykorzystanie metod redukcji zależności, ich wpływ na liczbę relacji zależności oraz na możliwość obliczenia tranzytywnego domknięcia grafu zależności.
EN
The paper presents the impact of reducing dependence on possibility of calculating the transitive closure. The reductions were made according to the well known techniques (scalar reduction, induction variable elimination, loop skewing, loop splitting, loop fissioning, scalar expansion). The publication presents the background associated with data dependencies. In addition, reduction techniques (with simple examples) used in the experiments are presented. The problems associated with the transitive closure calculation are discussed. There are given the statistic results of experimental studies on a set of benchmark loop. For a chosen loop from NAS Parallel Benchmark the effectiveness of each reduction technique is shown. The impact of reduction on the transitive closure calculation is described for a selected example, where the impact of each reduction technique on the number or dependency relations is presented in detail. In the last section the experimental observations are summarized and the importance of reducing dependence is explained.
4
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
PL
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.
EN
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.
5
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.
6
Obliczenie potęgi k znormalizowanej afinicznej relacji
Bielecki W., Klimek T., Trifunovic K.
Metody Informatyki Stosowanej
|
2008
|
nr 2 (Tom 15)
5-20
PL
W artykule rozważane są idealnie zagnieżdżone pętle afiniczne, w których dolne oraz górne granice pętli, a także odwołania do tablic oraz instrukcji warunkowych są określane przy pomocy funkcji afinicznych, których argumentami są indeksy otaczających pętli oraz opcjonalnie parametry stukturalne.
EN
An approach to calculate the power k of an affine normalized relation is presented. A way to normalize an arbitrary affine relation is discussed. The approach is illustrated by an example. It is clarified how to calculate the positive transitive closure and transitive closure of a relation on the basis of the power k of the relation. Results of experiments are discussed. It is demonstrated how the calculated power k of a relation can be used for extracting both coarse- and fine-grained parallelism available in program loops. Feature, research is outlined.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.