Aktuální informace FIT ke koronaviru najdete zde.

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

Publikace

Emerging Technologies: Challenges and Opportunities for Logic Synthesis

Autoři
Fišer, P.; Bosio, A.; Cantan, M.; Marchand, C.; O'Connor, I.; Poittevin, A.; Traiola, M.
Rok
2021
Publikováno
Proceedings of 24th International Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway (New Jersey): IEEE, 2021. p. 93-98. ISBN 978-1-6654-3595-6.
Typ
Stať ve sborníku
Anotace
In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior is turned into a design implementation in terms of logic gates. Historically, logic synthesis was tightly related to the physical implementation of the logic gates. Nowadays, pushed by the forecasted end of Moore's law, several emerging technologies (e.g., nanodevices, optical computing, quantum computing) are candidates to either replace or co-exist with the \textit{de facto} standard CMOS technology. The main consequence of the rising of those emerging technologies is that the logic synthesis has to face new issues and, at the same time, exploits new opportunities. The goal of this paper is thus to present three emerging technologies (Vertical Nanowire Field Effect Transistors, Ferroelectric Transistors, and Memristors), how to use them to implement logic gates, and the main challenges and issues for the logic synthesis.

Minimization of Switching Activity of Graphene Based Circuits

Autoři
Fišer, P.; Das, S.; Pandit, S.; Das, D.K.
Rok
2021
Publikováno
Proc. of the 34th International Conference on VLSI Design. Piscataway (New Jersey): IEEE, 2021. p. 139-144. ISSN 1063-9667. ISBN 978-1-6654-3127-9.
Typ
Stať ve sborníku
Anotace
Reduction of power dissipation is a key challenge of VLSI circuits designers. In traditional CMOS-based circuits, dynamic power dissipation occurs due to the switching activity, i.e., transitions at logic nodes. In graphene-based circuits, power dissipation is also caused by the switching activity. In this paper, we compute the switching activity of these circuits considering the switching at every transistor. We propose an algorithm to minimize the total switching activity of graphene-based logic circuits. The algorithm is tested on benchmark circuits and the results show the reduction of average switching activity, area, and switching activity x area respectively by 9,17%, 0,81%, and 9,82%.

Nonlinear codes for test patterns compression: the old school way

Rok
2020
Publikováno
Proc. of 14th International Workshop on Boolean Problems. Bremen: University of Bremen/DFKI GmbH, 2020. p. 1-16.
Typ
Stať ve sborníku
Anotace
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.

CMOS Illumination Discloses Processed Data

Rok
2019
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.; Šimek, V.
Rok
2019
Publikováno
JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS. 2019, 28(Supp01), ISSN 0218-1266.
Typ
Článek
Anotace
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

Rok
2019
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Rok
2018
Publikováno
Further Improvements in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2018. p. 280-301. ISBN 978-1-5275-0371-7.
Typ
Kapitola v knize
Anotace
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.

Optimum Polymorphic Circuits Synthesis Method

Autoři
Fišer, P.; Šimek, V.
Rok
2018
Publikováno
Proc. of 13th IEEE International Conference on Design and Technology of Integrated Systems in nanoscale era. Piscataway, NJ: IEEE, 2018. p. 1-6. ISBN 978-1-5386-5291-6.
Typ
Stať ve sborníku
Anotace
Polymorphic circuits represent a newly emerging computation paradigm, where one hardware structure is capable to perform two or more different intended functions, depending on instantaneous conditions in the target operating environment. Due to the peculiarity of this paradigm, design of these circuits also calls for a novel approach to logic synthesis procedures. Several attempts to enhance the design of such circuits have already been made, producing highly suboptimal solutions. As an ingenious attempt to set lower bounds on complexity and support designers of sophisticated logic synthesis algorithms, a method with the prospect to facilitate the generation of optimum-size polymorphic circuits is presented in this paper. The core of the proposed method is based on a purposeful exploitation of formal techniques, comprising SAT and PBO in the first place.

Synthesis of Finite State Machines on Memristor Crossbars

