doc. Ing. Jan Schmidt, Ph.D.

Stať ve sborníku

10.1109/DDECS60919.2024.10508902

Katedra číslicového návrhu

Small quantized neural networks with strong requirements on throughput and latency can be translated into combinational logic circuits and synthesized by logic design tools. To capture the function of the network (or a part of it) as a logic function, two approaches have been taken. The first one observes the inputs and outputs, while the network predicts a training set, and uses them directly as specification. The response to activation values that have not occurred in the training set remain unspecified. The other approach uses a complete set of activation values at the input of the examined part. Our study aims to quantify the inaccuracy of the first method, the influence of logic minimization used on accuracy, and the impact on the final synthesized circuit. We also document the quantitative changes in quantized networks.

Stať ve sborníku

10.1109/DDECS60919.2024.10508927

Katedra číslicového návrhu

Neural networks with quantized activation functions cannot adapt the quantization at the input of their first layer. Preprocessing is therefore required to adapt the range of input data to the quantization range. Such preprocessing usually includes an activation-wise linear transformation and is steered by the properties of the training set. We suggest to include the linear transform into the training process. We document that it improves accuracy, requires the same resources as standard preprocessing, plays a role in network pruning, and is reasonably stable with respect to initialization.

Stať ve sborníku

Katedra číslicového návrhu

Two-level logic optimization is a well-established process that efficiently minimizes a Sum-of-Products (SOP) form. Espresso is the most known two-level minimizer since its release in 1984. And indeed, it produces optimum or near-optimum results regarding the SOP size. However, there could be an issue with multi-level circuit implementation. When a two-level minimizer processes a completely specified function before multilevel synthesis, it helps since no information is lost. However, as for incompletely specified functions, this needs not be the case since the two-level minimization could introduce a heavy structural bias by assigning the don’t cares particular values. In this paper, we show that a two-level minimization conducted in the standard way significantly worsens the result of the subsequent multi-level optimization for heavily incompletely specified multiple-output functions, regardless of the optimization process and tool used. In particular, the more incompletely specified the input function is, the more harm the multipleoutput minimization does. In conclusion, we propose using a single-output minimization instead. Using this procedure, the obtained circuits are sometimes more than 2-times smaller, while no significant deterioration has been observed for any other functions.

Stať ve sborníku

Katedra číslicového návrhu

Two-level logic minimization is a well-established process that efficiently minimizes functions described in the Sum-of-Products (SOP) form. Current two-level minimizes, like Espresso and Boom, produce optimum or near-optimum results regarding the SOP size. However, there could be an issue when multi-level logic synthesis follows the two-level optimization. In this paper, we show that a two-level minimization conducted in the standard way significantly worsens the result of the subsequent multi-level synthesis, especially for heavily incompletely specified multiple-output functions, regardless of the optimization process and the tool used. In conclusion, we propose using a single-output two-level minimization for incompletely specified functions. In this way, the obtained circuits are sometimes multiple times smaller, while no significant deterioration has been observed for any other functions.

Stať ve sborníku

10.1109/DDECS57882.2023.10139408

Katedra číslicového návrhu

In digital circuit testing, output response compaction can have a significant impact on fault coverage. The loss of fault coverage is caused by aliasing in the output response compaction. Classical approaches to reducing (eliminating) fault aliasing are based on modifications of the compactor design or modifying precomputed test sequence. In this paper, we propose a completely different approach based on a dedicated test pattern generation algorithm. The algorithm generates a test sequence with minimal aliasing for targeted faults. As the generated test sequence is tailored to given static and dynamic compactor structures, any response compactor can be used without a change in the design. We expand on our previous work, zero-aliasing ATPG, and incorporate pseudo-Boolean optimization techniques in the process. The algorithm is evaluated using an LFSR-based MISR on a selection of benchmark circuits. A comparison with a state-of-the-art ATPG process without anti-aliasing measures is drawn.

Stať ve sborníku

10.1109/MECO55406.2022.9797220

Katedra číslicového návrhu

Interval constraint satisfaction problems (CSPs) are typically hard to solve and, therefore, desirable candidates for acceleration. Although there were successful attempts in this area, several paths remain unexplored. Let’s describe, discuss, and generalize our findings among partial algorithms and approaches used for interval CSP solving. We have divided the interval CSP solving process into several levels of abstraction. We analyzed them individually to find common traits and patterns among them. These can indicate possible areas for future acceleration attempts, especially on edge systems where effectiveness plays an important role.

Kapitola v knize

10.1007/978-3-030-68071-8_6

Katedra číslicového návrhu

The problem is to design a nonlinear code for test vectors expander, with the requirement of all r-tuples possible in the output. We formulated the problem as a clique cover problem. The instances of the problem have a high degree of symmetry, which offers the possibility of analytical solution or better heuristic construction. To benefit from the degrees of freedom in the problem, assigning expander inputs to the produced vectors has been identified as a Multi-Valued (MV) variable encoding problem. Experimental evaluation shows that good MV encoding is important for small r. Instances up to n=32 and r=6 were solved, with the resulting expander widths i mostly equal to or better than existing solutions. For the synthesis of the expanders, both the classical minimization-decomposition and resynthesis approaches can be used. The produced circuits were larger than corresponding linear expanders.

Článek

10.1016/j.microrel.2021.114281

Katedra číslicového návrhu
Katedra informační bezpečnosti

Physical attacks, namely invasive, observation, and combined, represent a great challenge for today's digital design. Successful class of strategies adopted by industry, allowing hiding data dependency of the side channel emissions in CMOS is based on balancing. Although attacks on CMOS dynamic power represent a class of state-of-the-art attacks, vulnerabilities exploiting data dependency in CMOS static power and light-modulated static power were recently presented. In this paper, we describe structures and techniques developed to enhance and balance the power imprint of the traditional static CMOS bulk structures under invasive light attack. The novel standard cells designed according to the presented techniques in the TSMC180nm technology node were used to synthesize the dual-rail AES SBOX block. The behavior of the AES SBOX block composed of the novel cells is compared to classical approaches. Usage of novel cells enhances circuit security under invasive light attack while preserving comparable circuit resistance against state-of-the-art power attacks.

