doc. Ing. Jan Schmidt, Ph.D.

Publications

Reducing Output Response Aliasing Using Boolean Optimization Techniques

Year
2023
Published
Proceedings of the 2023 26th International Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway: IEEE - Electron Devices Society, 2023. p. 33-38. ISSN 2473-2117. ISBN 979-8-3503-3277-3.
Type
Proceedings paper
Annotation
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.

Interval Constraint Satisfaction: Towards Edge Acceleration

Authors
Khun, J.; Schmidt, J.
Year
2022
Published
Proceedings of the 11th Mediterranean Conference on Embedded Computing (MECO 2022). Institute of Electrical and Electronics Engineers, Inc., 2022. p. 1-4. ISSN 2377-5475. ISBN 978-1-6654-6828-2.
Type
Proceedings paper
Annotation
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.

Nonlinear codes for test patterns compression: the old school way

Year
2021
Published
Recent Findings in Boolean Techniques. Cham: Springer International Publishing AG, 2021. p. 125-142. 1. ISBN 978-3-030-68070-1.
Type
Book chapter
Annotation
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.

Optically induced static power in combinational logic: Vulnerabilities and countermeasures

Year
2021
Published
Microelectronics Reliability. 2021, 124 ISSN 0026-2714.
Type
Article
Annotation
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.

Satisfiability Modulo Simulation: What Can It Do?

Authors
Khun, J.; Schmidt, J.
Year
2021
Published
Proceedings of the 9th Prague Embedded Systems Workshop. Praha: Czech Technical University in Prague, 2021. p. 32-41. ISBN 978-80-01-06858-8.
Type
Proceedings paper
Annotation
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.

Nonlinear codes for test patterns compression: the old school way

Year
2020
Published
Proc. of 14th International Workshop on Boolean Problems. Bremen: University of Bremen/DFKI GmbH, 2020. p. 1-16.
Type
Proceedings paper
Annotation
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.

Novel Partial Correlation Method Algorithm for Acquisition of GNSS Tiered Signals

Authors
Svatoň, J.; Vejražka, F.; Schmidt, J.; Kubalík, P.; Borecký, J.
Year
2020
Published
Navigation. 2020, 67(4), 745-762. ISSN 0028-1522.
Type
Article
Annotation
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.

Standard Cell Tuning Enables Data-Independent Static Power Consumption

Year
2020
Published
Proceedings of the 23rd International Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway, NJ: IEEE, 2020. ISSN 2334-3133. ISBN 978-1-7281-9938-2.
Type
Proceedings paper
Annotation
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.

Analyzing and Optimizing the Dummy Rounds Scheme

Year
2019
Published
Proceedings of the 22nd International Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway, NJ: IEEE, 2019. p. 1-4. ISBN 978-1-7281-0073-9.
Type
Proceedings paper
Annotation
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.

CMOS Illumination Discloses Processed Data

Year
2019
Published
Proceedings of the 22nd Euromicro Conference on Digital Systems Design. Los Alamitos, CA: IEEE Computer Soc., 2019. p. 381-388. ISBN 978-1-7281-2861-0.
Type
Proceedings paper
Annotation
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.

SAT-Based Generation of Optimum Circuits with Polymorphic Behavior Support

Authors
Fišer, P.; Háleček, I.; Schmidt, J.; Šimek, V.
Year
2019
Published
JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS. 2019, 28(Supp01), ISSN 0218-1266.
Type
Article
Annotation
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.

Using Voters May Lead to Secret Leakage

Year
2019
Published
Proceedings of the 22nd International Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway, NJ: IEEE, 2019. p. 1-4. ISBN 978-1-7281-0073-9.
Type
Proceedings paper
Annotation
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.

A Prudent Approach to Collection of Examples for Logic Synthesis and Optimization

Year
2018
Published
Further Improvements in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2018. p. 280-301. ISBN 978-1-5275-0371-7.
Type
Book chapter
Annotation
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.

Dummy Rounds as a DPA countermeasure in hardware

Year
2018
Published
Proceedings of the 21st Euromicro Conference on Digital System Design. Piscataway: IEEE, 2018. p. 523-528. ISBN 978-1-5386-7376-8.
Type
Proceedings paper
Annotation
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.

