Abstract:
A method for performing a global timing analysis of a proposed digital circuit comprising receiving timing models and the proposed digital circuit; determining at least one mode of circuit operation of the proposed digital circuit; deriving a sub-circuit corresponding to each of at least one mode of circuit operation; performing timing analysis on each of the sub-circuits derived corresponding to each of the modes; and combining the timing analysis results for all of the modes to determine an overall maximum circuit delay.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application is related to commonly-assigned U.S. patent application Ser. No. 10/266,831 entitled “METHOD FOR DESIGNING MINIMAL COST, TIMING CORRECT HARDWARE DURING CIRCUIT SYNTHESIS,” and U.S. patent application Ser. No. 10/266,826 entitled “METHOD OF USING CLOCK CYCLE-TIME IN DETERMINING LOOP SCHEDULES DURING CIRCUIT DESIGN,” filed concurrently herewith, the disclosures of which are hereby incorporated by reference in their entireties. 
     FIELD OF THE INVENTION 
     The present invention is directed to digital circuit verification and, in particular, to timing analysis of digital circuits. 
     BACKGROUND 
     Continuing advances in technology combined with dropping production costs have led to a proliferation of electronic devices that incorporate or use advanced digital circuits including desktop computers, laptop computers, hand-held devices, such as Personal Digital Assistants (PDA), and hand-held computers, cellular telephones, printers, digital cameras, facsimile machines and other electronic devices. These digital circuits are typically required to provide the basic functionality of the electronic device. Digital circuits may also be incorporated in many other household or business appliances. To continue to develop and produce these digital circuits, fast, efficient means of synthesizing and/or designing these circuits are required. In addition, at each step of the design process, it is necessary to verify the correct operation of these digital circuits. 
     Digital circuit verification includes, (1) ensuring that the circuit performs the correct functionality and (2) ensuring that the circuit satisfies the timing requirements. Functional verification ensures that the circuit produces the correct result or output. Timing verification ensures that the correct output is produced within a given amount of time or that the output is available when it is required. One possible approach for timing verification is timing simulation where the functionality and delay of each component in the circuit is used to repeatedly simulate the circuit response for each input stimulus from a set of input stimuli. The disadvantage of timing simulation is that the verification cannot be guaranteed for the input stimuli that have not been simulated. An alternative approach to timing verification is timing analysis, which overcomes this disadvantage by analyzing (rather than simulating) the circuit for all stimuli that can possibly occur at the circuit-inputs. Furthermore, timing analysis can also be used to determine the maximum circuit delay, as opposed to simply ensuring that the circuit satisfies the given timing requirements. 
     Typically, a clock is used to coordinate the sequence of events performed by the digital circuit. This coordination is referred to as synchronization. The period of time between successive clock cycles is the clock period. 
     Analyzing the timing of a digital circuit includes an examination of the circuit path from the primary input or latching element, through one or more combinational circuit components to a primary output or latching element. A combinational circuit component is one whose output function depends solely on the input values applied to it, not on any past history or internal state. Latching elements include registers, d-type and similar type flip-flops or other storage devices that store the value present at its input upon the occurrence of a synchronization event, such as a clock edge. Timing analysis ensures that the delays along a circuit path from the input to the output are less than the period of time between the synchronization events, such as successive clock cycles. 
     The simplest form of timing analysis performs only topological analysis, i.e., it only accounts for the delay of each component and their interconnectivity (the way they are connected with each other) and ignores the functionality of the circuit components. One of the earliest timing analysis tools which followed this approach was Program Evaluation and Review Technique (PERT), which calculated the maximum delay of a circuit as the delay of the topologically longest path in the circuit. The run-time complexity of this analysis is “big O of M,” i.e., O(M), where M stands for the number of circuit components. In other words, the time it takes to perform this analysis is linearly proportional to the circuit size. Any timing analysis algorithm will have to look at each circuit component at least once during its analysis, therefore a run-time complexity that is linearly proportional to circuit size is optimal (and hence, desirable). PERT is described in T. I. Kirkpatrick and N. R. Clark, “PERT as an aid to logic design,” IBM Journal of Research and Development, vol. 10, 1966, pp. 135–141 which is hereby incorporated by reference in its entirety. 
     Unfortunately, there are two drawbacks with PERT: (1) it over-estimates the maximum circuit delay because it does not account for false paths, and (2) it cannot handle combinational loops that may be present in the circuit. 
     A path is said to be false or unsensitizable when a signal cannot propagate from the beginning to the end of the path under any combination of primary inputs.  FIG. 1  illustrates a sensitization example. 
     Unit gate delays and zero wire delays are assumed in the following functional analysis of  FIG. 1 . Input  101  is connected to non-inverting buffer  102 , output  104  of buffer  102  is connected to a first input of AND gate  105  and input  103  is connected to a second input of AND gate  105 . Input  103  is also connected to buffer  106 . Output  107  of AND gate  105  is connected to a first input of OR gate  109  and output  108  of buffer  106  is connected to a second input of OR gate  109 . OR gate  109  has output  110 . 
     The circuit path starting at input  101 , through buffer  102 , output  104 , AND gate  105 , output  107 , OR gate  109  and output  110  has a delay of three units (one unit delay for each of buffer  102 , AND gate  105  and OR gate  109 ). For a rising or falling transition (at time zero) to propagate from input  101  through this circuit path to output  110 , the second input ( 103 ) of AND gate  105  must be a logic 1 (non-controlling or sensitizing value) at the time the transition propagates through AND gate  105  (i.e., at time t=1 unit). In order for this to occur, input  103  should be a logic 1 at time t=1 unit. Similarly, the second input ( 108 ) to OR gate  109  must be at logic 0 (non-controlling or sensitizing value) at the time the transition along the path propagates through OR gate  109  (i.e., at time t=2 units). In order for this to occur, the output of buffer  106  should be a logic 0 at time t=2 units, which implies that input  103  should be a logic 0 at time t=1 unit. It is seen that to meet these two criteria, input  103  is required to be both a logic 1 and a logic 0 at time=1 unit which is not possible. Therefore, a transition cannot propagate through this circuit path. This path is therefore not sensitizable. The maximum delay of this circuit path is therefore less than three units, but PERT will evaluate the circuit delay as three units since the topologically longest path in the circuit is equal to three units. 
     Several algorithms have been proposed in the literature to perform timing analysis accounting for false paths. An example of such an algorithm is S. Devadas, K. Keutzer, and S. Malik, “Computation of floating mode delay in combinational logic circuits: Theory and algorithms,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, December 1993, pp. 1913–1922. These algorithms are able to determine the maximum circuit delay with greater accuracy, however, they have super-linear run-time complexity (i.e., their run-time scales worse than linearly with respect to circuit size), so they are less efficient than purely topological timing analysis (i.e., PERT). Moreover, they still cannot handle combinational loops that may be present in the circuit. 
     A loop in a circuit occurs when a combinational path goes through the same combinational component more than once. Combinational components include AND gates, OR gates, etc., but excludes latches and registers. A loop is said to be combinational when, in spite of the structural feedback, there is no logical feedback that is transmitted to the primary outputs. In other words, a signal cannot go completely around a combinational loop and then propagate to a primary output (it will be stopped either before it completes one entire loop, or before it reaches the primary output). 
     Several techniques have been proposed in the literature to perform timing analysis accounting for combinational cycles. One example is found in S. Malik, “Analysis of cyclic combinational circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 7, July 1994, pp. 950–956, the disclosure of which is incorporated by reference herein. Malik has proposed a technique for estimating the maximum delay of any given cyclic combinational circuit by unrolling the cyclic circuit to obtain an equivalent acyclic circuit. This potentially makes the circuit large and complex. This technique relies on Binary Decision Diagrams (BDDs) for the necessary logical analysis. These factors make the technique impractical for large circuits. Another example is found in A. Srinivasan and S. Malik, “Practical analysis of combinational circuits,” Proceedings Custom Integrated Circuits Conference, 1996, pp. 381–384, the disclosure of which is incorporated by reference herein. Srinivasan and Malik have proposed a heuristic process for handling a restricted case of cyclic combinational circuits. This is based on finding a minimal set of gates that, when removed, results in an acyclic circuit. The heuristic process is super-linear in run-time complexity, therefore the authors proposed a user-specified budget to terminate the heuristic unsuccessfully if it exceeds the budget. 
     In summary, timing analysis that does not account for false paths and combinational loops, although being of linear run-time complexity, over-estimates the maximum delay of a circuit. Algorithms that include false paths and combinational loops analysis are super-linear in run-time complexity and, therefore, less efficient. 
     SUMMARY OF THE INVENTION 
     A method of performing a global timing analysis of a proposed digital circuit comprising receiving timing models and said proposed digital circuit; determining a plurality of modes of circuit operation of said proposed digital circuit; deriving a sub-circuit corresponding to each of said modes of circuit operation; performing timing analysis on each of said sub-circuits derived corresponding to each of said modes; and combining the timing analysis results for said modes to determine an overall maximum circuit delay. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic diagram of a logic circuit useful for a sensitization example; 
         FIG. 2  is a flow diagram of an embodiment of the present invention for analyzing a digital circuit by a mode-sliced method; 
         FIG. 3  is a schematic diagram of a circuit in which the method of  FIG. 2  may be used to determine maximum circuit delay; and 
         FIG. 4  is a schematic diagram of a circuit in which the method of  FIG. 2  may be used to determine maximum circuit delay. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 2  is a flow diagram of an embodiment of the present invention for performing timing analysis of a digital circuit by a mode-sliced method. The flow diagram of  FIG. 2  shows the provision of two inputs associated with respective input steps: input circuit graph step  201 , and timing models input step  202 . Input circuit graph step  201  includes providing descriptions of circuit components and the interconnections between the components of the digital circuit. A component is considered to be a hardware element that performs a set of one or more functions or operations. Muliplexers, registers, AND gates, adders, and subtractors are examples of components. The functionality of the component is also received in step  201 . Interconnections refers to wires or other signal conductors that are capable of transporting data values (or signal values) in the form of electrical signals, from one point to a second point. 
     In step  202  timing models are received. Timing models are received for the components and the interconnections received in step  201 . Timing models for components and interconnections include timing edges and associated delay values for the timing edges. A delay is associated with the time required to execute an operation and/or propagate a result. For instance, the timing model for an adder with two inputs in0 and in1 and one output out0 will contain: 2 timing edges (one from in0 to out0 and another from in1 to out0) and a delay value associated with each timing edge. The delay value represents the maximum time it takes for an electrical signal to propagate from the appropriate input to the output of the adder when an addition operation is performed. 
     In step  203  a subset of input signals that control the sensitization of long circuit paths are identified. Long paths in circuits determine the maximum circuit delay. The identified input signals are designated as control signals. An example of a control signal is the select input of a multiplexer that is used along a long circuit path. 
     The set of all possible combinations of a Boolean value of a “0” or “1” to each control signal that was identified in step  203  represents all the possible ways in which the circuit operates from a timing analysis perspective. Each such combination of control signal values is a control state. A mode comprises a set of control states such that, a mode of the circuit corresponds to an assignment of “0” or “1” or unknown “U” values to the control signals. In step  204  the modes of circuit operation for which timing analysis is to be performed are determined. The modes are selected such that every possible control state is in at least one mode, so that the set of modes cover the space of all possible control states of the circuit. Furthermore, the modes are determined such that, in each mode, the control signals that influence the sensitization of those long paths that are sensitized in this mode are assigned a “0” or a “1” value. Note that there is a trade-off between the granularity of the mode and the minimum number of modes required to cover all of the control states. At one extreme, each mode consists of exactly one control state, in which case, there need to be as many modes as control states. On the other extreme, there may be only one mode representing all possible control states. After the completion of step  204 , control signals and associated modes have been identified. 
     Each mode identified in step  204  is individually considered in steps  205 ,  206  and  207 . In step  205 , values corresponding to the mode under consideration are applied to the control signals. In other words, for control signals that have been assigned a “0” or a “1” value within the mode, the control signal inputs are set to the appropriate value. 
     In step  206 , the timing edges for the component and interconnections are annotated onto the input circuit description to form a circuit graph amenable to timing analysis. The “0” or “1” control signal values are then propagated through this circuit graph resulting a modified circuit graph wherein the timing edges which become disabled are removed from further consideration. Disabled timing edges are those timing edges through which no signal propagates in the mode under consideration. After completion of step  206 , a sub-circuit graph remains which consists of timing edges that have not been proven to be inactive in the mode under consideration. 
     Timing analysis is then performed in step  207  on the modified circuit graph to determine the maximum delay for this mode. Any timing analyzer can be used for this purpose. By virtue of step  206 , many false paths and combinational loops have been eliminated from the circuit graph, therefore, a simple timing analyzer may be used. In a preferred embodiment, a PERT-like timing analyzer can be used. 
     In step  208  determination is made as to whether additional modes remain to be considered. If additional modes are available, step  205  is again encountered to begin the examination of remaining modes. Once all modes have been examined, step  209  determines the overall maximum circuit delay. Since steps  205 – 207  perform the timing analysis for every individual mode of the circuit, and the modes selected by step  204  cover all possible states, the overall maximum delay of the circuit is equal to the maximum of the maximum delay determined within each mode. Note that the steps of  FIG. 2  may be implemented within a program stored on computer readable media. 
     The methodology of  FIG. 2  eliminates the false paths and combinational loops from consideration and results in an extremely efficient analysis methodology. In a preferred embodiment where a PERT-like timing analyzer is used, the run-time complexity of PERT is O(M) where M is the circuit size. If the number of modes determined in step  204  is N, the total run-time complexity of the global timing analysis method of  FIG. 2  is O(NM). The number of modes N is independent of circuit size. Therefore, the global timing analysis still has linear run-time complexity. This is an improvement over prior approaches that account for false paths and combinational loops with super-linear run-time complexity. 
     While the flow diagram of  FIG. 2  is applicable to any digital hardware circuit, it is especially beneficial for the timing analysis for certain classes of circuits. In one embodiment, the timing of a circuit datapath that is controlled by a Finite-State Machine (FSM) based controller may be efficiently analyzed using the flow diagram of  FIG. 2 . In this example, the control signals are the signals that originate from the FSM controller and are sent to the datapath elements. Also in this example, each mode to be analyzed corresponds to a state of the FSM. 
     In a second embodiment, the timing of a periodic circuit may be efficiently analyzed using the flow diagram of  FIG. 2 . Periodicity means that the operation of every component in the circuit repeats every N clock cycles. Additionally, periodicity requires that the operation of every component which provides an input to the components of the circuit as well as the operation of every component that receives an output from the components of the circuit also repeat every N clock cycles. In this case, there is a periodicity of N clock cycles. In other words, the general circuit operation repeats every N clock cycles, such that only the data being operated on changes from cycle to cycle without necessarily repeating every N cycles. For example, a Functional Unit (FU) will execute the same operation every N cycles. Moreover, the locations from which the FU receives the input operand values and the locations to which the FU writes its results, also repeats every N cycles. However, the input data values may differ as may the resultant date output signal(s). Note that FUs are components that are capable of performing some set of operations, e.g., an adder can add two numbers, a multiplier can multiply two numbers, a multiply-add unit may be capable of multiplying two numbers, adding two numbers, or multiplying two numbers and adding the product with a third number. 
     In the methodology of  FIG. 2 , the N clock cycles of the periodicity of the digital circuit are split into N modes for the timing analysis. Each of the N modes is associated with a phase or a distinct clock cycle of the overall periodicity. To enable this, the signals that determine what phase the circuit is operating in are designated to be the control signals. Some examples of periodic circuits are those that execute software pipelined code and those that execute modulo scheduled code. Software pipelining is described in A. E. Charlesworth, “AN APPROACH TO SCIENTIFIC ARRAY PROCESSING: THE ARCHITECTURAL DESIGN OF THE AP-120B/FPS-164 FAMILY,” computer, vol. 14, No. 9, September 1981, pp. 18–27, the disclosure of which is hereby incorporated by reference herein. Modulo scheduling is described in B. R. Rau, “ITERATIVE MODULO SCHEDULING,” International Journal of Parallel Processing, vol. 24, pp. 3–64, 1996, the disclosure of which is hereby incorporated by reference herein. This document is also available as HP Labs Tech. Report HPL-94-115 from Hewlett-Packard Co. 
     In yet another embodiment of the invention, the flow diagram of  FIG. 2  may be applied to the timing analysis of a circuit generated using Program-In-Chip-Out Nonprogrammable Accelerator (PICO-NPA) synthesis (refer to FIG. 24 and Section 5.10.2 of HP patent application HP10990413 titled “PROGRAMMATIC SYNTHESIS OF PROCESSOR ELEMENT ARRAYS”, the disclosure of which is hereby incorporated by reference herein). PICO-NPA schema generated circuits have a periodic operation with a period of Initiation Interval (II) cycles. Additionally, the control signals are the phase bus bits and each mode to be analyzed corresponds to a distinct value that the phase bus may take. 
       FIG. 3  shows an example circuit in which the method of  FIG. 2  may be used to determine the maximum circuit delay. In this circuit, signals  306 ,  307 ,  313 ,  314 ,  324 ,  325 ,  319  and  329  are all connected to the “phase” input.  FIG. 3  depicts a circuit including input register  301 , containing value “A”, connected to a first input of multiplexer  302  and input register  303 , containing value “B”, connected to a first input of multiplexer  304 . Multiplexers  302  and  304  also receive respective input select signal inputs  306  and  307 . Outputs from both multiplexers  302  and  304  are electrically connected to respective addend signal inputs of adder  305 . Input register  308 , containing value “C”, is connected to a first input of multiplexer  309  and input register  310 , containing value “D”, is connected to a second input of multiplexer  309 . 
     Output  316  of adder  305  is connected to a first input of multiplexer  311  and input register  312 , containing value “E”, is connected to a second input of multiplexer  311 . A select signal at input  313  causes the selection of an input for multiplexer  309  and a select signal at input  314  is used to select an input for multiplexer  311 . Outputs for multiplexer  309  and multiplexer  311  are electrically connected to respective inputs of adder  315 . The value present on output  317  of adder  315  may be selected through multiplexer  318  with the appropriate input select signal  319  and stored in output register  320 . Input register  321 , containing value “F”, is connected to the second input of multiplexer  322  and output  317  of adder  315  is connected to the second input of multiplexer  323 . Outputs of multiplexers  322  and  323  are electrically connected to adder  326 . Output  327  of adder  326  may be selected by multiplexer  328  (with the appropriate select signal applied to input  329 ) and stored in output register  330 . 
     When the “phase” input is ‘0’, the select signals at inputs  306 ,  307 ,  313 ,  314  and  319  each causes multiplexers  302 ,  304 ,  309 ,  311  and  318  to pass the value present on their first inputs, as a result of which the sum A+B+C will be present on the output of multiplexer  318  and the value may be stored in output register  320 . Also, when the “phase” input is ‘0’, the select signals at inputs  324 ,  325  and  329  each causes multiplexers  322 ,  323  and  328  to pass the value present on their first inputs, as a result of which any signal at output  327  of adder  326  is not used and is considered a “don&#39;t care”. Alternatively, when the “phase” input is ‘1’, the select signals at inputs  306  and  307  each causes multiplexers  302  and  304  to pass the value present on their second inputs, as a result of which any signal at output  316  of adder  305  is not used and is considered a “don&#39;t care”. Also, when the “phase” input is ‘1’, the select signals at inputs  313 ,  314 ,  324 ,  325  and  329  each causes multiplexers  309 ,  311 ,  322 ,  323  and  328  to pass the value present on their second inputs, as a result of which the sum D+E+F will be present on the output of multiplexer  328  and the value may be stored in output register  330 . 
     The method of  FIG. 2  can be applied to the circuit of  FIG. 3  as follows: an input circuit description representing the circuit of  FIG. 3  is provided at step  201 . Timing models for all the components and interconnections are provided at step  202 . In step  203 , the control signals are determined. The “phase” signal controls the sensitization of all paths in this circuit datapath. Therefore, it is designated as a control signal. In step  204 , the states of the circuit operation, which correspond to all possible combinations of “0” or “1” control signal values, are grouped together to form modes. For this example, there are two states of circuit operation corresponding to when the control signal “phase” has value “0” and when the control signal “phase” has value “1”. The modes are determined such that in each mode, the control signals that influence the sensitization of those long paths that are sensitized in this mode are assigned a “0” or a “1” value. Therefore, there are two modes, each consisting of exactly one state. 
     The global timing analysis is partitioned into two timing analyses, one for each mode. In the first mode, in step  205 , the control signal “phase” takes value ‘0’. In step  206 , this ‘0’ value is propagated through the circuit, removing timing edges that get disabled. For example, “phase”=‘0’, results in signal  306  being equal to ‘0’, which disables the timing edge from the second input (i.e., rightmost as depicted) of multiplexer  302  to its output. Similarly, the other disabled timing edges are: from the second input of multiplexer  304  to its output; from the second input of multiplexer  309  to its output; from the second input of multiplexer  311  to its output; from the second input of multiplexer  322  to its output; from the second input of multiplexer  323  to its output; from the second input of multiplexer  319  to its output; and, from the second input of multiplexer  328  to its output. These timing edges are removed from the original circuit graph. In step  207 , timing analysis is performed on the modified circuit graph resulting from step  206 . The latch-to-latch paths consisting of only active timing edges and interconnects go through adder  305  and adder  315 , or through adder  326 . No path through all three adders is active, because the timing edge from the second input of multiplexer  323  to its output is disabled. Therefore, the maximum delay found for the circuit operating in the first mode will exclude the delay of these paths. 
     In the second mode, in step  205 , the control signal “phase” takes value ‘1’. In step  206 , this ‘1’ value is propagated through the circuit, removing timing edges that get disabled. For example, “phase”=‘1’, results in signal  306  being equal to ‘1’, which disables the timing edge from the first input of multiplexer  302  to its output. Similarly, the other disabled timing edges are: from the first input of multiplexer  304  to its output; from the first input of multiplexer to its output; from the first input of multiplexer  311  to its output; from the first input of multiplexer  322  to its output; from the first input of multiplexer  323  to its output; from the first input of multiplexer its output; and, from the first input of multiplexer  328  to its output. These timing edges are removed from the original circuit graph. In step  207 , timing analysis is performed on the modified circuit graph resulting from step  206 . The latch-to-latch paths consisting of only active timing edges and interconnects go through adder  305 , or through adder  315  and adder  326 . No path through all three adders is active, because the timing edge from the first input of multiplexer  311  to its output is disabled. Therefore, the maximum delay found for the circuit operating in the second mode will exclude the delay of these paths. 
     After timing analysis has been performed for both modes of circuit operation, step  209  determines the overall maximum circuit delay by taking the maximum of the delays found in each mode. Since no path that goes through all three adders is active in any mode, the overall maximum delay thus determined will exclude the delay of all paths that go through all three adders. It can be noted that any path through all three adders is a false path, i.e., one that cannot be sensitized for any combination of input values. For instance, the path from register  301  through multiplexer  302  through adder  305  through multiplexer  314  through adder  315  through multiplexer  325  through adder  326  through multiplexer  328  to register  330  is false because, for a signal to go through this entire path, the “phase” input has to take both ‘0’ and ‘1’ values. Therefore, the method of  FIG. 2  correctly and efficiently eliminates false paths from contributing to the maximum delay of a circuit. 
       FIG. 4  illustrates another circuit for which an embodiment of the present invention may be used in timing analysis and to determine a maximum circuit delay. In this circuit, signals  421 ,  422 ,  423 ,  424 ,  425  and  426  are all connected to the “phase” input. Input “A” is connected to a first input of multiplexer  402  and input “F” is connected to a second input of multiplexer  402 . Input “B” is connected to a first input of multiplexer  404  and the second input of a multiplexer  404  is connected to the output of adder  405 . Output  406  of multiplexer  402  and output  407  of multiplexer  404  are electrically connected to respective inputs of adder  408 . Output  409  of adder  408  is electrically connected to a first input of multiplexer  416  and second input of multiplexer  411 . Output  412  of multiplexer  411  is connected to register  413 . Multiplexer  414  has two inputs “C” on a first input and “D” on a second input. Output  415  of multiplexer  414  is electrically connected to a first input of adder  405 . Multiplexer  416  has a first input electrically connected to output  409  of adder  408  and a second input connected to input “E.” The second input of adder  405  is electrically connected to output  417  of multiplexer  416 . Output  418  of adder  405  is electrically connected to a second input multiplexer  404  and a first input of multiplexer  419 . Output  420  of multiplexer  419  is electrically connected to output register  420 . Select signals are provided to respective inputs  421 ,  422 ,  423 ,  424 ,  425 , and  426  of multiplexers  402 ,  404 ,  411 ,  416 , and  419 . Each of these select inputs are connected to a single “phase” input. 
     When the “phase” input is equal to ‘0’, multiplexers  402 ,  404 ,  411 ,  414 ,  416  and  419  each connect the signal present on their first inputs to their respective outputs. With a select input of ‘0’, signal “A” would be present on output  406  of multiplexer  402 , and signal “B” would be present on output  407  of multiplexer  404 , signal “C” would be present on output  415  of multiplexer  414  and the output of adder  408  would be present on output  417  of multiplexer  410 . Therefore, the sum A+B will be present on the output of adder  409 , and the sum A+B+C will be present on the output of adder  405  which will be stored in output register  420 . Moreover, the ‘0’ connected to control input  423  of multiplexer  411  would store a “don&#39;t care” into output register  413 . 
     Alternatively, when the “phase” input is ‘1’, a ‘1’ value is applied to the select inputs  421 ,  422 ,  423 ,  424 ,  425 , and  426  of multiplexers  402 ,  404 ,  411 ,  414 ,  416 , and  419  respectively. For this select input, multiplexer  402  passes input “F” output  406  and multiplexer  404  passes output  418  of adder  405  to output  407  of multiplexer  404 . Multiplexer  414  passes an input of “D” to its output  415  and multiplexer  416  passes the input “E” from its second input to output  417  of multiplexer  416 . Adder  405  combines its two inputs, D and E and “D+E” is present on output  418  of adder  405 . Adder  408  has an “F” on its first input and a “D+E” on its second input. “D+E+F” is therefore present on output  409  of adder  408  and “D+E+F” is stored in output register  413  through multiplexer  411  by virtue of a “1” on control signal  423 . Moreover, the ‘1’ connected to control input  423  of multiplexer  411  would store a “don&#39;t care” into output register  420 . 
     The method of  FIG. 2  can be applied to the circuit of  FIG. 4  as follows: an input circuit description representing the circuit of  FIG. 4  is provided at step  201 . Timing models for all the components and interconnections are provided at step  202 . In step  203 , the control signals are determined. The “phase” signal ( 421 – 426 ) controls the sensitization of all paths in this circuit datapath, therefore it is designated as a control signal. In step  204 , the states of the circuit operation, which correspond to all possible combinations of “0” or “1” control signal values, are grouped together to form modes. For this example, there are two states of circuit operation corresponding to when the control signal “phase” has value “0”, and when the control signal “phase” has value “1”. The modes are determined such that, in each mode, the control signals that influence the sensitization of those long paths that are sensitized in this mode are assigned a “0” or a “1” value. Therefore, there are two modes, each consisting of exactly one state. 
     The global timing analysis is partitioned into two timing analyses, one for each mode. In the first mode, in step  205 , the control signal “phase” takes value ‘0’. In step  206 , this ‘0’ value is propagated through the circuit, removing timing edges that get disabled. For example, “phase”=‘0’, results in signal  421  being equal to ‘0’, which disables the timing edge from the second input (i.e., rightmost as depicted) of multiplexer  402  to its output. Similarly, the other disabled timing edges are: from the second input of multiplexer  404  to its output; from the second input of multiplexer  411  to its output; from the second input of multiplexer  414  to its output; from the second input of multiplexer  416  to its output; and, from the second input of multiplexer its output. These timing edges are removed from the original circuit graph. In step  207 , timing analysis is performed on the modified circuit graph resulting from step  206 . The timing edge from the second input of multiplexer  404  to its output is disabled, therefore any path that uses the interconnection from the output of adder  418  to the second input of multiplexer  404  is not sensitized in this mode. In other words, the combinational loop between the two adders is broken at this interconnect in the first mode. Therefore, the maximum delay found for the circuit operating in the first mode will exclude the combinational loop. 
     In the second mode, in step  205 , the control signal “phase” takes value ‘1’. In step  206 , this ‘1’ value is propagated through the circuit, removing timing edges that get disabled. For example, “phase”=‘1’, results in signal  421  being equal to ‘1’, which disables the timing edge from the first input of multiplexer  402  to its output. Similarly, the other disabled timing edges are: from the first input of multiplexer  404  to its output; from the first input of multiplexer  411  to its output; from the first input of multiplexer  414  to its output; from the first input of multiplexer  416  to its output; and, from the first input of multiplexer its output. These timing edges are removed from the original circuit graph. In step  207 , timing analysis is performed on the modified circuit graph resulting from step  206 . The timing edge from the first input of multiplexer  416  to its output is disabled. Therefore, any path that uses the interconnection from the output of adder  408  to the first input of multiplexer  416  is not sensitized in this mode. In other words, the combinational loop between the two adders is broken at this interconnect in the second mode. Therefore, the maximum delay found for the circuit operating in the second mode will exclude the combinational loop. 
     After timing analysis has been performed for both modes of circuit operation, step  209  determines the overall maximum circuit delay by taking the maximum of the delays found in each mode. Since the combinational loop is broken by some disabled timing edge in every mode of circuit operation, the overall maximum delay thus determined will exclude the combinational loop. Therefore, the method of  FIG. 2  correctly and efficiently eliminates combinational loops from contributing to the maximum delay of a circuit. 
     Note that the system for a method of clock cycle time analysis as described may be used to perform timing analysis on any circuit, including FSM controlled circuits, periodic circuits, software pipelined circuits, modulo scheduled circuits, and circuits designed by PICO-NPA. Additionally, the timing analysis of the present invention may be performed in a standalone environment, as well as in a high-level synthesis environment.