Stať ve sborníku

Katedra číslicového návrhu

We analyze the situation where reasoning about a system is required, yet parts of the system can be only simulated. Several tools integrated a simulator with an SMT solver in various ways, creating Satisfiability Modulo Simulation. The problem, what questions such tools can answer in principle, remained open. We aim at such an analysis, based on the lazy solver architecture. We studied modifications that in general are required to accommodate a simulator. We identified the so-called domain propagation in the domain-specific part of the solver as the crucial process defining the properties of the entire solver. It is a Constraint Propagation problem. Based on the outcome of its solution, the solver can or cannot prove unsatisfiability. Also, various strategies to employ simulation experiments are possible. In the end, we show that the way to Satisfiability Modulo Black Box Evaluator is open.

Stať ve sborníku

Katedra číslicového návrhu

The problem is to design a nonlinear code for test vectors expander, with the requirement of all r-tuples possible in the output. We formulated the problem as a clique cover problem. The instances of the problem have a high degree of symmetry, which offers the possibility of analytical solution or better heuristic construction. To benefit from the degrees of freedom in the problem, assigning expander inputs to the produced vectors has been identified as a multi-valued (MV) variable encoding problem. Experimental evaluation shows that good MV encoding is important for small r. Instances up to n=32 and r=6 were solved, with the resulting expander widths i mostly equal to or better than existing solutions. For the synthesis of the expanders, both the classical minimization-decomposition and resynthesis approaches can be used. The produced circuits were larger than corresponding linear expanders.

Článek

10.1002/navi.390

Katedra číslicového návrhu

This paper presents a new modified Single Block Zero-Padding (mSBZP) Partial Correlation Method (PCM) Parallel Code Search (PCS) algorithm for effective acquisition of weak GNSS tiered signal using coherent processing of its secondary code (SC) component. Two problems are discussed: acquisition of primary codes with longer period using FFT blocks of limited length, and the utilization of PCS in the presence of SC bit transition. The PCM and SC bit transition forms parasitic fragments in the Cross-Ambiguity-Function (CAF) to devaluate signal detection performance. A novel analysis of this mechanism and its impact is presented. A novel mSBZP-PCM-PCS algorithm is proposed, which does not degrade the CAF. Then, the algorithm is combined with SC bit transition removal schema and sequential search to construct an estimator for weak tiered signal acquisition. The performance of the method is demonstrated by analysis and computer simulation using Galileo E1C and GPS L1C-P signals.

Stať ve sborníku

10.1109/DDECS50862.2020.9095656

Katedra číslicového návrhu

Physical attacks, namely invasive, observation and combined, represent a great challenge for today’s digital design. Successful class of strategies adopted by industry, allowing hiding data dependency of the side channel emissions in CMOS is based on balancing. Although attacks on CMOS dynamic power represent a class of state-of-the-art attacks, vulnerabilities exploiting data dependency in CMOS static power and light- modulated static power were recently presented. In this paper, we describe structures and techniques developed to enhance and balance traditional static CMOS bulk structures. To enable data dependency hiding, we propose low-level techniques based on complementary-value induced balancing currents, constant current source behavioral approximation, and light-sensing capability of traditional CMOS structures. The proposed techniques may be used to build a dual-rail circuit balanced from both perspectives: static and dynamic power. The publicly available TSMC180nm node standard cell simulation is used for evaluation.

Stať ve sborníku

10.1109/DDECS.2019.8724632

Katedra číslicového návrhu

The dummy rounds protection scheme, intendedto offer resistance against Side Channel Attacks to Feisteland SP ciphers, has been introduced in earlier work. Itsexperimental evaluation revealed weaknesses, most notablyin the first and last round. In this contribution, we showthat the situation can be greatly improved by controllingthe transition probabilities in the state space of the algo-rithm. We derived necessary and sufficient conditions forthe round execution probabilities to be uniform and hencethe minimum possible. The optimum trajectories over thestate space are regular and easy to implement.

Stať ve sborníku

10.1109/DSD.2019.00062

Katedra číslicového návrhu

As digital devices penetrate to many areas important for the present society, it is important to analyze even potential threats to mitigate vulnerabilities during their lifetime. In this paper, we analyze the data dependency of the photocurrent induced by a laser beam in the illuminated CMOS circuit. The data dependency may introduce potential threat(s) originating in the nature of the CMOS technology. The data dependency can be potentially misused to compromise the data processed by an embedded device. We show that also the devices employing dual-rail encoding to hide data-dependency are not safe.

Článek

10.1142/S0218126619400103

Katedra číslicového návrhu

This paper presents a method for generating optimum multi-level implementations of Boolean functions based on Satisfiability (SAT) and Pseudo-Boolean Optimization (PBO) problems solving. The method is able to generate one or enumerate all optimum implementations, while the allowed target gate types and gates costs can be arbitrarily specified. Polymorphic circuits represent a newly emerging computation paradigm, where one hardware structure is capable of performing two or more different intended functions, depending on instantaneous conditions in the target operating environment. In this paper we propose the first method ever, generating provably size-optimal polymorphic circuits. Scalability and feasibility of the method are documented by providing experimental results for all NPN-equivalence classes of four-input functions implemented in AND–Inverter and AND–XOR–Inverter logics without polymorphic behavior support being used and for all pairs of NPN–equivalence classes of three-input functions for polymorphic circuits. Finally, several smaller benchmark circuits were synthesized optimally, both in standard and polymorphic logics.

Stať ve sborníku

10.1109/DDECS.2019.8724663

Katedra číslicového návrhu

The security of many digital devices strongly depends on a secret value stored in them. To mitigate security threats, high protection of such a value must be provided. Many attacks against (cryptographic) hardware as well as attack countermeasures were presented recently. As new attacks are invented continuously, it is important to analyze even potential threats to mitigate device vulnerability during its lifetime. In this paper, we report a novel voter-related vulnerability, which can be potentially misused to compromise the secret value stored in an embedded device.

Kapitola v knize

Katedra číslicového návrhu

