Search

The continuously growing complexity of digital circuits and shortening time-to-market has put pressure on the verification methodology. To reach this goal, automatic correction of design bugs has become necessary. Existing methods for automatic correction, suffer from consuming so much time and memory usage which makes them mostly inapplicable for large circuits. Our main idea to come up with a solution is reusing partially corrected circuits in the process of finding the final solution. Experimental results show that, in comparison with existing methods, our method can accurately detect bugs and correct them up to $2.3\times $ faster with less than half of memory usage in comparison with existing methods due to decreasing the number of generated solutions by $2.1\times $ and reducing the size of the SAT problem by $3\times $. [ABSTRACT FROM AUTHOR]

As the complexity of digital designs continuously increases, existing methods to ensure their correctness are facing more serious challenges. Although many studies have been provided to enhance the efficiency of debugging methods, they are still suffering from the lack of scalable automatic correction mechanisms. In this paper, we propose a method for correcting multiple design bugs in gate level circuits. To reduce the correction time, an incremental satisfiability-based mechanism is proposed which not only does not require a complete set of test patterns to produce a gate level implementation which does not exhibit erroneous behavior, but also will not reintroduce old bugs after fixing new bugs. The results show that our method can quickly and accurately suggest corrected gates even for large industrial circuits with many bugs. Average improvements in terms of the runtime and memory usage in comparison with existing methods are ${2.8 \times }$ and ${{6.5 \times }}$ , respectively. Also, the results show that our method compared to the state-of-the-art methods needs ${{2.6 \times }}$ less test patterns. [ABSTRACT FROM AUTHOR]

Having an automatic tool capable of completing all steps of debugging including correction specially for complex designs such as modern processors is ideal for every debugging engineer. Although in theory, quantified Boolean formulas (QBFs) can be used to formulate this class of problems effectively, current solvers are still too immature for accomplishing this goal. In this paper, we propose a scalable symbolic simulation-based method utilizing QBF to correct the candidate bug locations in abstract formal models. We assume that candidate bug locations are determined already, the bug is located in bit-level logic, and the input arguments are known. We define correcting functions and adjust their parameters by formulating the problem as QBF and solving it using symbolic simulation-based method. To further improve scalability, we propose dynamic pruning which breaks the main problem into several smaller subproblems. The efficiency of the proposed method is proved by solving problems for which existing methods are not capable of providing results. [ABSTRACT FROM AUTHOR]

The increasing demand for lower power forces designers to use sophisticated power management strategies such as multivoltage and power gating which are often accompanied with many design bugs. Correcting such bugs can be a timeconsuming process that requires considerable manual efforts. In this paper, we propose a scalable automated method for correcting dynamic power management architectures by an incremental SAT-based mechanism. First, an initial counterexample (CEX) is generated by checking the equivalency between the specification model of the processor and its buggy implementation model. Then, we find two candidate solutions instead of one to satisfy this CEX. If two solutions are not equivalent, we generate new CEX in an iterative process which effectively converges into the final solution. The proposed method enables designers to correct multiple bugs such as missing isolation cells between two power domains, disordering in the sequence of control signals, error in the data restoring or saving, and powering off in always-on domains which are not addressed by existing methods. We have shown the effectiveness of our method on modern processors supporting complex power management mechanisms. The results confirm that our proposed method, respectively, reduces symbolic simulation steps and runtime by 2.33× and 47.93× compared to the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Although using presilicon information in postsilicon debugging phase seems interesting, space and time limitations of existing formal verification tools restrict the possibility of this idea. In this paper, the effective usage of presilicon information to enhance postsilicon trace signal selection in modern processors is discussed. Furthermore, a novel architecture for dynamic per-cycle selection of signals based on the present instruction is implemented and synthesized. In presilicon phase, first, a set of controlling signals and their corresponding rules are extracted manually. Based on these rules, a set of data from model is extracted using an automatic formal method, which determines which signals should be traced at postsilicon according to the values of controlling signals. This mechanism alone results in an average of 79% and 54% bits to be pruned from the traceable signals for Leon3 and multithreaded DLX processors and 86% and 75% improvement when used in conjunction with traditional methods, respectively. [ABSTRACT FROM AUTHOR]

