A Design Space Exploration Framework for Memristor-Based Crossbar Architecture
Authors
Barbareschi, M.; Bosio, A.; O'Connor, I.; Fišer, P.; Traiola, M.
Year
2022
Published
Proceedings of the 2022 25th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). Piscataway: IEEE, 2022. p. 38-43. ISSN 2473-2117. ISBN 978-1-6654-9431-1.
Type
Proceedings paper
Departments
Annotation
In the literature, there are few studies describing how to implement Boolean logic functions as a memristor-based crossbar architecture and some solutions have been actually proposed targeting back-end synthesis. However, there is a lack of methodologies and tools for the synthesis automation. %More in detail, what is missing is a methodology able to optimize a given Boolean logic function for the memristor-based implementation.
The main goal of this paper is to perform a Design Space Exploration (DSE) in order to analyze and compare the impact of the most used optimization algorithms on a memristor-based crossbar architecture. %The synthesized circuits are quantified in terms of area, energy consumption, and performance.
The results carried out on 102 circuits lead us to identify the best optimization approach, in terms of area/energy/delay. The presented results can also be considered as a reference (benchmarking) for comparing future work.
Emerging Technologies: Challenges and Opportunities for Logic Synthesis
Authors
Bosio, A.; Cantan, M.; Marchand, C.; O'Connor, I.; Fišer, P.; Poittevin, A.; Traiola, M.
Year
2021
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
Das, S.; Fišer, P.; Pandit, S.; Das, D.K.
Year
2021
Published
Proc. of the 34th International Conference on VLSI Design. Piscataway (New Jersey): IEEE, 2021. p. 139-144. ISSN 1063-9667. ISBN 978-1-6654-4087-5.
Type
Proceedings paper
Departments
Annotation
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
Authors
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
Departments
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
Authors
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.
Evaluation of the SEU Faults Coverage of a Simple Fault Model for Application-Oriented FPGA Testing
Authors
Year
2020
Published
Proceedings of the 23rd Euromicro Conference on Digital Systems Design. Los Alamitos, CA: IEEE Computer Soc., 2020. p. 684-691. ISBN 978-1-7281-9535-3.
Type
Proceedings paper
Departments
Annotation
Testing of FPGA-based designs persists to be a challenging task because of the complex FPGA architecture with heterogeneous components, and therefore a complicated fault model. The standard stuck-at fault model has been found insufficient. On the other hand, very precise FPGA fault models have been recently devised. However, these models are often excessively complex and require a lot of resources (run-time, memory) to manipulate with.
In this paper, we propose a simple yet efficient combined fault model comprising bit-flips in look-up tables and stuck-at faults in the rest of logic. On~top of this model, a dedicated SAT-based application-oriented ATPG has been designed.
The main contribution of this paper is the evaluation of efficiency of the fault model with the respective ATPG by exhaustive hardware emulation of all possible SEUs in the configuration memory that may influence the functionality of the circuit implemented in the FPGA. We show that the obtained fault coverage reaches up to more than 99%, which makes the method applicable in practice. Even though combinational circuits are assumed only, the method can be used to quickly test safety-critical combinational cores.
Nonlinear codes for test patterns compression: the old school way
Authors
Year
2020
Published
Proc. of 14th International Workshop on Boolean Problems. Bremen: University of Bremen/DFKI GmbH, 2020. p. 1-16.
Type
Proceedings paper
Departments
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.
Standard Cell Tuning Enables Data-Independent Static Power Consumption
Authors
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
Departments
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.
CMOS Illumination Discloses Processed Data
Authors
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
Departments
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
Departments
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
Authors
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
Departments
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
Authors
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
Departments
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.
Optimum Polymorphic Circuits Synthesis Method
Authors
Fišer, P.; Šimek, V.
Year
2018
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
Ferrandino, U.; Traiola, M.; Barbareschi, M.; Mazzeo, A.; Fišer, P.; Bosio, A.
Year
2018
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
Háleček, I.; Fišer, P.; Schmidt, J.
Year
2018
Published
Microelectronics Reliability. 2018, 81 274-286. ISSN 0026-2714.
Type
Article
Departments
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
Departments
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
Authors
Year
2018
Published
Microprocessors and Microsystems. 2018, 2018(61), 43-57. ISSN 0141-9331.
Type
Article
Departments
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.
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
Departments
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.
Error Masking Method Based On The Short-Duration Offline Test
Authors
Year
2017
Published
Microprocessors and Microsystems. 2017, 52 236-250. ISSN 0141-9331.
Type
Article
Departments
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.
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
Departments
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
Authors
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
Departments
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
Departments
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
Authors
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
Departments
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
Authors
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
Departments
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 New Method for Path Criticality Calculation
Authors
Tamáši, R.; Siebert, M.; Gramatová, E.; Fišer, P.
Year
2016
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
Lipovský, M.; Švarc, J.; Gramatová, E.; Fišer, P.
Year
2016
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
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
Departments
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.
A Rule-Based Approach for Minimizing Power Dissipation of Digital Circuits
Authors
Das, S.; Dasgupta, P.; Fišer, P.; Ghosh, S.; Das, D. K.
Year
2016
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
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
Departments
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
Authors
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
Departments
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
Departments
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
Authors
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
Departments
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
Departments
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.
A New Method for Speficication of Parameters to Path Delay Fautls Testing
Authors
Tamaši, R.; Siebert, M.; Fišer, P.
Year
2015
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
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
Departments
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
Authors
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
Departments
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
Departments
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.
Asynchronous sum-of-products logic minimization and orthogonalization
Authors
Lemberski, I.; Fišer, P.; Suleimanov, R.
Year
2014
Published
International Journal of Circuit Theory and Applications. 2014, 42(6), 562-571. ISSN 0098-9886.
Type
Article
DOI
Departments
Annotation
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
Authors
Lemberski, I.; Fišer, P.
Year
2014
Published
Integration, the VLSI Journal. 2014, 47(1), 148-159. ISSN 0167-9260.
Type
Article
Departments
Annotation
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
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
Departments
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
Departments
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
Departments
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
Departments
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
Authors
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
Departments
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
Departments
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.
Weighted Don't Cares in Logic Synthesis
Authors
Bernasconi, A.; Ciriani, V.; Fišer, P.; Trucco, G.
Year
2014
Published
Recent Progress in the Boolean Domain. Newcastle upon Tyne: Cambridge Scholars Publishing, 2014. p. 263-277. ISBN 978-1-4438-5638-6.
Type
Book chapter
Departments
Annotation
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
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
Departments
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
Departments
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
Departments
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
Departments
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?
Authors
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
Departments
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
Departments
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
Authors
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
Departments
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
Authors
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
Departments
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
Departments
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.
Weighted Don't Cares
Authors
Bernasconi, A.; Ciriani, V.; Fišer, P.; Trucco, G.
Year
2012
Published
Proc. of 10th International Workshop on Boolean Problems. Freiberg: Technische Universität Bergakademie, 2012, pp. 123-130. ISBN 978-3-86012-438-3.
Type
Proceedings paper
Departments
Annotation
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?
Authors
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
Departments
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
Departments
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
Departments
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.
Using Ternary Trees in Logic Synthesis
Authors
Toman, D.; Fišer, P.
Year
2011
Published
Workshop 2011. Praha: České vysoké učení technické v Praze, 2011, pp. 1-16.
Type
Proceedings paper
Departments
Annotation
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
Authors
Toman, D.; Fišer, P.
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. 165-172. ISBN 978-3-86012-404-8.
Type
Proceedings paper
Departments
Annotation
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
Authors
Lemberski, I.; Fišer, P.
Year
2010
Published
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.
Type
Proceedings paper
Departments
Annotation
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
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
Departments
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
Authors
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
Departments
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
Authors
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
Departments
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
Departments
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
Departments
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.
A Fast SOP Minimizer for Logic Functions Described by Many Product Terms
Authors
Fišer, P.; Toman, D.
Year
2009
Published
Proc. of 12th EUROMICRO Conference on Digital System Design. Los Alamitos: IEEE Computer Society, 2009. p. 757-764. ISBN 978-0-7695-3782-5.
Type
Proceedings paper
Departments
Annotation
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
Authors
Fišer, P.; Lemberski, I.
Year
2009
Published
Proc. of 4th Descrete-Event System Design. Valencia: University of Valencia, 2009, pp. 213-218. ISBN 978-3-902661-69-2.
Type
Proceedings paper
Departments
Annotation
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
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
Departments
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
Authors
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
Departments
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
Authors
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
Departments
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.