We present experimental evidence that logic synthesis procedure, especially those based on resynthesis, do net perform well when the original (designer-given) structure of input description is lost. As such performance has not been observed otherwise, we must conclude that such operation is outside of the intended range, and that synthesis examples with their original structure lost are not valid for evaluation of synthesis procedures. We also outline other causes that may render an example invalid. We, however, document that such losses did occur with circuit examples circulating in the logic synthesis community. Therefore, we have to suggest what constitutes prudence in examples collection.

Stať ve sborníku

10.1109/DSD.2018.00092

Katedra číslicového návrhu

This paper describes the technique of Dummy Rounds as a countermeasure against DPA in hardware implementation of round-based ciphers. Its principle is inspired by several well-known countermeasures used in hardware as Hiding and Dynamic Reconfiguration as well as countermeasures used in software implementations as Dummy cycles, Random order execution or Hiding in time. Being inspired by countermeasures based on dynamic reconfiguration, this method combines hiding of power consumption with hiding in time. In this work we also discuss the amount of randomness available for the control of the computation.

Stať ve sborníku

Katedra číslicového návrhu

Tato práce popisuje techniku Dummy Rounds jako protiopatření vůči DPA v hardwarových implementacích rundovních šifer. Princip je inspirován dobře známými metodami používaných v hardwaru jako skrývání a dynamická rekonfigurace stejně jako metodami z softwarových implementací jako nadbytečné cykly, náhodné provádění instrukcí nebo skrývání v čase. Tato metoda inspirovaná dynamickou rekonfigurací kombinuje skrývání spotřeby se skrýváním v čase. V této práci také diskutujeme množství náhodnosti dostupné pro kontrolu výpočtu.

Stať ve sborníku

Katedra číslicového návrhu

This contribution describes an architecture of additional system of memories for an existing GNSS (Global Navigation Satellite Systems) signal acquisition unit in frequency domain. The unit is designed for an FPGA-based HW receiver and has three 4K FFT blocks. The receiver is based on the System on Chip (SoC) Xilinx ZYNQ platform. The proposed additional memories are used as accumulators of complex signals samples and are placed in front or after the acquisition unit. They enable to process GNSS signals of different navigation systems more effectively with limited resources

Článek

10.1016/j.microrel.2017.12.031

Katedra číslicového návrhu

Although contemporary logic synthesis performs well on random logic, it may produce subpar results in XOR-intensive circuits. This indicated the need of equal status of XORs and ANDs, with their respective Negation-Permutation-Negation (NPN) equivalents in logic synthesis procedures. To test the hypothesis of XOR importance, we introduced a novel logic representation with a native support of XOR gates, the XOR-AND-Inverter Graph (XAIG). As the first test, we implemented a rewriting algorithm in the logic synthesis and optimization package ABC and compared it with the standard rewriting algorithm based on the AND-Inverter Graph (AIG). The main experimental evaluation was performed in the context of a complete logic synthesis process, particularly the FPGA LUT mapping and mapping to standard cells. To eliminate algorithmic noise, input circuit descriptions were randomly modified while preserving their semantics. In the FPGA mapping, the XAIG rewriting dominated the AIG procedure in 8.6% of cases, while it was dominated in 1.6% of cases. For the standard cells mapping, the respective percentages were 3% and 1.5%. We conclude that the best rewriting is a combination of both approaches.

Stať ve sborníku

Katedra číslicového návrhu

This paper discusses the feasibility and efficiency of a native XOR based logic synthesis. Particularly, a natively XOR-supporting rewriting algorithm is pre-sented. It is based on a novel data structure – the XOR-And-Inverter Graph. Ma-jor problems that appeared by extending the And-Inverter Graph rewriting to support XORs are discussed. The algorithm was implemented in a logic synthe-sis and optimization package ABC and compared to standard And-Inverter-Graph based rewriting. Its benefits are shown by experiments.

Článek

10.1016/j.micpro.2018.05.001

Katedra číslicového návrhu

Aliasing in test response compaction is an important source of fault coverage loss. Methods to avoid the aliasing mostly require modification of the compactor to some extent. This can lead to a higher compactor complexity and consequently to higher area overhead, longer signal propagation delays, etc. In contrast to this standard approach, we propose a novel method, the Zero-aliasing ATPG (ZATPG), which is able to reduce the aliasing for any compactor used, thus without need of the compactor modification or redesign. This is achieved by constraining the test pattern generation process (ATPG), so that patterns exhibiting no aliasing are produced directly. Aliasing in both the spatial and temporal compactors is assumed. The method is based on modification of very basic SAT-based ATPG principles, thus any SAT-based ATPG can be used for its purpose. Also, the method is general enough to be applicable to any compactor design. We demonstrate our method on MISR compactors based on LFSR and cellular automata, using the single stuck-at fault model. Our method is able to find a test with zero aliasing and complete fault coverage for smaller compactors than a conventional, unguided ATPG. Thus, the area overhead of the compactor can be reduced, while the complete fault coverage is preserved.

Stať ve sborníku

Katedra číslicového návrhu

The objective of this contribution is a design of optimal algorithms for an universal GNSS acquisition unit. The unit is designed for a FPGA-based HW receiver and is implemented in frequency domain with three 4K FFT blocks. The unit is able to acquire usual civil signals (GPS C/A, BeiDou B1, IRNSS L5/S-band, and GLONASS L1OF) directly and to acquire the Galileo E1 longer code signal with proposed improved algorithm of the partial correlation. Pre- and mainly post-correlation methods are analyzed and selected with respect to implementation on the target System on Chip (SoC) Xilinx ZYNQ platform with limited computing resources.

Stať ve sborníku

10.1109/DDECS.2017.7934583

Katedra číslicového návrhu

This paper follows recent research on insufficient synthesis performance for XOR-intensive circuits, and introduces a novel logic representation with a native support of XOR gates, the XOR-AND-Inverter Graphs (XAIGs). A rewriting algorithm over XAIG has been implemented in the logic synthesis and optimization package ABC, as the first step towards a complete synthesis process. The results show that XAIG based rewriting can help to discover XORs and improves the area of a mapped network in some cases.

Stať ve sborníku

Katedra číslicového návrhu

