Abstract:
A method and apparatus for modifying a synchronous logic network so that the hold slack calculated at all pins is greater than or equal to a user-specified threshold, with the condition that the setup slack at any pin does not become negative or smaller than a user-specified margin. The result is an improved design which is less likely to fail due to a hold time violation. The method and apparatus introduce a limited number of logic cells which helps keep power consumption and design size to a minimum.

Description:
FIELD OF INVENTION 
       [0001]    This application is related to improved timing analysis. 
       BACKGROUND 
       [0002]    A logic network of a circuit may be analyzed to identify timing problems in the design of a circuit. A single hold analysis violation that manifests in silicon can cause, a functional failure, rendering the product unusable. A thorough analysis and resolution of all potential hold failures is therefore critical to the viability of the final product. When a particular place in a design exhibits a hold race, (a violation of the hold analysis), tens of thousands of similar paths could be related to this same electrical failure. Determining the most optimal location to insert delay cells to address all failures is challenging and resource intensive. 
         [0003]    Design engineers must add enough delay cells within a path to slow down the data in order to meet the hold requirement of the downstream flop, but must avoid putting too many delay cells in, which may violate the setup requirements of the path and related paths. There is a balance between having just the right amount of logic to meet the hold requirements and not breaking the timing requirements. 
         [0004]    There may be several ways to insert delay cells to fix hold failures and not violate setup timing requirements. However, some possible solutions may adversely impact power if too many delay cells are inserted into a design. 
         [0005]    There is a need to address situations where there is a hold race, and to provide automated feedback to design engineers to enable a solution which optimizes a balance in delay, power, and electrical robustness. Currently, there is a need to identify an optimal set and location of points to address hold analysis in a structure custom cell-based design. 
       SUMMARY OF EMBODIMENTS 
       [0006]    A method and apparatus for modifying a synchronous logic network so that the hold slack calculated at all pins is greater than or equal to a user-specified threshold, with the condition that the setup slack at any pin does not become negative or smaller than a user-specified margin. The result is an improved design which is less likely to fail due to a hold time violation. The method and apparatus limit the number of logic cells, which helps keep power consumption and design size to a minimum. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    A more detailed understanding may be had from the following description, given by way of example in conjunction with the accompanying drawings wherein: 
           [0008]      FIG. 1  is a schematic representation of a logic network; 
           [0009]      FIG. 2  shows pins labeled above with setup slack and below with hold slack; 
           [0010]      FIG. 3  shows pins with a critical hold slack; 
           [0011]      FIG. 4  shows the process of improving hold slack in a structure custom cell-based design. 
           [0012]      FIG. 5  shows a critical network resulting from  FIG. 3  and a user specified threshold of 0 (the pins are labeled with critical congestion values); 
           [0013]      FIG. 6  shows forward levelized order: A, B, C . . . L and reverse levelized order L, K, J . . . A; 
           [0014]      FIG. 7  shows pins in a logic network labeled with forward and backward path counts; 
           [0015]      FIG. 8  shows predecessors and successors (pins are labeled with general congestion values); 
           [0016]      FIG. 9  shows pins in a network for topological sorting; 
           [0017]      FIG. 10  shows a chart grouping the pins in the critical network of  FIG. 5  into classes with equivalent hold slacks; 
           [0018]      FIG. 11  shows a chart ranking the pins of Class B, wherein each pin in Class B is ranked based on it critical congestion value; 
           [0019]      FIG. 12  shows a logic cone; and 
           [0020]      FIG. 13  shows a fixed network with inserted delay cells. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    Logic networks typically comprise logic cells and state cells. State cells may provide storage for logic values and may serve as memory for a digital system. In a synchronized logic network, state cells may change value in synchrony with a periodic clock signal.  FIG. 1  is a schematic representation of a logic network.  FIG. 1  shows a plurality of state cells  110 , a clock  120 , a plurality of logic cells  130 , and the pins  140  associated with each logic cell  130 . State cells  110  are a type of cell that captures logic values to be preserved for the next clock  120  cycle. Logic cells  130  are cells with calculated values based on the logic values of the state cells  110 . Logic cells  130 , or logic gates, differ from state cells  110  in that they are not synchronized to a clock  120  signal and may transmit logic from input to output as soon as a clock  120  signal arrives at the input, (but subject to a delay inherent to logic cells  130 ). 
         [0022]    A state cell  110  may be configured to change state when a clock  120  signal transitions from a logic value 0 to a logic value 1. In this case, the state cell may capture the data on the clock  120  signal&#39;s rising transition. To successfully capture the data, the signal at the input of the state cell  110  must be present some amount of time before the clock signal rises. This margin of time may be called the setup time of the cell. Subtracting the setup time from the time at which the clock signal may rise yields the required setup arrival time (T rs ). If the state cell  110 &#39;s input data arrives after the T rs  its logic value may not be captured by the state cell  110 . This may result in a failure of the system in which the logic network is realized. 
         [0023]    The state cell  110 &#39;s input signal should arrive early enough to avoid violating the setup constraint, but it must not arrive too early. Otherwise, the state cell  110  will not have enough time to read the value from the previous computation. This may be avoided by ensuring that the signal holds constant for an amount of time past the capturing transition of the clock  120 . This margin may be called the state cell  110 &#39;s hold time. 
         [0024]    To verify the viability of a design, a static timing analyzer performs static timing analysis (STA) to examine a representation of the logic network to reveal areas which may cause failures related to setup and hold constraints. 
         [0025]    For each pin  140  in the design, the STA may calculate the maximum arrival time (T max ), the minimum arrival time (T min ), the required setup arrival time (T rs ), the required hold arrival time (T rh ), the setup slack, and the hold slack. T max  may be the upper-bounded time at which a signal may arrive, (i.e., signal may transition), at the pin. T min  may be the lower-bounded time at which a signal may transition at the pin. T rs  may be the time before which all signals of the current cycle of computation must arrive to avoid violating any setup constraint. T rh  may be the time after which all signals of the next cycle of computation must arrive to avoid violating any hold constraint. 
         [0026]    The setup slack may be the pin  140 &#39;s T rs  minus the pin  140 &#39;s T max . A positive value may represent the amount of time delay which may be inserted without violating any setup constraints; (in other words how much room exists to slow down the path). A negative value may represent the amount by which a setup constraint has been violated. 
         [0027]    The hold slack may be the pin  140 &#39;s T rh  minus the pin  140 &#39;s T min . A positive value may represent the amount of delay which may be removed without violating any hold constraints, in other words how much room exists to speed up the path. A negative value may represent the amount by which a hold constraint is violated. 
         [0028]    The STA may calculate the clock cycle time, described above, the setup and hold times of the states cells  110 , and other data such as the connectivity of the design, the delay inherent to each logic cell  130 , and the delay properties of the cell interconnections. 
         [0029]      FIG. 2  illustrates a logic network  200  with setup slacks  210  (at the top of each pin) and hold slacks  220  (at the bottom of each pin) as a static timing analyzer might calculate. In practice, the numeric values contain more significant digits. It should be noted that different slack values may be associated with rising versus falling signals and with different clock phases. Networks may vary in the number of cells and interconnections. Cell delays associated with setup slack calculation may be different than those used for hold slack calculation. 
         [0030]      FIG. 3  illustrates pins  304  (for example) with critical hold slack. Pin  304  (for example) is one of the pins located within the dotted line of  FIG. 2 . A pin  304  may have critical hold slack, −2, where the value of the hold slack is less than or equal to a user-specified threshold. In  FIG. 3 , the user-specified threshold has pins with the greatest critical congestion are ranked highest (step  450 ). For each pin, in order of decreasing rank, a determination is made whether the pin has been previously tagged (step  460 ). If a pin has been previously tagged, it may already be marked with the number of times STA was performed (step  480 ). If the pin has not been tagged before or if it has been tagged, but only with a number of times less than the number of times STA has been performed, it is recommended as an insertion point (step  470 ). The network is then modified by inserting delay cells at each of the recommended insertion points (step  490 ). The method is repeated until no further pins are recommended (step  495 ). 
         [0031]    First, a static timing analysis may be performed (step  410  in  FIG. 4 ) by an STA on a representation of the design. The STA calculates the setup slack and hold slack at all pins in the network and annotates a schematic with numerical values, as described above in  FIG. 2 . 
         [0032]    Second, the general congestion of the logic network may be calculated (step  420  in  FIG. 4 ). The general congestion may be defined as the number of unique paths that exist through a pin in the logic network. The value of general congestion may be used later in the process as a “tie breaker” when pins in a critical network are ranked (step  450  in  FIG. 4 ). 
         [0033]    A “critical network” may be defined as a reduced version of the logic network with elements removed. The critical network may be obtained by removing pins that are sub-critical, (having a calculated hold slack that is greater than a user-specified threshold). The critical network is shown within the dotted lines of  FIG. 3 . Each pin  304  (for example) in  FIG. 3  that has a hold slack less than or equal to zero is used to form the critical network The critical network may be conceptual, and removing pins is not a step in the process described. It is described herein so that the concept of “critical congestion” may be established. 
         [0034]    Third, the critical congestion for each pin in the critical network may be calculated (step  430  in  FIG. 4 ). Critical congestion may be defined as the congestion calculated in the critical network.  FIG. 5  illustrates the pins  501  (for example) in the critical network labeled with a critical congestion value. In practice, the calculation of critical congestion may be implemented algorithmically using a representation of the entire network. As describe hereinafter, congestion, both general and critical, may be calculated, by performing a calculation at each pin in a particular order. This can be determined in one of several ways including levelization and topological sort. 
         [0035]    Levelization, is a process by which pins are grouped into levels A, B, C, etc. which can be seen in  FIG. 6 . Congestion may be calculated via levelization, using three steps. First, the backward path count at every pin in a forward levelized order A, B, C . . . L may be calculated. If a pin is the output of a state cell or is a primary output, (a logic net intended to present digital information to other parts of a system, i.e. logic that is not part of the design being considered), it is labeled with a backward path count of 1. Otherwise label it with a backward path count equal to the sum of the backward path counts of its predecessors. Second, the forward path count at every pin in a reverse levelized order L, K, J . . . A may be calculated. If the pin is the input of a state cell or is a primary output, it is labeled with a forward path count of 1. Otherwise it is labeled with a forward path count equal to the sum of the forward path counts of its successors. Third, for each pin, the forward path count is multiplied with its backward path count to obtain a congestion value. 
         [0036]      FIG. 7  shows a logic network  700  with pin  720  (for example) with a forward path count  701  and a backward path count  702 . To calculate general congestion of pin  720  levelization may be used following the steps described above. First a backward path count  702  is calculated. Pin  720  is an output of a state cell and therefore has a backward path count  702  of 1. Second a forward path count  701  is calculated. Pin  720  is not an input of a state cell or a primary output and therefore has a forward path count  701  equal to the sum of pin  720 &#39;s successors, pin  710 . Pin  710  has a forward path count  701  equal to 4 and therefore pin  720  has a forward path count  701  equal to 4. Third, the backward path count  702  of pin  720  has a value of 1 and the forward path count  701  of pin  720  has a value of 4 are multiplied together to get a general congestion of 4. 
         [0037]    A second calculation of general congestion for a pin  710  (for example), that is not a state cell or a primary input, is also described. First, the backward path count  702  of pin  710  is calculated. Pin  710  has a backward path count  702  equal to the sum of the backward path counts  702  of pin  710 &#39;s predecessors, pins  720  and  730 . Pin  720  has a backward path count  702  of 1 and pin  730  has a backward path count  702  of 1 and when the two pins  720  and  730  are summed, a backward path count  702  of 2 is the resulting backward path count  702  for pin  710 . Second, the forward path  701  of pin  710  is calculated. Pin  710  has a forward path count  701  equal to the sum of the forward path counts  701  of pin  710 &#39;s successors, pins  740 ,  750 ,  760 , and  770 . Pin  740  has a forward path count  701  of 1, pin  750  has a forward path count  701  of 1, pin  760  has a forward path count  701  of 1, and pin  770  has a forward path count  701  and when pins  740 ,  750 ,  760 , and  770  are summed, a forward path count  701  of 4 is the resulting forward path count  701  for pin  710 . Third, the backward path count  702  of pin  710  has a value of 2 and the forward path count  701  of pin  710  has a value of 4 are multiplied together to get a general congestion value of 8. 
         [0038]      FIG. 8  illustrates the value of general congestion for pin  810  (equivalent to pin  710  in  FIG. 7 ) based on the calculations described above. As can be seen in  FIG. 8 , the general congestion value of pin  810  is equal to 8 and the general congestion value of pin  840  (equivalent to pin  720  in  FIG. 7 ) is 4.  FIG. 8  also shows the predecessors  820  and successors  830  of pin  810 . 
         [0039]    Topological sort is a method for arranging the nodes of a directed acyclic graph (DAG) in a particular order which can be seen in  FIG. 9 . A logic network  900  can be represented as a DAG where a pin is a node  1  (for example) and edge  1 A and  1 B (for example) are directed from each node  1  to its successors, nodes  4  and  5 . Topological sorting may calculate congestion using several steps. First, a list of start nodes  1 ,  2 , and  3 , nodes which have no incoming edges, are inserted into a set S, (at least one such node must exist in an acyclic graph). Second, an empty list L is created that will contain the sorted nodes. Third, a node  1  (for example) is removed from set S and inserted into list L. Fourth, for each node  4  (for example) (a node with an edge  1 B from node  1  to node  4 ), remove the edge  1 B from the graph. Fifth, if node  4  has no other incoming edges  2 A, then inset node  4  into set S. However, because node  4  has another incoming edge  2 A, the topological sorting moves onto another node  2  (for example) in set S. If the logic network  900  still has edges, an error message is output, meaning that the graph has at least one cycle. If the logic network  900  does not still have edges, a message is output with the proposed topologically sorted order of list L. 
         [0040]    An alternative method for topological sort is based on depth-first search. First, a list of start nodes  1 ,  2 , and  3  are inserted into a set S. Second, an empty list L is created that will contain the sorted nodes. Third, if node  1  (for example) in set S has not been visited yet then mark node  1  as visited. Fourth, if node  4  (for example) (a node with an edge  1 B from node  1  to node  4 ), has not been visited yet then mark node  4  as visited. Fifth, add node  1  to list L. Each node  4  (for example) gets added to list L only after considering all nodes on which node  4  depends. Another alternative method bypasses the aforementioned steps, processing the path count of each pin immediately in lieu of being added to a list. 
         [0041]    Fourth, each pin in the critical network may be grouped into a class (step  440  in  FIG. 4 ) where pins with approximately equivalent hold slacks are grouped into the same class (for simplicity, the example provided has hold slacks with whole numbers). The user may specify a rule for numeric rounding to identify what is approximately equivalent. Pins with a negative setup slack or a setup slack less than a user-specified value are excluded. Grouping the pins into classes may be used to prioritize the pins that are causing the biggest problem in the logic network. 
         [0042]      FIG. 10  illustrates a chart grouping the pins in the critical network of  FIG. 5  into classes with equivalent hold slack (the hold slack values of  FIG. 3  are used to sort the pins of the critical network in  FIG. 5 ). Class A has a hold slack of 1, Class B has a hold slack of 2, and Class C has a hold slack of 4. As shown in  FIG. 8 , pins  510 ,  511 , and  513  are all grouped in Class A, based on the equivalent hold slack value of 1. Pins  501 ,  504 ,  505 ,  506 ,  512 ,  514 ,  515 ,  516 ,  517 ,  518 ,  521 ,  522 ,  523 ,  524 ,  525 , and  527  are all grouped in Class B, based on the equivalent hold slack value of 2. All the remaining pins in the critical network of  FIG. 5  are grouped in Class C, based on the equivalent hold slack value of 4. 
         [0043]    Fifth, the pins in each pin class may be ranked by order of calculated critical congestion (step  450  in  FIG. 4 ), starting with the class of pins that has the least hold slack and continuing with the remaining classes in order of increasing hold slack. The pins in each pin class may continue to be ranked until no other classes exist or until a class is reached with a hold slack greater than the user specified-threshold. The pin having the greatest critical congestion is ranked highest. In the case where two or more pins have the same critical congestion, the pins may then be ranked by their general congestion. A pin with less calculated general congestion, calculated above (step  420  in  FIG. 4 ), is ranked higher. 
         [0044]      FIG. 11  illustrates a chart ranking the pins of Class C. Each pin in Class C is ranked based on it critical congestion value (the critical congestion values of  FIG. 5  are used to rank the pins). Pins  502  and  509  are ranked 1 because they have the highest critical congestion value, 2, while the remaining pins are all ranked 2 because they have a critical congestion value of 1. Pins  502  and  509  have the same critical congestion value and in order to break the tie, the general congestion value of both pins  502  and  509  is considered. The pin with the lower general congestion is ranked higher. As shown in  FIG. 11 , pin  509  has a lower general congestion, a value of 8, and is therefore ranked higher than pin  502 . The last column in  FIG. 11  illustrates the final ranking of all pins after the tie between pins  502  and  509  has been broken. Pin  509  is ranked 1 overall. 
         [0045]    For each pin, in order of decreasing rank, it may be determined whether the pin has been tagged with the number of times STA has been performed. If a pin has been tagged in a previous iteration, it may already be marked with a number (step  480  in  FIG. 4 ). For example if this is the fourth time STA has been performed, the pin may have been identified as an insertion point ht second time STA was performed and would be marked with a 2. Therefore, since 2 is less than 4, this pin is recommended as an insertion point. If a pin has not been tagged or it has been tagged with a number less than the number of times STA has been performed, recommend this pin as an insertion point for a delay cell (step  470  in  FIG. 4 ). This pin is tagged and the pins in its logic cone with the number of times STA has been performed.  FIG. 12  illustrates a logic cone  1210 . A logic cone  1210  of pin  1220  may be defined as a set of pins that can be reached by traversing the network in either a forward or backward manner starting from pin  1220 . A logic cone  1210  may be the set of all pins contained in both the transitive fan-in and transitive fan-out. 
         [0046]    Sixth, the network may be modified by inserting delay cells at each of the recommended insertion points (step  490  in  FIG. 4 ). 
         [0047]    Steps one to six may be repeated until no further pins are recommended (step  495  in  FIG. 4 ), providing an improved network which is less likely to fail due to hold time violation.  FIG. 13  illustrates a fixed network with inserted delay cells. The network  1300  includes inserted delay cells  1350  (one at pin  509  of  FIG. 5 , which was ranked 1 and therefore recommended as an insertion point for a delay cell). The hold slack  1330  of each pin has a value greater or equal to a user-specified threshold of zero. These hold slack  1330  (for example) values illustrate that the inserted delay cells  1350  may improve the network and decrease the likelihood of failing due to a hold time violation. 
         [0048]    Although features and elements are described above in particular combinations, each feature or element may be used alone without the other features and elements or in various combinations with or without other features and elements. The apparatus described herein may be manufactured by using a computer program, software, or firmware incorporated in a computer-readable storage medium for execution by a general purpose computer or a processor. Examples of computer-readable storage mediums include a read only memory (ROM), a random access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs). 
         [0049]    Embodiments of the present invention may be represented as instructions and data stored in a computer-readable storage medium. For example, aspects of the present invention may be implemented using Verilog, which is a hardware description language (HDL). When processed, Verilog data instructions may generate other intermediary data (e.g., netlists, GDS data, or the like) that may be used to perform a manufacturing process implemented in a semiconductor fabrication facility. The manufacturing process may be adapted to manufacture semiconductor devices (e.g., processors) that embody various aspects of the present invention. 
         [0050]    Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, a graphics processing unit (GPU), a DSP core, a controller, a microcontroller, application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), any other type of integrated circuit (IC), and/or a state machine, or combinations thereof.