By increasing the complexity of digital systems, verification and debugging of such systems have become a major problem and economic issue. Although many computer aided design (CAD) solutions have been suggested to enhance efficiency of existing debugging approaches, they are still suffering from lack of providing a small set of potential error locations and also automatic correction mechanisms. On the other hand, the ever-growing usage of digital signal processing (DSP), computer graphics and embedded systems applications that can be modeled as polynomial computations in their datapath designs, necessitate an effective method to deal with their verification, debugging and correction. In this paper, we introduce a formal debugging approach based on static slicing and dynamic ranking methods to derive a reduced ordered set of potential error locations. In addition, to speed up finding true errors in the presence of multiple design errors, error candidates are sorted in decreasing order of their probability of being an error. After that, a mutation-based technique is employed to automatically correct bugs even in the case of multiple bugs. In order to evaluate the effectiveness of our approach, we have applied it to several industrial designs. The experimental results show that the proposed technique enables us to locate and correct even multiple bugs with high confidence in a short run time even for complex designs of up to several thousand lines of RTL code. [ABSTRACT FROM PUBLISHER]

By increasing the complexity of system on chip (SoC) designs formal equivalence verification and debugging have become more and more important. Lower level methods such as BDDs and SAT solvers suffer from space and time explosion problems to match sizes of industrial designs in formal equivalence verification and debugging. This paper proposes techniques to verify and debug datapath intensive designs based on a canonical decision diagram called Horner Expansion Diagram (HED). It allows us to check the equivalence between two models in different levels of abstraction, e.g., a Register Transfer Level (RTL) implementation and a non-cycle-accurate specification. In order to reduce the complexity of equivalence checking problem, we tackle the exponential path enumeration problem by automatically identifying internal equivalent conditional expressions as well as suitable merge points. Our debugging technique is based on introducing mutations into the buggy implementation and then observing if the specification is capable of detecting these changes. We make use of a simple heuristic to reduce the number of mutants when dealing with multiple errors. We report the results of deploying our equivalence verification technique on several industrial designs which show 16.8× average memory usage reduction and 8.0× speedup due to merge-point detection. Furthermore, our debugging technique shows 13.7× average memory usage reduction and 4.6× speedup due to using SMT solvers to find equivalent conditions. In addition, the proposed debugging technique can avoid the computation of unnecessary mutants so that the results show 2.9× average reduction of the number of mutants to be processed. [ABSTRACT FROM AUTHOR]

This paper presents a novel automatic debugging algorithm for a postsynthesis combinational arithmetic circuit. The approach is robust under wide varieties of arithmetic circuit architectures and design optimizations. The debugging algorithm in this paper consists of three phases of partial product initialization, XOR extraction, and carry-signal mapping. The run-time complexity of conventional carry-signal-mapping algorithms, such as the approach described by Stoffel and Kunz, is exponential. However, in the proposed algorithm, by making use of some important design issues, we categorize the extracted XORs into half/full-adders to make a very fast debugging algorithm. This approach is robust under multioperand adders, pin-swap techniques, optimizations concerning carry signals or XOR terms, and irregularities, such as commutative and associative laws. Moreover, the XOR extraction in the proposed algorithm is much faster than conventional techniques, as it does not evaluate the whole netlist. The bugs delected in the partial product initialization and the carry-signal mapping can automatically be replaced with proper logics. However, during the XOR extraction phase, the problematic XORs are only reported by the algorithm, and no automatic replacement is performed for such logic gates. To evaluate the effectiveness of our approach, we run it on several arithmetic circuits. [ABSTRACT FROM AUTHOR]