Tableau representation offers an efficient framework for describing quantum circuits and has been widely adopted in tableau-based quantum circuit optimization (QCO) flows. While these flows can substantially reduce the T -count, which is critical for fault-tolerant implementations, resynthesizing the optimized tableaux back into circuits often introduces excessive two-qubit gates (2Q-gates), leading to significant 2Q-count overhead. To address this issue, we propose a unified synthesis strategy that departs from the conventional tableau-by-tableau approach. Instead of resynthesizing each tableau in isolation, our method consolidates Clifford and Pauli rotation tableaux and applies a holistic resynthesis algorithm. This unified treatment contrasts with prior approaches and enables systematic reduction of the overall 2Q-count. Experimental results on standard Clifford+T benchmarks show that our method achieves a Geomean 2Q-count ratio of 1.28, compared to 4.24 for TKET and 1.93 for LazySynth—the state-of-the-art tableau synthesis approach—, demonstrating that unified synthesis effectively mitigates the 2Q-gate overhead in tableau-based QCO.

Synthesis-based functional Engineering Change Order (ECO) algorithms, as classified in [1], are particularly effective for addressing functional bugs. These algorithms typically involve two primary steps: (1) identifying rectification signals to address functional mismatches, and (2) generating patch circuits based on these signals. While much of the existing research focuses on enhancing step (2), step (1) often remains somewhat ad hoc and inefficient.In this paper, we propose a novel approach for systematically collecting and validating all possible sets of rectification signals from a given set of candidates. Leveraging a heuristic for grouping and ranking rectification signals, our ECO flow efficiently identifies minimal patches while achieving a highly competitive runtime. Our contributions include three key innovations: a heuristic for identifying high-quality rectification candidates, an efficient algorithm for validating all feasible sets of rectification signals, and a signal grouping and ranking technique that ensures minimal patch size. When integrated with an open-source patch generation tool, our method demonstrates an average reduction of 44% in patch sizes compared to a leading commercial ECO tool on benchmark circuits.

Qubit mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the existing algorithms for qubit mapping encounter difficulties when dealing with larger circuit sizes involving hundreds of qubits. In this article, we introduce an innovative qubit mapping algorithm, Duostra, tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices with limited connectivity. Duostra operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic scheduling algorithms, Limitedly Exhaustive Search and Shortest-Path Estimation, it yields results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage. Experimental results showcase our algorithm’s superiority, especially for large circuits beyond the NISQ era. For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t \(|ket\rangle\) , Qiskit, and SABRE. Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t \(|ket\rangle\) , Qiskit, and SABRE, respectively.

The X-value arises in various contexts of system design. It often represents an unknown value or a don't-care value depending on the application. Verification of X-valued circuits is a crucial task but relatively unaddressed. The challenge of equivalence checking for X-valued circuits, named compatible equivalence checking, is posed in the 2020 ICCAD CAD Contest. In this paper, we present our winning method based on X-value preserving dual-rail encoding and incremental identification of compatible equivalence relation. Experimental results demonstrate the effectiveness of the proposed techniques and the outperformance of our approach in solving more cases than the commercial tool and the other teams among the top 3 of the contest.

Deep learning models such as convolutional neural network have been widely used in 3D biomedical segmentation and achieve state-of-the-art performance. However, most of them often adapt a single modality or stack multiple modalities as different input channels, which ignores the correlations among them. To leverage the multi-modalities, we propose a deep convolution encoder-decoder structure with fusion layers to incorporate different modalities of MRI data. In addition, we exploit convolutional LSTM (convLSTM) to model a sequence of 2D slices, and jointly learn the multi-modalities and convLSTM in an end-to-end manner. To avoid converging to the certain labels, we adopt a re-weighting scheme and two phase training to handle the label imbalance. Experimental results on BRATS-2015 [13] show that our method outperforms state-of-the-art biomedical segmentation approaches.

Localization abstraction is a powerful technique that has long been a solution to the scalability problem of hardware model checking. However, computation resources are often inefficiently consumed during the repeated trial-and-errors between abstraction refinement engines and proof engines. To this end, many efforts have been made to combine the two independent techniques for better efficiency in recent years. In this paper, we present a novel model checking method that combines PDR (aka IC3) with a gate-level, hybrid abstraction technique to achieve further enhancement of scalability and performance for PDR. We implemented our work in ABC and evaluated it on the HWMCC13, HWMCC14 benchmark suites. The results show that our method substantially outperforms PDR as implemented in ABC and complements it on a large number of benchmark instances.

