Wydział Informatyki

Stały URI zbioru

https://oa.zut.edu.pl/handle/20.500.12539/8

Przeglądaj

Przeglądaj Wydział Informatyki wg Temat "algorytmy NPDP"

Teraz wyświetlane 1 - 1 z 1
  • Miniatura
    PozycjaOpen Access
    Zastosowanie nowych technik w kompilatorach opartych na modelu wielościennym do generowania wydajnego i wieloplatformowego kodu dla procesów wielordzeniowych
    (2025) Grużewski, Mateusz Dominik; Pałkowski, Marek (promotor); Błaszczyński, Piotr (promotor); Zachodniopomorski Uniwersytet Technologiczny. Wydział Informatyki
    Celem rozprawy było opracowanie i ewaluacja metod automatycznej oraz półautomatycznej optymalizacji kodu oraz zastosowanie ich dla algorytmów dynamicznego programowania klasy NPDP (ang. non-serial polyadic dynamic programming). Schematy obliczeniowe NPDP są często wykorzystywane w zadaniach bioinformatycznych, w których zagnieżdżone pętle programowe tworzą niejednorodne, wieloindeksowe zależności danych. Optymalizacja tych procesów, zarówno ręczna, jak i poprzez kompilatory, mająca na celu zrównoleglenie oraz poprawę lokalności kodu, była przedmiotem badań od początku lat 90. i nadal stanowi istotne wyzwanie. Teza niniejszej rozprawy zakłada, że integracja technik automatycznych i półautomatycznych, rozwijanych w ramach kompilatorów opartych na modelu wielościennym, przekształcających pętle programowe (ze szczególnym uwzględnieniem transformacji blokowania), z metodami przetwarzania wstępnego i końcowego oraz z modelami sztucznej inteligencji, umożliwia generowanie kodu wieloplatformowego, który charakteryzuje się wysoką wydajnością w porównaniu z rozwiązaniami znanymi w literaturze, a jednocześnie zachowuje przenośność na zróżnicowanych architekturach obliczeniowych. W rozprawie przeanalizowano szerokie spektrum podejść pokrewnych, opracowanych głównie dla kodów NPDP, na przykładzie algorytmu predykcji RNA Nussinovej. Jest to znany w literaturze przykład bazowy, dla którego stosowane obecnie metody — w tym najpowszechniej wykorzystywane w kompilatorach przekształcenia afiniczne — zawodzą w ekstrakcji dostępnej równoległości i lokalności. W pracy dokonano przeglądu literatury oraz istniejących narzędzi optymalizacyjnych, ze szczególnym uwzględnieniem ich mocnych i słabych stron w kontekście transformacji zagnieżdżonych pętli programowych. Dalej poszerzono optymalizację kodu o techniki przetwarzania wstępnego i końcowego, których celem było poprawienie lokalności pamięci i ułatwienie dalszych transformacji, oraz zastosowano dedykowane modele językowe wspierające wygenerowanie kodu GPU. Równolegle rozwinięto metody półautomatyczne, w których automatyczne transformacje zostały uzupełnione o wiedzę dziedzinową i ręczne strojenie kodu. Przeprowadzone badania wykazały, że proponowane rozwiązania stanowią solidną podstawę procesu transformacji i umożliwiają uzyskanie poprawnych oraz przenośnych implementacji. W przypadku złożonych algorytmów NPDP dopiero ich rozszerzenie o komponent półautomatyczny pozwoliło osiągnąć zadowalającą wydajność i skalowalność na procesorach CPU i GPU przy wykorzystaniu modelu wielościennego. Eksperymenty zostały przeprowadzone na zróżnicowanym zestawie architektur, obejmujących procesory serwerowe x86-64 (AMD EPYC, Intel Xeon, Ryzen Threadripper), układy GPU programowane w CUDA i OpenCL (NVIDIA Tesla i RTX, układy Intela) oraz procesory RISC. Analizy obejmowały zarówno przyspieszenie, skalowalność, wektoryzację i lokalność kodu, jak i zużycie energii, co umożliwiło kompleksową ocenę efektywności badanych metod. Wyniki wskazały, że zaproponowane rozwiązania oparte na modelu wielościennym oraz modele językowe umożliwiają nie tylko szybkie i poprawne generowanie kodu, lecz także otwierają dyskusję na temat przyszłości automatycznych kompilatorów optymalizujących oraz ich rozwoju w kontekście eksperckich metod półautomatycznych i zastosowań sztucznej inteligencji.