Reliability and security are critical properties of all hardware designs. However improving of one of the metrics causes very often decrease of the other metric. Our goal is to find novel method of programmable hardware design increasing both, reliability and security, or at least one of them without decreasing the other. We want to use dynamic reconfiguration on FPGA with lightweight cipher PRESENT implemented as countermeasure against differential power analysis. We will implement on our own existing method described in one of the earlier published papers. After that we will investigate influence of some modifications, implement our novel usage of dynamic reconfiguration usage combining it with hiding in time method and also investigate combination of our novel method and the previously published.

Stať ve sborníku

Katedra číslicového návrhu

Tato práce pojednává o směřování výzkumu v rámci tématu dizertační práce věnující se bezpečným a spolehlivým architekturám pro programovatelný hardware, především FPGA. Konkrétně práce pojednává o již existující implementaci šifry PRESENT na FPGA, kde je použita dynamická rekonfigurace jako jedno z opatření proti útoku pomocí rozdílové odběrové analýzy. Poté obsahuje diskusi nových možností pužití dynamické rekonfigurace a jejich vliv na bezpečnost i spolehlivost výsledného obvodu.

Stať ve sborníku

10.1109/MECO.2017.7977169

Katedra číslicového návrhu
Katedra počítačových systémů

This paper describes implementation of contactless smart card emulator compliant with ISO/IEC 14443 in Field Programmable Gate Array (FPGA). Systems using contactless smart cards are widely used and some of these systems are not secured properly. For example in many such systems smart card Unique Identifier (UID) is used as the only one authentication mean. As the UID is not encrypted and is read from the card in plain, it is easy to make a copy of the smart card and use the clone as the original card. In this work we describe emulator of a smart card implemented in FPGA which is able to spoof some genuine smart card. Emulator described in this work emulates protocol described in ISO/IEC 14443 standard, which in detail describes all aspects of RFID smart cards (from physical attributes of both - cards and readers - to communication by digital signals). The emulator is able to come through the whole card selection process and to spoof the real smart card with given UID. Moreover emulator can be selected also for higher application layer protocol communication. If we know the proprietary application layer protocol, emulator is able to spoof communication on this protocol with data recorded in it. This functionality was successfully tested on systems used at Czech Technical University in Prague, where the weak implementation of UID as the only one authentication mean is used. Emulator is responding faster than most of other existing smart card emulators thanks to high efficient implementation in hardware.

Článek

10.1016/j.micpro.2017.06.007

Katedra číslicového návrhu

The method proposed in this article allows to construct error-masking fail-operational systems by com- bining time and area redundancy. In such a system, error detection is performed online, while error masking is achieved by a short-duration offline test. The time penalty caused by the offline test applies only when an error is detected. The error-masking ability in such a system is very close to TMR, the area overhead is smaller for a well defined class of circuits, and the delay penalty caused by the offline test remains reasonably small. The short-duration offline test is possible only when extensive design-for-test practices are used. Therefore, a novel gate structure is presented, which allows to construct combina- tional circuits testable by a short-duration offline test. The proposed test offers com plete fault coverage with respect to the stuck-on and stuck-open fault model. The proposed solutions are combined and a comprehensive description of the overall error-masking architecture is provided.

Stať ve sborníku

Katedra číslicového návrhu

V tomto článku shrnuji své výsledky za 2. rok doktorského studia. Prezentuji automatický generátor testovacı́ch vektorů (ATPG), který je schopen vygenerovat test s nulovým maskovánı́m v daném libovolném kompaktoru: ZATPG. Disku- tuji silné a slabé stránky tohoto algoritmu, včetně námětů, jak jeho slabé stránky překonat. V závěru nastiňuji dalšı́ směřovánı́ výzkumu, které by mělo vést k disertačnı́ práci.

Stať ve sborníku

Katedra číslicového návrhu

The objective of this contribution is a design of universal GNSS acquisition unit for an FPGA-based HW receiver, which is able of direct acquisition of usual civil signals (GPS C/A, BeiDou B1, IRNSS L5/S-band, and GLONASS L1OF). Due to high complexity of calculation and requirements for latency, processing in frequency domain with parallel search in code is adopted. Optimal processing methods even for the long codes of Galileo E1 or future GPS L1C signals are analyzed. For each block of the acquisition unit, a method is selected with respect to implementation on the target System on Chip (SoC) Xilinx ZYNQ platform. The unit is intended as a HW acquisition accelerator with a minimal SW handling requirements for the developed receiver.

Stať ve sborníku vyzvaná či oceněná

Katedra číslicového návrhu

Experimental evaluation can be used quantitatively or qualitatively. In the latter case, an understanding a explanation of the observed phenomena is sought. To give relevant results, sources of variance must be identified and their influence eliminated. In certain situations, elimination is not possible and special measures must be taken.

Stať ve sborníku

Katedra číslicového návrhu

This paper presents a rewriting algorithm based on XOR-AND-Inverter Graphs (XAIGs). Such logic representation allows for synthesis algorithms work with XOR gates in a native way. Basic support for XAIGs has already been implemented in the ABC9 package GIA manager, where AND, XOR, and MUX nodes are allowed. However, the rewriting algorithm was missing in ABC9, hence we have re-implemented the original, AIG-based algorithm, and included it in the ABC9 package. For our purposes, we have restricted the nodes set to AND and XOR gates only. The presented XAIG-based rewriting algorithm is compared with the standard AIG-based rewriting algorithm. Since more node types bring some new decisions the rewriting algorithm has to make, we have implemented different rewriting mechanisms and compared them. The results indicate that XAIG based rewriting can lead to different circuits than the original rewriting and although AIG based rewriting produces slightly smaller circuits in most cases, some circuits are better handled with XAIG based rewriting, which points to future research and improvements. The XAIG based rewriting was also able to find significantly more XORs than ABC9 structural hashing and rewriting.

Stať ve sborníku

10.1109/DSD.2017.73

Katedra číslicového návrhu