Autoři
Fišer, P.; Ferrandino, U.; Traiola, M.; Barbareschi, M.; Mazzeo, A.; Bosio, A.
Rok
2018
Publikováno
Proc. of 2018 IEEE 21st International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Piscataway, NJ: IEEE, 2018. p. 107-112. ISBN 978-1-5386-5755-3.
Typ
Stať ve sborníku
Anotace
Memristor device represents one of the most relevant technologies to deal with CMOS technological issues. In the scientific literature, a relevant amount of works have discussed the memristor device, with a particular emphasis on memristor-based crossbar architectures. However, while the synthesis of combinational logic circuits is widely discussed, the same cannot be said for sequential logic circuits. In this work, we propose a new approach for synthesizing sequential circuits based on memristor crossbar, by enhancing an existing architecture. This approach only exploits memristors within the crossbar for implementing the state feedback mechanism, with the aim of advancing the integration process of memristor-based circuits. Moreover, to provide an automated synthesis process of memristor-based sequential circuits, we extend a pre-existing automated synthesis framework so it can be integrated with widely used tools and formats as register-transfer level (RTL) or Berkeley Logic Interchange Format (BLIF) files. We performed several experiments on publicly available benchmarks in order to compare the proposed architecture against its predecessor in terms of circuit integration and efficiency. Obtained results highlight acceptable overheads (up to a maximum of 24%) compared with the opportunity of integration offered by the proposed architecture.

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

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2018
Publikováno
Microelectronics Reliability. 2018, 81 274-286. ISSN 0026-2714.
Typ
Článek
Anotace
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?

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2018
Publikováno
Proc. of 13th International Workshop on Boolean Problems. Bremen: University of Bremen/DFKI GmbH, 2018. p. 167-176.
Typ
Stať ve sborníku
Anotace
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

Rok
2018
Publikováno
Microprocessors and Microsystems. 2018, 2018(61), 43-57. ISSN 0141-9331.
Typ
Článek
Anotace
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.

Are XORs in logic synthesis really necessary?

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2017
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Error Masking Method Based On The Short-Duration Offline Test

Rok
2017
Publikováno
Microprocessors and Microsystems. 2017, 52 236-250. ISSN 0141-9331.
Typ
Článek
Anotace
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.

Generovánı́ testu s nulovým maskovánı́m poruch

Rok
2017
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

On XAIG Rewriting

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2017
Publikováno
Proc. of 26th International Workshop on Logic & Synthesis. Bremen: University of Bremen/DFKI GmbH, 2017. p. 89-96.
Typ
Stať ve sborníku
Anotace
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

Rok
2017
Publikováno
Proc. of the 20th Euromicro Conference on Digital System Design. Piscataway, NJ: IEEE, 2017. p. 307-314. ISBN 978-1-5386-2146-2.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2017
Publikováno
Proc. of the 20th Euromicro Conference on Digital System Design. Piscataway, NJ: IEEE, 2017. p. 163-170. ISBN 978-1-5386-2146-2.
Typ
Stať ve sborníku
Anotace
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.

A Comprehensive Set of Logic Synthesis and Optimization Examples

Rok
2016
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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 New Method for Path Criticality Calculation

Autoři
Fišer, P.; Tamáši, R.; Siebert, M.; Gramatová, E.
Rok
2016
Publikováno
Proceedings of the 2016 IEEE 19th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Piscataway: IEEE, 2016. p. 190-193. ISSN 2334-3133. ISBN 978-1-5090-2467-4.
Typ
Stať ve sborníku
Anotace
Technology scaling and manufacturing process affect the performance of digital circuits, making them more vulnerable to environmental influences. Some defects are shown manifested as delay faults. Some various factors have impact to signal propagation delay. A new method is presented for determining factors impact measurement on the path delay in the digital circuits. The method is focused to find the best weights of the factors used as parameters for the PaCGen (Parameterized Critical Path Generator) system. PaCGen is used for critical paths selection based on static timing analysis data with impact of factors to propagation delay. Experimental results are provided using the ISCAS'89 benchmark circuits.

A New User-Friendly ATPG Platform for Digital Circuits

