Search

Minimizing the loss of raw materials is an important issue in the construction industry. The construction material often encounters two-dimensional cutting problems such as steel plates and wooden plates. Reducing material waste by using building information modeling (BIM) and artificial intelligence methods has received considerable attention. Thus, this study focused on two-dimensional cutting stock problems (2D-CSP), and employed the auto-tuning Symbiotic Organisms Search algorithm (SOS) to establish residual material optimization model. The results considering the placement strategy with the rotation of the cutting plates, showed that, compared to other heuristic algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), the SOS algorithm obtained superior solutions to the two-dimensional cutting operation. Therefore, the proposed model possesses a certain application value for solving the optimization problem in the construction industry, and helps reducing the material waste and budget cost.

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%.

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.

MachineryApproximate computing is an emerging design paradigm for error-tolerant applications. e.g., signal processing and machine learning. In approximate computing, the area, delay, or power consumption of an approximate circuit can be improved by trading off its accuracy. In this paper, we propose an approximate logic synthesis approach based on a node-merging technique with an error rate guarantee. The ideas of our approach are to replace internal nodes by constant values and to merge two similar nodes in the circuit in terms of functionality. We conduct experiments on a set of IWLS 2005 and MCNC benchmarks. The experimental results show that our approach can reduce area by up to 80%, and 31% on average. As compared with the state-of-the-art method, our approach has a speedup of 51 under the same 5% error rate constraint.

Logic minimization attracted much attention in the early days because it is the engine for logic synthesis and optimization. Recently, a previous work proposed a SAT-based minimization algorithm for the patch function in the Engineering Change Order (ECO) problem. However, the algorithm is time-consuming for the functions in high dimension Boolean space. Therefore, in this paper, we propose an efficient algorithm that is suitable for the functions in high dimension Boolean space.

The binary-weight-binary-input binarized neural network (BNN) allows a much more efficient way to implement convolutional neural networks (CNNs) on mobile platforms. During inference, the multiply-accumulate operations in BNNs can be reduced to XNOR-popcount operations. Thus, the XNOR-popcount operations dominate most of the computation in BNNs. To reduce the number of required operations in convolution layers of BNNs, we decompose 3-D filters into 2-D filters and exploit the repeated filters, inverse filters, and similar filters to share results. By sharing the results, the number of operations in convolution layers of BNNs can be reduced effectively. Experimental results show that the number of operations can be reduced by about 60% for CIFAR-10 on BNNs while keeping the accuracy loss within 1% of originally trained network.

This paper presents a method based on range-equivalent circuit technique for SAT-based bounded sequential equivalence checking. Given two sequential circuits to be verified, instead of straightforward unrolling the miter of two sequential circuits, we iteratively minimize the miter with a range-equivalent circuit technique before adding a new timeframe. This is because the previous timeframes can be considered as a pattern generator that feeds input patterns to the next timeframe. Experimental results show that the proposed method saved up to 91% of time for reaching the same bounded depth compared with previous work on IWLS2005 benchmarks.

Recently, Threshold logic attracts a lot of attention due to the advances of its physical implementation and the strong binding to neural networks. Approximate computing is a new design paradigm that focuses on error-tolerant applications, e.g., machine learning or pattern recognition. In this paper, we integrate threshold logic with approximate computing and propose a synthesis algorithm to obtain cost-efficient approximate threshold logic circuits with an error rate guarantee. We conduct experiments on IWLS 2005 benchmarks. The experimental results show that the proposed algorithm can efficiently explore the approximability of each benchmark. For a 5% error rate constraint, the circuit cost can be reduced by up to 65%, and 22.8% on average. Compared with a naive method, our approach has a speedup of 2.42 under a 5% error rate constraint.

Boolean Relation (BR) is a many-to-many mapping between two domains. Logic optimization considering BR can exploit the potential flexibility existed in logic networks to minimize the circuits. In this paper, we present a logic optimization approach considering BR. The approach identifies a proper sub-circuit and locally changes its functionality by solving the corresponding BR in the sub-circuit without altering the overall functionality of the circuit. We conducted experiments on a set of MCNC benchmarks that cannot be further optimized by resyn2 script in ABC. The experimental results show that the node counts of these benchmarks can be further reduced. Additionally, when we apply our approach followed by the resyn2 script repeatedly, we can obtain 6.11% improvements in average.

