6218156482

Kompilator zrównoleglający wyspecjalizowany na algorytmy szyfrowania 19

w którym każdy procesor wykonuje ten sam program działając na własnym zestawie danych, konstrukcje podziału pracy (ang. work-sharing constructs), konstrukcje synchronizacji (ang. synchronization constructs) oraz konstrukcje środowiska danych (ang. data enuironment constructs) umożliwiają kompilatorowi wygenerowanie wielowątkowych programów wykonywalnych [9]. Zrównoleglenie kodu odbywa się w oparciu o model równoległego wykonywania programu - fork-and-join bazujący na operacjach rozwidlenia (ang. fork) oraz połączenia (ang. join). Wykonywanie programu rozpoczyna wątek pojedynczy zwany wątkiem nadrzędnym (ang. master thread), który w momencie napotkania konstrukcji równoległej tworzy grupę wątków (ang. team of threads). Każdy z wątków grupy wykonuje instrukcje znajdujące się w zasięgu dynamicznym rejonu równoległego, za wyjątkiem niektórych instrukcji podziału pracy (ang. work-sharing constructs). Po zakończeniu wykonywania rejonu równoległego następuje synchronizacja barierowa, a następnie wątek nadrzędny kontynuuje wykonywanie części sekwencyjnej programu (pozostałe wątki są niszczone), aż do momentu napotkania kolejnego rejonu równoległego (kod źródłowy może zawierać wiele rejonów równoległych, a rejony równolegle mogą być zagnieżdżone, zatem program w czasie wykonywania może być wielokrotnie poddawany operacjom rozwidlenia i połączenia). Ilość tworzonych wątków może być różna dla różnych rejonów równoległych - możliwe jest wykorzystanie mechanizmu wątków dynamicznych (ang. dynamie threads) [9].

4. Metoda automatycznego zrównoleglenia wybranych algorytmów szyfrowania

Metoda automatycznego zrównoleglenia wybranych algorytmów szyfrowania bazuje na wykorzystaniu kodu źródłowego danego algorytmu sekwencyjnego poprzez znalezienie fragmentów kodu potencjalnie równoległych, ich odpowiednie przekształcenie, a następnie zrównoleglenie. Zrównoleglenia algorytmów szyfrowania odbywa się na poziomie danych, gdyż ten poziom zrównoleglenia gwarantuje maksymalny stopień zużytkowania możliwości obliczeniowych komputerów wieloprocesorowych ze wspólną pamięcią [10]. Wymaga to odpowiednich transformacji kodu źródłowego algorytmów sekwencyjnych. Metoda automatycznego zrównoleglenia wybranych algorytmów szyfrowania obejmuje trzy etapy transformacji pętli przeznaczonych do zrównoleglenia [6|:

—    transformacje wstępne - umożliwiające przeprowadzenie analizy zależności,

—    transformacje usuwające, bądź redukujące istniejące zależności w kodzie źródłowym blokujące proces zrównleglenia- zależności odwrotne, zależności po

wyjściu, zależności proste oraz zależności sterowania,

—    transformacje umożliwiające przetwarzanie równoległe pętli.

Opracowano trzy niezależne od siebie procedury zrównoleglenia pętli programowych występujących w implementacjach algorytmów szyfrowania oparte na przedstawionej powyżej kolejności transformacji kodu źródłowego [6]:

—    Procedurę 1 - dla szyfrów blokowych pracujących trybie ECB,