Dummy Rounds jako opatření proti DPA v hardwaru

Year
2018
Published
Počítačové architektury a diagnostika 2018. Plzeň: Západočeská univerzita v Plzni, 2018. p. 33-36. ISBN 978-80-261-0814-6.
Type
Proceedings paper
Annotation
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.

Proposal of a Memory Architecture for Pre and Post-Correlation coherent Processing of GNSS Signal with SoC based Acquisition Uni

Authors
Svatoň, J.; Vejražka, F.; Kubalík, P.; Schmidt, J.
Year
2018
Published
Proceedings of the 6th Prague Embedded Systems Workshop. ČVUT v Praze, Fakulta informačních technologií, 2018. p. 21-25. ISBN 978-80-01-06456-6.
Type
Proceedings paper
Annotation
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

Towards AND/XOR balanced synthesis: Logic circuits rewriting with XOR

Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2018
Published
Microelectronics Reliability. 2018, 81 274-286. ISSN 0026-2714.
Type
Article
Annotation
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.

XOR-Based Synthesis: Does it Pay off?

Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2018
Published
Proc. of 13th International Workshop on Boolean Problems. Bremen: University of Bremen/DFKI GmbH, 2018. p. 167-176.
Type
Proceedings paper
Annotation
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.

ZATPG: SAT-based Test Patterns Generator with Zero-Aliasing in Temporal Compaction

Year
2018
Published
Microprocessors and Microsystems. 2018, 2018(61), 43-57. ISSN 0141-9331.
Type
Article
Annotation
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.

Acquisition of Modern GNSS Signals in SoC ZYNQ with its Limited Computational Resources in Frequency Domain

Authors
Svatoň, J.; Vejražka, F.; Kubalík, P.; Schmidt, J.
Year
2017
Published
Proceedings of the 5th Prague Embedded Systems Workshop. Praha: katedra číslicového návrhu, 2017. pp. 64-66. ISBN 978-80-01-06178-7.
Type
Proceedings paper
Annotation
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.

Are XORs in logic synthesis really necessary?

Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2017
Published
Proceedings of the 2017 IEEE 20th International Symposium on Design and Diagnotics of Electronic Circuit & Systems. Piscataway, NJ: IEEE, 2017. p. 134-139. ISSN 2473-2117. ISBN 978-1-5386-0472-4.
Type
Proceedings paper
Annotation
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.

Dynamic Reconfiguration as Countermeasure against DPA

Year
2017
Published
Počítačové architektúry & diagnostika PAD 2017 - Zborník príspevkov. Bratislava: STU Scientific, 2017. ISBN 978-80-972784-0-3.
Type
Proceedings paper
Annotation
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.

Dynamic Reconfiguration as Countermeasure against DPA

Year
2017
Published
Proceedings of the Work in Progress Session SEAA/DSD 2017. Linz: Johannes Kepler University, 2017. ISBN 978-3-902457-48-6.
Type
Proceedings paper
Annotation
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.

Emulator of Contactless Smart Cards in FPGA

Year
2017
Published
Proceedings of the 6th Mediterranean Conference on Embedded Computing (MECO 2017). IEEE (Institute of Electrical and Electronics Engineers), 2017. p. 96-99. ISBN 978-1-5090-6741-1.
Type
Proceedings paper
Annotation
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.

Error Masking Method Based On The Short-Duration Offline Test

Year
2017
Published
Microprocessors and Microsystems. 2017, 52 236-250. ISSN 0141-9331.
Type
Article
Annotation
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.

Methods and Hardware achitecture for Multi-constellation GNSS signal acqusition unit in frequency domain

Authors
Svatoň, J.; Vejražka, F.; Kubalík, P.; Schmidt, J.
Year
2017
Published
ENC2017_Programme_NonCopyright. Lausanne: The Swiss Institute of Navigation, 2017. pp. 252-261.
Type
Proceedings paper
Annotation
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.

On Quality in Experimental Evaluation

Authors
Year
2017
Published
Proceedings of the Eighteenth International Symposium on Quality Electronic Design ISQED 2017. Piscataway, NJ: IEEE, 2017. p. 1-466. ISSN 1948-3287. ISBN 978-1-5090-5404-6.
Type
Invited/Awarded proceedings paper
Annotation
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.

