Témata dizertačních prací

Se stále zvyšujícím se počtem tranzistorů na čipu se také zvyšuje množství dat potřebné pro jeho testování. Integrované obvody jsou poprvé testovány při výrobě, před zapouzdřením. Zde jsou testovací vektory generovány tzv. ATE (Automated Test Equipment) zařízením a přenášeny do čipu. Množství dat je zde obrovské, paměť v ATE je extrémně drahá, to samé platí o době testu. Je tudíž nutné tato data komprimovat. Poměr nákladů vynaložených na test čipu a na jeho návrh se stále zvyšuje. Komprese testovacích vektorů je tedy aktuální téma a stále více nabývá na významu. 

Je tedy zapotřebí intenzivního výzkumu v této oblasti a pokoušet se překonat stávající kompresní techniky.
Bylo navrženo mnoho kompresních technik, některé se používají v průmyslové praxi [1], [2]. Většina z nich je založená na kombinaci pseudo-náhodného testu (který může být implementován na čipu) a deterministického testu. Deterministické vektory jsou algoritmicky zkomprimované a uložené v ATE a posléze dekomprimované na čipu.
Cílem doktorského studia bude navrhnout nové metody pro kompresi a dekompresi testu pro pokročilé design-for-testability (DFT) architektury [3]. To bude zahrnovat návrh nových dekompresních architektur, algoritmů pro kompresi testu a návrh celkové HW architektury.

Tento výzkum bude (může) volně navazovat na dokončenou dizertační práci [4], [5].

[1] J. Rajski et al. “Embedded Deterministic Test”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no. 5, pp. 776-792, 2004.
[2] Y. Huang, S. Milewski, J. Rajski, J. Tyszer and C. Wang, “Low Cost Hypercompression of Test Data,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 10, pp. 2964-2975, 2020.
[3] R. Dorsch, H. Wunderlich, “Reusing Scan Chains for Test Pattern Decompression”, Journal of Electronic Testing: Theory and Applications, vol. 18, no. 2, pp. 231-240, 2002.
[4] J. Balcárek, P. Fišer, and J. Schmidt, “Techniques for SAT-based Constrained Test Pattern Generation,” in Microprocessors and Microsystems, Elsevier, Vol. 37, Issue 2, March 2013, pp. 185-195.
[5] J. Balcárek, „Implicit Representations in Testing and Dependability of Digital Circuits“, Ph.D. Thesis, CTU in Prague, 2016.

Současné nástroje pro logickou syntézu a optimalizaci (komerční i akademické) z převážné míry kladou důraz na rychlost, na úkor kvality. Nedávný výzkum ukázal, že tyto nástroje mají tendenci uváznout v hlubokých lokálních minimech a často produkují velice suboptimální výsledky (plocha, zpoždění). Jedním z důvodů je deterministická povaha používaných algoritmů. Randomizované iterativní algoritmy se ukázaly být jedním z řešení tohoto problému [1], [2] – nabízejí možnost zlepšit kvalitu řešení za cenu delšího výpočetního času.

Současné studie navíc ukazují, že většina nástrojů pro logickou syntézu a optimalizaci je velice citlivá na „náhodnost“ vnesenou zvnějšku, samotným návrhářem [3], [4]. Syntéza pak při nepatrné změně zdrojového kódu (při zachování funkční ekvivalence) produkuje kvalitativně značně odlišné výsledky. Toto chování není příliš žádoucí. Je tedy záhodno analyzovat toto chování, identifikovat jeho příčiny a navrhnout efektivnější algoritmy.

Cílem výzkumu bude analýza chování dostupných nástrojů (algoritmů) pro logickou syntézu a optimalizaci [5], identifikace příčin výše zmíněného chování, identifikace bodů algoritmu, kam lze explicitně vložit náhodnost a randomizace těchto algoritmů. Bude analyzován vliv náhodnosti a navrženy algoritmy, které vliv náhodnosti minimalizují, případně ji využijí v pozitivním smyslu [1], [2].