Autoři
Fišer, P.; Lipovský, M.; Švarc, J.; Gramatová, E.
Rok
2016
Publikováno
Proceedings of the 2016 IEEE 19th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Piscataway: IEEE, 2016. p. 210-213. ISSN 2334-3133. ISBN 978-1-5090-2467-4.
Typ
Stať ve sborníku
Anotace
The paper presents a new graphical platform for automatic test patterns generation and fault simulation for digital circuits. The platform integrates two existing academic tools for test pattern generation and fault simulation: ATALANTA and HOPE. Both tools use a specific format “bench” for circuit description which is not suitable in connection to professional CAD tools. Therefore, the platform has been extended by a new translator for mapping a VHDL digital circuit model to the format “bench”. The platform contains also a separate random test patterns generator linked to the fault simulator HOPE and generation of test pairs for delay faults using the transition fault model. The new automatic test pattern generation platform provides a user-friendly environment suitable for education.

A Prudent Approach to Benchmark Collection

Rok
2016
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

A Rule-Based Approach for Minimizing Power Dissipation of Digital Circuits

Autoři
Fišer, P.; Das, S.; Dasgupta, P.; Ghosh, S.; Das, D. K.
Rok
2016
Publikováno
Proceedings of the 2016 IEEE 19th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Piscataway: IEEE, 2016. p. 237-242. ISSN 2334-3133. ISBN 978-1-5090-2467-4.
Typ
Stať ve sborníku
Anotace
Minimization of power dissipation of VLSI circuits is one of the major concerns of recent digital circuit design primarily due to the ever decreasing feature sizes of circuits, higher clock frequencies and larger die sizes. The primary contributors to power dissipation in digital circuits include leakage power, short-circuit power and switching power. Of these, power dissipation due to the circuit switching activity constitutes the major component. As such, an effective mechanism to minimize the power loss in such cases often involves the minimization of the switching activity. In this paper, we propose an intelligent rule-based algorithm for reducing the switching activity of the digital circuits at logic optimization stage. The proposed algorithm is empirically tested for several standard digital circuits with Synopsys EDA tool and the results obtained are quite encouraging.

Error Correction Method Based on the Short-Duration Offline Test

Rok
2016
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Generovánı́ testu pro prostředky vestavěné diagnostiky

Rok
2016
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Logická syntéza s nativní podporou XOR hradel

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2016
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Rok
2016
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Schmidt, J.; Fišer, P.; Blažek, R.
Rok
2016
Publikováno
Problems and New Solutions in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2016. p. 167-186. ISBN 978-1-4438-8947-6.
Typ
Kapitola v knize
Anotace
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.

A New Method for Speficication of Parameters to Path Delay Fautls Testing

Autoři
Fišer, P.; Tamaši, R.; Siebert, M.
Rok
2015
Publikováno
Proceedings of the 3rd Prague Embedded Systems Workshop. Praha: ČVUT FIT, Katedra číslicového návrhu, 2015. p. 26-32. ISBN 978-80-01-05776-6.
Typ
Stať ve sborníku
Anotace
Technology scaling and manufacturing process affect the performance of digital circuits, making them more vulnerable to environmental influences. Some defects are shown as delay faults, therefore their testing is very important, mainly for path delay faults. Such faults are tested over critical paths which have to be specified in a digital circuit. A problem of the critical paths selection is discussed in this paper. Some various factors have impact to signal propagation delay. A new method is presented for determining the measurement of the parameters impact on the path delay in the digital circuit. The method is focused to find the best weights of parameters for system PaCGen (Parameterized Critical Path Generator). The PaCGen is system for critical paths selection based on static timing analysis data with impact of factors to propagation delay. Accordingly, the critical paths are selected to be used for simulating fault coverage of path delay faults on transition delay fault model. Experimental results are provided using the ISCAS’89 benchmark circuits.

Introduction to Lethal Circuit Transformations

Rok
2015
Publikováno
AIP Conference Proceedings. Melville, NY: AIP Publishing, 2015. p. 1-4. ISSN 0094-243X. ISBN 978-0-7354-1349-8.
Typ
Stať ve sborníku
Anotace
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

Rok
2015
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Háleček, I.
Rok
2015
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Asynchronous sum-of-products logic minimization and orthogonalization

