Abstract:
A method for reducing false electrical rule violations during the analysis of a digital circuit having mutually exclusive signal relationships therein. The use of designer knowledge about signals which are mutually exclusive in the circuit design is employed to determine, based on all relevant mutually exclusive signal relationships in the circuit design under test, all possible permutations of active signals used in the analysis. For each permutation, the analysis is performed using the active signals associated with the permutation while ignoring the effect of all signals that are inactive based on the mutually exclusive signal relationships. The invention may be applied to any digital circuit test wherein the effect of mutually exclusive signal relationships affects the outcome of the analysis.

Description:
FIELD OF THE INVENTION 
     The present invention pertains generally to electronic circuit testing, and more particularly to a method for reducing false electrical rule violations during the testing of a digital circuit design by making use of designer knowledge about signals which are mutually exclusive in the circuit design. 
     BACKGROUND OF THE INVENTION 
     The semiconductor industry continues to yield integrated circuits (ICs) of increasing density in order to reduce their overall required chip space and therefore allow circuit designs of increasing complexity. At the present time, such ICs can implement complex circuit designs with up to millions of transistors. 
     Due to the sheer volume of transistors and complexity of modern day circuit designs, the testing of such circuit designs prior to actual implementation requires increasingly complex testing tools. These testing tools typically operate on a net list file describing a schematic of the circuit design, which specifies the components, nodes, connections of the components between the nodes, and relative sizes of each of the components. Logic and timing analysis is performed via computer simulations of the circuit design. Given a set of specifications, or electrical rules checks (ERCs), a test will run the analysis and output violations of the specifications. 
     Present day testing tools are limited to generating specification violations for every violation of the electrical rules checks, without regard to the impossibility of such a violation due to signals in the circuit that are mutually exclusive. Accordingly, “false” ERC violations are often reported for signal combinations that cannot actually occur. In a large design, this can result in the reporting of a considerably large number of “false” ERC violations, which get reported to the designers from the testers. Upon investigation, the designers determine that the “false” ERC violations are not really violations at all because the combination of signals that result in the violation cannot actually occur because the signals are mutually exclusive. Accordingly, it will be appreciated that the reporting of false ERC violations results in loss of both designer and tester time, and is thus undesirable. 
     Accordingly, a need exists for a way to communicate mutually exclusive signal information to the testing tool to avoid reporting of ERC violations that cannot in fact occur due to mutually exclusive signals. 
     SUMMARY OF THE INVENTION 
     The present invention is a novel method for reducing the reporting of false ERC violations by a testing tool during the testing of a digital circuit design having mutually exclusive signals. In accordance with the method of the invention, all relevant mutually exclusive signal relationships in the circuit design under test are determined. Then, based on the relevant mutually exclusive signal relationships, all possible permutations of active signals used in the analysis are determined. For each possible permutation, the analysis is performed using the active signals associated with the permutation while ignoring the effect of all signals that are inactive based on the mutually exclusive signal relationships. 
     In a preferred embodiment, the list of relevant mutually exclusive signal relationships in the circuit design under test is performed by obtaining a list of mutually exclusive signal relationships in the circuit, determining a set of signals that are relevant to the circuit, and creating a mutex list comprising each of the mutually exclusive signal relationships in the circuit that include at least two of the signals that are relevant to the circuit. Also in the preferred embodiment, the list of all possible permutations of active signals used in the analysis is performed by creating an active signal list, that comprises one or more active signal elements that each comprise a different permutation of the relevant signals and that also does not include any of the mutually exclusive signal relationships contained in the mutex list. 
     In accordance with the apparatus of the invention, an electrical rules checker for detecting violations of a set of electrical rules in a digital circuit design includes a mutex list generator which reads a mutex file containing a set of mutually exclusive signal relationships of the circuit design. The electrical rules checker also includes an active signal generator which calculates a set of active signal permutations relevant to the circuit that also do not include any of the mutually exclusive signal relationships. A test controller then causes a test to be applied to the circuit design at least once for each different active signal permutation in the set of active signal permutations. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     The invention will be better understood from a reading of the following detailed description taken in conjunction with the drawing in which like reference designators are used to designate like elements, and in which: 
     FIG. 1 is a schematic diagram of a precharge node subcircuit; 
     FIG. 2 is an operational flowchart of a method in accordance with the invention; 
     FIG. 3 is a block diagram of a test system implemented in accordance with the invention; 
     FIG. 4 is a block diagram of an active signal list for the subcircuit of FIG. 1; 
     FIG. 5 is a block diagram of a mutex list for the example subcircuit of FIG. 1; 
     FIGS. 6A-6C are block diagrams of the various stages of creation of an active signal list for the example subcircuit of FIG.  1 . 
    
    
     DETAILED DESCRIPTION 
     A method for reducing the reporting of false electrical rules check violations by a testing tool during the testing of a digital circuit design having mutually exclusive signals is described in detail hereinafter. The method is described in conjunction with a specific example of a dynamic logic pre-charge node subcircuit example implementing a 4-input logical AND-OR function. This example is presented for illustrative purposes only and not by way of limitation, and the inventive principles described herein extend to any digital circuit or subcircuit thereof having mutually exclusive signal relationships therein. In addition, the method is also described in conjunction with the analysis of the subcircuit using a specific test, namely, a “charge leakage” test. Again, this test is presented for illustrative purposes only and not by way of limitation, and the inventive principles described herein extend to the analysis of any digital circuit or subcircuit thereof having mutually exclusive signal relationships therein using any test wherein the effect of mutually exclusive signal relationships affects the outcome of the analysis. 
     FIG. 1 is an example of a well-known precharge node subcircuit  10  that might be found in a larger dynamic logic circuit, and is presented herein for illustrative purposes only and not by way of limitation. As illustrated, pre-charge node subcircuit  10  implements a logical AND-OR function because in order to pull down pre-charged node N 0 , either A and B, or C and D, must both be on. Thus, output node NOUT goes high (logically true) only when neither A and B are both true, nor C and D are both true. In particular, as known by those skilled in the art, node N 0  is precharged high by FET P 1  during a pre-charge phase; thus, output node NOUT is held low by inverter  11  and held stable by FET P 2  as will be recognized as a conventional stability technique by those skilled in the art. During an evaluate phase, precharge FET P 2  is turned off, thereby allowing precharged node N 0  to be pulled down if either inputs A and B, or inputs C and D are respectively both logically true. When an input A, B, C, or D is logically true, a high-level voltage is presented at the gate of the respective FET N 1 , N 2 , N 3 , or N 4 , thereby operating to turn on the respective FET. Thus, if A and B are both logically true, FETs N 1  and N 2  will both turn on, causing the precharged node N 0  to discharge to ground and the output node NOUT to go high. Likewise, if input signals C and D are both logically true, FETs N 3  and N 4  will both turn on, causing the precharged node N 0  to discharge to ground and the output node NOUT to go high. 
     One analysis test that is typically performed on such a circuit is a “charge leakage” test, wherein the relative strengths (or “sizes”) of the FETs implementing the logic function (i.e., FETs N 1 , N 2 , N 3 , and N 4 ) are analyzed to determine whether in a worst case scenario, they will be able to hold the charge on precharged node N 0 . In the example of FIG. 1, the FETs must be able to hold the charge on node N 0  when any of inputs A or B and C or D are true. As known in the art, even in cutoff a small leakage current is produced between the source and drain of a transistor. The larger the size (or width) of the transistor, the more leakage current produced. Accordingly, in a worst case scenario, one of N 1  and N 2  and one of N 3  and N 4  will have to hold the charge on precharged node N 0 . The charge leakage test examines the relative sizes of the transistors N 1 , N 2 , N 3 , and N 4 , to determine what the worst case combined FET strength is for holding the charge. Because N 1  and N 2 , and N 3  and N 4 , are coupled in parallel, the FET strengths of the off FETs are added together for the analysis. As an example of the function of the charge leakage test, suppose the relative strengths of FETs N 1 , N 2 , N 3 , and N 4  are  2 ,  4 ,  6 , and  8  respectively. In this example, the worst case scenario (without any information regarding mutually exclusive relationships of the signals A, B, C and D) occurs when only B and D are off, requiring N 2  (with strength  4 ) and N 4  (with strength  8 ) to hold the charge on node N 0  with a combined strength of  12 . The next worst case scenario occurs when only A and D are off, requiring N 1  and N 4  to hold the charge on node N 0  with a combined strength of  10 . If the charge leakage test signals an ERC violation for any combined signal strength of 10 or greater, both violations will be reported. However, if it turns out that signals B and D are mutually exclusive, the reporting of the violation of the N 2  and N 4  combination is actually “false” 
     The designers are aware of which signals in the circuit design are mutually exclusive. The present invention uses this knowledge of mutually exclusive signals in the circuit design to prevent the reporting of “false” ERC violations by the testing tool. FIG. 2 is an operational flowchart of the method of the invention, and FIG. 3 is a block diagram of a test system implemented in accordance with the invention. As illustrated in the flowchart of FIG. 2, the mutually exclusive signals in the circuit design under test are obtained  102 . In the illustrative embodiment, the circuit designers enter all known mutually exclusive signals in an ASCII file  25  which is read by an electrical rules checker (ERC)  20 . The ERC builds  104  a model of the circuit design, or an extracted subcircuit thereof, and finds  106  the mutually exclusive signal relationships relevant to the circuit or subcircuit (hereinafter subcircuit) under test. The ERC then calculates  108  all of the active signal permutations of the signals relevant to the subcircuit under test, but not including any of the mutually exclusive signal combinations that were found in step  106 . Then, for each untested active signal permutation calculated in step  108 , as determined in step  110 , the tester  30  is conditioned  112  to ignore the effect of any signal not included in the active signal permutation, and the test is run  114  applying the particular active signal permutation for that iteration  110 . In this manner, none of the ERC violations detected will include “false” violations due to mutually exclusive signal relationships as long as the relationship was included in the mutex file  25 . It will be appreciated that this invention thereby reduces the debug time of a circuit design by eliminating the time required for investigation of “false” ERC violations due to mutually exclusive signal relationships. 
     Applying the invention to the AND-OR gate precharge node subcircuit  10  of FIG. 1, suppose that the designer knows that the signals A and C are mutually exclusive and that the signals B and D are mutually exclusive. Accordingly, the designers communicate this known information to the ERC tool  20  via mutex file  25 . ERC  20  reads mutex file  25  and creates a list of mutually exclusive signals for the subcircuit under test. In the illustrative embodiment, ERC  20  extracts a logic subcircuit for each pre-charge node in the design. In the illustrative embodiment, the pre-charge node subcircuit  10  is modeled by the tester  30  in a conventional manner. The ERC  20  determines the relevant signals of the subcircuit  10 , which include input signals A, B, C, and D. The mutually exclusive signal relationships relevant to the subcircuit  10  are extracted from the mutex file  25 , thereby communicating to the ERC  20  that there are mutex signal relationships including A and C, and B and D, applicable to the testing of subcircuit  10 . ERC  20  then builds a list of allowable active signal combinations applicable to subcircuit  10 . The active signal list.includes A and B, A and D, C and B, and C and D. The active signal list notably does not include impossible signal combinations including A and C, or B and D. ERC  20  then runs the test once for each active signal combination and reports any violations detected during the running of the tests. 
     Appendix A contains a software implementation written in C of one illustrative embodiment for implementing the invention. This embodiment includes a top-level routing called build_mutex_list build_mutex_list returns an active signal list for a given subcircuit under test. Each element in the active signal list includes a list of “active” signals that are to be included in the analysis for one iteration of the test. The number of elements in the active signal list is corresponds to the number of iterations that the test will be run, each time with a different set of “active” signals corresponding to one element in the list. The number of elements in the active signal list depends on the number of permutations of relevant mutually exclusive signal relationships in the subcircuit under test. Accordingly, in the example of FIG. 1, there are four elements in the active signal list  40 , shown in FIG.  4 . The first element  42  in the list  40  includes the permutation including active signals A and B; the second element  44  includes the permutation including active signals A and D; the third element  46  includes the permutation including active signals C and B; and the fourth element  48  includes the permutation including active signals C and D. 
     Build_mutex_list calls a routine called build_circuit_mutex_list in order to examine the circuit under test and determine which mutually exclusive signal relationships are relevant to the analysis. Build_circuit_mutex_list examines all the signals in the circuit under test and returns a circuit mutex list, which includes a linked list of all signals relevant to the subcircuit under test that have a mutually exclusive relationship to another signal in the subcircuit. In the example of FIG. 1, build_circuit_mutex_list returns a circuit mutex list  50 , shown in FIG. 5, with two elements including a first element  52  identifying the mutually exclusive relationship between signals A and C and a second element  54  identifying the mutually exclusive relationship between signals B and D. 
     Routing calc_num_mutex_lists calculates the total number of elements needed in the active signal list  40  based on the contents of the circuit mutex list  50 . The number of elements need in the active signal list  40  is calculated by stepping along the circuit mutex list  50  and accumulating a total count. The total count is initialized to zero, and the list pointer points to the first link in the circuit mutex list  50  and increments the total count for each entry in the first element. The list pointer is then incremented to point to the next link in the circuit mutex list  50 , and the total count is incremented for each entry in the second element. This process is repeated for each element in the circuit mutex list  50 . In the example of FIG. 5, there are two mutually exclusive signals (A and C) in the first element  52 . Accordingly, the total count is incremented twice. There are two mutually exclusive signals (B and D) in the second element  54 . Accordingly, the total count is increment twice more. Thus, the final total count is 4, corresponding to the number of entries that the active signal list  40  will contain. 
     Once the number of entries in the active signal list  40  is calculated, a linked list is created by routine create_mutex_lists with a number of entries equal to the number of entries calculated by the calc_num_mutex_lists routine. This is illustrated in FIG.  6 A. Create_mutex_lists then enters the active signals into the active signal list  40  by repeatedly running through the active signal list and simultaneously running through the circuit mutex list  50 . A repeat count is used to determine how many successive times across the active signal list a particular active signal is deposited. The repeat count starts at 1. There are three loops in this routine: 
     loop A—an outermost while loop (over the circuit mutex list) 
     loop B—an inner for loop (over the active signal list of elements) 
     loop C—an innermost for loop (over the repeat count) 
     The outermost loop (loop A) steps through the circuit mutex list. There are two for loops nested within the outermost loop. The outer for loop (loop B) iterates as many times as there are elements in the active signa list  40  (in this case 4 times). Each one of the active signal list elements is visited to add a sub-element (if appropriate). The inner loop (loop C) counts the number of elements in the active signal list into which to deposit this signal. Thus, after the first iteration through the outermost loop, the active signal list  40  contains the elements and sub-elements shown in FIG.  6 B. 
     At the end of the outermost for loop (loop B), the repeat count is updated to repeat_count=repeat_count * count_node_nutexes for this link in the circuit mutex list. In this example, this link has the list A→B, so count_node_mutexes returns  2 , and repeat —count= 1*2=2. After the second iteration through the outermost loop, the active signal list  40  contains the elements and sub-elements shown in FIG.  6 C. 
     Although the invention has been described in terms of the illustrative embodiments, it will be appreciated by those skilled in the art that various changes and modifications may be made to the illustrative embodiments without departing from the spirit or scope of the invention. It is intended that the scope of the invention not be limited in any way to the illustrative embodiment shown and described but that the invention be limited only by the claims appended hereto.