Aliasing in the test response compaction is an important source of fault coverage loss. Methods to combat the aliasing generally require modification of the compactor to some extent. This can lead to a higher compactor complexity and consequently to higher area overhead, longer signal propagation delays, etc. We propose a novel method, the Zero-aliasing ATPG (ZATPG), which is able to reduce the aliasing without need of designing new compactors. ZATPG works by augmenting the SAT-based ATPG process to constrain test pattern generation to produce no aliasing in the compactor. The method is general enough to be applicable to any compactor design. We demonstrate our method on LFSR-based MISR compactors, using the Single Stuck-At fault model. Our method is able to find a test with zero-aliasing and complete fault coverage for smaller compactors than conventional, unguided ATPG. Thus, the area overhead of the compactor can be reduced, while the complete fault coverage is retained.

Stať ve sborníku

10.1109/DSD.2017.74

Katedra číslicového návrhu

This paper presents a method for generating optimum multi-level implementations of Boolean functions. It is based on Satisfiability (SAT) problem solving, while different SAT techniques are employed to reach different targets. The method is able to generate one, or enumerate all optimum implementations, while any technology constraints can be applied. Results for 4 input functions implemented by XOR AND-Inverter-Graphs (XAIGs) with different XOR nodes costs are presented. Scalability and feasibility of the method is presented. Finally, an experimental evaluation of XAIG based rewriting algorithm with optimum replacement circuits is presented and compared with the previous solution.

Stať ve sborníku

Katedra číslicového návrhu

In this paper we introduce a new set of example circuits, primarily intended for using in logic synthesis and optimization, mostly for testing and benchmarking purposes. Basically, the proposed set of circuits is a collection of former popular benchmark sets. By putting these circuits together, we have formed a more comprehensive, but unified and well-arranged set of example circuits, from which a user can select circuits (or the whole benchmarks) upon his wishes and needs. The collection comprises of several sets, which, even though they sometimes contain the same circuits, are customized to particular needs of the user. This paper documents the example set, together with origins of its parts, and statistics on the circuits are provided.

Stať ve sborníku

Katedra číslicového návrhu

We present experimental evidence that logic synthesis procedure, especially those based on resynthesis, do net perform well when the original (designer-given) structure of input description is lost. As such performance has not been observed otherwise, we must conclude that such operation is outside of the intended range, and that synthesis examples with their original structure lost are not valid for evaluation of synthesis procedures. We also outline other causes that may render an example invalid. We, however, document that such losses did occur with circuit examples circulating in the logic synthesis community. Therefore, we have to suggest what constitutes prudence in examples collection.

Stať ve sborníku

10.1109/DSD.2016.62

Katedra číslicového návrhu

The method proposed in this paper allows to construct error-correcting systems by combining time and area redundancy. In such a system, error detection is performed online, while error correction uses a short-duration offline test. The time penalty caused by the offline test applies only when an error is detected. The error-correcting ability in such a system is comparable with TMR, the area overhead is smaller for a class of circuits, and the delay penalty caused by the offline test remains reasonably small. The short-duration offline test is possible only when extensive design-for-test practices are used. Therefore, a novel gate structure is presented, which allows to construct combinational circuits testable by a short-duration offline test. The proposed test offers complete fault coverage with respect to the stuck-on and stuck-open fault model.

Stať ve sborníku

Katedra číslicového návrhu

V tomto článku shrnuji své výsledky za 1. rok dok- torského studia, porovnánı́ poruchových modelů pro aplikačně specifické testovánı́ FPGA, zkoumánı́ vlastností SAT instancí vzniklých v procesu ATPG. Dále nastiňuji dalšı́ možný směr pokračovánı́ výzkumu, generovánı́ testu s nulovým aliasingem.

Stať ve sborníku

Katedra číslicového návrhu

V článkuje představena možnost využití nové reprezentace logických obvodů pomocí Xor-And-Invertor grafů (XAIG) v syntézních algoritmech. XAIG jsou založeny na And-Invertor grafech, orientovaných acyklických grafech, kde uzly představují dvou-vstupá hradla AND či XOR a hrany mohou být negované.Předpokládá se, že tato reprezentace umožní algoritmům s XORy nativně pracovat a odhalit komplexnější závislosti.Pro experimentální ověření pravdivosti bude reimplementován algoritmus rewrite a bude porovnán s originálním rewritingem.

Stať ve sborníku

10.1109/BEC.2016.7743734

Katedra číslicového návrhu

In this paper we propose a SAT-based ATPG algorithm for application-oriented FPGA testing. For this purpose, a novel fault model is introduced which combines the stuck-at fault model for interconnects testing with the bit-flip model for LUT testing. The concept of SAT-based ATPG enables integrating these two models easily. Fault coverage and fault dominance of the two models is discussed in this paper, yielding suggestions for using the proposed combined model.

Kapitola v knize

Katedra číslicového návrhu
Katedra aplikované matematiky

EDA tools employ randomized algorithms for their favorable properties. Deterministic algorithms have been found sensitive to details in the input, and thus they also behave as the randomized ones. In both cases, performance analysis and comparison shall be made by histograms, or more precisely, by their probability density distribution. We present a modeling of ABC performance and, to gain understanding, a simple randomized algorithm solving the 3MAX-SAT problem. Also, a simulated annealing algorithm solving the same problem is studied. We claim that Gaussian Mixtures are suitable for such models and that truncated models must be considered.

Stať ve sborníku

10.1063/1.4938891

Katedra číslicového návrhu

Logic optimization is a process that takes a logic circuit description (Boolean network) as an input and tries to refine it, to reduce its size and/or depth. An ideal optimization process should be able to devise an optimum implementation of a network in a reasonable time, given any circuit structure at the input. However, there are cases where it completely fails to produce even near-optimum solutions. Such cases are typically induced by non-standard circuit structure modifications. Surprisingly enough, such deviated structures are frequently present in standard benchmark sets too. We may only wonder whether it is an intention of the benchmarks creators, or just an unlucky coincidence. Even though synthesis tools should be primarily well suited for practical circuits, there is no guarantee that, e.g., a higher-level synthesis process will not generate such unlucky structures. Here we present examples of circuit transformations that lead to failure of most of state-of-the-art logic synthesis and optimization processes, both academic and commercial, and suggest actions to mitigate the disturbing effects.

Stať ve sborníku

10.1109/DSD.2015.95