Autoři
Fišer, P.; Lemberski, I.; Suleimanov, R.
Rok
2014
Publikováno
International Journal of Circuit Theory and Applications. 2014, 42(6), 562-571. ISSN 0098-9886.
Typ
Článek
Anotace
We propose a method of the asynchronous sum-of-products (SOP) logic simplification that comprises of minimization and orthogonalization. The method is based on a transformation of the conventional single-rail SOP synchronous logic into the dual-rail asynchronous one operating under so-called modified weak constraints. We formulate and prove the product terms constraint that ensures a correct logic behavior. We have processed the MCNC benchmarks and generated the asynchronous SOP logic. The complexity of the logic obtained is compared with the state-of-the-art representation. Using our approach, we achieve a significant improvement. Copyright ˆ 2012 John Wiley & Sons, Ltd.

Dual-Rail Asynchronous Logic Multi-Level Implementation

Autoři
Fišer, P.; Lemberski, I.
Rok
2014
Publikováno
Integration, the VLSI Journal. 2014, 47(1), 148-159. ISSN 0167-9260.
Typ
Článek
Anotace
A synthesis flow oriented on producing the delay-insensitive dual-rail asynchronous logic is proposed. Within this flow, the existing synchronous logic synthesis tools are exploited to design technology independent single-rail synchronous Boolean network of complex (AND-OR) nodes. Next, the transformation into a dual-rail Boolean network is done. Each node is minimized under the formulated constraint to ensure hazard-free implementation. Then the technology dependent mapping procedure is applied. The MCNC and ISCAS benchmark sets are processed and the area overhead with respect to the synchronous implementation is evaluated. The implementations of the asynchronous logic obtained using the proposed (with AND-OR nodes) and the state-of-the-art (nodes are designed based on DIMS, direct logic, NCL) network structures are compared. A method, where nodes are designed as simple (NAND, NOR, etc.) gates is chosen for a detailed comparison. In our approach, the number of completion detection logic inputs is reduced significantly, since the number of nodes that should be supplied with the completion detection is less than in the case of the network structure that is based on simple gates. As a result, the improvement in sense of the total complexity and performance is obtained.

On don't cares in test compression

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2014
Publikováno
Microprocessors and Microsystems. 2014, 38(8), 754-765. ISSN 0141-9331.
Typ
Článek
Anotace
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

Autoři
Schmidt, J.; Fišer, P.; Blažek, R.
Rok
2014
Publikováno
Proceedings of the 11th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2014, pp. 67-74. ISBN 978-3-86012-488-8.
Typ
Stať ve sborníku
Anotace
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

Autoři
Schmidt, J.; Fišer, P.; Balcárek, J.
Rok
2014
Publikováno
Proceedings of 2014 17th Euromicro Conference. Piscataway: IEEE, 2014. p. 427-434. ISBN 978-1-4799-5793-4.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2014
Publikováno
Proceedings of 2014 17th Euromicro Conference. Piscataway: IEEE, 2014. p. 679-682. ISBN 978-1-4799-5793-4.
Typ
Stať ve sborníku
Anotace
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

Rok
2014
Publikováno
Recent Progress in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2014. p. 213-230. ISBN 978-1-4438-5638-6.
Typ
Kapitola v knize
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2014
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Weighted Don't Cares in Logic Synthesis

Autoři
Fišer, P.; Bernasconi, A.; Ciriani, V.; Trucco, G.
Rok
2014
Publikováno
Recent Progress in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2014. p. 263-277. ISBN 978-1-4438-5638-6.
Typ
Kapitola v knize
Anotace
In this paper we introduce and discuss the new concept of weighted don’t cares, i.e., we propose to enrich the notion of don’t cares, by assigning them a weight. These weights might be used to guide and refine the choices operated by the minimization algorithms in handling the don’t care conditions. We then propose, and experimentally validate, the first synthesis tool for functions with weighted don’t cares, called wBOOM. Experimental results show that wBOOM covers, on average, 66% more weighted don’t cares than the classical synthesis tool BOOM.

New SEU Modeling by Architecture Analysis

