Bachelor's Thesis

Comparison of Algorithms Suitable for Circuit-Level Implementation of Vector Arithmetic

Final Thesis 1.01 MB

Author of thesis: Bc. Matěj Gruszkowski

Acad. year: 2025/2026

Supervisor: Ing. Václav Šimek

Reviewer: doc. Ing. Vojtěch Mrázek, Ph.D.

Abstract:

The goal of this work is to create a configurable SIMD module extension for an existing RISC-V-based Instruction Set Architecture model, with emphasis on SIMD division. The implemented module consists of 16 architectural registers with a configurable number of 64-bit lanes, which can be interpreted as vectors of 8-, 16-, 32-, or 64-bit integer elements. The implemented divider module uses a fixed-point Newton-Raphson division algorithm with a Booth Radix-4-encoding parallel multiplier with internal partitioning.

Keywords:

Arithmetic Division, SIMD, Hardware, Newton-Raphson, SRT, Goldschmidt, RISC-V, Vector arithmetic, Booth's algorithm, Codasip

Date of defence

18.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaEznamka

Grading

E

Process of defence

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 dále zvážila fakt, že zadání bylo náročné, výklad zadání byl pro studenta nejednoznačný a konzultant z firmy nebyl ochoten komunikovat v poslední době se studentem. 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 E.

Topics for thesis defence

  1. Na jakých programech bylo vyhodnoceno, že vaše implementace je funkčně správná? Jaká byla metodologie testování?

Language of thesis

English

Faculty

Department

Study programme

Information Technology (BIT)

Composition of Committee

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)

Supervisor’s report
Ing. Václav Šimek

S ohledem na výše uvedené skutečnosti navrhuji souhrnné hodnocení stupněm D - uspokojivě, 65 bodů.

Evaluation criteria Verbal classification
Informace k zadání

Domnívám se, že je možno zadání této bakalářské práce považovat za spíše náročnější. Už jen realizace SIMD verze zvolené metody dělení a její začlenění do stávající architektury uRISC-V není v žádném případě triviální záležitostí, byť tento krok do jisté míry usnadňuje využití nástroje Codasip Studio.

Zadání jako takové bych z pozice vedoucího označil ve formální rovině za splněné. Nejsem však zcela spokojen s vyhodnocením jednotlivým metod či přístupů k obvodové realizaci dělení, co se tedy nároků na zdroje a škálovatelnost týče (viz 4. bod zadání). Kromě toho vlastnosti realizovaného řešení byly vyhodnoceny jen z pohledu syntézy do FPGA a nikoliv po stránce jeho dopadů na běh konkrétního algoritmu či scénáře (viz 7. bod zadání).

Práce s literaturou

Studentovi byla v počáteční fázi projektu udělena základní doporučení k vyhledávání a použití informačních pramenů, přičemž kromě několika výchozích materiálů si byl schopen zbývající iniciativně dohledat sám. V technické zprávě uváděné reference bych označil za vhodně zvolené a použité.

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

Komunikaci se studentem v průběhu řešení projektu  bych označil za spíše občasnou. Z jeho strany bylo iniciováno pár konzultací, do nichž byl zapojen i zástupce společnosti Codasip, a to zejména v období kolem obhajoby semestrálního projektu a před odevzdáním práce.

Aktivita při dokončování

Závěrečná fáze a odevzdání projektu se odehrávalo v poněkud hektickém tempu, kdy již nezbyl prostor na pečlivou analýzu dosažených výsledků. Měl jsem možnost připomínkovat asi dvě verze technické zprávy s určitým odstupem před termínem odevzdání, nicméně tyto ještě nezahrnovaly všechny potřebné detaily. I přesto byly alespoň některé připomínky vedoucího reflektovány.

Publikační činnost, ocenění

V souvislosti s řešením této bakalářské práce mi není znám zisk souvisejících ocenění či další publikační činnost.

Points proposed by supervisor: 65

Grade proposed by supervisor: D

Zadání vyžadovalo porovnat složitost a HW náročnost jednotlivých algoritmů dělení. Autor vyhodnotil pouze teoreticky složitost bez určení HW náročnosti. Měl vyhodnotit také náročnost jednotlivých aplikačních scénářů (které nejsou explicitně jmenované), ale i tak autor vyhodnocuje obvody nevhodným metodologickým postupem. Proto práci považuji za nevyhovující - F a doporučuji práci k doplnění.


