Szyfr DES jest 40 razy szybszy w OpenCL

Implementacja szyfru DES w OpenCL jest znacznie szybsza niż zwykły jednowątkowy program w C. 1 mln operacji szyfrowania zajmuje mniej niż sekundę na RTX 3050 Ti, ale aż prawie 40 sekund w jednowątkowej aplikacji na Intel i5-10200h.

Brak kompaktowej i niezwykle przenośnej biblioteki SSL/TLS w projekcie sprzed C++11 skłonił mnie do poszukania czegoś łatwego do samodzielnego zaimplementowania w zakresie szyfrowania danych. Wybrałem DES, czyli Data Encryption Standard, ze względu na moje ogólne rozumienie tego algorytmu. Pochodzi on z 1975 roku i ma pewne ograniczenia, w tym krótką długość klucza czy znane słabe klucze. Jeśli jednak odłożymy uprzedzenia na bok, możemy dostrzec kilka interesujących rzeczy, a także możliwości.

Napisanie kernela C99 w OpenCL zajęło mi kilka dni. Wcześniej wypróbowałem kilka zewnętrznych przykładów w c++. Ich główną wadą jest to, że wszystkie używają strings, vectors, stringstreams i kilku innych funkcji typowych wyłącznie dla c++. Nawet użycie printf jest problematyczne w implementacjach OpenCL, ponieważ może być niedostępne albo działać różnie w zależności od implementacji. Nie będzie można też użyć niektórych funkcji c99, takich jak malloc/free. Aby więc uzyskać maksymalną kompatybilność, zszedłem do najprostszych rozwiązań.

Szczególnie podoba mi się przykład, w którym używa się danych binarnych w postaci ciągów znaków (tablic uchar). Dzięki temu łatwo zobaczyć, co się dzieje. Oczywiście (naprawdę?) zwiększa to złożoność oraz liczbę instrukcji, a także zużycie pamięci, ale jak na pierwszą implementację DES jest to akceptowalne. W różnych miejscach zobaczysz więc tablice 8-bajtowych elementów oznaczających 64 bity danych. Klucze i inne wartości jako 56 lub 48 bitów danych, a połówki jako wartości 32-bitowe (4-bajtowe liczby). Zarówno dane wejściowe, jak i wyjściowe można wyświetlić jako znaki. Wejście będzie zwykłym ASCII, ale wyjście przekracza kod ASCII 128 dziesiętnie, więc w przypadku wypisywania znaków zamiast samych liczb możesz zobaczyć dziwne symbole.

OpenCL kontra jednowątkowy C #

Aby uruchomić kod kernela poza środowiskiem uruchomieniowym OpenCL, trzeba zapewnić kilka rzeczy:

#include "stdio.h"
#include <math.h>

typedef unsigned char uchar;

Trzeba dodać bibliotekę matematyczną w wywołaniu GCC, ponieważ domyślnie nie jest dołączana:

gcc des.c -lm

Następnie główną funkcję kernela trzeba dostosować, na przykład tak:

void kernel() { 
  // here we have the kernel function body...
}

I na koniec dostarczyć funkcję main języka C z już sparametryzowanymi iteracjami:

int main() {
    int i;
	for (i=0; i<1024*1024; i++) {
		if (i % 1024 == 0) {
			printf("i: %i ", i);
		}
		kernel();
	}
}

Dla uproszczenia pomijam definicję uchar8 i jej obsługę, ponieważ nie dodaje wiele do ogólnej złożoności kodu i algorytmu. Uruchamiam na różnym sprzęcie z 1024*1024 iteracjami. Najpierw porównam czas wykonania na CPU:

Teraz porównajmy to z czasem wykonania w OpenCL:

Bazowy projekt w Javie #

Korzystam z bazowego projektu OpenCL, który można znaleźć tutaj. Jest w nim jeden dodatkowy moduł o nazwie „des”. Pierwotnie używałem Javy 17, ale dziś wybieram Javę 19. Szczerze mówiąc, nie potrafię łatwo wskazać niczego aż tak istotnego między Javą 11 a 19. Każda wersja wprowadza albo drobne zmiany w języku, albo nie wprowadza żadnych. Jeśli jednak piszesz złożone aplikacje obiektowe, te zmiany mogą być dla Ciebie interesujące.

Zatem… najpierw wypełniam tablicę danych źródłowych następującą funkcją:

    public void generateSampleRandomData() {
        Random rd = new Random();
        for (int i = 0; i <= (n*8) - 1; i++) {
            byte c = (byte)('a' + rd.nextInt(10));
            srcArrayA[i] = c;
        }
    }

Ta funkcja generuje n*8 elementów typu byte w zakresie od dziesiętnej reprezentacji litery ‘a’ w ASCII i 10 kolejnych wartości. Innymi słowy losowe znaki będą w zakresie od ‘a’ do ‘j’, czyli dziesiętnie od 97 do 106. Słowo o typie byte w języku Java – jest on zawsze ze znakiem, więc nie ma bezpośredniej możliwości użycia go jako typu bez znaku. Istnieje jednak funkcja Byte.toUnsignedInt, która zamienia ujemne wartości byte na dodatnie.