Autoři
Schmidt, J.; Fišer, P.; Pospíšil, J.
Rok
2013
Publikováno
Proceeding of the Work in Progress Session of 16th Euromicro Conference on Digital System Design. 2013, ISBN 978-3-902457-38-7.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2013
Publikováno
Proceedings of 16th Euromicro Conference on Digital System Design. Piscataway: IEEE Service Center, 2013. p. 445-452. ISBN 978-0-7695-5074-9.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2013
Publikováno
Microprocessors and Microsystems. 2013, 37(2), 185-195. ISSN 0141-9331.
Typ
Článek
Anotace
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

Autoři
Schmidt, J.; Fišer, P.; Balcárek, J.
Rok
2013
Publikováno
Microprocessors and Microsystems. 2013, 6-7(37), 641-648. ISSN 0141-9331.
Typ
Článek
Anotace
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?

Rok
2012
Publikováno
Proc. of 10th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2012, pp. 115-122. ISBN 978-3-86012-438-3.
Typ
Stať ve sborníku
Anotace
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

Autoři
Schmidt, J.; Fišer, P.; Balcárek, J.
Rok
2012
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Rok
2012
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Rok
2012
Publikováno
Proc. of 10th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2012. p. 107-114. ISBN 978-3-86012-438-3.
Typ
Stať ve sborníku
Anotace
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

Autoři
Schmidt, J.; Fišer, P.; Balcárek, J.
Rok
2012
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Weighted Don't Cares

Autoři
Fišer, P.; Bernasconi, A.; Ciriani, V.; Trucco, G.
Rok
2012
Publikováno
Proc. of 10th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2012, pp. 123-130. ISBN 978-3-86012-438-3.
Typ
Stať ve sborníku
Anotace
In this paper we introduce and discuss the new concept of weighted don't cares, i.e., we propose to enrich the notion of don't cares, by assigning them a weight. These weights might be used to guide and refine the choices operated by the minimization algorithms in handling the don't care conditions. We then propose, and experimentally validate, the first synthesis tool for functions with weighted don't cares, called wBOOM. Experimental results show that wBOOM covers, on average, 66% more weighted don't cares than the classical synthesis tool BOOM.

How Much Randomness Makes a Tool Randomized?

Rok
2011
Publikováno
Proc. of 20th International Workshop on Logic and Synthesis 2011. La Jolla: University of California San Diego, 2011, pp. 136-143.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2011
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2011
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

Using Ternary Trees in Logic Synthesis

Autoři
Fišer, P.; Toman, D.
Rok
2011
Publikováno
Workshop 2011. Praha: České vysoké učení technické v Praze, 2011, pp. 1-16.
Typ
Stať ve sborníku
Anotace
We introduce a new efficient minimization method for functions described by many (up to millions) product terms. The algorithm is based on processing a newly proposed efficient representation of a set of product terms - a ternary tree. The minimization procedure is based on a fast application of basic Boolean operations upon the ternary tree, combined with algorithms used in the Espresso minimizer. Minimization of incompletely specified functions is supported as well. The minimization method was tested on randomly generated large sums-of-products and collapsed ISCAS benchmark circuits. The performance of the proposed algorithm was compared with Espresso.

A SOP Minimizer for Logic Functions Described by Many Product Terms Based on Ternary Trees

Autoři
Fišer, P.; Toman, D.
Rok
2010
Publikováno
Proceedings of the 9th International Workshop on Boolean Problems. Freiberg: Freiberg University of Mining and Technology, Institute of Computer Science, 2010, pp. 165-172. ISBN 978-3-86012-404-8.
Typ
Stať ve sborníku
Anotace
We introduce a new efficient minimization method for functions described by many (up to millions) product terms. The algorithm is based on processing a newly proposed efficient representation of a set of product terms - a ternary tree. The minimization procedure is based on a fast application of basic Boolean operations upon the ternary tree, combined with algorithms used in the Espresso minimizer. Minimization of incompletely specified functions is supported as well. The minimization method was tested on randomly generated large sums-of-products and collapsed ISCAS benchmark circuits. The performance of the proposed algorithm was compared with Espresso.

Area and Speed Oriented Implementations of Asynchronous Logic Operating Under Strong Constraints