Pro doplnění práce doporučuji následující zlepšení výsledků:



  • přidání automatického testování navržených obvodů na úrovni SystemVerilog,

  • vyhodnocení implementace s HW děličkou dostupnou v procesoru,

  • podrobnější analýzu HW řešení (i spotřeba),

  • porovnání vektorizované a nevektorizované implementace.


Na základě existujících výsledků i toho, že implementace je hotova a je třeba jen zlepšit evaluaci, doporučuji práci k doplnění do srpnového termínu.

Evaluation criteria Verbal classification Points
Náročnost zadání

Evaluation level: průměrně obtížné zadání

Zadání požaduje prozkoumání a implementaci několika algoritmů pro násobení, sčítání a dělení celých čísel. Jedná se o reimplementaci a evaluaci několika existujících přístupů.

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

V technické zprávě se na začátku popisuje problematika návrhu instrukčních sad a architektury procesoru v jazyce Codal. Při popisu jednotlivých možností realizace aritmetických operací se však některé aspekty moc nediskutují (např. přesnosti iteračních algoritmů, kde bych očekával matematické či experimentální odvození) či obsahují zavádějící informace. V textu se často mluví o hradlech pro implementaci elementárních prvků, jako je poloviční sčítačka, přičemž autor pak implementuje systém na FPGA s LUT tabulkami, takže je to irelevantní. Navíc i při základní ASIC implementaci by se došlo k závěru, že tato hradla jsou přímo řešena na úrovni CMOS. Základní informace jsou však v textu uvedeny.

60
Formální úprava technické zprávy

Jazykově a typograficky práce nevykazuje závažnější chyby.

80
Realizační výstup

Autor implementoval v jazyce Codal sčítání, násobení (ve 4 variantách) a dělení (1 varianta využívající tato 4 násobení) pro SIMD zpracování instrukcí. Implementace mi byla předvedena a podle popisu autora je na základě manuálního testování funkční. Vlastní součásti však nebyly podrobeny funkčnímu testování – pro vybrané moduly je nutné vytvořit testy ověřující aritmetickou správnost instrukcí.

Největší slabina je však to, že zadání explicitně požadovalo vyhodnocení více algoritmů dělení, což autor udělal pro 4 implementace stejného iteračního algoritmu, ale nevyhodnotil základní implementaci dělení v použitém procesoru (non-restoring divider). Není vůbec vyhodnocena možnost různého stupně zřetězení iteračního algoritmu, vliv na celkový průběh počítání benchmarkových programů a vyhodnocení je provedeno pouze na jednom FPGA. Očekával bych vyhodnocení aspoň na více variantách FPGA a také po syntéze do ASIC obvodů - buď s využitím komerčních či open-source nástrojů.

40
Využitelnost výsledků

Vzhledem k nízkému objemu výsledků tyto výsledky nepovažuji za využitelné.

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

Evaluation level: zadání splněno pouze částečně

Autor provedl rešerši existujících algoritmů pro sčítání, násobení a dělení. Měl porovnat jejich složitost a HW náročnost (bod 4 zadání), což řešil pouze z pohledu toho, co jednotky obsahují. Fyzicky implementoval pouze Newton-Raphson iterační algoritmus dělení (v jazyce Codal), ve kterém vytvořil dvě varianty násobení. Očekával bych porovnání např. vůči děličce existující v dodaném RISC-V procesoru.

Vlastní vyhodnocení různých aplikačních scénářů (bod 7) je provedeno pouze pro varianty implementací algoritmu násobení a aplikační scénář není řešen. Očekával bych porovnání vůči základní implementaci nevektorizované variantě dělení z pohledu času, energie a HW prostředků,

Rozsah technické zprávy

Evaluation level: je v obvyklém rozmezí

Práce s literaturou

Autor ve své práci používá relevantní zdroje, které jsou dobře odkazovány.

90
Topics for thesis defence:
  1. Na jakých programech bylo vyhodnoceno, že vaše implementace je funkčně správná? Jaká byla metodologie testování?
Points proposed by reviewer: 40

Grade proposed by reviewer: F

Responsibility: Mgr. et Mgr. Hana Odstrčilová