Interpolation-based model checking (IMC) is an important technique in modern formal verification tools. In essence, it relies on an abstraction and refinement process to derive an adequate image approximation for the reachability analysis. However, previous IMC algorithms only offer fixed degrees of abstraction and thus may fail in the proofs if the abstraction is too coarse- or fine-grained. In this paper, we propose an adaptive interpolation-based model checking algorithm in which the degree of abstraction can be adjusted on demand. That is, during the proof process, we closely monitor the effectiveness of the interpolation-based over-approximated image computation and thus adjust the degree of abstraction for the best performance. The experimental results confirm that our flexible interpolation indeed leads to an adequate degree of abstraction as our IMC algorithm outperforms previous ones in various aspects.

Interpolation is an important and distinguished method popularly applied to recent synthesis and verification research topics. Existing approaches generate interpolants by analyzing unsatisfiability (UNSAT) proofs from satisfiable (SAT) solvers. Unfortunately, the interpolant is predestinedly determined by how the UNSAT proof is logged. This particularly weakens the abstraction of interpolation-based model checking procedure. In this paper, a new approach to generate a variety of functionally different interpolants using simulation and SAT solving is proposed. We further seamlessly integrated the novel interpolant generation algorithm into a reinterpreted interpolation-based model checking procedure. Moreover, spurious counterexamples from the model checker further guide the generation of interpolants to refute excessive refinements. As an extra benefit, proof logging is not required for SAT solvers. Experiments show promising results of our interpolation-based model checker NewITP on solving a large set of HWMCC benchmarks.

Constrained random simulation is becoming the mainstream methodology to verify system-wide properties in functional verification. It is a must to develop a high-throughput constrained random pattern generator, which is able to support arbitrary distribution. In this paper, we propose a novel range-splitting heuristic and a solution-density estimation technique to conquer the challenges of random pattern generators proposed in the recent literature. The solution densities can significantly increase by pruning infeasible subspaces. On the other hand, the estimated solution densities stored on a range-splitting tree statistically predict the distribution of solutions. Therefore, the generated patterns are ensured to meet the desired distribution with high throughput. Experimental results show that our framework achieves more than 10X speedup on average when compared to a commercial generator.

To verify system-wide properties on SoC designs in Constrained Random Verification (CRV), the default set of constraints to generate patterns could be overridden frequently through the complex testbench. It usually results in the degradation of pattern generation speed because of low hit-rate problems. In this paper, we propose a technique to preprocess the solution space under each constraint set. Regarding the similarity between constraint sets, the infeasible subspaces under a constraint set help identify the infeasible subspaces under another constraint set. The profiled results under each constraint set are then stored in a distinct range-splitting tree (RS-Tree). These trees accelerate pattern generation under multiple constraint sets and, simultaneously, ensure the produced patterns are evenly-distributed. In our experiments, our framework achieved 10X faster pattern generation speed than a state-of-art tool in average.

Interpolation is an important and distinguished method popularly applied to recent synthesis and verification research topics. Existing approaches generate interpolants by analysing unsatisfiability proofs from SAT solvers. Unfortunately, the interpolant is predestinedly determined by how the unsatisfiability proof is logged. This particularly weakens the abstraction of interpolation-based model checking procedure. In this paper, a new approach to generate a variety of functionally different interpolants using simulation and SAT solving is proposed. We further seamlessly integrated the novel interpolant generation algorithm into the reinterpreted interpolation-based model checking procedure. Moreover, spurious counterexamples from the model checker further guide the generation of interpolants to refute excessive refinements. As an extra benefit, proof logging is not required for SAT solvers. Experiments show promising results of our interpolation-based model checker NewITP on solving a large set of HWMCC benchmarks.

Due to the non-determinism of the SystemC scheduler, SystemC symbolic simulation faces a scalability issue. The issue stems from enumerating all scheduling alternatives such that all design behaviors can be captured assuredly. To conquer the scheduling alternative explosion problem, we first adopt symbolic partial order reduction to reduce the equivalent scheduling alternatives for exploration. Moreover, for those scheduling alternatives that cannot be reduced by partial order reduction, we merge their execution paths (and also states) into fewer ones to prevent the number of paths from explosion. The experimental results show that we achieve a tremendous scalability improvement by combining these two techniques together.

