bakalářská práce

Efektivní hashovací algoritmy pro vysokorychlostní FPGA aplikace

Text práce 5.33 MB

Autor práce: Bc. Ondřej Schwarz

Ak. rok: 2025/2026

Vedoucí: Ing. Jiří Matoušek, Ph.D.

Oponent: Ing. Marcela Zachariášová, Ph.D.

Abstrakt:

Hashovací funkce představují klíčovou součást moderní vysokorychlostní síťové infrastruktury. V aplikacích pro FPGA jsou využívány primárně k implementaci hardwarových vyhledávacích tabulek; pro efektivní vyhledávání je přitom nezbytné využít algoritmy s vysokou kvalitou výstupu. V rámci této práce byly v jazyce VHDL implementovány čtyři moderní hashovací algoritmy: nekryptografický SpookyHash, kryptografické algoritmy SipHash a Chaskey a experimentální funkce PCASD včetně jejich variant. Implementace těchto algoritmů byly následně porovnány z hlediska odolnosti proti kolizím, propustnosti, latence a spotřeby logických zdrojů. Výsledky ukazují, že SpookyHash exceluje ve všech sledovaných metrikách, a představuje tak optimální volbu pro systémy, kde nehrozí cílený útok. Z kryptografických algoritmů disponuje nejvyšší propustností a nejnižší spotřebou hardwarových zdrojů algoritmus Chaskey, v oblasti počáteční latence jej však předčil SipHash. U modifikované implementace algoritmu PCASD a odvozeného algoritmu PCARX byla prokázána schopnost funkcí založených na paralelních hashovacích stromech a celulárních automatech konkurovat kvalitou výstupu zavedeným sekvenčním protějškům. Byla předvedena jak jejich výhoda v podobě nízké počáteční latence, tak i vyšší nároky na spotřebu logických zdrojů.

Klíčová slova:

hashovací funkce, FPGA, kryptografie.

Termín obhajoby

18.06.2026

Výsledek obhajoby

obhájeno (práce byla úspěšně obhájena)

znamkaAznamka

Klasifikace

A

Průběh obhajoby

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.

Otázky k obhajobě

  1. V akom prostredí boli spustené testy z kapitoly 7? V simulácii a zároveň v reálnom HW?
  2. Jeden z algoritmov je experimentálne nasadený v reálnej prevádzke. Prečo práve SpookyHash a na základe akých kritérii prebiehal výber?

Jazyk práce

čeština

Fakulta

Ústav

Studijní program

Informační technologie (BIT)

Složení komise

prof. Ing. Lukáš Sekanina, Ph.D. (předseda)
doc. Ing. Ondřej Lengál, Ph.D. (místopředseda)
Ing. Marta Jaroš, Ph.D. (člen)
Ing. Libor Polčák, Ph.D. (člen)
Ing. Tomáš Milet, Ph.D. (člen)

Posudek vedoucího
Ing. Jiří Matoušek, Ph.D.

Celkový přístup studenta k řešení bakalářské práce byl příkladný. Ačkoliv se nepodařilo stihnout zkonzultovat všechny části technické zprávy, výstupy bakalářské práce jsou svým rozsahem i kvalitou nadprůměrné a výrazně překonávající původní záměr zadání. Navrhuji proto hodnocení stupněm výborně / A.

Kritérium hodnocení Slovní hodnocení
Informace k zadání

Zadání bakalářské práce vychází z praktických potřeb OP TAK projektu SmartNIC4DC (Vysoce výkonný a flexibilní SmartNIC pro aplikace a služby v datových centrech), řešeného ve spolupráci společnosti DynaNIC Semiconductors a sdružení CESNET, a cílí na vytvoření FPGA implementací hashovacích funkcí pro potřeby modulu CTT (Connection Tracking Table) vyvíjeného Oliverem Gurkou v rámci bakalářské práce Efektivní implementace tabulky síťových toků v externí paměti (obhájena 2024) a diplomové práce Stavové zpracování síťových toků s využitím FPGA pro sítě s propustností 400 Gb/s (odevzdána v květnu 2026).

Zadání bakalářské práce považuji v základu za standardně náročné. Nadstandardní však byl požadavek na implementaci a srovnání minimálně čtyř hashovacích algoritmů. Tento požadavek student beze zbytku splnil. Nad rámec původního záměru zadání pak student:

  • rozšířil hashovací algoritmus PCASD na algoritmus PCARX tak, aby byl reálně implementovatelný na dostupných FPGA čipech, a
  • doplnil množinu dostupných implementací zvolených hashovacích algoritmů tak, aby bylo možné s algoritmy pracovat nejen v FPGA (implementace ve VHDL), ale i v softwarových nástrojích (implementace v C++) a verifikačních nástrojích (implementace v Python a v SystemVerilog).

S dosaženými výsledky jsem tedy nadmíru spokojen.