On XAIG Rewriting

Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2017
Published
Proc. of 26th International Workshop on Logic & Synthesis. Bremen: University of Bremen/DFKI GmbH, 2017. p. 89-96.
Type
Proceedings paper
Annotation
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.

SAT-based ATPG for Zero-Aliasing Compaction

Year
2017
Published
Proc. of the 20th Euromicro Conference on Digital System Design. Piscataway, NJ: IEEE, 2017. p. 307-314. ISBN 978-1-5386-2146-2.
Type
Proceedings paper
Annotation
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.

SAT-Based Generation of Optimum Function Implementations with XOR Gates

Authors
Fišer, P.; Háleček, I.; Schmidt, J.
Year
2017
Published
Proc. of the 20th Euromicro Conference on Digital System Design. Piscataway, NJ: IEEE, 2017. p. 163-170. ISBN 978-1-5386-2146-2.
Type
Proceedings paper
Annotation
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.

Test Patterns Generation with Zero-Aliasing

Year
2017
Published
Počítačové architektúry & diagnostika PAD 2017 - Zborník príspevkov. Bratislava: STU Scientific, 2017. pp. 35-38. ISBN 978-80-972784-0-3.
Type
Proceedings paper
Annotation
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.

A Comprehensive Set of Logic Synthesis and Optimization Examples

Year
2016
Published
Proceedings of the 12th International Workshop on Boolean Problems. Freiberg: Freiberg University of Mining and Technology, Institute of Computer Science, 2016. p. 151-158. ISBN 978-3-86012-540-3.
Type
Proceedings paper
Annotation
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.

A Prudent Approach to Benchmark Collection

Year
2016
Published
Proceedings of the 12th International Workshop on Boolean Problems. Freiberg: Freiberg University of Mining and Technology, Institute of Computer Science, 2016. pp. 129-136. ISBN 978-3-86012-540-3.
Type
Proceedings paper
Annotation
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.

Error Correction Method Based on the Short-Duration Offline Test

Year
2016
Published
Proceedings of 19th Euromicro Conference on Digital System Design DSD 2016. Los Alamitos, CA: IEEE Computer Soc., 2016. p. 495-502. ISBN 978-1-5090-2816-0.
Type
Proceedings paper
Annotation
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.

Generating Test for BIST

Year
2016
Published
Počítačové Architektury & Diagnostika PAD 2016 - Sborník příspěvků. Brno: Vysoké učení technické v Brně, 2016. ISBN 978-80-214-5376-0.
Type
Proceedings paper
Annotation
In this paper, I summarize results of my research in the 1st year of doctoral study, comparison of fault models for use in application-oriented FPGA testing, examination of properties of SAT instances encountered in an ATPG process. Additionally I present next possible research, generating test with zero aliasing.

Logická syntéza s nativní podporou XOR hradel

Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2016
Published
Počítačové Architektury & Diagnostika PAD 2016 - Sborník příspěvků. Brno: Vysoké učení technické v Brně, 2016. ISBN 978-80-214-5376-0.
Type
Proceedings paper
Annotation
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.

SAT-ATPG for Application-Oriented FPGA Testing

Year
2016
Published
Proceedings of the 15th Biennial Baltic Electronics Conference. Tallin: Tallin University of Technology, 2016. p. 83-86. ISSN 1736-3705. ISBN 978-1-5090-1393-7.
Type
Proceedings paper
Annotation
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.

Towards Understanding the Performance of Randomized Algorithms

Authors
Schmidt, J.; Blažek, R.; Fišer, P.
Year
2016
Published
Problems and New Solutions in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2016. p. 167-186. ISBN 978-1-4438-8947-6.
Type
Book chapter
Annotation
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.

Introduction to Lethal Circuit Transformations

Year
2015
Published
AIP Conference Proceedings. Melville, NY: AIP Publishing, 2015. p. 1-4. ISSN 0094-243X. ISBN 978-0-7354-1349-8.
Type
Proceedings paper
Annotation
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.

Novel C-Element Based Error Detection and Correction Method Combining Time and Area Redundancy

Year
2015
Published
Proceedings of the Euromicro Conference on Digital System Design - DSD 2015. Los Alamitos: IEEE Computer Society, 2015. p. 280-283. ISBN 978-1-4673-8035-5.
Type
Proceedings paper
Annotation
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.