Functional engineering change order (ECO) is a popular technique for rectifying design errors after synthesis and placement stages. We present a new approach to generating the patch circuits for multierror circuit rectification. In this paper, we propose a two-phase approach of: 1) discovering the functional matches in two circuits followed by 2) determining the final patch circuits from the matches. The ECO engine in this paper discovers functional and structural matches in two circuits by coordinating the SAT-sweeping and the cut-matching algorithms. Then, the patch selection is conducted by the combinational equivalence checking technique and a linear-time selection heuristic. The experimental results on public benchmark and industrial circuits demonstrate that this ECO engine outperforms state-of-the-art interpolation-based engines.

Efficiency and accuracy are two critical concerns in multiprocessor system on chip (MPSoC) virtual platform simulation. Traditional simulation approaches that achieve high efficiency usually sacrifice accuracy. On the other hand, the cycle-accurate simulation algorithms are generally slow in speed. In this paper, we propose an ultrasynchronization checking method with an efficient trace-driven simulation mechanism that can not only improve simulation speed, but also maintain simulation accuracy. We build a SystemC-based MPSoC virtual platform to evaluate the effectiveness of our approach. The experimental results show that our proposed simulation scheme can improve simulation speed up to 156× over the traditional clock-step simulation method. Furthermore, our proposed method can also guarantee the cycle-accurate simulation result.

Buffer Insertion has always been the most effective approach for timing optimization in VLSI designs. However, the emerging low-power design paradigm and the consideration of multiple operation modes and process corners (MMMC) have raised great challenges. Traditional dynamic-programming-based techniques are unable to cope with these challenges. In this paper, we develop a novel buffer insertion algorithm that utilizes a neighborhood restriction to simplify the constraint formulation and apply a semi-formal buffer refinement process to minimize buffer cost. The experimental results show that our tool can significantly reduce the buffer cost while meeting the MMMC timing constraints.

SystemC is a de-facto standard for modeling system-level designs in the early design stage. Verifying SystemC designs is critical in the design process since it can avoid error propagation down to the final implementation. Recent works exploit the software model checking techniques to tackle this important issue. But they abstract away relevant semantic aspects or show limited scalability. In this paper, we devise a symbolic model checking technique using bounded model checking and induction to formally verify SystemC designs. We introduce the notions of behavioral states and transitions to guarantee the soundness of our approach. The experiments show the scalability and the efficiency of our method.

For a design with multiple functional errors, multiple patches are usually needed to correct the design. Previous works on logic rectification are limited to either single-fix or partial-fix rectifications. In other words, only one or part of the erroneous behaviors can be fixed in one iteration. As a result, it may lead to unnecessarily large patches or even failure in rectification. In this paper, we propose a multi-patch generation technique by interpolation with cofactor reduction. In particular, our method considers multiple errors in the design simultaneously and generates multiple patches to fix these errors. Experimental results show that the proposed method is effective on a set of large circuits, including the circuits synthesized from industrial register-transfer level (RTL) designs.

Constrained random verification (CRV) methodology has been identified as an efficient solution to functional verification challenges. In practical cases, it is required to implement constraints with variable ordering to put essential efforts on cared patterns. However, handling constraints with variable ordering may encounter performance degradation of pattern generation speed and distribution. To resolve these challenges, we provide a preprocessing technique to analyze solution space by adaptively splitting ranges of variables and prove the feasibility of each subspace. This analysis allows us to perform effective range-reduction to enhance pattern generation speed and ensure the desired distribution. From the experimental results, our framework outperforms a state-of-art tool with 10X speedup in average and retains better stability of performance with the increase of number of variable orders.

ECO re-mapping is a key step in functional ECO tools. It implements a given patch function on a layout database with a limited spare cell resource. Previous ECO re-mapping algorithms are based on existing technology mappers. However, these mappers are not designed to consider the resource limitation and thus the corresponding ECO results are generally not good enough, or even become much worse when the spare cells are sparse. In this paper, we proposed a new solution for ECO remapping. It includes a robust resource-constraint-aware technology mapper and a fast incremental router for wire-length optimization. Moreover, we adopt a Pseudo-Boolean solver to search feasible solutions when the spare cells are sparse. Our experimental results show that our ECO engine can outperform the previous tool in both runtime and routing costs. We also demonstrate the robustness of our tool by performing ECOs on various spare cell limitations.