Katedra číslicového návrhu

In this work we present a novel fault-tolerant circuits design method. It combines time and area redundancy to achieve error-correction abilities similar to a triple-modular redundancy (TMR) and the area-overhead close to a duplex system. New logic gates design allowing a complete stuck-at fault testability will be presented. Our method allows to test combinational parts of the circuit using a universal short-duration offline test. The offline-testable module with an online-checker allows to compose a fault-tolerant system with the mentioned properties. This system will be denoted as a time-extended duplex scheme. In this scheme the offline test is sufficiently short to allow error correction during the computation (paused pipeline). The presented method adopts some principles from dual-rail logic and asynchronous circuits design.

Stať ve sborníku

Katedra číslicového návrhu

In this paper we present a preliminary work, where XOR structures are identified in an AIG. We study how structural hashing in ABChandles XOR gates coming from an already mapped netlist, whether they are structurally retained and whether new XOR structures can be identified in the AIG.

Článek

10.1016/j.micpro.2014.07.006

Katedra číslicového návrhu

Both test compression tools and ATPGs directly producing compressed test greatly benefit from don’t care values present in the test. Actually, presence of these don’t cares is essential for success of the compression. Contemporary ATPGs produce tests having more than 97% of don’t cares for large industrial circuits, thus high compression ratios can be expected. However, these don’t cares are placed in the test in an “uninformed” way. There are many possibilities of constructing a complete test for a circuit, while the ATPG chooses just one particular, without respect to the subsequent compression process. Therefore, the don’t cares cannot be fully exploited. In this paper we show how severe this issue is. A novel ATPG algorithm directly producing compressed test patterns for the RESPIN decompression architecture is presented. Test don’t cares are placed in an informed way, so that they are maximally exploited by compression. We compare the results with several ways of uninformed don’t care generation to show the benefits of the proposed method. Results for the ISCAS and ITC’99 benchmark circuits are shown and compared to state-of-the-art test compression techniques.

Stať ve sborníku

Katedra číslicového návrhu
Katedra aplikované matematiky

EDA tools employ randomized algorithms for their favorable properties. Deterministic algorithms have been found sensitive to details in the input, and thus they also behave as the randomized ones. In both cases, performance analysis and comparison shall be made by histograms, or more precisely, by their probability density distribution. We present a modeling of ABC performance and, to gain understanding, a simple randomized algorithm solving the 3MAX-SAT problem. Also, a simulated annealing algorithm solving the same problem is studied. We claim that Gaussian Mixtures are suitable for such models and that truncated models must be considered.

Stať ve sborníku

10.1109/DSD.2014.22

Katedra číslicového návrhu

It is known that EDA tools produce results of different quality dependent on seemingly neutral details in the input. We bring further results in this direction, which show that the differences can impair any quantitative comparisons of the tools. To gain qualitative insight, we present a stochastic model of result quality based on Gaussian Mixtures. We show on three case studies how these models help to evaluate and improve EDA algorithms.

Stať ve sborníku

10.1109/DSD.2014.86

Katedra číslicového návrhu

This paper presents a novel ATPG and test compression algorithm based on Pseudo-Boolean (PBO) optimization. Similarly to SAT-based ATPGs, the test for each fault is represented implicitly as a PBO instance. The optimization process solves the problem of maximizing the number of unspecified values in the test. A novel don’t care aware circuit-to-PBO conversion procedure is presented. The obtained unspecified values in the test are efficiently exploited in test compression. The produced compressed test sequence is suited for the RESPIN decompression architecture, thus for testing systems-on-chip. The presented experimental results show the efficiency and competitiveness of the proposed method.

Kapitola v knize

Katedra číslicového návrhu

Behavior of many contemporary logic synthesis and optimization processes depends on variable ordering in their input; they produce different results for different variable orderings. This fact can be exploited to escape local optima in the iterative resynthesis process, where individual synthesis and optimization steps are run repeatedly, in order to gradually improve the solution quality. In this chapter we show an experimental analysis of influence of variable ordering on the result quality, for different synthesis steps in ABC. Next, we present a method of using random permutations of variables in the overall iterative synthesis process, in order to improve the result quality. Experimental evaluation using both standard benchmarks and industrial circuits is presented, to show the viability of the concept.

Stať ve sborníku

10.1109/DDECS.2014.6868803

Katedra číslicového návrhu

In this paper we present an experimental analysis of robustness of Electronic Design Automation (EDA) tools, with respect to different seemingly unimportant aspects (bias) introduced by the designer, “from outside”. The algorithms employed in EDA tools should be immune to these completely, since such aspects do not carry any useful information – source files differing in these aspects are semantically equivalent. However, we show that most of the studied tools are seriously sensitive here, much more than ever reported. The results indicate, that experiments conducted to evaluate the performance of EDA tools must take such behavior into consideration. Also the notion of a benchmark is questioned.

Stať ve sborníku

Katedra číslicového návrhu

Abstract—Field Programmable Gate Arrays (FPGAs) offer great opportunity for wide range of applications. FPGA chips are also used in secure applications, where they can represent critical parts of such systems when implementing some of key functions. On one hand, FPGAs offer universal usage through their programmability, but on the other hand their complex structure is prone to several types of disturbances, one of which can be a radiation, either natural, or induced by an attacker. The response of basic CMOS structures to radiation (e.g. laser or ionizing radiation) is well documented in terms of Single Event Effects (SEE) and Single Event Upsets (SEU), but the impact of these interferences on a particular design implemented in an actual FPGA can be predicted with difficulty. This weakness can be exploited to fault-attack the target design. Although radiation attack is less probable than other types, a security device properly eliminated from service by radiation can impose a significant risk to the whole system. There are two main possibilities of testing the impact of radiation on the design dependability parameters. The first one is the Accelerated Life Test (ALT), which is based on increasing the amount of the radiation in the environment, where the device is tested. Using this method (in simple terms), the device receives the same amount of radiation as it would receive during years of operation, in few minutes. If appropriate energy spectrum of particles is used, this method gives very accurate results. The problem is that it is very expensive and not easily accessible. The alternative is to use a simulation model. To create the model, it is necessary to have a detailed description of the physical structure of the tested hardware, which is not always available for commercial FPGAs, thus we can use only approximate models. Methods allowing to classify faults in nearly all models have been published.