Single-electron transistor (SET) at room temperature has been demonstrated as a promising device for extending Moore’s law due to its ultralow power consumption. However, early realizations of SET array lacked variability and reliability due to their fixed architectures and high defect rates of nanowire segments. Therefore, a reconfigurable version of SET was proposed to deal with these issues. Recently, several automated mapping approaches have been proposed for area minimization of reconfigurable SET arrays. However, to the best of our knowledge, seldom mapping algorithms that consider the existence of defective nanowire segments were proposed. Furthermore, before the defect-aware mapping, we have to know the locations of defects in SET arrays. Thus, this paper presents the first diagnosis approach to identify the locations of defects in SET arrays followed by two defect-aware algorithms for mapping SET arrays in different scenarios. The experimental results show that the proposed diagnosis method can detect 100% of defects under a defect rate and distribution in SET arrays. As for the mapping algorithms, the results show that our approach can successfully map the SET arrays with 11.13% and 7.69% width overhead on average in the baseline detour mapping algorithm and defect-reuse mapping algorithm, respectively, in the presence of 5000-ppm defects.

Power consumption has become one of the primary challenges to meetMoore’s law. For reducing power consumption, single-electron transistor (SET) at room temperature has been demonstrated as a promising device for extending Moore’s law due to its ultralow power consumption in operation. Previous works have proposed automated mapping approaches for SET arrays that focused on minimizing the number of hexagons in the SET arrays. However, the area of an SET array is the product of the bounded height and the bounded width, and the height usually equals the number of inputs in the Boolean function. Consequently, in this paper, we focus on the width minimization to reduce the overall area in the mapping of the SET arrays. Our approach consists of techniques of product term minimization, branch-then-share (BTS)-aware variable reordering, SET array architecture relaxation, and BTS-aware product term reordering. The experimental results on a set of MCNC and IWLS 2005 benchmarks show that the proposed approach saves 45% of width compared with the work by Chiang et al. , which focused on hexagon count minimization, and also saves 13% of width compared with the work by Chen et al. , which focused on width minimization.

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.

Reducing power consumption has become one of the primary challenges in chip design, and therefore significant efforts are being devoted to find holistic solutions on power reduction from the device level up to the system level. Among a plethora of low power devices that are being explored, single-electron transistors (SETs) at room temperature are particularly attractive. Although prior work has proposed a binary decision diagram-based reconfigurable logic architecture using SETs, it lacks an automatic synthesis algorithm for the architecture. Consequently, in this work, we develop a product-term-based approach that synthesizes a logic circuit by mapping all its product terms into the SET architecture. The experimental results show the effectiveness and efficiency of the proposed approach on a set of MCNC benchmarks.

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.

The large number of latches in current digital designs increases the complexity of formal verification and logic synthesis, since an increase in latch numbers leads to an exponential expansion of the state space. One solution to this problem is to find the functional dependences among these latches. With the information of functional dependences, these latches can be identified as dependent or essential latches, and the state space can be constructed using only the essential latches. Although much research has been devoted to exploring the functional dependences among latches using binary-decision-diagram (BDD)-based symbolic algorithms, this issue is still unresolved for large sequential circuits. In this paper, we propose a heuristic to identify the dependent latches based on the state-of-the-art work. In addition, our proposed approach detects sequential functional dependences existing in the reachable state space only. The sequential functional dependences can identify additional dependent latches after a specific time frame in order to achieve additional reduction of the state space. Experimental results show that this approach can deal with large sequential circuits with up to 9000 latches in a reasonable time while simultaneously identifying their combinational and sequential dependent latches. For instance, with s13207 in ISCAS'89, 23% of the latches are identified as combinational dependent latches, and an additional 13% of the latches are identified as sequential dependent latches. For the reachability analysis of s13207, with the benefits of dependent-latch identification, 70.70% of the BDD size and 73.32% of the CPU time can be reduced within the same time frame. Furthermore, 2890.76% more states can be reached under the 600 000-s run-time limit.