In modern SoC design flow, verification and validation are key components to reduce time-to-market and enhance product quality. To avoid trade-offs between timing accuracy and simulation speed in RTL simulation and C++/SystemC virtual prototyping, FPGA prototyping has become a better choice in the design flow. However, the time-consuming bring-up procedure and insufficient debugging visibility has impaired its potential strengths in verification and validation. In this paper, we present the technology from InPA Systems in which four different modes of operations, RTL-FPGA co-simulation, SystemC-FPGA co-emulation, vector prototyping, and in-circuit prototyping, are supported. With these different modes of FPGA operations, users can develop and verify their SoCs in different stages of the design flow with different abstraction levels. This methodology efficiently and robustly completes the SoC HW/SW verification and validation flow.

Dynamic power saving is gaining its dominance in modern low power designs, while clock gating, which blocks unnecessary clock switching activities, is one of the most efficient approaches to reduce the dynamic power. In this paper, we exploit the interpolation technique in a SAT-based clock gating algorithm in order to grant a greater flexibility in enlarging the gating capabilities over the original gating candidates. We also developed several techniques to improve the runtime and memory usage of the clock gating algorithm, including a gating capability filter to reduce the number of formal SAT proofs, a dynamic backtracking limit controller to shorten the SAT runs, and a shrinking method to ease the final gate count overhead. The experimental results show that our proposed algorithm can gate up to 2X clock switches with less than 5% area overhead when compared to the state-of-the-art SAT-based clock gating methodology.

To cope with last-minute design bugs and specification changes, engineering change order (ECO) is usually performed toward the end of the design process. This paper proposes an automatic ECO synthesis algorithm by interpolation. In particular, we tackle the problem by a series of partial rectifications. At each step, partial rectification can reduce the functional difference between an old implementation and a new specification. Our algorithm is especially effective for multiple error circuits. Experimental results show the proposed method is far superior to the most recent work and scales well on a set of large circuits.

Virtual platform simulation is an essential technique for early-stage system-level design space exploration and embedded software development. In order to explore the hardware behavior and verify the embedded software, simulation speed and accuracy are the two most critical factors. However, given the increasing complexity of the Multi-Processor System-on-Chip (MPSoC) designs, even the state-of-the-art virtual platform simulation algorithms may suffer from the simulation speed issue. In this paper, we proposed an Ultra Synchronization Checking Method (USCM) for fast and robust virtual platform simulation. We devise a data dependency table (DDT) so that the memory access information by the hardware modules and software programs can be predicted and checked. By reducing the unnecessary synchronizations among simulation modules and utilizing the asynchronous discrete event simulation technique, we can significantly improve the virtual platform simulation speed. Our experimental results show that the proposed USCM can simulate a 32-processor SoC design in the speed of multimillion instructions per second. We also demonstrate that our method is less sensitive to the number of cores in the virtual platform simulation.

Functional ECO has been an indispensible technique in modern VLSI design flow. This paper proposes an ECO engine in a two-phase approach: a matching phase for rectification pair identification and a replacement phase for pair selection and patch minimization. The rectification pair identification algorithm explores rectification pairs between the original circuit and the golden circuit. The rectification pair selector determines final patches through a linear-time heuristic. A gate-recycle process performs patch minimization for final refinement. The experiments show that this ECO engine outperforms a state-of-the-art interpolation-based engine in both patch quality and runtime.

Constrained random simulation is becoming the mainstream methodology in functional verification. In order to achieve the verification closure, a high-throughput and evenly-distributed constrained random pattern generator has become a must. In this paper, we propose a novel Range-Splitting heuristic and a Solution-Density Estimation technique (RSSDE) to partition sample space. The chosen cutting planes target to prune more infeasible subspaces so that the solution densities in other subspaces increase correspondingly. In addition, with statistics-based analyses, the estimated solution densities precisely predict the distribution of solutions. The intermediate statistical information is recorded in a range-splitting tree (RS-tree). By top-down random walking on the RS-tree, random pattern generation produces evenly-distributed patterns with high throughput. Experimental results show that our framework guarantees evenly-distributed stimuli and achieves more than 10× speedup in average when compared to a state-of-the-art commercial generator.