Dále mohou být navrženy nové algoritmy, které budou minimálně citlivé na náhodnost zanešenou zvenku, při zachování akceptovatelné výpočetní složitosti.

[1] P. Fišer and J. Schmidt, “Improving the Iterative Power of Resynthesis,” in Proc. of 15th IEEE Symposium on Design and Diagnostics of Electronic Systems (DDECS), Tallinn (Estonia), April 18-20, 2012, pp. 30-33.
[2] P. Fišer and J. Schmidt, “On Using Permutation of Variables to Improve the Iterative Power of Resynthesis,” in Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), Freiberg (Germany), September 19-21, 2012, pp. 107-114.
[3] A. Puggelli, T. Welp, A. Kuehlmann, and A. Sangiovanni-Vincentelli, “Are Logic Synthesis Tools Robust?,” in Proc. of  the 48th ACM/EDAC/IEEE Design Automation Conference (DAC), 5-9 June 2011, pp. 633-638.
[4] P. Fišer, J. Schmidt, and J. Balcárek, “On Robustness of EDA Tools,” in Proc. of 17th Euromicro Conference on Digital Systems Design (DSD), Verona (Italy), August 27-29, 2014, pp. 427-434.
[5] Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification” [Online]. Available: http://www.eecs.berkeley.edu/alanmi/abc/.

Současné nástroje pro logickou syntézu a optimalizaci (komerční i akademické) z převážné míry kladou důraz na rychlost, na úkor kvality. Nedávný výzkum ukázal, že tyto nástroje mají tendenci uváznout v hlubokých lokálních minimech a často produkují velice suboptimální výsledky (plocha, zpoždění). Jedním z důvodů je deterministická povaha používaných algoritmů. Randomizace algoritmů [1], [2] se ukázala být pouze částečným řešením tohoto problému. Druhým, důležitějším důvodem, je chybějící řízení syntézních algoritmů na nejvyšší úrovni. Současná logická syntéza je většinou iterativní proces, ve kterém se jednotlivé syntézní kroky spouštějí spekulativně. Zavedení pokročilejších technik řízení by mohlo značně vylepšit celý syntézní proces.

Cílem výzkumu je prozkoumat chování jednotlivých kroků logické syntézy (např. v nástroji ABC [3]), zjistit jejich závislost a ortogonalitu a navrhnout algoritmus pro efektivní řízení celého procesu.

[1] P. Fišer and J. Schmidt, “Improving the Iterative Power of Resynthesis,” in Proc. of 15th IEEE Symposium on Design and Diagnostics of Electronic Systems (DDECS), Tallinn (Estonia), April 18-20, 2012, pp. 30-33.
[2] P. Fišer and J. Schmidt, “On Using Permutation of Variables to Improve the Iterative Power of Resynthesis,” in Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), Freiberg (Germany), September 19-21, 2012, pp. 107-114.
[3] Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification” [Online]. Available: http://www.eecs.berkeley.edu/alanmi/abc/.

Hluboké sítě se staly v současné době nejpoužívanější metodou v oblasti rozpoznávání obrazů, zejména vizuálních a klasifikačních úloh. Několik nedávných studií ale ukázalo, že se některé hluboké sítě dají snadno zmást malou, pro lidské oko nepostřehnutelnou, změnou obrázku, která vede k tomu, že je obrázek klasifikován jako něco úplně jiného. Je proto potřebné zkoumat robustnost neuronových sítí vzhledem k matoucím vzorům.

Cílem dizertace je navrhnout multiobjektivní algoritmy generující nepostřehnutelné perturbace obrázků vedoucí k jejich nesprávné klasifikaci. Budou vyvinuty evoluční algoritmy pro generování matoucích obrázků, které maximalizují chyby klasifikace a zachovávají co největší podobnost originálním trénovacím vzorům. Bude analyzována role hloubky sítě a lokálních vlastností výpočetních jednotek. Budou zkoumány metody pro zvýšení robustnosti neuronových sítí vzhledem k matoucím vzorům.