Exact approaches to combinational equivalence checking, such as automatic test pattern generation-based, binary decision diagrams (BDD)-based, satisfiability-based, and hybrid approaches, have been proposed over the last two decades. Recently, we proposed another exact approach using signal probability. This probability-based approach assigns probability values to the primary inputs and compares the corresponding output probability of two networks via a probability calculation process to assert if they are equivalent. The shortcoming of all these exact approaches is that if two networks are too complex to be handled, their equivalence cannot be determined, even with tolerance. An approximate approach, named the probabilistic approach, is a suitable way to give such an answer for those large circuits. However, despite generally being more efficient than exact approaches, the probabilistic approach faces a major concern of a non zero aliasing rate, which is the possibility that two different networks have the same output probability/signatures. Thus, minimizing aliasing rate is substantial in this area. In this paper, we propose a novel probabilistic approach based on the exact probability-based approach. Our approach exploits proposed probabilistic equivalence checking architecture to efficiently calculate the signature of network with virtually zero aliasing rate. We conduct experiments on a set of benchmark circuits, including large and complex circuits, with our probabilistic approach. Experimental results show that the aliasing rate is virtually-zero, e.g., 10-6013. Also, to demonstrate the effectiveness of our approach on error detection, we randomly inject errors into networks for comparison. As a result, our approach more efficiently detects the error than a commercial tool, Cadence LEC, does. Although our approach is not exact, it is practically useful. Thus, it can effectively complement exact methods to improve the efficiency and effectiveness of combination equivalence checking algorithms.

Prior works have demonstrated opportunities for achieving more minimized combinational circuits by introducing combinational loops during the synthesis. However, they achieved this by using a branch-and-bound technique to explore possible cyclic dependencies of circuits, which may not scale well for complex designs. Instead of using exploration, this paper proposes a formal algorithm using logic implication to identify cyclifiable structure candidates directly, or to create them aggressively in circuits. Additionally, we also propose a SAT-based algorithm to validate whether the formed loops are combinational or not. The effectiveness and scalability of the identification and validation algorithms are demonstrated in the experimental results performed on a set of IWLS 2005 benchmarks. As compared to the state-of-the-art algorithm, our validation algorithm produces speedups ranging from 2 to 2350 times.

Redundancy Addition and Removal (RAR) and ATPG/Diagnosis-based Design Rewiring (ADDR) are both logic restructuring techniques used in the synthesis and optimization of logic designs. However, not every irredundant target wire can be successfully removed due to some limitations in these two approaches. Therefore, this paper proposes an efficient restructuring technique, Error Injection & Correction (EIC), which formally constructs a corresponding rectification network at feasible locations without verification efforts for the injected errors of the wire removal, addition, or gate replacement. We use the EIC to serve as a logic perturbation engine and combine other logic optimization engines to optimize the circuit. The experimental results show that the size of highly optimized circuits can be further reduced with this EIC technique as compared with the configuration using only logic optimization engines.

This paper presents a statistic-based method to estimate the testability of a design at Register-Transfer Level. This testability estimation technique is composed of a new proposed high-level design representation and a Monte Carlo simulation which exploits a statistic model to bound the error rate and confidence level of simulation results. The experimental results show that the proposed method can efficiently report more than 60% hard-to-test points of an RL design on average prior to the synthesis task.

In this paper, we propose a new node merging algorithm using logic implications. The proposed algorithm only requires two logic implications to find the substitute nodes for a given target node, and thus can efficiently detect node mergers. Furthermore, we also apply the node merger identification algorithm for area optimization in VLSI circuits. We conduct experiments on a set of IWLS 2005 benchmarks. The experimental results show that our algorithm has a competitive capability on area optimization compared to a global observability don't care (ODC)-based node merging algorithm which is highly time-consuming. Our speedup is approximately 86 times for overall benchmarks. Categories and Subject Descriptors B.6.3 [Logic Design]: Design Aids-Optimization General Terms Algorithms

The sequential depth determines the completeness of bounded model checking in design verification. Recently, a SAT-based method is proposed to compute the sequential depth of a design by searching the state space. Unfortunately, it suffers from the search space explosion due to the exponential growth of design complexity. To alleviate the impact of state space explosion, we propose a search space reduction method. We collect the learned states and consider them constraints for further path searching. Furthermore, we propose a heuristic to guide the SAT-solver to efficiently find a shortest path. The experimental results show that as compared to another method which also enhances the previous SAT-based method using a branch-and-bound strategy, our approach obtains more improvements.