In this paper, we propose a property-specific sequential invariant extraction algorithm to improve the performance of the SAT-based Unbounded Modeling Checkers (UMCs). By analyzing the property-related predicates and their corresponding high-level design constructs such as FSMs and counters, we can quickly identify the sequential invariants that are useful in improving the property proving capabilities. We utilize these sequential invariants to refine the inductive hypothesis in induction-based UMCs, and to improve the accuracy of reachable state approximation in interpolation-based UMCs. The experimental results show that our tool can outperform a state-of-the-art UMC in most cases, especially for the difficult true properties.

In this paper, we proposed a novel simulation scheme, called data-dependency-aware synchronization and scheduling, for SoC virtual platform simulation. In contrast to the conventional clock-or transaction-based synchronization, our simulation scheme can work with the clock decoupling and direct-data-access techniques to implement the trace-driven virtual synchronization methodology. In addition, we further extend the virtual synchronization concept to handle the interrupt signals in the system. This enables the porting of operating system (uCLinux) in our virtual platform. The experimental results show that our virtual platform can achieve 3 to 5 million-instructions-per-second simulation speed, or 44 times speed-up over the conventional cycle accurate approach, while still maintaining the same cycle-count accuracy.

In this paper, we proposed a unified multi-corner multi-mode (MCMM) static timing analysis (STA) engine that can efficiently compute the worst-case delay of the process corners in various very large scaled circuits. Our key contributions include: (1) a seamless integration of the path-and parameter-based branch-and-bound algorithms so that the engine is very robust for different kinds of circuits, (2) an improved search space pruning technique, (3) a simple yet efficient critical path delay bound for the initial search space pruning. Our experimental results show that our engine can significantly outperform the prior MCMM STA approaches in various benchmark circuits with different number of process parameters.

In this paper, we proposed an Automatic Target Constraint Generation (ATCG) technique to automatically generate compact and high-quality constraints for the guided random simulation environment. Our objective is to tackle the biggest bottleneck of the entire constrained random simulation process — the time-consuming and error-prone manual testbench composition process. By taking only the design under verification and simulation coverage as our inputs, our automatic constraint generation technique can successfully generate just a few key constraints while achieving very high simulation coverage. Our experimental results show that the proposed approach can outperform both directed and random simulations in both coverage and simulation runtime for a variety of designs

One of the main purposes to use SystemC in system development is to perform system-level verification in the early design stage. However, simulation is still by far the only available solution for the high-level SystemC design verification. Nonetheless, traditional formal verification techniques, which rely on the translation of designs under verification to logic netlists, cannot be easily adopted here due to the concurrent/asynchronous nature and the abundant synthesis flexibilities of the high-level designs. In this paper, we propose a multi-layer modeling to represent the highlevel SystemC designs. By representing the different aspects of the design with different structures — simulation kernel, predictive synchronization dependence graph (PSDG), and extended Petri net (extPN), our modeling can be very concise and faithfully capture the original design semantics. We develop a formal verification engine on this modeling for the deadlock checks. With various novel ideas to enable the symbolic simulation, bounded model checking (BMC) and invariant checking techniques to work on high-level, our experimental results demonstrate the robustness and effectiveness of the formal deadlock checking on high-level SystemC designs.

Functional rectification in late design stages has been a crucial process in modern complex system design. This paper proposes a robust functional ECO engine, which applies SAT proof minimization and interpolation techniques to automate patch construction to make old implementation and golden specification functionally equivalent. The SAT proof minimization technique provides a sound and efficient way of fixing easy errors, and the interpolation technique provides a complete and robust way of fixing remaining errors. Experimental results show that our engine performs robustly to generate small patches in fixing various design rectification instances.

Functional dependency is concerned with rewriting a Boolean function f as a function h over a set of base functions {g1,¿,gn}, i.e., f = h(g1,¿,gn). It plays an important role in many aspects of electronic design automation (EDA). Prior approaches to the exploration of functional dependency are based on binary decision diagrams (BDDs), which may not be easily scalable to large designs. This paper formulates both single-output and multiple-output functional dependencies as satisfiability (SAT) solving and exploits extensively the capability of a modern SAT solver. Thereby, functional dependency can be detected effectively through incremental SAT solving, and the dependency function h, if it exists, is obtained through Craig interpolation. The proposed method enables (1) scalable detection of functional dependency, (2) fast enumeration of dependency function under a large set of candidate base functions, and (3) potential application to large-scale logic synthesis and formal verification. Experimental results show that the proposed method is far superior to prior work and scales well in dealing with the largest ISCAS and ITC benchmark circuits with up to 200 K gates.

