Concurrent Start Tiling of Stencil Computations based on the Transitive Closure of a Data Dependence Graph

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.

---

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.