Stať ve sborníku

Katedra číslicového návrhu

Recently, FPGA devices are more often used in applications demanding dependability and safety. These FPGAs are, nevertheless, manufactured using CMOS technology with SRAM memory cells, which are prone to ionizing radiation. In our work we propose a method of modeling the behavior of FPGA in radiation harsh environment based on parameters obtained from experiments on real hardware. The proposed method utilizes academic toolchain VPR. By modifications of this toolchain, and from SEU characteristics gathered from ”in vivo” experiments a modeling and simulation platform for future designs can be constructed, with close-to-reality results.

Stať ve sborníku

10.1109/DSD.2013.56

Katedra číslicového návrhu

This paper presents a novel ATPG algorithm directly producing compressed test patterns. It benefits both from the features of satisfiability-based techniques and symbolic simulation. The ATPG is targeted to architectures comprised of interconnected embedded cores, particularly to the RESPIN architecture. We show experimentally that the proposed ATPG significantly outperforms the state-of-the-art approaches in terms of the test compression ratio.

Článek

10.1016/j.micpro.2012.09.010

Katedra číslicového návrhu

Testing of digital circuits seems to be a completely mastered part of the design flow, but Constrained Test Patterns Generation (CTPG) is still a highly evolving branch of digital circuits testing. Our previous research on CTPG proved that we can benefit from an implicit representation of test patterns set. The set of test patterns is implicitly represented as a Boolean formula satisfiability problem in CNF, like in common SAT-based ATPGs. However, the CTPG process can be much more memory or time consuming than common TPG, thus some techniques of speeding up the constrained SAT-based test patterns generation are described and analyzed into detail in this paper. These techniques are experimentally evaluated on a real SAT-based algorithm performing a test compression based on overlapping of test patterns. Experiments are performed on ISCAS’85, ’89 and ITC’99 benchmark circuits. Results of the experiments are discussed and recommendations for further development of similar SAT-based tools for CTPG are given.

Článek

10.1016/j.micpro.2013.06.005

Katedra číslicového návrhu

Circuits which are designed to be dependable are evaluated after gate-level design. For circuits actually implemented in programmable devices, where different fault mechanisms dominate, it is unclear whether such evaluation is relevant. To explore the difference in dependability parameters, we developed a simple method which transforms the evaluation problem into conceptual hardware and then to SAT instances. The method can accommodate any combinational fault model. We evaluated circuits constructed from benchmarks using Modified Duplex Scheme (MDS). The performed evaluation demonstrated that the dependability parameters of the implementations correlate to a significant degree. The number of points vulnerable under the chosen fault models in circuits constructed using the MDS scheme depends much more on the circuit than on implementation type.

Stať ve sborníku

Katedra číslicového návrhu

The causal connection between input circuit representation and the quality of the syn- thesis result is investigated, with special attention to the LEKU examples of Cong and Minkovich. It is shown that transformations totally obscuring the original circuit structure can enlarge the input to a great degree, that the LEKU circuits are nothing special in this respect, and that contemporary tools invariably produce poor results. On the other hand, such descriptions do not occur in practice.

Stať ve sborníku

Katedra číslicového návrhu

We present a simple method which transforms evaluation problem into conceptual hardware and then to a SAT instance. The evaluation problem over digital circuit is formulated by predicates. These predicates can be further described by logic gates which represent the circuit structure called generalized miter. Then we review the class of dependable circuits studied and present their fault classification. We demonstrate application of the proposed method on this problem, discuss fault classification results for two different implementation technologies, and finally discuss possible applications in other fields of hardware design.

Stať ve sborníku

10.1109/DDECS.2012.6219019

Katedra číslicového návrhu

We present a method of improving the iterative power of resynthesis of Boolean networks in this paper. In principle it is based on iterative resynthesis of parts of the network, instead of processing the network as a whole. The parts are randomly selected, thus more variability is introduced. The process is scalable, at least as much as the state-of-the-art. We show that our method performs better than the academic state-of-the-art, the ABC tool from Berkeley. This is documented by extensive experiments on LGSynth'93 benchmark circuits.

Stať ve sborníku

Katedra číslicového návrhu

Recently we have observed, that behavior of many contemporary logic synthesis and optimization processes depends on variable ordering in their input; they produce different results for different variable orderings. This fact can be exploited to escape local optima in the iterative resynthesis process, where individual synthesis and optimization steps are run repeatedly, in order to gradually improve the solution quality. In this paper we show an experimental analysis of influence of variable ordering on the result quality, for different synthesis steps in ABC. Next, we present a method of using random permutations of variables in the overall iterative synthesis process, in order to improve the result quality. Experimental evaluation using both standard benchmarks and industrial circuits is presented, to show the viability of the concept.

Stať ve sborníku

10.1109/DSD.2012.128

Katedra číslicového návrhu

Circuits which are designed to be dependable are evaluated after gate-level design. To demonstrate the influence of implementation technology on dependability parameters, we developed a simple method which transforms the evaluation problem into conceptual hardware and then to SAT instances. The method can accommodate any combinational fault model. The performed evaluation demonstrated that the dependability parameters of the implementations correlate to a significant degree.

Stať ve sborníku

Katedra číslicového návrhu

Most of presently used academic logic synthesis tools, including SIS and ABC, are fully deterministic. Up to the knowledge of the authors, this holds for all available commercial tools as well. This means that no random decisions are made; the algorithms fully rely on deterministic heuristics. In this paper we present several hints of insufficiency of such an approach and show examples of perspective randomized logic synthesis algorithms. Judging from our experiments, these algorithms have a higher potential of performing better than the deterministic ones. Further we study how much randomness is actually needed for the algorithms to perform well. We show that some algorithms require only a small amount of randomness, while still taking full advantage of their randomized nature. On the other hand, some algorithms require a very high level of randomness to perform well. We propose reasons for this behavior and show a way of computing the necessary measure of randomness required.

Stať ve sborníku

Katedra číslicového návrhu