We proposed a novel Boolean Satisfiability (SAT)-controlled redundancy addition and removal (RAR) algorithm to resolve the performance and quality problems of the previous RAR approaches. With the introduction of modern SAT techniques, such as efficient Boolean constraint propagation (BCP), conflict-driven learning, and flexible decision procedure, our RAR engine can identify 10x more alternative wires/gates while achieving 70% reduction in runtime.

Timing closure has always been the biggest bottleneck in the modern VLSI design flow. Traditional timing verification techniques such as Static Timing Analysis (STA) are usually too conservative or sometimes too optimistic. This inaccuracy may lead to an unnecessary procrastination of time to market or even silicon failure. It is mainly due to the inability to detect false paths and handle multiple-input-transitioning effects in the timing analysis process. In this paper, we proposed a novel Formal Static Timing Analysis (FSTA) technique which can model the multiple-input transitioning effects, detect the false paths, and generate an input transition pattern for the true critical path at the same time. This is achieved by tightly integrating a state-of-the-art Boolean Satisfiability (SAT) solver with a STA engine, under a specialized multiple-input-transition timing library. Our experiments compare the FSTA engine with the traditional STA and random simulation techniques. The results show that our approach greatly outperforms random simulation while obtaining more accurate timing analysis results than STA.

In this paper, we proposed a novel interpolant generation algorithm without constructing the resolution graph of the unsatisfiability proof. Our algorithm generates the interpolant by building sub-interpolants from conflict analyses and then merges them based on the last decision conflict. The experimental results show that our algorithm has the advantages over the prior interpolant generation techniques in both memory usage and interpolation circuit size.

Constant-coefficient multipliers are fundamental components in digital signal processing and arithmetic-based systems. Their verification, however, remains difficult and time-consuming. This is caused by the inability to identify the partial products from the number representation system of the constant. In this paper, we introduce an efficient number representation system as an observation on how modern synthesizers interpret constants. We also propose a robust and efficient partial product identification algorithm to improve the verification process. Experimental results show that our algorithm not only reduces the number of failing cases of the verification to one third but also speeds up the verification process by at least an average of 25%.

Functional dependency is concerned with rewriting a Boolean function f as a function h over a set of base functions {g1, ..., gn), i.e. f = h(g1, ..., gn). It plays an important role in many aspects of electronic design automation (EDA), ranging from logic synthesis to formal verification. Prior approaches to the exploration of functional dependency are based on binary decision diagrams (BDDs), which may not be easily scalable to large designs. This paper proposes a novel reformulation that extensively exploits the capability of modern satisfiability (SAT) solvers. Thereby, functional dependency is detected effectively through incremental SAT solving, and the dependency function h, if it exists, is obtained through Craig interpolation. The main strengths of the proposed approach include: (1) fast detection of functional dependency with modest memory consumption and thus scalable to large designs, (2) a full capacity to handle a large set of base functions and thus discovering dependency whenever exists, and (3) potential application to large-scale logic optimization and verification reduction. Experimental results show the proposed method is far superior to prior work and scales well in dealing with the largest ISCAS89 and ITC99 benchmark circuits with up to 200 K gates.

We present a new approach to checking assertion properties for register-transfer level (RTL) design verification. Our approach combines structural word-level automatic test pattern generation (ATPG) and modular arithmetic constraint-solving techniques to solve the constraints imposed by the target assertion property. Our word-level ATPG and implication technique not only solves the constraints on the control logic, but also propagates the logic implications to the datapath. A novel arithmetic constraint solver based on modular number system is then employed to solve the remaining constraints in datapath. The advantages of the new method are threefold. First, the decision-making process of the word-lever ATPG is confined to the selected control signals only. Therefore, the enumeration of enormous number of choices at the datapath signals is completely avoided. Second, our new implication translation techniques allow word-level logic implication being performed across the boundary of datapath and control logic and, therefore, efficiently cut down the ATPG search space. Third, our arithmetic constraint solver is based on modular instead of integral number systems. It can thus avoid the false-negative effect resulting from the bit-vector value modulation. A prototype system has been built that consists of an industrial front-end hardware description language (HDL) parser, a property-to-constraint converter, and the ATPG/arithmetic constraint-solving engine. The experimental results on some public benchmark and industrial circuits demonstrate the efficiency of our approach and its applicability to large industrial designs.