Testovací vzorky jsou generovány v systému ATPG. Kromě logických hodnot 0 a 1 vzniká při generování velké množství nedefinovaných bitů. Při kompresi vzorků, které jsou přiváděny na vstupy číslicových obvodů, je výhodné využít exstenci neurčených bitů a podobnosti za sebou jdoucích vzorků. Kritériem optimality je míra redukce vzorků, složistost hardwaru nutného pro dekompresi testovací sekvence a počet hodinových cyklů nutných pro vlastní dekompresi. Optimalizace je možné provádět v prostředí MATLAB a C.

Rozvoj výpočetních prostředků a algoritmů umožňuje experimentálně ověřovat kvalitu automatů podle specifických požadavků na komplexnější úrovni než v minulosti. Pro kompresi a dekompresi testovacích vzorků se používají takové automaty, které umožňují během daného počtu hodinových taktů přejít mezi stavy, které representují jednotlivé vzorky. Vzhledem k charakteru vzorků se jako automaů používá obvodů LFSR, které mají vhodně zvolené charakteristické polynomy. Ukazuje se však, že je možné hledat jiné typy automatů, které mají lepší řiditelnost při přechodu mezi stavy reprezentujícími nejčastěji vyskytující se vzorky. Na základě experimentů pomocí řešičů soustav lineárních rovnic a vhodného algoritmu prohledávajícího prostor možných automatů předpokládáme vylepšení sledovaných kompresních vlastností tím, že vybereme obecně nejvhodnější strukturu dekompresního automatu podle zadaných charakteristik vzorků.

Výzkum metod implementace a akcelerace vybraných kryptologických operací a schémat ve vestavných systémech a v rekonfigurovatelných obvodech, zejména pak v programovatelných hradlových polích.

Školitel specialista – Ing. Michal Valenta, Ph.D.

Hlavním cílem práce je výzkum technik optimalizace dotazů nad grafovou databází ve formě atributového orientovaného grafu a též s ohledem na specifika konkrétního grafu a typických dotazů nad ním. Vhodnou aplikační doménou je analýza datových toků (data lineage).

Dalším cílem práce je výzkum a návrh metod pro dynamickou distribuci dat v distribuované grafové databázi na základě analýzy dotazů nad touto databází

Řídké matice se ukládají do paměti počítačů v souřadnicovém (COO) nebo řádkově komprimovaném (CSR) formátu. Kromě těchto základních formátů bylo vyvinuto mnoho dalších paměťových formátů pro řídké matice (sparse matrix storage formats, SMSF). Tuto problematiku jsme shrnuli v přehledovém článku Langr, Tvrdik: Evaluation Criteria for Sparse Matrix Storage Formats. IEEE Trans. Parallel Distrib. Syst. 27(2): 428-440 (2016). Vhodnost a vlastnosti jednotlivých SMSF pro různé třídy vědeckých výpočtů závisejí na struktuře řídké matice. Abychom minimalizovali např. paměťovou náročnost uložení velké řídké matice na paralelním počítači se sdílenou nebo distribuovanou pamětí, je vhodné převést řídké matice namapované na paralelní počítač z těchto základních SMSF na úspornější blokové formáty, což typicky znamená dekompozici na pokud možno husté čtvercové submatice pokud možno podobné velikosti. Úlohu transformace SMSF je třeba řešit pro rozsáhlé řídké matice, které jsou distribuovány v pamětech uzlů paralelního počítače. Výpočty nad řídkými maticemi dat jsou ze své podstaty iterační a vyžadují několik průchodů distribuovanými daty reprezentujícími strukturu řídké matice. Jejich klíčovou komponentou je řazení. Optimalizace velikosti bloků vyžaduje opakované paralelní řazení dat popisující strukturu řídkosti matice podle různých klíčů.

Cílem dizertační práce je výzkum paralelních algoritmů pro efektivní a škálovatelné transformace velkých řídkých matic v základních SMSF na blokové. Práce na tomto projektu je podpořena 5letým projektem OP VVV CRI a studenti získají přístup a budou moci pracovat na nejvýkonnějších superpočítačích na světě.