On Identification of XOR Gates in AIGs

Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2015
Published
Proceedings of the Work in Progress Session of the 18th EUROMICRO Conference on Digital System Design. Sangt Augustin: Euromicro, 2015, ISBN 978-3-902457-44-8.
Type
Proceedings paper
Annotation
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.

On don't cares in test compression

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2014
Published
Microprocessors and Microsystems. 2014, 38(8), 754-765. ISSN 0141-9331.
Type
Article
Annotation
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.

On Probability Density Distribution of Randomized Algorithms Performance

Authors
Schmidt, J.; Blažek, R.; Fišer, P.
Year
2014
Published
Proceedings of the 11th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2014, pp. 67-74. ISBN 978-3-86012-488-8.
Type
Proceedings paper
Annotation
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.

On Robustness of EDA Tools

Authors
Schmidt, J.; Fišer, P.; Balcárek, J.
Year
2014
Published
Proceedings of 2014 17th Euromicro Conference. Piscataway: IEEE, 2014. p. 427-434. ISBN 978-1-4799-5793-4.
Type
Proceedings paper
Annotation
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.

PBO-Based Test Compression

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2014
Published
Proceedings of 2014 17th Euromicro Conference. Piscataway: IEEE, 2014. p. 679-682. ISBN 978-1-4799-5793-4.
Type
Proceedings paper
Annotation
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.

Permuting Variables to Improve Iterative Resynthesis

Year
2014
Published
Recent Progress in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2014. p. 213-230. ISBN 978-1-4438-5638-6.
Type
Book chapter
Annotation
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.

Sources of Bias in EDA Tools and Its Influence

Authors
Fišer, P.; Schmidt, J.; Balcárek, J.
Year
2014
Published
Proceedings of the 2014 IEEE 17th International Symposium on Design and Diagnostics of Electronic Circuits & Systems. Piscataway: IEEE, 2014. p. 258-261. ISSN 2334-3133. ISBN 978-1-4799-4558-0.
Type
Proceedings paper
Annotation
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.

Towards Trusted Devices in FPGA by Modeling

Authors
Pospíšil, J.; Vaňát, T.; Schmidt, J.
Year
2014
Published
Proceedings of the 2nd Prague Embedded Systems Workshop. 2014, pp. 16.
Type
Proceedings paper
Annotation
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.

New SEU Modeling by Architecture Analysis

Authors
Pospíšil, J.; Schmidt, J.; Fišer, P.
Year
2013
Published
Proceeding of the Work in Progress Session of 16th Euromicro Conference on Digital System Design. 2013, ISBN 978-3-902457-38-7.
Type
Proceedings paper
Annotation
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.

Simulation and SAT Based ATPG for Compressed Test Generation

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2013
Published
Proceedings of 16th Euromicro Conference on Digital System Design. Piscataway: IEEE Service Center, 2013. p. 445-452. ISBN 978-0-7695-5074-9.
Type
Proceedings paper
Annotation
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.

Techniques for SAT-Based Constrained Test Pattern Generation

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2013
Published
Microprocessors and Microsystems. 2013, 37(2), 185-195. ISSN 0141-9331.
Type
Article
Annotation
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.

The influence of implementation type on dependability parameters

Authors
Schmidt, J.; Fišer, P.; Balcárek, J.
Year
2013
Published
Microprocessors and Microsystems. 2013, 6-7(37), 641-648. ISSN 0141-9331.
Type
Article
Annotation
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.

A Difficult Example Or a Badly Represented One?

Year
2012
Published
Proc. of 10th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2012, pp. 115-122. ISBN 978-3-86012-438-3.
Type
Proceedings paper
Annotation
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.

Generalized Miter and its Application in Hardware Design

Authors
Schmidt, J.; Fišer, P.; Balcárek, J.
Year
2012
Published
Proceedings of the 8th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: NOVPRESS, 2012, pp. 119-120. ISBN 978-80-87342-15-2.
Type
Proceedings paper
Annotation
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.

Improving the Iterative Power of Resynthesis

Year
2012
Published
Proceedings of the 2012 IEEE 15th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). New York: IEEE Computer Society Press, 2012. p. 30-33. ISBN 978-1-4673-1185-4.
Type
Proceedings paper
Annotation
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.