Autoři
Fišer, P.; Lemberski, I.
Rok
2010
Publikováno
Proceedings of the 13th Euromicro Conference on Digital System Design. Los Alamitos: IEEE Computer Society Press, 2010. pp. 155-162. ISBN 978-0-7695-4171-6.
Typ
Stať ve sborníku
Anotace
Asynchronous circuit implementations operating under strong constraints (DIMS, Direct Logic, some of NCL gates, etc.) are attractive due to: 1) regularity; 2) combined implementation of the functional and completion detection logics, what simplifies the design process; 3) circuit output latency is based on the actual gate delays of the unbounded nature; 4) absence of additional synchronization chains (even of a local nature). However, the area and speed penalty is rather high. In contrast to the state-of-the-art approaches, where simple (NAND, NOR, etc.) 2 input gates are used, we propose a synthesis method based on complex nodes, i.e., nodes implementing any function of an arbitrary number of inputs. Synchronous synthesis procedures may be freely adopted for this purpose.

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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2010
Publikováno
Informal Proceedings of European Test Symposium. Praha: ČVUT v Praze, 2010,
Typ
Stať ve sborníku
Anotace
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

Rok
2010
Publikováno
Proceedings of the 19th International Workshop on Logic and Synthesis. Irvine, CA: University of California, Irvine, 2010. p. 17-24.
Typ
Stať ve sborníku
Anotace
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

Rok
2010
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Sekanina, L.; Vašíček, Z.
Rok
2010
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2010
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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.

A Fast SOP Minimizer for Logic Functions Described by Many Product Terms

Autoři
Fišer, P.; Toman, D.
Rok
2009
Publikováno
Proc. of 12th EUROMICRO Conference on Digital System Design. Los Alamitos: IEEE Computer Society, 2009. p. 757-764. ISBN 978-0-7695-3782-5.
Typ
Stať ve sborníku
Anotace
We introduce a fast and efficient minimization method for functions described by many (up to millions) product terms. The algorithm is based on processing a newly proposed efficient representation of a set of product terms - a ternary tree. A significant speedup of the look-up of the term operation is achieved, with respect to a standard tabular function representation. The minimization procedure is based on a fast application of basic Boolean operations upon a ternary tree. Minimization of incompletely specified functions is supported as well. The minimization method was tested on randomly generated large sums-of-products, collapsed ISCAS benchmark circuits and SAT problems. The performance of the proposed algorithm was compared with Espresso.

Multi-Level Implementation of Asynchronous Logic Using Two-Level Nodes

Autoři
Fišer, P.; Lemberski, I.
Rok
2009
Publikováno
Proc. of 4th Descrete-Event System Design. Valencia: University of Valencia, 2009, pp. 213-218. ISBN 978-3-902661-69-2.
Typ
Stať ve sborníku
Anotace
We propose a novel synthesis method of a dual rail asynchronous two-level logic of reduced cost. It is based on a model that operates under so called modified weak constraints. The logic is implemented as a minimized AND-OR structure, together with the completion detection logic. We formulated and proved the product term minimization constraint that ensures a correct logic behavior. We processed the MCNC benchmarks and generated asynchronous two-level logic. The implementation complexity was compared with the state-of-the-art approach. Using our approach, we achieved a significant improvement.

On Properties of SAT Instances Produced by SAT-Based ATPGs

Autoři
Fišer, P.; Schmidt, J.; Balcárek, J.
Rok
2009
Publikováno
Fifth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: neuveden, 2009, pp. 3-10. ISBN 978-80-87342-04-6.
Typ
Stať ve sborníku
Anotace
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

Rok
2009
Publikováno
Proc. of 12th EUROMICRO Conference on Digital System Design. Los Alamitos: IEEE Computer Society, 2009. p. 601-604. ISBN 978-0-7695-3782-5.
Typ
Stať ve sborníku
Anotace
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

Rok
2009
Publikováno
Proceedings of the International Workshop on Logic and Synthesis 2009. Berkeley, CA: IWLS Organizing Committee, 2009. p. 210-213.
Typ
Stať ve sborníku
Anotace
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.