Práce s literaturou

Student zvládal práci s literaturou zcela samostatně a po představení základních studijních materiálů Oliverem Gurkou byl schopný dohledávat a zpracovávat další relevantní studijní materiály bez další pomoci.

Aktivita během řešení, konzultace, komunikace

Po celou dobu řešení bakalářské práce byl student nadprůměrně aktivní a iniciativně řešil výzvy, které se v průběhu práce na zadaném tématu objevily. Svůj postup přitom student průběžně konzultoval, a to nejen na osobních setkáních, ale i s vyžitím prostředků elektronické komunikace.

Aktivita při dokončování

Implementační a experimentální práce byly dokončeny v dostatečném předstihu. Dokončování technické zprávy se však protáhlo až do posledních dnů před termínem odevzdání bakalářské práce, a některé části technické zprávy tudíž nebyly dopodrobna konzultovány. Důvodem uvedeného zpoždění však nebyla nedostatečná aktivita studenta při dokončování technické zprávy, ale její rozsah, který se student snažil naplnit.

Publikační činnost, ocenění

Implementované hashovací algoritmy byly zveřejněny v open-source repozitáři NDK platformy pro síťové karty s FPGA čipem (viz https://github.com/CESNET/ndk-fpga), který spravuje sdružení CESNET. Na studentské konferenci Excel@FIT 2026 pak byl prezentován poster o tématu bakalářské práce a dosažených výsledcích.

Výsledný počet bodů navržený vedoucím: 100

Známka navržená vedoucím: A

Jednalo sa o náročnejšie zadanie, realizačný výstup je kompletný, vhodne testovaný, pripravený na praktické využitie. 

Kritérium hodnocení Slovní hodnocení Body Max. body
Náročnost zadání

Stupeň hodnocení: obtížnější zadání

Hodnotím zadanie tejto práce ako náročnejšie, pretože vyžaduje prácu s komplexnými technológiami - štúdium state-of-the-art hashovacích algoritmov, ich implementáciu v FPGA, analýzu vlastností a efektívnosti implementácie z pohľadu zdrojov, výkonu. 
Oceňujem snahu o verifikáciu jednotlivých implementácii a tiež úpravu jedného z algoritmov, ktorá viedla k efektívnejšiemu riešeniu. Považujem obe za zmysluplné rozšírenia práce.

Prezentační úroveň technické zprávy

Práca má logickú štruktúru a jednotlivé časti na seba nadväzujú. Na teoretické základy plynule nadväzuje návrhová, implementačná, a testovacia časť. Veľmi podstatná je výsledná analýza riešení, tu by som uvítala prehľadné tabuľkové porovanie (najmä u analýzy vlastností z pohľadu hashovacích algoritmov), nie iba textové závery. Doporučujem do prezentácie. 

90 100
Formální úprava technické zprávy

Typografická a jazyková stránka práce je v poriadku, s drobnými výhradami. Napr. pretečenie niektorých častí pseudokódov za hranicu textu, drobný text v niektorých obrázkoch, napr. grafy v kapitole 8, obr. 5.19. Chápem, že niektoré obrázky sú prevzaté, ale pre lepšiu čitateľnost práce mohli byť ich texty v češtine, hlavne v teoretickom úvode. 

80 100
Realizační výstup

Realizačný výstup je kompletný, spustiteľný a na základe podrobného popisu v práci dobre reprodukovateľný. Študent FPGA implementácie overil vo verifikácii s náhodným generovaním správ (10000) a rôznymi seed hodnotami + sadou špeciálne zameraných testov, ktoré overovali hashovacie vlastnosti.   

95 100
Využitelnost výsledků

Práca čiastočne rozširuje už publikované výsledky (jeden z vybraných hashovacích algoritmov), prínosom sú implementácie vybraných hashovacích funkcií, ktoré sú optimalizavané pre využitie v FPGA. Výsledky sú využiteľné v praxi, jeden z výstupov je už experimentálne nasadený do reálnej sieťovej prevádzky. 

Rozsah splnění požadavků zadání

Stupeň hodnocení: zadání splněno

Jednotlivé body zadania boli splnené v plnom rozsahu. 

Rozsah technické zprávy

Stupeň hodnocení: je v obvyklém rozmezí

Rozsah technickej správy je v poriadku.

Práce s literaturou

S ohľadom na zameranie práce, je výber literatúry v poriadku.

95 100
Otázky k obhajobě:
  1. 1. V akom prostredí boli spustené testy z kapitoly 7? V simulácii a zároveň v reálnom HW?
  2. 2. Jeden z algoritmov je experimentálne nasadený v reálnej prevádzke. Prečo práve SpookyHash a na základe akých kritérii prebiehal výber?
Výsledný počet bodů navržený oponentem: 92

Známka navržená oponentem: A

Odpovědnost: Mgr. et Mgr. Hana Odstrčilová