Blokowanie pętli programowych bazujące na zastosowaniu domknięcia przechodniego grafu zależności danych
Ładowanie...
Data
2025
Tytuł czasopisma
ISSN czasopisma
Tytuł tomu
Wydawca
Abstrakt
The objective of this doctoral dissertation is to develop and present new techniques for the automatic optimization of affine loop nests using a tiling transformation — a reorgani zation of loop nest representation at the source code level that alters the execution order of iterations to improve the utilization of available hardware resources by increasing the locality of computations and extracting parallelism. The conducted research continues the line of studies on the application of the transitive closure of a parameterized graph as a tool extending the analysis of a loop nest structure and data dependences within the polyhedral model. Both general-purpose methods and techniques dedicated to specific classes of computations are presented. Each of the proposed algorithms has been formalized and validated through a self-developed implementation of the solutions. The results obtained from experiments are compared against the performance of state-of-the-art techniques.
Celem niniejszej rozprawy doktorskiej jest opracowanie i przedstawienie nowych metod automatycznej optymalizacji gniazd afinicznych pętli programowych poprzez transformację blokowania — przekształcenia zapisu pętli na poziomie kodu źródłowego, wpływającego na zmianę kolejności wykonywania jej iteracji, do postaci odpowiedniej dla efektywnego wykorzystania dostępnych zasobów warstwy sprzętowej, poprzez zwiększenie stopnia lokalności obliczeń oraz ekstrakcję równoległości. Zrealizowane prace stanowią kontynuację badań nad zastosowaniem domknięcia przechodniego sparametryzowanego grafu w roli narzędzia rozszerzającego analizę struktury gniazda pętli i zależności danych w modelu wielościennym. Przedstawiono metody ogólnego przeznaczenia oraz techniki dedykowane specyficznym klasom obliczeń. Każdy z proponowanych algorytmów został sformalizowany oraz zweryfikowany w postaci autorskiej implementacji omawianych rozwiązań. Uzyskane w drodze eksperymentów rezultaty zestawione są z wynikami technik współczesnego stanu wiedzy.
Celem niniejszej rozprawy doktorskiej jest opracowanie i przedstawienie nowych metod automatycznej optymalizacji gniazd afinicznych pętli programowych poprzez transformację blokowania — przekształcenia zapisu pętli na poziomie kodu źródłowego, wpływającego na zmianę kolejności wykonywania jej iteracji, do postaci odpowiedniej dla efektywnego wykorzystania dostępnych zasobów warstwy sprzętowej, poprzez zwiększenie stopnia lokalności obliczeń oraz ekstrakcję równoległości. Zrealizowane prace stanowią kontynuację badań nad zastosowaniem domknięcia przechodniego sparametryzowanego grafu w roli narzędzia rozszerzającego analizę struktury gniazda pętli i zależności danych w modelu wielościennym. Przedstawiono metody ogólnego przeznaczenia oraz techniki dedykowane specyficznym klasom obliczeń. Każdy z proponowanych algorytmów został sformalizowany oraz zweryfikowany w postaci autorskiej implementacji omawianych rozwiązań. Uzyskane w drodze eksperymentów rezultaty zestawione są z wynikami technik współczesnego stanu wiedzy.
Opis
Słowa kluczowe
programowanie dynamiczne, przetwarzanie równoległe (informatyka), kompilacja (informatyka), algorytmy równoległe, pętla programowa, kompilator optymalizujący
Cytowanie
Skotnicki, P. (2025. Blokowanie pętli programowych bazujące na zastosowaniu domknięcia przechodniego grafu zależności danych. Szczecin, 144 k. (niepublikowana praca doktorska)
https://hdl.handle.net/20.500.12539/4215