We present a new approach to checking assertion properties for RTI, design verification. Our approach combines structural, word-level automatic test pattern generation (ATPG) and modular arithmetic constraint-solving techniques to solve the constraints imposed by the target assertion property. Our word-level ATPG and implication technique not only solves the constraints on the control logic, but also propagates the logic implications to the datapath. A novel arithmetic constraint solver based on modular number system is then employed to solve the remaining constraints in datapath. The advantages of the new method are threefold. First, the decision-making process of the word-level ATPG is confined to the selected control signals only. Therefore, the enumeration of enormous number of choices at the datapath signals is completely avoided. Second, our new implication translation techniques allow word-level logic implication being performed across the boundary of datapath and control logic, and therefore, efficiently cut down the ATPG search space. Third, our arithmetic constraint solver is based on modular instead of integral number system. It can thus avoid the false negative effect resulting from the bit-vector value modulation. A prototype system has been built which consists of an industrial front-end HDL parser, a property-to-constraint converter and the ATPG/arithmetic constraint-solving engine. The experimental results on some public benchmark and industrial circuits demonstrate the efficiency of our approach and its applicability to large industrial designs.

Static property checking verifies pre-defined functional design rules such as "bus contention", "racing condition"; and "don't-care case". A static property checker typically uses formal verification techniques to prove the property under verification. If the property is proven false, a counter-example is generated for debugging the design. Among the different static property checking approaches, ATPG-based and BDD-based are the most powerful and successful ones. We implement both approaches with several optimization techniques on the same framework to compare their performance. The experimental results on industrial designs show that these two approaches have different strength and weakness in proving the static properties. Furthermore, the results indicate that they often complement each other and therefore a hybrid approach may result in better performance. We propose a static property checker based on combined ATPG and BDD techniques. The experimental results show that this combined approach can prove all the static properties in the test cases while still maintaining comparable performance.

In this paper, we present a practical method for verifying the functional equivalence of two synchronous sequential designs. This tool is based on our earlier framework that uses Automatic Test Pattern Generation (ATPG) techniques for verification. By exploring the structural similarity between the two designs under verification, the complexity can be reduced substantially. We enhance our framework by three innovative features. First, we develop a local BDD-based technique which constructs Binary Decision Diagram (BDD) in terms of some internal signals, for identifying equivalent signal pairs. Second, we incorporate a technique called partial justification to explore not only combinational similarity, but also sequential similarity. This is particularly important when the two designs have a different number of flip-flops. Third, we extend our gate-to-gate equivalence checker for RTL-to-gate verification. Two major issues are considered in this extension: (1) how to model and utilize the external don't care information for verification; and (2) how to extract a subset of unreachable states to speed up the verification process. Compared with existing approaches based on symbolic Finite State Machine (FSM) traversal techniques, our approach is less vulnerable to the memory explosion problem and, therefore, is more suitable for a lot of real-life designs. Experimental results of verifying designs with hundreds of flip-flops will be presented to demonstrate the effectiveness of this approach.

In this paper we present a post-layout timing optimization framework which (1) is library-independent such that it can take the logic-optimized Verilog file as its input netlist, (2) provides a prototype interface which can communicate with any vendor's physical design tools to obtain the accurate timing, topological and physical information, and perform ECO placement and routing, and (3) has fast and powerful rewiring routines that offer an extra solution space beyond the existing physical-level optimization methodologies. We conduct the post-layout performance optimization experiments on some benchmark circuits which are originally optimized by Synopsys's Design Compiler, (with high timing effort), followed by Avant!'s timing-driven place-and-route tool, Apollo. The optimization strategies we used include rewiring, buffer insertion, and cell sizing. To study the trade-offs between these transformations and the benefits of mixing them together, they are applied both separately and closely integrated by some heuristic cost functions. The result shows that by using all these strategies, post-layout timing optimization can further achieve up to 23.9% of improvement after global routing. We also discuss the pros and cons for our proposed procedures applied after global routing versus after detail routing. Some factors that can affect the quality of rewiring such as level of recursive learning and type of rewiring will also be addressed.