On Using Permutation of Variables to Improve the Iterative Power of Resynthesis

Year
2012
Published
Proc. of 10th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2012. p. 107-114. ISBN 978-3-86012-438-3.
Type
Proceedings paper
Annotation
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.

The Influence of Implementation Technology on Dependability Parameters

Authors
Schmidt, J.; Fišer, P.; Balcárek, J.
Year
2012
Published
Proceedings of the 15th Euromicro Conference on Digital System Design. Los Alamitos: IEEE Computer Society Press, 2012, pp. 368-373. ISBN 978-0-7695-4798-5.
Type
Proceedings paper
Annotation
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.

How Much Randomness Makes a Tool Randomized?

Year
2011
Published
Proc. of 20th International Workshop on Logic and Synthesis 2011. La Jolla: University of California San Diego, 2011, pp. 136-143.
Type
Proceedings paper
Annotation
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.

Implicit Techniques for Constrained Test Patterns Generation

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2011
Published
Proceeding of the 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Brno University of Technology, 2011, pp. 106. ISBN 978-80-214-4305-1.
Type
Proceedings paper
Annotation
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.

Techniques for SAT-Based Constrained Test Pattern Generation

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2011
Published
Proceedings of the 14th Euromicro Conference on Digital System Design. Los Alamitos: IEEE Computer Society Press, 2011. p. 360-366. ISBN 978-0-7695-4494-6.
Type
Proceedings paper
Annotation
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.

Implicit Representations in Test Patterns Compression for Scan-Based Digital Circuits

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2010
Published
Informal Proceedings of European Test Symposium. Praha: ČVUT v Praze, 2010,
Type
Proceedings paper
Annotation
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.

It Is Better to Run Iterative Resynthesis on Parts of the Circuit

Year
2010
Published
Proceedings of the 19th International Workshop on Logic and Synthesis. Irvine, CA: University of California, Irvine, 2010. p. 17-24.
Type
Proceedings paper
Annotation
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

New Ways of Generating Large Realistic Benchmarks for Testing Synthesis Tools

Year
2010
Published
Proceedings of the 9th International Workshop on Boolean Problems. Freiberg: Freiberg University of Mining and Technology, Institute of Computer Science, 2010, pp. 157-164. ISBN 978-3-86012-404-8.
Type
Proceedings paper
Annotation
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.

On Logic Synthesis of Conventionally Hard to Synthesize Circuits Using Genetic Programming

Authors
Fišer, P.; Schmidt, J.; Sekanina, L.; Vašíček, Z.
Year
2010
Published
Proc. of the 13th IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway: IEEE, 2010. p. 346-351. ISBN 978-1-4244-6613-9.
Type
Proceedings paper
Annotation
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.

Test Patterns Compression Technique Based on a Dedicated SAT-Based ATPG

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2010
Published
Proceedings of the 13th Euromicro Conference on Digital System Design. Los Alamitos: IEEE Computer Society Press, 2010. p. 805-808. ISBN 978-0-7695-4171-6.
Type
Proceedings paper
Annotation
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.

On Properties of SAT Instances Produced by SAT-Based ATPGs

Authors
Balcárek, J.; Fišer, P.; Schmidt, J.
Year
2009
Published
Fifth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: neuveden, 2009, pp. 3-10. ISBN 978-80-87342-04-6.
Type
Proceedings paper
Annotation
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.

The Case for a Balanced Decomposition Process

Year
2009
Published
Proc. of 12th EUROMICRO Conference on Digital System Design. Los Alamitos: IEEE Computer Society, 2009. p. 601-604. ISBN 978-0-7695-3782-5.
Type
Proceedings paper
Annotation
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.

The Observed Role of Structure in Logic Synthesis Examples

Year
2009
Published
Proceedings of the International Workshop on Logic and Synthesis 2009. Berkeley, CA: IWLS Organizing Committee, 2009. p. 210-213.
Type
Proceedings paper
Annotation
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.

The Attractor Structure of Rule 60 Cellular Automata

Authors
Year
2006
Published
Proceedings of the 7th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2006, pp. 151-158. ISBN 3-86012-287-8.
Type
Proceedings paper
Annotation
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.