Kolejna rzecz to bufor. Jak zobaczymy później, funkcja kernela wykorzystuje typ danych uchar8, więc trzeba odwzorować taki typ w Javie. Wpadłem na pomysł użycia zwykłej tablicy bajtów (byte[]). Każde wywołanie kernela będzie mapować kolejne grupy po 8 elementów z tej płaskiej tablicy:

   public void createBuffers() {
        // Allocate the memory objects for the input- and output data
        this.memObjects[0] = clCreateBuffer(this.context, CL_MEM_READ_ONLY | CL_MEM_COPY_HOST_PTR, (long) Sizeof.cl_uchar8 * this.n, KernelConfigurationSet.srcA, null);
        this.memObjects[1] = clCreateBuffer(this.context, CL_MEM_READ_WRITE, (long) Sizeof.cl_uchar8 * this.n, null, null);
    }

Zarówno tablica źródłowa, jak i docelowa są typu cl_uchar8, który w samym kernelu odpowiada typowi uchar8. Do wypisania wyników zwracanych z wywołań kernela użyjemy wspomnianej wcześniej funkcji Byte.toUnsignedInt:

public void printResults() {
        System.out.println("Elements: " + dstArray.length);
        int i = 0;
        for (byte tmp : dstArray) {
            System.out.println(String.valueOf(i) + " : " + (Byte.toUnsignedInt(tmp)) );
            i++;
        }
}

I to w zasadzie wszystko, jeśli chodzi o część w Javie tego wyzwania. Użycie Javy to tutaj kwestia wygody, bo można to zrobić również w c lub c++. Na razie nie wiem o żadnych rozbieżnościach w bibliotece JOCL i innych dostępnych bibliotekach.

OpenCL 1.1 #

Aby uruchomić kod kernela na niektórych starszych urządzeniach, trzeba dostosować kilka rzeczy. Po pierwsze należy pozbyć się wywołań funkcji printf albo zdefiniować ją samodzielnie. Po drugie trzeba włączyć cl_khr_fp64, czyli rozszerzenie dla liczb zmiennoprzecinkowych, w przypadku używania typu double:

#pragma OPENCL EXTENSION cl_khr_fp64 : enable

Istnieją możliwości, by nie używać funkcji pow i przerobić cały algorytm szyfru na operacje wyboru bitów. Dla moich celów edukacyjnych znacznie łatwiej jest jednak widzieć, co się dzieje, właśnie w takiej formie.

Kernel C99 #

Podzieliłem algorytm szyfru DES na 27 punktów funkcjonalnych od FP00 do FP26. Niektóre z nich zawierają wyłącznie dane, a inne składają się z procedur.

Sekcja ogólna #

• FP00 – funkcje pomocnicze (linie 1-133)
• FP01 – definicja kernela
• FP02 – dane i identyfikacja
• FP03 – klucz
• FP04 – tekst jawny
• FP05 – dane tablic PC1/PC2

Generowanie kluczy #

• FP06 – permutacja klucza PC1
• FP07 – podział klucza na dwie równe połowy
• FP08 – 16 kluczy rund, dla 1, 2, 9 i 16 pojedyncze przesunięcia w lewo
• FP09 – dla pozostałych iteracji podwójne przesunięcia w lewo
• FP10 – połączenie lewej i prawej części
• FP11 – permutacja klucza PC2

Procedura szyfrowania #

• FP12 – tylko dane, dane permutacji początkowej i tablicy rozszerzenia
• FP13 – tylko dane, S-boksy: 8 boksów, każdy po 4 wiersze i 16 kolumn
• FP14 – tylko dane, tablica permutacji
• FP15 – zastosowanie permutacji początkowej
• FP16 – podział wyniku na dwie równe połowy
• FP17 – szyfrowanie 16 razy, prawa połowa jest rozszerzana
• FP18 – XOR wyniku z kluczem
• FP19 – 8-krotne zastosowanie S-boksów
• FP20 – zastosowanie permutacji
• FP21 – XOR wyniku z lewą połową
• FP22 – zamiana lewej i prawej części tekstu jawnego
• FP23 – połączenie lewej i prawej części
• FP24 – zastosowanie permutacji odwrotnej
• FP25 – przygotowanie wyniku końcowego
• FP26 – zapis wyniku do wyjściowego bufora OpenCL

Podsumowanie #

W tym wyzwaniu… którego kod źródłowy można znaleźć tutaj, sprawdziłem możliwość zaimplementowania algorytmu szyfru DES na urządzeniach obsługujących OpenCL. Te 500 linii kodu można uruchomić albo na urządzeniu OpenCL, albo w nieco zmodyfikowanej formie na dowolnym innym urządzeniu, które potrafi skompilować język C. Implementacja OpenCL działa na GPU 40 razy szybciej niż na jednowątkowym CPU. To było całkiem interesujące…