Estimation of maximal power consumption is an essential task in VLSI circuit realizations since power value significantly affects the reliability of the circuits. The key issue of this task is which pattern pair would cause this peak power value. An exhaustive search from all possible combinations is time-consuming and impractical for VLSI circuits with hundreds of inputs. In this paper, a new pattern generation approach with Ant Colony Optimization, which imitates the behavior of ants looking for foods, is proposed for peak power estimation. The approach returns patterns which are highly suspicious to consuming the peak power. The gate delay issue is considered in this work. Furthermore, the valid state issue in sequential circuits is considered as well. Since the real delay value is technology-dependent, these generated patterns of our approach and other approaches are then applied into a commercial power calculation tool, PrimePower, to demonstrate the effectiveness of the approach under the TSMC 0.18 µm and TSMC 0.13 µm library. The experimental results show that an average of 76% tighter lower bound for the ISCAS'85 combinational benchmarks and 52% for the ISCAS'89 sequential circuits are obtained as compared to random patterns under the TSMC 0.18 µm library. For TSMC 0.13µm library, our patterns obtain 90% and 56% improvements over the random patterns for ISCAS'85 and ISCAS'89, respectively. As compared with the previous work, our results are also competitive.

This paper presents a parallel vector simulation-based approach to locating multiple errors in large combinational circuits. Two heuristics are proposed to avoid the explosion of the error space. Experimental results on a set of ISCAS'85 and two large benchmarks show that our approach efficiently identifies a small set of correctable nodes that contains the actual error sources. Thus, further error correction can be conducted on the erroneous implementation.

This paper presents a statistic-based approach for evaluating the testability of nodes in combinational circuits. This testability measurement is obtained via Monte Carlo simulation governed by the formulated Monte Carlo model. The Monte Carlo simulation is terminated when the predefined error with respect to the Monte Carlo model, under a specified confidence level, is achieved. We conduct the experiments on a set of ISCAS '85 and MCNC benchmarks. As compared with previous work, our approach more efficiently evaluates the testability with less error rate.

Factoring is a logic minimization technique to represent a Boolean function in an equivalent function with minimum literals. When realizing the circuit, a function represented in a more compact form has smaller area. Some Boolean functions even have equivalent forms where each variable appears exactly once, which are known as fanout-free functions. John P. Hayes (Hayes, 1975) had devised an algorithm to determine if a function can be fanout-free and construct the circuit if fanout-free realization exists. In this paper, we propose a property and an efficient technique to accelerate this algorithm. With our improvements, execution time of this algorithm is more competitive with the state-of-the-art method (Golumbic, 2001).

This paper describes an approximate approach for combinational equivalence checking. We propose an architecture such that a virtually-zero aliasing rate is obtained in a single-pass probability calculation. Furthermore, the aliasing rate can be easily configured in various precision by designers. We conduct experiments on a set of ISCAS'85 benchmarks. Experimental results show that with virtually-zero aliasing rate, for example, 10?74, our approach is more efficient than those exact approaches.

Redundancy addition and removal (RAR) is a restructuring technique used in the synthesis and optimization of logic designs and physical designs. It finds alternative wires to replace a given target wire without changing the functionality of the circuit. Previous approaches apply two-stage algorithms for this problem. First, they build up a set of candidate wires for the target wire. Second, they perform redundancy test on each candidate wire to determine if it is an alternative wire. Recently, a one-stage algorithm RAM-FIRE (Chang et al., 2003) is proposed. It conducts three logic implications to identify backward alternative wires without trial-and-error redundancy tests. However, the number of alternative wires it can find is smaller than that obtained by the previous two-stage approaches. Here, we propose an improved one-stage algorithm, which only conducts two logic implications. The experimental results show that compared to RAMFIRE, our approach only requires 83% cpu time on average, while obtaining the same number of backward alternative wires. As extending to finding both backward and forward alternative wires, on average our approach gets 157% improvement with 32% cpu time overhead.

Symmetric input identification is an important technique in logic synthesis. Previous approaches deal with this problem by building BDDs and developing algorithms to determine symmetric inputs. For the design whose corresponding BDDs cannot be built, BDD-based approaches cannot be applied on this problem. To avoid the limitations of BDD-based approaches, simulation-based methods have been proposed. It is applicable to designs described in arbitrary level, especially to high-level and black box designs. Previous simulation-based approaches focus on determining the inputs of nonequivalence symmetry. In this paper, we propose a simulation-based approach to identify equivalence symmetric inputs. The experimental results on a set of ISCAS-85 and MCNC benchmarks are also presented.

We propose a graph automorphism-based algorithm for computing maximal sets of symmetric inputs of circuits. It can be used to identify nonsymmetric inputs in a circuit and enhance the efficiency of input matching, library binding, as well as logic verification problems. We conduct the experiments on some benchmarks. The experimental results demonstrate that our approach distinguishes more non-symmetric inputs than that of previous work.