Search

This article proposes a new necessary condition and the corresponding speedup strategies to the threshold function (TF) identification problem. The state-of-the-art to this identification problem could be very time-consuming when the function-under-identification is a non-TF with the unateness property. The proposed new necessary condition can be seamlessly integrated into this identification algorithm. As compared with the state-of-the-art, the improved identification algorithm with the proposed necessary condition can more effectively and efficiently detect non-TFs. Furthermore, according to the experimental results, the ratio of CPU time overhead in the process of checking the proposed necessary condition for identifying all the 8-input TF is only 0.1%.

SAT Attack, CycSAT, and Removal Attack have demonstrated their abilities to break most existing logic locking methods. In this article, we propose a new cyclic logic locking method to invalidate these attacks simultaneously. Our main intention is to create noncombinational cycles to lock a circuit. Specifically, the noncombinational behavior in the noncombinational cycles that is unobservable at the primary outputs (POs) needs to be preserved when the correct key-vector is fed to resist CycSAT, and the noncombinational behavior in the noncombinational cycles affecting POs needs to be preserved when the incorrect key-vector is fed to invalidate SAT Attack. Furthermore, some nodes will be removed when applying our locking method, which is able to defend Removal Attack. The experimental results show the effectiveness and low area overhead of the proposed method.

The identification of threshold function (TF), which determines whether a Boolean function can be represented by an linear threshold logic gate (LTG) or not, is a fundamental but important task in the theories of threshold logic. In this paper, we propose a more efficient and effective algorithm of TF identification by constructing the system of irredundant inequalities and adjusting the weight assignment comprehensively. This is the first non-ILP-based approach that is able to identify all the eight-input TFs. The experimental results demonstrated that the proposed approach is more effective than all the existing non-ILP-based approaches and the LTGs obtained by the proposed approach are optimal for near 100% cases. For TFs with 9–15 inputs, the proposed approach can identify 100 000 randomly generated TFs as well in a reasonable CPU time.

Traditionally, we expect that circuit designs can be executed without errors. However, for error resilient applications such as image processing, 100% correctness is not necessary. By pursuing less than 100% correctness, power consumption can be significantly reduced. Recently, probabilistic CMOS and probabilistic Boolean circuits (PBCs) have been proposed to deal with power consumption issue. However, to the best of our knowledge, no correctness analysis and power optimization algorithms have been proposed for PBCs. Thus, in this paper, we first propose a statistical approach for evaluating the correctness of PBCs. Then, we propose strategies for power optimization of PBCs. Finally, we integrate these strategies with the correctness analysis as a power optimization algorithm for PBCs. The experimental results show that the proposed correctness analysis method is highly efficient and accurate, and that the power optimization algorithm saves 36% of total power-delay-product on average under a correctness constraint of 90% on a set of International Workshop on Logic and Synthesis (IWLS) 2005 benchmarks.

Recently, single-electron transistors (SETs) have been attracting substantial attention and are considered candidate devices for future integrated circuits due to their ultralow power consumption. To realize SETs, a binary decision diagram-based SET array is proposed as a suitable candidate for implementing Boolean circuits. Then, some works started developing computer-aided design techniques for this new architecture. However, most of them focused on the development of mapping techniques. How to verify the mapping results is still an open problem. Thus, in this paper, we address this problem and develop a satisfiability (SAT)-based verification method. We propose a transformation approach to model the functionality of a mapped SET array as a conjunctive normal form formula. Then, the problem that whether the SET array is functionally equivalent to its specification circuit can be solved with a SAT solver. The experimental results show that the proposed method can successfully verify correct and incorrect SET array implementations with reasonable verification time.

This paper presents a logic restructuring technique named node addition and removal (NAR). It works by adding a node into a circuit to replace an existing node and then removing the replaced node. Previous node-merging techniques focus on replacing one node with an existing node in a circuit, but fail to replace a node that has no substitute node. To enhance the node-merging techniques on logic restructuring and optimization, we propose an NAR approach in this paper. We first present two sufficient conditions that state the requirements of added nodes for safely replacing a target node. Then, an NAR approach is proposed to quickly detect the added nodes by performing logic implications based on these conditions. We apply the NAR approach to circuit minimization together with two techniques: redundancy removal and mandatory assignment reuse. We also apply it to satisfiability (SAT)-based bounded sequential equivalence checking (BSEC) to reduce the computation complexity of SAT solving. The experimental results show that our approach can enhance our prior automatic test pattern generation-based node-merging approach. Additionally, our approach has a competitive capability of circuit minimization with 44 times speedup compared to a SAT-based node-merging approach. For BSEC, our approach can work together with other optimization technique to save a total of approximately 39-h verification time for all the benchmarks.

A crosstalk effect leads to increases in delay and power consumption and, in the worst-case scenario, to inaccurate results. With the scale down of technology to deep-submicrometer level, the crosstalk effect between adjacent wires becomes more and more serious, particularly between long on-chip buses. In this paper, we propose a deassembler/assembler technique to eliminate undesirable crosstalk effects on bus transmission. By taking advantage of the prefetch process, where the instruction/data fetch rate is always higher than the instruction/data commit rate, the proposed method incurs almost no penalty in terms of dynamic instruction count. In addition, when the bus width is 128 b, the required number of extra bus wires is only 7 as compared to the 85 extra bus wires needed in the work of Victor and Keutzer.

Embedded cores are being increasingly used in large system-on-a-chip (SoC) designs. The high complexity of SoC designs lead the design verification to be a challenge for system integrators. This paper presents an automatic interconnection rectification (AIR) technique based on the port order fault model to detect, diagnose, and correct the misplacements of interconnection that occurred in the integration of a SoC design automatically. The experiments are conducted on combinational and sequential benchmarks. Experimental results show that the AIR can correct the misplaced interconnection exactly within reasonable efforts and, therefore, accelerates the integration verification of SoC designs.

Embedded cores are being increasingly used in the design of large system-on-a-chip (SoC). Because of the high complexity of SoC, the design verification is a challenge for system integrators. To reduce the verification complexity, the port-order fault (POF) model was proposed. It has been used for verifying core-based designs and the corresponding verification pattern generation has been developed. Here, the authors present an automorphic technique to improve the efficiency of the automatic verification pattern generation (AVPG) for SoC design verification based on the POF model. On average, the size of pattern sets obtained on the ISCAS-85 and MCNC benchmarks are 45% smaller and the run time decreases 16% as compared with the previous results of AVPG.

Embedded cores are being increasingly used in the design of large system-on-a-chip (SoC). Because of the high complexity of SoC, the design verification is a challenge for system integrators. To reduce the verification complexity, the port-order fault (POF) model has been used for verifying core-based designs (Tang and Jou, 1998). In this paper, we present an automatic-verification pattern generation (AVPG) for SoC design verification based on the POF model and perform experiments on combinational and sequential benchmarks. Experimental results show that our AVPG can efficiently generate verification patterns with high POF coverage.