Abstract:
Techniques in which an optimal set of clock gating elements is determined for a selected circuit design. Those clock gating elements are coupled to selected flip-flops, with the effect that those selected flip-flops will consume less dynamic power during operation of the logic circuit. The selected set of clock gating elements provides an optimal savings in overall power consumption after modification of that selected circuit design.

Description:
BACKGROUND 
     A logic circuit design might incorporate one or more flip-flops, and related types of circuits, such as buffers and registers. These circuits are each generally capable of maintaining one bit of memory from time to time during operation of the logic circuit, typically including a clock input C, a data input D, and a data output Q. The flip-flop is disposed so that when the clock input C is changed, the data input D is stored in the flip-flop, with the effect that the value of data output Q will be set, on the next cycle of the clock input C, to the value of data input D. This has the effect that a new value D t+1  stored in the flip-flop after clocking might or might not change from its old value D t , depending on the input to the flip-flop. 
     Due to the design of these circuits and the nature of the transistors used in that design, each of those flip-flops consumes dynamic power when clocked, even when their maintained memory bit remains unchanged. This has the effect that, if selected flip-flops are disabled when their memory bit maintained remains unchanged, those selected flip-flops should consume less dynamic power during operation of the logic circuit. 
     SUMMARY OF THE DESCRIPTION 
     The description includes techniques, including apparatuses and methods, in which, for a selected circuit design, an optimal (or near-optimal) set of clock gating elements is determined for that selected circuit design. Those clock gating elements (sometimes referred to herein as “ICG&#39;s”) are coupled to corresponding ones of those selected flip-flops, with the effect that those selected flip-flops will consume less dynamic power during operation of the logic circuit. However, those clock gating circuits themselves consume at least some dynamic power during operation of the logic circuit, as well as requiring additional circuit space and wiring to be incorporated into the logic circuit design. 
     The selected set of clock gating elements provides that, after that selected circuit design has been modified to include those clock gating elements, an optimal (or near-optimal) savings in overall power consumption by that selected circuit design. This power savings is primarily derived from disabling selected flip-flops within that selected circuit design, with the effect that those flip-flops do not consume dynamic power for switching when disabled. 
     This has the effect that the clock gating elements reduce dynamic power (and possibly static power) consumption, as well as providing opportunities for logic optimization in that selected circuit design. This also has the effect that any additional power consumption by those clock gating elements (and any other additional logic elements needed to incorporate those clock gating elements and couple them to appropriate flip-flops) does not overmatch the power consumption savings derived from adding those clock gating elements to that selected circuit design. 
    
    
     DETAILED DESCRIPTION 
     Nature of the Description 
     Read this application in its most general form. This includes, without limitation:
         References to specific structures or techniques include alternative or more general structures or techniques, especially when discussing aspects of the invention, or how the invention might be made or used.   References to “preferred” structures or techniques generally mean that the invenfor contemplates using those structures are techniques, and think they are best for the intended application. This does not exclude other structures or techniques for the invention, and does not mean that the preferred structures or techniques would necessarily be preferred in all circumstances.   References to first contemplated causes or effects for some implementations do not preclude other causes or effects that might occur in other implementations, even if completely contrary, where circumstances would indicate that the first contemplated causes or effects would not be as determinative of the structures or techniques to be selected for actual use.   References to first reasons for using particular structures or techniques do not preclude other reasons or other structures or techniques, even if completely contrary, where circumstances would indicate that the first structures or techniques are not as compelling. The invention includes those other reasons or other structures or techniques, especially where circumstances would indicate they would achieve the same effect or purpose as the first reasons, structures, or techniques.       

     In this application, each flip-flop&#39;s maintained memory bit is generally associated with its data output Q, and each flip-flop is considered to be disabled when its clock input C is held stable, i.e., does not change or have a transition time (neither a down transition nor an up transition). However, in the context of the invention, there is no particular requirement for any such limitation. 
     FIGURES AND TEXT 
     
       FIG. 1 
     
       FIG. 1  shows a conceptual diagram of a circuit. 
     A circuit  100  includes elements as shown in the  FIG. 1 , including at least a selected circuit design  110 , that selected circuit design  110  having one or more flip-flops  111  (sometimes referred to herein as “flops”). The circuit  100  includes a set of one or more clock gating elements  120 , each including at least some logical circuit elements  121 . The logical circuit elements  121  might be instantiated from a circuit library, e.g., one or more standardized circuits for ICG&#39;s, or might be built including a latch and an AND gate, as shown in the  FIG. 1 . The circuit  100  possibly also includes a set of logic circuitry  130  capable of disabling or enabling one or more of the flip-flops  111 . The logic circuitry  130  might include combinational logic, sequential logic, some combination or conjunction thereof, or some other type of circuit, and might use one or more clock gating elements  120  coupled to corresponding flip-flops  111 . In some cases, it might be desirable to include one or more flip-flops or multiplexers  131  in addition to those found in the selected circuit design  110  as part of the logic circuitry  130 . 
     Dynamic Power Savings 
     In the circuit  100 , there are at least three primary contributors to power consumption for any selected circuit design  110 , as modified by inclusion of one or more clock gating elements  120  and possibly other logic circuitry  130 . These might include one or more of, or some combination or conjunction of, the following:
         reduction of dynamic power consumption from disabled flip-flops  111 ;   reduction of dynamic power consumption from logic optimization after inclusion of clock gating elements  120  and possibly other logic circuitry  130  (e.g., including, for example without limitation, a multiplexer  131  or other circuit elements) in the selected circuit design  110 ;   increase in dynamic power consumption from use of clock gating elements  120  and possibly other logic circuitry  130  in the selected circuit design  110 ;       

     In one or more cases, total reduction of power consumption can be expressed as:
 
 G=P   1   +P   2   −P   3   (191)
 
     where, in equation (191),
         G=total reduction in power consumption;   P 1 =reduction of dynamic power consumption from disabled flip-flops  111 ;   P 2 =reduction of dynamic power consumption from logic optimization after inelusion of clock gating elements  120  and possibly other logic circuitry  130  in the selected circuit design  110 ;
           and   
           P 3 =increase in dynamic power consumption from use of clock gating elements  120  and possibly other logic circuitry  130  in the selected circuit design  110 .       

     
       FIG. 2 
     
       FIG. 2  shows a conceptual diagram of a method. 
     After reading this application, those skilled in the art would recognize that the method  200  can be performed by a computing device, such as one including a processor and memory or mass storage, and including a removable memory for reading or writing physical media having data or instructions related to the method  200 . For example and without limitation, those data or instructions might include instructions capable of being interpreted by a computing device as instructions or data for performing the method  200 . 
     A method  200  includes flow labels and method steps as shown in the  FIG. 2 , including at least the following: 
     A flow label  200 A indicates a beginning of the method  200 . 
     A flow label  210  indicates that the method  200  is ready to (optionally) perform simulation for the selected circuit design  110 . Performing simulation is optional, as it might occur that the method  200  receives simulation data from another source, such as from the supplier of the selected circuit design  110 . 
     At a step  211 , the method  200  determines one or more responses of the selected circuit design  110  to one or more simulation “test bench” sets of inputs. 
     In one or more such cases, the method  200  uses a circuit simulator to provide at least approximate probabilities, for each node in the selected circuit design  110 , of that node being equal to logical value 0 or logical value 1 when tested. The circuit simulator might also provide at least approximate numbers, for the input and output values for each node, of that node transitioning from logical value 0 to logical value 1, or the reverse. 
     The responses of the selected circuit design  110  might be saved for later use, or might be used in further method steps shown in the  FIG. 2 . 
     As shown herein, the method  200  generally attempts to optimize a total number of transitions as a proxy for an amount of power measurement. The actual amount of power measurement would likely depend on the capacitances of cells and wires, which are not generally known at the time the method  200  is performed. 
     Although this application provides greater detail regarding embodiments in which the number of transitions is used as a proxy for an amount of power measurement, there is no particular reason to limit any part of this application in this regard. 
     At a step  212 , the method  200  determines a number of such transitions that would be saved, for each possible enable signal e, i.e., signal to enable one or more flip-flops  111 . In one or more cases, the number of such transitions that would be saved can be expressed as:
 
 G=Pr ( e= 0) N   cycles   N   flops +Σ (redundant P) ( N   trans  at  P )−( N   trans  of  HW   new )  (291)
 
     where, in equation (291),
         G=total reduction in number of transitions;   Pr(e=0)=approximate probability (or a proxy for approximate probability) of the enable signal e being off;   N cycles =number of cycles for the simulated circuit operation;   N flops =number of flip-flops disabled/enabled by the enable signal e;   Σ (redundant P)  (N trans  at P)=sum, for all redundant pins P that can be removed in response to one or more such enable signals e; of the number of transitions at each such pin P;
           and   
           N trans  of HW new =number of transitions added by new hardware, i.e., clock gating elements  120  and possibly other logic circuitry  130 .       

     For example and without limitation, if HW new  includes just a single ICG,
         N trans  at P (clock pin of the ICG)=N trans  for the main clock signal at that clock cycle;   N trans  at P (enable pin of the ICG)=N trans  for the enable signal e;
           and   
           N trans  of HW new =number of transitions added by the ICG, which can be estimated from a library definition of the ICG.
 
Static Power Savings
       

     At a step  213 , the method  200  estimates an amount of static power consumption that is reduced by inclusion of the clock gating elements  120  and possibly other logic circuitry  130  in the selected circuit design  110 . 
     In one or more cases, the amount of such static power consumption can be expressed as a selected fraction, e.g., a known percentage, of the amount of dynamic power consumption. For example and without limitation:
 
 G   static   =F   static [Σ (redundant P) ( N   trans  at  P )−( N   trans  of  HW   new )]  (292)
 
     where, in equation (292),
         G=total reduction in static power consumption;   F static =a selected fraction, e.g., a fixed percentage, used for determining static power consumption;   Σ (redundant P) (N trans  at P)=as in equation (291);
           and   
           N trans  of HW new =as in equation (291).       

     For example and without limitation, if an input pin P for an AND gate is removed (or added), F static  can be set equal to 1.0 when that input pin P is switched at a selected frequency, which, for selected clock gating elements  120  and possibly other logic circuitry  130 , can be estimated from a library definition. 
     Selecting ICG&#39;s 
     A flow label  220  indicates that the method  200  is ready to find an optimal (or near-optimal) set of clock gating elements  120 , and possibly other logic circuitry  130 , to build in response to the determined gain (G) from each enable signal e. 
     At a step  221 , the method  200  provides a table  281 , in which each row  282  of the table  281  indicates a possible enable signal e, and in which each column  283  of the table  281  indicates a possible flip-flop  111  in the selected logic circuit no. In one or more cases, the table  281 , with its rows  282  and columns  283 , might be implemented using a sparse matrix data structure with a computing device using memory or mass storage. However, in the context of the invention, there is no particular requirement for any such limitation. 
     At a step  222 , the method  200  computes, for each row  282  of the table  281 , a total gain (G), i.e., G row , as described above with respect to the sum of equation (291) and equation (292). 
     In one or more cases, the method  200  proceeds using a greedy algorithm to select a set of possible enable signals e. However, in the context of the invention, there is no particular requirement for using this particular algorithm, or for any other such limitation. 
     Greedy Algorithm 
     A flow label  230  indicates that the method  200  is ready to begin the greedy algorithm. 
     At a step  231 , the method  200  finds the row  282  e i  with substantially the best gain (i.e., highest value of G for that row  282  e i ). 
     At a step  232 , the method  200  finds substantially all rows  282  e j  which have non-null intersection with the row  282  e i , i.e., row  282  e i  and row  282  e j  have at least one column  283  f k  in common. 
     At a step  233 , the method  200  finds the row  282  e j  with substantially the best gain increase, if combined with the row  282  e i . In one or more cases, the gain increase can be expressed as:
 
 G′=G   combined ( e   i   ,e   j )+ G (remaining  e   i )  (293)
 
     where, in equation (293),
         G combined (e i , e j )=G (e 1 ) as in equation (291), where e 1 =all f k  gated by (e i  AND e j ), possibly adjusted using G static  (e 1 ) as in equation (292);   G (remaining e i )=G (e 2 ) as in equation (291), where e 2 =all f k  gated by all e i , having a null intersection with e i , possibly adjusted using G static  (e 2 ) as in equation (292);
           and
 
 Pr ([ e   i  AND  e   j ]=0)= Pr ( e   i =0)+ Pr ( e   j =0)−[ Pr ( e   i =0) Pr ( e   j =0)] (approximately).
   
               

     At a step  234 , the method  200  determines if G′(e i , e j )&gt;G(e i ). 
     If so, the method  200  proceeds with the step  241 , where the rows  282  e i  and e j  are combined. 
     If not, the method  200  proceeds with the step  251 , where it determines whether there are any other combinations of rows  282  e i  and e j  using e i . 
     Removing Intersecting Rows 
     At a step  241 , the method  200  provides a new row  282  e ij =[e i  AND e j ]. 
     At a step  242 , the method  200  adds the new row e ij  to the table  281 . 
     At a step  251 , the method  200  repeats the step  232  through the step  234 , i.e., the method  200  finds if there are any further rows  282  e j′  for which G′(e ij , e j′ )&gt;G(e ij ). 
     After reading this application, those skilled in the art would recognize that the step  231  need not be performed, as the new row  282  e ij  is already known to have substantially the best gain. 
     If there are any such further rows  282  e j′ , the method  200  proceeds with the step  241 , where a new intersecting row is provided. 
     If there are not any such further rows  282  e j′ , the method  200  proceeds with the step  261 , where it removes the substantially best-gain row  282  e ij  (or just e i  if no e j  was found for that e i ). 
     At a step  261 , the method  200  removes the substantially best-gain row  282  e ij  (or just e i ). 
     At a step  262 , the method  200  removes all columns  283  f k  gated by the substantially best-gain row  282  e ij  (or just e i ). 
     At a step  263 , the method  200  determines if there are any rows  282  left after removing the substantially best-gain row  282  e ij  (or just e i ). 
     After reading this application, those skilled in the art would recognize that the step  263  might compare any remaining rows  282  with a minimum threshold g θ , i.e., those remaining rows  282  e i  for which G(e i )&gt;g θ  (versus those remaining rows  282  e i  for which G(e i )&gt;0). In such cases, the method  200  determines that “any rows  282  left” is a null set if there are no remaining rows  282  e i  for which G(e i )&gt;g θ . 
     If there are any such rows  282  left, the method  200  proceeds with the step  232 , where the method  200  proceeds to find if there are any further rows  282  e j  for which G′(e i′ , e j )&gt;G(e i′ ). 
     If there are no such rows  282  left, the method  200  proceeds with the flow label  200 B, where the method  200  ends. 
     End of Method 
     A flow label  200 B indicates an end of the method  200 . 
     After reading this application, those skilled in the art would recognize that other factors might be considered in the selection of clock gating elements  120 . These other factors that might be considered include the relative closeness of the dependent flip-flops to the selected nodes, and the like. 
     Alternative Embodiments 
     After reading this application, those skilled in the art would recognize that the scope and spirit of the invention includes other and further embodiments beyond the specifics of those disclosed herein, and that such other and further embodiments would not require new invention or undue experimentation.