doc. Ing. Petr Fišer, Ph.D.

Pracoviště
ČVUT FIT, Katedra číslicového návrhu
Výzkumná skupina
Digital Design & Dependability Research Group
Osobní stránky
https://users.fit.cvut.cz/~fiserp/
E-mail
petr.fiser@fit.cvut.cz

Randomizované iterativní algoritmy v logické syntéze

Randomized Iterative Algorithms in Logic Synthesis

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.

Contemporary logic synthesis and optimization tools (both commercial and academic) mostly emphasize computational speed, at expense of result quality. Our resent research has shown, that these tools tend to get stuck in deep local optima, and therefore they often produce very inferior results (in terms of area and/or delay). Randomized iterative algorithms appear to efficiently solve this problem [1], [2] – they offer a trade-off between the run-time and result quality.

Moreover, present studies have shown that most of logic synthesis and optimization tools are very sensitive to randomness accidently introduced “from outside”, by the designer itself [3], [4]. Synthesis then produces results significantly differing in quality, when only slight changes in the source circuit description are made. Such a behavior is highly unwanted. Thus, it is required to analyze this behavior, determine its reasons, and to suggest more efficient algorithms.

The aim of the research is to analyze selected logic synthesis and optimization algorithms [5], identify the reasons of the above-mentioned behavior, and identify points, where randomness can be introduced. The influence of randomness will be then analyzed and algorithms exploiting the randomness in a positive way will be devised [3], [4]. Next, new algorithms minimizing the sensitivity on the external randomness will be developed.

Reference

  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: https://people.eecs.berkeley.edu/~alanmi/abc/.

Komprese testu pro ASIC obvody

Test Compression for ASIC Circuits

Se stále zvyšujícím se počtem tranzistorů na čipu se také zvyšuje počet vektorů potřebných pro testování čipu. 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. Dle International Technology Roadmap for Semiconductors (ITRS) [1] je požadováno, aby v roce 2020 bylo dosahováno kompresního poměru 20 000. Bohužel, současné kompresní techniky se ani zdaleka neblíží tomuto poměru. 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 [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é 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 volně navazovat na právě dokončovanou doktorskou práci [4].

With the increasing complexity of presently manufactured chips, increasingly more data must be delivered to individual chip cores to test them. Compression of this data becomes now inevitable, because of expensiveness of the ATE memory and test time expenses. According to International Technology Roadmap for Semiconductors (ITRS) [1], test data compression ratio of 20,000 is required in the year 2020. Presently, commercial tools do not even approach this compression requirements. Therefore, it is very challenging to contribute to the research in the area of test compression and to try to overcome established industrial tools in performance.

Different test compression mechanisms have been proposed, some of them are used in industry [2]. Most of them rely on a combination of pseudo-random testing (and possibly BIST), which can be implemented on-chip as whole and does not need any data to be transmitted, and deterministic test. The deterministic test is algorithmically compressed, stored in the ATE memory, and decompressed on-chip.

The aim of the research is to design test compression/decompression methods based on advanced design-for-testability (DFT) architectures [3]. This will comprise of a design of possibly novel decompression architectures, algorithms for test compression for these architectures, and design of the overall HW architecture, where test decompression, BIST and various DFT features will be implemented.

This research will be follow up the research conducted until now (finishing Ph.D. student) [4].

Reference

  1. International Technology Roadmap for Semiconductors, http://www.itrs2.net/
  2. 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.
  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.

Zdokonalení řízení procesu logické syntézy a optimalizace

Improvements in the Logic Synthesis and Optimization Process Control

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.

Contemporary logic synthesis and optimization tools (both commercial and academic) mostly emphasize computational speed, at expense of result quality. Our resent research has shown, that these tools tend to get stuck in deep local optima, and therefore they often produce very inferior results (in terms of area and/or delay). One of the reasons for it is a deterministic nature of the algorithms. Randomization of the algorithms has been found to be a viable, but just partial solution to this problem [1], [2]. The second, and more important reason of failure is the lack of global algorithm control. Most of present logic synthesis and optimization algorithms are of an iterative nature, whereas their individual parts (elementary operations) are executed essentially ad-hoc and speculatively. Implementation of efficient top-level algorithm control means should significantly improve performance of logic synthesis and optimization.

The aim of the research is to investigate the behavior of individual elementary synthesis steps (e.g., in the ABC synthesis tool [3]), determine their dependence and orthogonality, and devise an improved overall algorithm control.

Reference

  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: https://people.eecs.berkeley.edu/~alanmi/abc/.


Poslední změna: 26.4.2019, 10:05