Current test generation processes still have a room for improvement. One important factor is the representation of test patterns sets that a tool uses internally. This paper presents a brief overview of our research on implicit representations of test patterns set for constrained test patterns generation (CTPG). The SAT-Compress algorithm which is a simple modification of a general SAT-based ATPG (Automatic TPG) has been proposed. The set of all test patterns for a fault is represented implicitly as Boolean formula satisfiability problem in the CNF (Conjunctive Normal Form). Test patterns are compressed by overlapping. Previous experiments proved that on average 80% of the test generation time is spent on CNF generation. We have found that on average 98% of CNFs solved during CTPG process (SAT-Compress) is unsatisfiable with given constraints. These filters can detect on average 50% of UNSAT instance and accelerate the SAT-Compress more than two times.

Stať ve sborníku

10.1109/DSD.2011.50

Katedra číslicového návrhu

Testing of digital circuits seems to be a completely mastered part of the design flow, but constrained test patterns generation is still a highly evolving branch of digital circuit testing. Our previous research on constrained test pattern generation proved that we can benefit from an implicit representation of test patterns set in CNF (Conjunctive Normal Form). Some techniques of speeding up the constrained SATbased test patterns generation are described and closely analyzed in this paper. These techniques are experimentally evaluated on a real SAT-based algorithm performing a constrained test patterns compression based on overlapping of test patterns. Experiments are performed on a subset of ISCAS'85 and '89 benchmark circuits. Results of the experiments are discussed and recommendations for a further development of similar SAT-based tools for constrained test patterns generation are given.

Stať ve sborníku

Katedra číslicového návrhu

Current test generation and compression processes still have a room for improvement. One important factor is the representation of test vector sets that a tool uses internally. We overview known approaches to this problem, and present our results obtained by using an implicit representation by instances of the satisfiability problem.

Stať ve sborníku

Katedra číslicového návrhu

In this paper we investigate iterative logic synthesis processes. A well known academic logic synthesis tool ABC incorporates many synthesis algorithms and scripts which may be run iteratively to possibly improve the result. When iterating the synthesis process, the whole network is considered. We propose an alternative approach to iterative synthesis - only properly selected parts of the circuit are submitted to resynthesis, which is done iteratively. We show that a significant improvement in the result quality may be achieved. This observation is rather surprising and witnesses probably a lack of efficiency of the ABC resynthesis control. The observations are documented by numerous experiments on ISCAS and IWLS'93 benchmark circuits

Stať ve sborníku

Katedra číslicového návrhu

In this paper we propose several methods of generating large benchmark circuits for testing logic synthesis tools. The benchmarks are derived from real circuits, so that they are functionally equivalent to their origins. We introduce misleading and/or redundant structures into them, making the benchmark size blow up significantly, with respect to the original circuit. Such benchmarks can be advantageously used for testing logic synthesis tools; the aim is to discover whether particular synthesis processes are sensitive or immune to particular circuit transformations.

Stať ve sborníku

10.1109/DDECS.2010.5491755

Katedra číslicového návrhu

Recently, it has been shown that synthesis of some circuits is quite difficult for conventional methods. In this paper we present a method of minimization of multi-level logic networks which can solve these difficult circuit instances. The synthesis problem is transformed on the search problem. A search algorithm called Cartesian genetic programming (CGP) is applied to synthesize various difficult circuits. Conventional circuit synthesis usually fails for these difficult circuits; specific synthesis processes must be employed to obtain satisfactory results. We have found that CGP is able to implicitly discover new efficient circuit structures. Thus, it is able to optimize circuits universally, regardless their structure. The circuit optimization by CGP has been found especially efficient when applied to circuits already optimized by a conventional synthesis. The total runtime is reduced, while the result quality is improved further more.

Stať ve sborníku

10.1109/DSD.2010.111

Katedra číslicového návrhu

In this paper we propose a new method of test patterns compression based on a design of a dedicated SAT-based ATPG (Automatic Test Pattern Generator). This compression method is targeted to systems on chip (SoCs) provided with the P1500 test standard. The RESPIN architecture can be used for test patterns decompression. The main idea is based on finding the best overlap of test patterns during the test generation, unlike other methods, which are based on efficient overlapping of pre-generated test patterns. The proposed algorithm takes advantage of an implicit test representation as SAT problem instances. The results of test patterns compression obtained for standard ISCAS'85 and '89 benchmark circuits are shown and compared with competitive test compression methods.

Stať ve sborníku

Katedra číslicového návrhu

In this paper we propose a study of properties of SAT (satisffability) instances produced by SAT-based Automatic Test Pattern Generators (ATPGs). Standard non-commercial SAT solvers are being widely used for the purpose of solving these instances.We show an analysis of properties of these special SAT instances. Even though these ATPG SAT instances have been thoroughly studied in the past, we show some newly found properties. Particularly, reasons why ATPG SAT instances are `easy to be solved' are shown by analysis of the SAT instances. Then, unexpected behavior of ATPG SAT instances, in terms of their satisfiffability, was observed. Next, we propose solution-preserving SAT transformations and study the properties of the reduced SAT instances.

Stať ve sborníku

10.1109/DSD.2009.156

Katedra číslicového návrhu

We present experiments with synthesis tools using examples which are currently believed to be very hard, namely the LEKU examples by Cong and Minkovich and parity examples of our construction. In both cases, we found a way to produce reasonable results with existing tools. We identify the abilities that are crucial for achieving such results, and also generalize them to avoid similar cases of poor performance in future tools.

Stať ve sborníku

Katedra číslicového návrhu

Logic synthesis Examples with Known Upper bound by Cong and Minkovich are circuits hard to synthesize and map to look-up tables. During experiments with the synthesis of these examples, a way to obtain reasonable results was discovered. The crucial step is to abandon the circuit structure, and to describe the circuit independently of its structure. The feasibility of taking such an approach in general is then discussed.

Stať ve sborníku

Katedra číslicového návrhu

The analysis of Rule 60 CA by Martin, Wolfram et al. is extended to Rule 60 CA with odd cylinder size. Two classes of such CA are recognized. Their maximum attrractor length and transient characteristics are given. An application of the results for diagnostics purposes is outlined.