Abstract:
A computer executable tool facilitates integrated circuit design and debugging by working directly at the Register Transfer Level, where most design activities take place. The tool determines when an integrated circuit design produces incorrect output responses for a given set of input vectors. The tool accesses the expected responses and returns the signal paths in the integrated circuit that are responsible for the errors along with suggested changes for fixing the errors. The tool may operate at the RTL, which is above the gate-level abstraction which means that the design errors will be much more readily understood to the designer, and may improve scalability and efficiency.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    The present application claims the benefit of U.S. Provisional Application No. 60/940,290, entitled “Automatic Error Diagnosis and Correction for RTL Designs,” filed on May 25, 2007, which is hereby incorporated by reference herein in its entirety. 
     
    
     BACKGROUND OF THE DISCLOSURE 
       [0002]    1. Field of the Disclosure 
         [0003]    The disclosure relates generally to integrated circuit design and, more particularly, to techniques for detecting and correcting errors in integrated circuit design. 
         [0004]    2. Brief Description of Related Technology 
         [0005]    The dramatic increase in design complexity of modern electronics challenges the ability of developers to ensure their functional correctness. While improvements in verification allow engineers to find a larger fraction of design errors more efficiently, little effort has been devoted to fixing such errors. As a result, debugging remains an expensive and challenging task. 
         [0006]    To address this problem, researchers have recently started to propose techniques that automate the debugging process, by locating the error source within a design and/or by suggesting possible corrections. The root causes of functional errors can be several, ranging from poor specifications, miscommunication among designers, or conceptual or typing mistakes by a designer. Often these errors occur in the Register-Transfer Level (RTL) description of a design because most design activities are carried out at this level. RTL abstraction is used in hardware description languages (HDLs) to create high-level representations of a circuit, from which lower-level representations and wiring actualization can be derived. Although in theory errors can be corrected either at the RTL or the gate level, most solutions proposed in the literature use a gate-level description (netlist) as the underlying model. On one hand, this model presents some valuable advantages. For instance, RTL modifications at late design stages are undesirable because they may invalidate previous optimizations and hamper design closure; errors due to flawed synthesis tools are also only visible at the gate level. Finally, hard-IP blocks usually do not have an associated RTL description. 
         [0007]    On the other hand, fixing errors at the RTL could offer several important advantages not available at the gate level. First, error diagnoses are generally most readily understood at the RTL. Second, in an RTL block the change propagates to all netlists synthesized from that code, while a correction at the gate level is only effective for one netlist. Third, corrections at the RTL require fewer changes, which are more effective, since in general a single erroneous RTL statement may affect a large portion of the corresponding netlist. In addition, the complexity of locating the source of bugs at the gate level grows considerably for compound errors (that is, when several error sources are present in the same design). Finally, since mapping the results of gate-level diagnosis back to the RTL is a difficult task, most often RTL errors can only be located through an RTL-based analysis. 
         [0008]    To support this effort, tools such as waveform viewers and simulation assertions are often used at the forefront of debugging activities in industry. However, even with these tools, diagnosing the root cause of an error and fixing it still requires engineers&#39; expertise, time, and effort. Existing techniques that address these problems range in their scope. For instance, the algorithms developed by Shi et al. “An Efficient Approach for Error Diagnosis in HDL Design”, in  Proc ISCAS,  2003, pp. 732-735, Jiang et al., “Estimating Likelihood of Correctness for Error Candidates to Assist Debugging Faulty HDL Designs,”  ISCAS,  2005, pp. 5682-5685 and Rau et al., “An Efficient Mechanism for Debugging RTL Description”,  IWSOC,  2003, pp. 370-373 generate lists of potentially error locations. Bloem and Wotawa, “Verification and Fault Localization for VHDL Programs”,  Journal of the Telematics Engineering Society  ( TIV ), pp. 30-33, Vol. 2, 2002 take a different approach by formally analyzing an HDL description and its failed properties. Because of this their technique can only be deployed in a formal verification framework and cannot be applied in a simulation-based verification flow common in the industry today. 
         [0009]    The work by Staber et al., “Finding and Fixing Faults”, in  CHARME,  Springer-Verlag LNCS 3725, 2005, pp. 35-49 can diagnose and correct RTL design errors automatically, but it relies on state-transition analysis and hence, it does not scale beyond tens of state bits. In addition, this algorithm requires a correct formal specification of the design, which is rarely available in today&#39;s design environments, because its development is often as challenging as the design process itself. In contrast, the most common type of specification available is a high-level model, often written in a high-level language, which produces the correct I/O behavior of the system. 
         [0010]    To develop a scalable and powerful RTL error diagnosis and correction system, a set of fundamentally new constructs and algorithms are desired. 
       SUMMARY OF THE DISCLOSURE 
       [0011]    In this application we propose several constructs and algorithms that provide a new way to diagnose and correct errors at the RTL, including: (1) an innovative RTL error modeling construct; (2) scalable error-diagnosis algorithms using Pseudo-Boolean constraints, synthesis, and simulation; and (3) a novel error-correction technique using signatures. To empirically validate the techniques, we developed a novel verification framework, called REDIR. To this end, our experiments with industrial designs demonstrate that REDIR is efficient and scalable. In particular, designs up to a few thousand lines of code (e.g., 100K cells after synthesis) can be handled within minutes. In addition, the described techniques can diagnose significantly more bugs than state-of-art gate-level approaches. The results indicate that error diagnosis at the RTL is rather different from that at the gate level, and applying gate level diagnosis algorithms to RTL is ineffective. Since the techniques rely on correct output responses and support both combinational and sequential circuits, they can be applied to various designs in all mainstream verification flows. Therefore, the algorithmic techniques and the overall methodology proposed in our work can greatly facilitate the RTL debugging process and improve the overall verification quality. 
         [0012]    With the present techniques, a controller may use conditional assignments to modify the RTL modules forming the overall RTL design for an integrated circuit. These modified (enriched) RTL modules have conditional assignments that may be adjusted (e.g., switched) by the framework and tested to determine which signals are problematic. The techniques may execute an error-diagnosis algorithm that converts an error-diagnosis problem of the enriched RTL modules into a Pseudo-Boolean (PB) problem, and then may use a PB solver to perform the diagnosis and infer which design RTL signals are responsible for the incorrect output behavior. 
         [0013]    By way of background, PB problems, also called 0-1 integer linear programming problems, are an extension of SATisfiability problems. PB constraints are specified as an inequality with a linear combination of Boolean variables: C 0 p o +C 1 p 1 + . . . +C n-1 p n-1 ≧C n , where the variables p i  are defined over the Boolean set {0, 1}. A PB problem allows the use of an additional objective function, which is a linear expression that should be minimized or maximized under the given constraints. A number of PB solvers have been developed recently by extending existing SAT solvers (for instance, MiniSAT). 
         [0014]    Gate-level Error Diagnosis Techniques—The power and effectiveness of the gate-level error diagnosis techniques have been recently discussed in the work of Smith et al., “Design Diagnosis Using Boolean Satisfiability”,  ASPDAC,  2004, pp. 218-233. In Smith&#39;s error-diagnosis technique, two types of components are added to a given buggy netlist. These components include (1) multiplexers, and (2) an error-cardinality constraint. The purpose of the multiplexers is to model errors—when their select lines are asserted, alternative sources drive the corresponding internal wires to correct the output responses. The number of asserted select lines is limited by the error-cardinality constraint, which is implemented as an adder and a comparator: the adder counts the number of asserted select lines, and its output is forced to a value N using the comparator. The circuit is then converted into Conjunctive Normal Form (CNF), and inputs and outputs are subjected to additional constraints from input vectors and correct output responses, obtained from a high-level model. Error diagnosis is then performed by iteratively solving the CNF using a SAT solver with an increasing value for N, until a solution is found. This Smith&#39;s technique diagnoses errors in combinational circuits only; to diagnose sequential circuits, others (namely Ali et al., “Debugging Sequential Circuits Using Boolean Satisfiability”,  ICCAD,  2004, pp. 44-49) have extended Smith&#39;s work by unrolling the circuit, before the CNF conversion step, M times, where M is the sequential length of the given trace. Similar approach is used in our synthesis-based diagnosis. 
         [0015]    Logic and Symbolic Simulation—Logic simulation models the behavior of a digital circuit by propagating scalar Boolean values (0 and 1) from primary inputs to primary outputs. For example, when simulating 2-input AND with both inputs set to 1, the output 1 is produced. On the other hand, symbolic simulation uses symbols instead of scalar values and produces Boolean expressions at the outputs. As a result, simulating a 2-input XOR with inputs a and b generates an expression “a XOR b” instead of a scalar value. To improve scalability, modern symbolic simulators employ several techniques, including approximation, parameterization and on-the-fly logic simplification. For example, with on-the-fly logic simplification, “0 XOR b” is simplified to b thus reducing the complexity of the expression. Traditional symbolic simulators operate on a gate-level model of a design; however, in recent years simulators operating on RTL descriptions have been proposed. 
         [0016]    Signature-based Resynthesis Techniques—The framework discussed herein may include error repair in addition to error diagnosis. An example of an error repair technique is from the CoR′e framework described by Chang et al., “Fixing Design Errors with Counterexamples and Resynthesis”,  ASPDAC,  2007, pp. 944-949, which models a combinational netlist as a multi-level Boolean network and strives to correct design errors by resynthesizing the sites responsible for erroneous behavior, using information from other nodes in the network. To support error correction, they propose two resynthesis techniques, Entropy-Guided Search (EGS) and Goal-Directed Search (GDS). EGS performs resynthesis by identifying suitable inputs and constructing a truth table using the identified inputs, while GDS performs exhaustive search for resynthesis functions using branch and bound. Their techniques use only signatures of nodes, where the bits in a signature are the simulation values of the given test vectors. A signature is essentially a node&#39;s partial truth table and represents a node&#39;s behavior. Given a set of candidate signatures and a target signature, these techniques can find resynthesis functions that generate the target signature using the candidates. 
         [0017]    Whether from a synthesis-based diagnosis, a simulation-based diagnosis, or a combination of both running simultaneously, the present techniques describe a computer executable framework that facilitates integrated circuit design and debugging by working directly at the Register Transfer Level, where most design activities take place. The framework may be executed in software or as an integrated circuit or other application in hardware. The framework determines when an integrated circuit design produces incorrect output responses for a given set of input vectors by comparing the actual responses with the expected responses. The framework accesses the expected responses and returns the signal paths in the integrated circuit that are responsible for the errors along with suggested changes for fixing the errors. The framework may operate at the RTL, which is above the gate level abstraction which means that the design errors will be much more readily understood to the designer, and may improve scalability and efficiency. 
         [0018]    In accordance with one aspect of the disclosure, a method of diagnosing erroneous behavior of node outputs in a register transfer level (RTL) design containing one or more RTL modules, comprises converting each RTL module to an enriched RTL module having one or more conditional states that each may take the form of different values; identifying an incorrect node output from the RTL design; and adjusting at least one of the conditional states in the enriched RTL modules to correct the incorrect node output from the RTL design. 
         [0019]    In some examples, a method of diagnosing erroneous behavior of node outputs in a Register Transfer Level (RTL) design containing one or more RTL modules, the method comprises: converting each RTL module to an enriched RTL module having one or more conditional states that each may take the form of different values, wherein converting each RTL module to an enriched RTL module comprises performing an insertion of a conditional assignment on at least one RTL variable in each RTL module; identifying an incorrect node output from the one or more RTL modules; and adjusting at least one of the conditional states of the enriched RTL modules by adjusting at least one select variable of the enriched RTL modules to correct the incorrect node output from one or more of the RTL modules. 
         [0020]    In accordance with another aspect of the disclosure, a method of debugging an integrated circuit design expressed through Register Transfer Level (RTL) modules producing intermediate node outputs respectively, comprises determining which of the RTL modules have intermediate node outputs resulting in an incorrect output data; modifying the RTL modules resulting in an incorrect output data with a selectable RTL variable; and adjusting the selectable RTL variable of at least one of the RTL modules until correct output data results. 
         [0021]    In accordance with another aspect of the disclosure, an article a computer-readable medium having stored thereon instructions that, when executed by a computer, cause the computer to: convert register transfer level (RTL) modules of an RTL design to enriched RTL modules each having one or more conditional states that may each take the form of different values; identify an incorrect node output from the RTL modules; and adjust at least one conditional state of the enriched RTL modules to correct the incorrect node output from the RTL modules. 
         [0022]    In some examples, an article comprising a computer-readable medium having stored thereon instructions that, when executed by a computer, cause the computer to: convert Register Transfer Level (RTL) modules of an RTL design to enriched RTL modules each having one or more conditional states that may each take the form of different values, wherein said conversion comprises inserting a conditional assignment on at least one RTL variable in each RTL module, wherein each conditional assignment contains a select variable that may be adjusted to change the conditional state of the respective enriched RTL module; identify an incorrect node output from the RTL modules; and adjust at least one of the conditional states of the enriched RTL modules by adjusting at least one of the select variables to correct the incorrect node output from the RTL modules. 
         [0023]    In accordance with another aspect of the disclosure, for debugging an integrated circuit design expressed through Register Transfer Level (RTL) modules producing intermediate node outputs respectively, an article comprises a computer-readable medium having stored thereon instructions that, when executed by a computer, cause the computer to determine which of the RTL modules have intermediate node outputs resulting in incorrect output data; modify the RTL modules resulting in the incorrect output data with a selectable RTL variable; and adjust the selectable RTL variable of at least one of the modified RTL modules until correct output data results. 
         [0024]    These node outputs may be internal node outputs from one of the RTL modules forming the RTL design or the outputs of Boolean expressions using RTL module node outputs as inputs thereto. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWING FIGURES 
         [0025]    For a more complete understanding of the disclosure, reference should be made to the following detailed description and accompanying drawing figures, in which like reference numerals identify like elements in the figures, and in which: 
           [0026]      FIG. 1  is a block diagram of a RTL level error model and diagnosis tool in accordance with an example; 
           [0027]      FIG. 2  illustrates an example conversion of an RTL module to an enriched RTL module having a conditional assignment in an example implementation; 
           [0028]      FIG. 3  illustrates an example algorithm for inserting a conditional assignment in an RTL module; 
           [0029]      FIG. 4  illustrates an example algorithm for performing error diagnosis using synthesis and circuit unrolling; 
           [0030]      FIG. 5  illustrates an example algorithm for performing error diagnosis using symbolic simulation; 
           [0031]      FIG. 6  illustrates an example circuit containing an error in an RTL module and an enriched RTL model that may be used to correct the incorrect output from the RTL module; and 
           [0032]      FIG. 7  illustrates a signature-construction example in accordance with an example. 
           [0033]      FIG. 8  illustrates Table  1  which lists characteristics of benchmarks in an example implementation; 
           [0034]      FIG. 9  illustrates Table  2  which provides a description of bug inserted into the benchmarks in an example implementation; 
           [0035]      FIG. 10  illustrates Table  3  which illustrates synthesis-based error diagnosis results in an example implementation; 
           [0036]      FIG. 11  illustrates Table  4  which illustrates error correction results in an example implementation; 
           [0037]      FIG. 12  illustrates a technique for RTL level diagnosis and correction in accordance with an example; and 
           [0038]      FIG. 13  illustrates a technique for RTL level diagnosis and correction in accordance with an example. 
       
    
    
       [0039]    While the disclosed methods and apparatus are susceptible of embodiments in various forms, there are illustrated in the drawing (and will hereafter be described) specific embodiments of the invention, with the understanding that the disclosure is intended to be illustrative, and is not intended to limit the invention to the specific embodiments described and illustrated herein. 
       DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0040]    Various techniques are described herein for achieving debugging at the RTL. These techniques generally include: (1) a RTL error model based on conditional assignment insertion; (2) error-diagnosis algorithms using synthesis or symbolic simulation; and (3) an error-correction technique using node behaviors (signatures) that is especially suitable for the RTL. The RTL error model differs from existing debugging techniques in numerous ways that will be apparent to persons of ordinary skill in the art. Conventional techniques are based on software analysis approaches and use MUXes implicitly to identify erroneous statements in the HDL code. On the other hand, the present techniques take a hardware analysis approach by explicitly inserting conditional assignments into the HDL code to identify erroneous signals. This approach allows us to provide significantly more accurate diagnoses than previous RTL solutions because we can analyze designs rigorously using formal hardware verification techniques. As we demonstrate, our techniques are also more precise and more efficient than existing gate-level diagnosis techniques. In addition, identifying RTL errors using gate-level results is difficult. The techniques of the instant application may be implemented in a framework  100  called REDIR (RTL Error Diagnosis and Repair), shown in  FIG. 1 . 
         [0041]    The inputs to the framework  100  include an RTL design  102  containing one or more bugs, a set of test vectors  104  exposing these bugs, and a set of correct output responses  106  for the RTL modules forming the design  102 . These correct outputs may be for the primary outputs over the given test vectors and may be generated by a high-level behavioral model  108 . By way of example, the model  108  may be written in C, C++, SystemC, or similar languages. The framework  100  may operate based on the correct responses at the primary outputs of the high-level model, without need for the correct values of the internal values. Thus, the framework  100  may operate from knowing the correct output responses to the primary outputs, without needing to know the correct output responses for each RTL module in the design  102 . In other examples, the framework  100  may operate by knowing various of the internal node output values for particular RTL modules and assessing these node outputs to determine if the corresponding RTL modules are producing the desired result. 
         [0042]    The output of the framework  100  may be a minimum cardinality set of RTL module signals that should be corrected in order to eliminate erroneous behavior in the design  102 . The set of RTL module signals that should be corrected is termed the symptom core, or the set of incorrect RTL module signals. It is noted that there may be numerous different sets of RTL module signals that may be corrected to correct the erroneous code. Some of these solutions may require the adjustment of more RTL module signals than others of these solutions. The solutions that require the least number of adjustments would be considered the minimum symptom core. There may be several minimum symptom cores, if multiple solutions require the same number of adjustments to the RTL module signals. 
         [0043]    When multiple cores exist, REDIR framework  100  provides all of the possible minimal cardinality sets. In addition, the framework may suggest several possible fixes of the signals in the symptom core to help a designer correct those signals. The framework  100  does not require a formal design specification and relies only on the availability of simulation test vectors. Moreover, the framework  100  supports both combinational and sequential designs; therefore, it can be applied to any mainstream verification flow. In addition, it is more scalable than gate-level approaches as indicated in our experimental results. Some example implementations can diagnose and correct multiple errors in design descriptions with thousands of lines of Verilog code (or approximately 100K cells after synthesis). Compared with state-of-the-art gate-level diagnosis techniques, the REDIR framework  100  may be more than 100× faster in most cases and may be able to diagnose more bugs with higher accuracy. In contrast with existing RTL diagnosis methods that only provide potential error lists, the REDIR framework  100  is significantly more accurate and can point out the exact signals responsible for the errors along with possible fixes. 
       1. RTL Error Diagnosis 
       [0044]    The initial part of RTL design error diagnosis is establishing an RTL error model which is done at a conditional assignment enrichment circuit  110  within the framework  100 . Next two diagnosis methods may be used that either synthesize (block  112 ) or symbolic simulate (block  114 ) the enriched RTL modules from the circuit  110 . 
       RTL Error Modeling 
       [0045]    In the framework  100 , the error-diagnosis problem is represented with (1) an RTL description containing one or more bugs that is composed of variables (wire, registers, I/O) and operations on those variables; (2) a set of test vectors exposing the bugs; and (3) the correct output responses for the given test vectors, usually generated by a high-level behavioral model. The objective of the error diagnosis is to identify a minimal number of variables in the RTL description that are responsible for the design&#39;s erroneous behavior. Moreover, by modifying the logic of those variables, the design errors can be corrected. 
         [0046]    Each RTL module signal found to affect the correctness of the design may be considered a symptom variable, or set of RTL module variables that when adjusted will result in the correct output response. Without minimization, the set of symptom variables reported would include the root cause of the bug and the cone of logic emanating from it: correcting all the symptom variables on any cut across this cone of logic would eliminate the bug. Therefore, by forcing a PB solver  116  to minimize the number of symptom variables and communicate those to a symptom core circuit  118  that may return a solution as close to the root cause of the erroneous behavior as possible. 
         [0047]    To model errors in a design, each RTL module in the design  102  may be converted to an enriched RTL module by introducing a conditional assignment for each RTL variable at the circuit  110 .  FIG. 2  shows an example. Each RTL design  102  may be formed of numerous RTL modules, some of which may operate incorrectly and some of which may operate correctly.  FIG. 2  shows one RTL module  200  (in this example a half adder) and a corresponding enriched RTL module  202  having conditional assignments that have been added to the RTL module  200 . The RTL module  200  includes input vectors  204  and output vectors  206 . The enriched RTL module  202  includes these same input and output vectors, but also includes conditional assignment variables  208 , illustrated in bold. Typically, these conditional assignments would be used for error diagnosis and would not appear in the final synthesized design. The conditional assignments allow the REDIR framework  100  to locate sites of erroneous behavior in RTL design  102 . 
         [0048]    For the illustrated example, suppose that the output responses of the design are incorrect because c should be driven by “a &amp; b” instead of “a|b”, for example through programmer error. That is output c ( 210 ) is a bad RTL module variable. Obviously, to produce the correct output that we obtain from a high-level model (such as the model  102 ), the behavior of c must be changed. To model this situation, the framework  100  inserts a conditional assignment, “assign c n =c sel  ? c f :c”, into the code of the RTL module  200 . The assignment is equivalent to (if (c sel ==1) then c n =c f ; else c n =c. Next, the framework  100  replaces all occurrences of c in the RTL module code with c n , except when c is used on the left-hand-side of an assignment. In the illustrated example, c sel  is a select variable and c f  is a free variable. By asserting the select variable c sel  and using an alternative signal source, modeled by c f , the framework  100  can force the circuit to behave as desired. When the framework  100  identifies the select variables that should be asserted and the correct signals that should drive the corresponding free variables to produce correct circuit behavior, the framework  100  will have diagnosed and fixed the errors in the design. 
         [0049]    The procedure performed by block  110  to introduce a conditional assignment for a design variable v is called conditional assignment-enrichment and an example of its pseudocode is shown in  FIG. 3 . It may be performed on each internal signal, defined in the circuit, including registers. The primary inputs, however, need not be conditional-assignment enriched since by construction they cannot have erroneous values. It also should be noted that for hierarchical designs the primary inputs of a module may be driven by the outputs of another module and, therefore, may assume erroneous values. To handle this situation, we insert conditional assignments into the hierarchical modules&#39; output ports. 
         [0050]    For example, each RTL variable may be assigned to have a select variable and a free variable, where the select variable turns on the conditional assignment in one state and turns it off in another. Other types of select variables may be used instead. This assignment creates an enriched RTL variable (or more broadly module). After adding the conditional assignment, all occurrences of the RTL variable that appear on the right-hand-side of the assignment are replaced with the enriched RTL variable to form the error model. This routine may be applied to each of the RTL variables in each of the RTL modules, or in RTL variables in an identified subset of the RTL modules. 
         [0000]    Diagnosis with Synthesis 
         [0051]    After the error-modeling constructs (e.g., conditional assignments) have been inserted into a design, error diagnosis is used to identify the minimal number of select variables that should be asserted along with the values of their corresponding free variables to produce the correct circuit behavior. The select variables and free variables correspond to particular RTL module variables, therefore identification of particular select variables and free variables will result in identification of the RTL module signals that must be changed. 
         [0052]    There are numerous ways in which to perform diagnosis. One type of error diagnosis technique is implemented using the synthesis and circuit unrolling (block  112  of  FIG. 1 ). In contrast with existing gate-level diagnosis techniques described above, the RTL error modeling constructs are synthesized with the design, which eliminates the need to insert multiplexers at the gate level. In this way, the synthesized netlist faithfully preserves the constructs inserted at the RTL, enabling accurate RTL error diagnosis. This is significantly different from diagnosing design errors at the gate level, since synthesis is only used to generate Boolean expressions between RTL variables, and the synthesized netlist is not the target of the diagnosis. As a result, the present diagnosis techniques have a much smaller search space and run significantly faster than gate-level techniques. 
         [0053]      FIG. 4  outlines an example algorithm that may be used for synthesis-based error diagnosis in the synthesizer  112 . Before the procedure is called, the design is synthesized and its combinational portion is converted to CNF format (designCNF). Other inputs to the procedure include the length of the bug trace, c, as well as the test vectors (inputs) and their correct output responses (outputs). To make sure that the diagnosis applies to all simulation cycles, the algorithm connects the select variables for each unrolled copy to the corresponding CNF variables in the first copy. On the other hand, free variables for each unrolled copy of the circuit are independent. When a solution is found, each asserted select variable is a symptom variable, and the solution for its corresponding free variable is an alternative signal source that can fix the design errors. Note that if state values over time are known, they can be used to constrain the CNF at register boundaries, reducing the sequential error-diagnosis problem to combinational. The constructed CNF, along with the objective to minimize the sum of select variables, forms a Pseudo-Boolean Constraint (PBC). Error diagnosis is then performed in the solver  116  by solving this PBC. 
         [0000]    Diagnosis with Symbolic Simulation 
         [0054]    Another type of diagnosis may be achieved through symbolic simulation (block  114  from  FIG. 1 ). The simulator  114  may perform symbolic simulation directly on the RTL representation and generate Boolean expressions at the primary outputs for all simulated cycles. The outputs&#39; Boolean expressions are used to build a Pseudo-Boolean problem&#39;s instance, that is then handed over to a PB solver  116  for error diagnosis.  FIG. 5  illustrates an example algorithm that uses symbolic simulation (block  114 ) and PB solving (block  116 ). 
         [0055]    We assume that the registers are initialized to known values before the procedure is invoked. We also assume that the circuit contains n conditional assignment-enriched signals named v i , where i={1..n}. Each v i  has a corresponding select variable v i     —     sel  and a free variable v i     —     f . There are o primary outputs, named PO j , where j={1..o}. The subscript “@” is used to prefix the cycle during which the symbols are generated. For each primary output j and for each cycle t we compute expression PO j@t  by symbolically simulating the given RTL design, and also obtain correct output value CPO j@t  from the high-level model. The inputs to the procedure are the RTL design (design), the test vectors (test vectors), and the correct output responses over time (CPO). 
         [0056]    In the algorithm shown in  FIG. 5 , a symbol is initially created for each select variable (line  1 ). During the simulation, a new symbol is created for each free variable in every cycle, and test vectors are applied to primary inputs, as shown in lines  2 - 4 . The reason for creating only one symbol for each select variable is that a conditional assignment should be either activated or inactivated throughout the entire simulation, while each free variable requires a new symbol at every cycle because the value of the variable may change. As a result, the symbols for the select variables are assigned outside the simulation loop, while the symbols for the free variables are assigned in the loop. The values of the free variables can be used as the alternative signal source to produce the correct behavior of the circuit. After simulating one cycle, a Boolean expression for all of the primary outputs are created and saved in PO @t  (line  5 ). After the simulation completes, the generated Boolean expressions for all the primary outputs are constrained by their respective correct output values and are ANDed to form a PBC problem as line  7  shows. In order to minimize the number of symptom variables, the sum of select variables is minimized, which is also added to the PBC as the objective function. The PB solver  112  is then invoked to solve the formulated PBC, as shown in line  8 . 
         [0057]    In these examples, the asserted select variables represent the symptom variables, and the values of the free variables represent the alternative signal sources that can be used to correct the erroneous output responses. Below is an example of a buggy design to illustrate the symbolic simulation-based error-diagnosis technique. 
       EXAMPLE 1 
       [0058]    Assume that the circuit shown (RTL module) in  FIG. 6  contains an error: signal g 1  is erroneously assigned to expression “r 1 |r 2 ” instead of “r 1  &amp; r 2 ”. Conditional assignments, highlighted in boldface, have been inserted into the circuit using the techniques described above. For simplicity reasons, the MUXes at the outputs of registers r 1  and r 2  are not included. The trace that exposes the error in two simulation cycles consists of the following values for inputs {I 1 , I 2 }: {0, 1}, {1, 1}. When the same trace is simulated by a high-level behavioral model, the correct output responses for {O 1 , O 2 } are generated: {0, 0}, {1, 0}. Besides these output responses, no addition information, such as values of internal signals and registers, is required. We annotate the symbols injected during the simulation by their cycle numbers using subscripts. The Boolean expressions for the primary outputs for the two cycles of simulation are: 
         [0000]        O 1 n@1   =O 1 sel   ? O 1 f@1   : [I 1 @1 |( g 1 sel   ? g 1 f@1 : 0)] 
         [0000]        O 2 n@1   =O 2 sel   ? O 2 f@1   : [I 2 @1 &amp; ( g 1 sel   ? g 1 f@1 : 0)] 
         [0000]        O 1 n@2   =O 1 sel   ? O 1 f@2   : {I 1 @2   |[g 1 sel   ? g 1 f@2 : ( I 1 @1 &amp;  I 2 @1 )]} 
         [0000]        O 2 n@2   =O 2 sel   ? O 2 f@2   : {I 2 @2 &amp; [ g 1 sel   ? g 1 f@2 : ( I 1 @1 &amp;  I 2 @1 )]} 
         [0000]    Since the primary inputs are scalar values, the expressions can be greatly simplified during symbolic simulation. For example, we know that I 1   @2 =1; therefore, O 1   n@2  can be simplified to O 1   sel  ? O 1   f@2 : 1. As a result, the Boolean expressions actually generated by the symbolic simulator are: 
         [0000]        O 1 n@1   =O 1 sel   ? O 1 f@1 : ( g 1 sel    ? g 1 f@1 : 0) 
         [0000]        O 2 n@1   =O 2 sel   ? O 2 f@1 : ( g 1 sel    ? g 1 f@1 : 0) 
         [0000]      O1 n@2 =O1 sel ? O1 f@2 : 1 
         [0000]        O 2 n@2   =O 2 sel   ? O 2 f@2 : ( g 1 sel    ? g 1 f@2 : 0) 
         [0000]    To perform error diagnosis, we constrain the output expressions using the correct responses, and then construct a PBC as follows: 
         [0000]        PBC =( O 1 n@1 =0) AND ( O 2 n@1 =0) AND ( O 1 n@2 =1) AND ( O 2 n@2 =0), min( O 1 sel   +O 2 sel   +g 1 sel ). 
         [0000]    One possible solution of this PBC is to assert g 1   sel , which provides a correct symptom core. 
       Handling Hierarchical Designs 
       [0059]    Current circuit designs often have hierarchical structures to allow the circuit to be decomposed into smaller blocks and thus reduce its complexity. The conditional assignment-enriched circuit techniques herein may be instantiated if it is encapsulated as a module in such a hierarchical design. 
         [0060]    The algorithm to insert conditional assignments into a single module m is shown in  FIG. 3 . If m is instantiated inside of another module M, however, conditional assignment-enrichment of M must include an extra step where new inputs are added to all instantiations of m. Therefore, for hierarchical designs, the insertion of conditional assignments is performed bottom-up: conditional assignment-enrichment in a module is executed before it is instantiated by another module. This is achieved by analyzing the design hierarchy and performing conditional assignment-enrichment in a reverse-topological order. 
         [0061]    It is important to note that in hierarchical designs, the select variables of instances of the same module may be shared, while typically the free variables should not be shared. This is because all instances of the same module will have the same symptom variables. As a result, select variables should share the same signals. On the other hand, each instance is allowed to have different values for their internal signals; therefore, each free variable should have its own signal. 
       2. RTL Error Correction 
       [0062]    Generally speaking, the RTL error-correction problem is formulated as follows: given an erroneous RTL description of a digital design, find a variant description for one or more of the modules (e.g., RTL modules) that compose the error so that the new design presents a correct behavior for the errors, while leaving the known-correct behavior (e.g., correct RTL modules) unchanged. 
         [0063]    Although many error-repair techniques exist for gate-level designs, very few studies focus on the RTL. One major reason is the lack of logic representations that can support the logic manipulation required during RTL error correction. In Chang et al., “Fixing Design Errors with Counterexamples and Resynthesis”,  ASPDAC,  2007, pp. 944-949, a framework has been proposed for gate-level error correction. The authors&#39; approach utilizes only signatures, which can be easily calculated via simulation, making their techniques especially suitable for RTL error correction. However, they only applied their techniques to combinational circuits, and they cannot handle design hierarchies. To support the error-correction requirements at the RTL, where most designs contain hierarchies and are sequential, we propose a new error-correction scheme based on similar concepts. The baseline error-correction technique is first described, following that a description of how signatures may be generated at the RTL module to handle hierarchical and sequential designs. 
       Baseline Error Correction Technique 
       [0064]    For a flattened combinational design, error correction may be performed as follows: (1) signatures of the RTL variables within an RTL module are generated using simulation; (2) error diagnosis is performed to find a symptom core which represents the RTL modules with erroneous symptom (RTL) variables; (3) signatures of the symptom (RTL) variables in the symptom core are replaced by the values of their corresponding free variables; and (4) logic synthesis (or resythesis) is applied (as discussed above) to find logic expressions generating the signatures of the symptom variables. By replacing the expressions that generate the functions of the symptom variables with those new expressions, design errors can be corrected. 
       Hierarchical and Sequential Designs 
       [0065]    In a flattened design, each RTL variable represents exactly one logic function. In a hierarchical design, however, each variable may represent more than one logic function. Therefore, we devise the following techniques to construct the signatures of RTL variables. For clarity, we call a variable in an RTL module a module variable and a variable in an instance generated by the module an instance variable. A module variable may generate multiple instance variables if the module is instantiated several times. 
         [0066]    In RTL error correction, the framework  100  modifies the source code of the modules in order to correct the design&#39;s behavior. Since changing an RTL module will affect all the instances produced by the module, the framework  100  concatenates the simulation values of the instance variables derived from the same module variable to produce the signature for the module variable. This way, the framework  100  can guarantee that a change in a module will affect its derived instances in the same way. Similarly, framework  100  concatenates the signatures of the module variable at different cycles for sequential error correction. A signature-construction example is given in  FIG. 7 . Note that to ensure the correctness of error repair, the same instance and cycle orders must be used during the concatenation of signatures for all module variables. 
       EXAMPLE 2 
       [0067]    Using the same circuit as Example 1, the values returned by the PB solver for g 1   f@0  and g 1   f@1  are both 0. Since the inputs to g 1  are {0, 0} and {0, 1} for the first two cycles, RTL error correction returns the following new logic expressions that can fix the error: g 1 =r 1 &amp;r 2 , g 1 =r 1 , etc. Note that although the correct fix is returned, the fix is not unique. In general, longer traces containing various test vectors will identify the error with higher precision and suggest better fixes than short ones. 
         [0068]    Fixing errors involving multi-bit variables is more difficult than fixing errors involving only one-bit variables because different bits in the variable may be generated differently. To solve this problem, the framework  100  may allow the user to insert a conditional assignment for each bit in the variable. Alternatively, the framework  100  can also be configured to consider only the least-significant bit when performing error correction. This is useful when the variable is considered as a whole. 
       3. Example Simulation Results 
       [0069]    In example experiments, we evaluated the performance of the techniques herein with a range of Verilog benchmarks. We used a proprietary Perl-based Verilog parser to insert conditional assignments into RTL code. Synthesis-based diagnosis was implemented using OAGear 0.96 and OpenAccess 2.2, as discussed at http://www.si2.org with RTL Compiler v4.10 from Cadence as the synthesis tool. For simulation-based diagnosis, we adopted an experimental RTL symbolic simulator, Insight 1.4, from Avery Design Systems as discussed at http://www.avery-design.com/. For efficiency, we implemented the techniques described in Eén et al., “An extensible SAT-solver,” in Proc. Theory and Applications of Satisfiability Testing, 2003, pp. 502-518 to convert PB problems to SAT problems and adopted MiniSAT as our SAT solver, which was implemented using that described in Eén et al., “An extensible SAT-solver,” in Proc. Theory and Applications of Satisfiability Testing, 2003, pp. 502-518. All the experiments were conducted on an AMD Opteron 880 (2.4 GHz) Linux workstation with 16 GB memory. The designs under test included several circuits selected from OpenCores, http://www.opencores.org (Pre_norm, MD5, MiniRISC, and CF_FFT), the picojava-II microprocessor (Pipe), and proprietary microprocessor designs DLX and Alpha. 
         [0070]    Bugs (described in Table  2  see  FIG. 9 ) were injected into these benchmarks except DLX and Alpha, which already included bugs. We used constrained-random simulation to generate bug traces for Pipe, Pre_norm, and CF_FFT, while the bug traces for the rest of the benchmarks were generated using the verification environment shipped with the designs. Traces to expose bugs in DLX and Alpha were given by the verification engineer and were generated using a constrained-random simulation tool. The characteristics of these benchmarks are summarized in Table  1  of  FIG. 8 . 
         [0071]    In Table  1 , “RTL #Lines” is the number of lines of RTL code in a design, and “Gate-level #Cells” is the cell count of the synthesized netlist. To compare our results with previous work, we implemented the algorithms for gate-level error diagnosis in Ali et al., “Debugging Sequential Circuits Using Boolean Satisfiability”,  ICCAD,  2004, pp. 44-49 and Smith et al., “Design Diagnosis Using Boolean Satisfiability”,  ASPDAC,  2004, pp. 218-223. In the table, we list the number of MUXes inserted by their techniques in column “#MUXes”, and the number of conditional assignments under “#Assign”. Note that MUXes and conditional assignments are conceptually similar; however, MUXes operate at the gate-level while conditional assignments are for the RTL. 
       Synthesis-Based Error Diagnosis 
       [0072]    In this experiment, we performed combinational and sequential error diagnosis using the synthesis-based techniques described above. For comparison with previous work, we also synthesized the benchmarks and performed gate-level error diagnosis using Smith&#39;s and Ali&#39;s techniques described above. The results are summarized in Table  3  ( FIG. 10 ). Recall that a symptom core suggests a possible set of signals to modify for correcting the design, and it includes one or more symptom variables. In all our experiments, we found that the reported symptom cores included the root causes of errors. In other words, the REDIR framework  100  accurately pointed out the signals that exhibited erroneous behavior. 
       Comparison Between RTL and Gate-Level Error Diagnosis 
       [0073]    This comparison clearly indicates that diagnosing functional errors at the RTL module has significant advantages over the gate level: shorter runtime and more detection power. As Table  3  shows, most errors can be diagnosed using our techniques within a few minutes, while identifying the same errors at the gate level takes more than 48 hours in many cases. One major reason for this is that the number of possible symptom variables (error sites), i.e., internal netlist nodes responsible for the bug, is significantly smaller in RTL diagnosis, as can be observed from the numbers of inserted conditional assignments shown in Table  1 . This is due to the fact that one simple RTL module may be synthesized into a complex netlist, which proliferates the number of error sites. For example, a statement like “a=b+c” creates only one symptom variable at the RTL. Its synthesized netlist, however, may contain hundreds of error sites, depending on the implementation of the adder and the bit-width of the signals. The small number of potential symptom variables at the RTL significantly reduces the search space for PB or SAT solvers and provides very short diagnosis runtime. In addition, one bug at the RTL may transform into multiple simultaneous bugs at the gate level. Since runtime of error diagnosis grows substantially with each additional bug, being able to diagnose errors at the RTL avoids the expensive multi-error diagnosis process at the gate level. 
         [0074]    We also observed that although the runtime of the RTL error diagnosis still increases with each additional bug, its growth rate is much smaller than the growth rate at the gate level. For example, as Table  3  shows, the runtime of the gate-level diagnosis for Pre_norm(A) and (D), which combined (A) and (B), was 63.6 and 88.7 seconds, respectively. For RTL diagnosis, the runtime was 13.2 and 13.8 seconds, respectively. 
       Comparison Between Combinational and Sequential Diagnosis 
       [0075]    The difference between combinational and sequential diagnosis is that sequential diagnosis only uses output responses for constraints, while combinational is allowed to use state values. As Table  3  shows, the runtime of combinational diagnosis is typically shorter, and the number of symptom cores is often smaller. In DLX(D), for example, the combinational technique runs significantly faster than sequential, and returns only three cores, while sequential returns nine. The reason is that combinational diagnosis allows the use of state values, which provide additional constraints to the PB instance. As a result, a PB solver can find solutions faster, and the additional constraints further localize the bugs. Being able to utilize state values is especially important for designs with very deep pipelines, where an error may be observed hundred cycles later. For example, the error injected into CF FFT requires more than 40 cycles to propagate to any primary output, making the use of sequential diagnosis difficult. In addition, bugs that are observed in design states can only be diagnosed when state values are available, such as DLX(G). On the other hand, sequential diagnosis is important when state values are unavailable. For example, the bug injected into the MiniRISC processor changed the state registers, damaging correct state values. In practice, it is also common that only responses at primary outputs are known. Therefore, being able to diagnose errors in combinational and sequential circuits is equally important, and both are supported by the REDIR framework. The comparison between MD5(B) and MD5(C) shows that there is a trade-off between diagnosis runtime and quality: MD5(C) uses a shorter trace and thus requires shorter diagnosis runtime; however, the number of symptom cores is larger than that returned by MD5(B), showing that the results are less accurate. The reason is that longer traces usually contain more information; therefore, they can better localize design errors. One way to obtain short yet high-quality traces is to perform bug trace minimization before error diagnosis. Such minimization techniques can remove redundant information from the bug trace and greatly facilitate error diagnosis. Various techniques for minimization will be known, including that described in Chang et al., “Simulation-based Bug Trace Minimization with BMC-based Refinement”,  ICCAD,  2005, pp. 1045-1051 to minimize the traces for DLX and Alpha. The length of the original traces produced by a constrained-random generator is shown in parentheses. In general, one trace is enough to localize the errors to a small number of symptom cores, and more traces may further reduce this number. 
       Simulation-Based Error Diagnosis 
       [0076]    In this example, the framework  100  was used to perform simulation-based diagnosis using the algorithm with Insight, an experimental RTL symbolic simulator from http://www.avery-design.com/. Benchmarks Pipe and CF FFT were used in this experiment. Simulation took 23.8 and 162.9 seconds to generate SAT instances for these benchmarks, respectively. The SAT solver included in Insight then solved the instances in 1 and 723 seconds respectively, and it successfully identified the design errors. Although the runtime of simulation-based approach is longer than the synthesis based method, it does not require the design to be synthesized in advance, thus saving the synthesizer runtime. 
       Error Correction 
       [0077]    In the example of error-correction, the framework  100  applied the techniques described above (in the RTL error correction section) to fix the errors diagnosed in Table  3 . Combinational diagnosis was used in this example, and the results are summarized in Table  4  ( FIG. 11 ). In the table, “#Cores fixed” is the number of symptom cores that can be corrected using our error-correction techniques, and “#Fixes” is the number of ways to fix the errors. The framework  100  applied GDS first in the experiment, and observed that GDS often returns a large number of valid fixes that can correct the design errors. One reason is that GDS performs exhaustive search to find new logic expressions; therefore, it may find many different ways to produce the same signal. For example, “A AND B′” and “A AND (A XOR B)” are both returned even though they are equivalent. Another reason is that the experiment was conducted, in this example, to only diagnose short bug traces, which may produce spurious fixes: signatures of different variables are the same even though their functions are different. As a result, only the first 100 fixes of the implementation are reported, where the fixes are sorted so that those with smaller number of gates are returned first. Due to the exhaustive-search nature of GDS, memory usage of GDS may be high during the search, as are the cases for benchmarks DLX (C-F) and Alpha. In these benchmarks, GDS ran out of memory, and we relied on EGS to find fixes that can correct the errors. Since EGS only returns one logic expression when fixing an error, the number of possible fixes is significantly smaller. Table  4  shows that valid fixes were not found for benchmarks MD5(B) and DLX(A). The reason is that the bugs in these benchmarks involve multi-bit variables. For example, bug MD5(B) is an incorrect state transition for a 3-bit state register. Because this example only considered the least-significant bits of such variables during error correction, the example did not find a valid fix. Of course, in accordance with the teachings herein, a conditional assignment could be inserted for every bit in a multi-bit variable to address this issue. 
         [0078]    The error-diagnosis results show that the present error modeling construct and diagnosis techniques can effectively localize design errors to a small number of symptom variables. On the other hand, our error-correction results suggest that options to repair the diagnosed errors abound. The reason is that the search space of error correction is much larger than error diagnosis. Numerous solutions may be used to fix a single incorrect RTL module in an integrated circuit design. Thus, finding high quality fixes for a bug requires much more information than providing high-quality diagnoses. Although this can be achieved by diagnosing longer or more numerous bug traces, the runtime of the REDIR framework will also increase. 
         [0079]    To reduce debugging time, in some examples, the error correction techniques can be used to facilitate manual error repair. For example (1) the engineer fixes the RTL code manually to provide new logic functions for the symptom cores identified by error diagnosis; and (2) the REDIR framework simulates the new functions to check whether the signatures of symptom cores can be generated correctly using the new functions. If the signatures cannot be generated by the new functions, then the fix is invalid. In this way, engineers can verify the correctness of their fixes before running verification, which can accelerate the manual error-repair process significantly. 
         [0080]    Experiments were applied to designs as large as 127K cells with traces that can be hundred-cycles long, which are more than 10× larger than the benchmarks reported in conventional RTL error-diagnosis literature. The present techniques can be applied to more complex designs than existing solutions are able to address. 
         [0081]      FIG. 12  illustrates another example technique  300  for RTL diagnosis and correction. A first block  302  identifies the RTL modules of the circuit design, which may include all or a predetermined subset of the RTL modules. A block  304  then determines which of these RTL modules result in incorrect output data, after which a block  306  modifies those RTL modules resulting in the incorrect output data with a selectable variable. That selectable variable is part of a conditional assignment for an RTL variable which conditional assignment also contains a free variable. The conditional state of that RTL variable produces a fixed variable output under a first condition and produces the value of the free variable under a second condition, where the first condition is a first binary condition on the select variable of the conditional state and where the second condition is a second binary condition on the select variable of the conditional state. In this way the binary state of the select variable determines the conditional state of the RTL variable. A block  308  adjusts the selectable RTL variables, one to all, until the correct output data is achieved. After this point an optional block  310  may permanently repair the RTL modules to prevent future incorrect output.  FIG. 13  illustrates a similar technique  300 ′ that is like that of technique  300 , except that the block  306  is replaced with a block  312  that modifies RTL modules other than those resulting in the incorrect output data to nonetheless correct the output data. While blocks  306  and  312  are shown in the alternative, in other examples these blocks may be used in the same system to provide for modification of RTL modules resulting in incorrect output data as well as modifications of RTL modules other than those resulting in incorrect output data. For example, the blocks  306  and  312  may be operated simultaneously as part of the same modification operation. 
         [0082]    The various blocks, operations, and techniques described above may be implemented in hardware, firmware, software, or any combination of hardware, firmware, and/or software. When implemented in software, the software may be stored in any computer readable memory such as on a magnetic disk, an optical disk, or other storage medium, in a RAM or ROM or flash memory of a computer, processor, hard disk drive, optical disk drive, tape drive, etc. Likewise, the software may be delivered to a user or a system via any known or desired delivery method including, for example, on a computer readable disk or other transportable computer storage mechanism or via communication media. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency, infrared and other wireless media. Thus, the software may be delivered to a user or a system via a communication channel such as a telephone line, a DSL line, a cable television line, a wireless communication channel, the Internet, etc. (which are viewed as being the same as or interchangeable with providing such software via a transportable storage medium). When implemented in hardware, the hardware may comprise one or more of discrete components, an integrated circuit, an application-specific integrated circuit (ASIC), etc. 
         [0083]    While the present invention has been described with reference to specific examples, which are intended to be illustrative only and not to be limiting of the invention, it will be apparent to those of ordinary skill in the art that changes, additions and/or deletions may be made to the disclosed embodiments without departing from the spirit and scope of the invention. 
         [0084]    The foregoing description is given for clearness of understanding only, and no unnecessary limitations should be understood therefrom, as modifications within the scope of the invention may be apparent to those having ordinary skill in the art.