Methods to cluster boolean functions for clock gating

• US 7,458,050 B1
• Filed: 03/21/2008
• Issued: 11/25/2008
• Est. Priority Date: 03/21/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levitt, David J., Eisner, Cynthia Rae, Fuhrmann, Oded, Arbel, Eli, Itskovich, Alexander
• Primary Examiner(s): Kik; Phallaka
• Application Number:
  US12/053,384
• Time in Patent Office: 249 Days
• Field of Search: 716/2, 716/7
• US Class Current: 716/125
• CPC Class Codes: G06F 2117/04 Clock gating
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/396 Clock trees

Abstract

A method to cluster Boolean functions for clock gating according to various exemplary embodiments can include identifying at least two small gating groups within a clock tree representative of an electrical network and at least two gating functions of the at least two small gating groups, wherein the at least two gating functions are Boolean functions; performing hierarchical clustering on the at least two gating functions using a similarity measure that describes a distance between the at least two gating functions such that the clustering forms a merge function of a cluster generated and displayed in a form of a dendrogram; assigning to each gating domain a merit value according to a power consumption profile of the gating domain using a merit function; and partitioning the cluster into gating groups using the dendrogram to construct a directed acyclic graph to determine a partition which maximize the overall power saving.

Claims

1. A method to cluster Boolean functions for clock gating, the method comprising:

identifying at least two small gating groups within a clock tree representative of an electrical network and at least two gating functions of the at least two small gating groups, wherein the at least two gating functions are Boolean functions;

performing hierarchical clustering on the at least two gating functions using a similarity measure that describes a distance between the at least two gating functions such that the clustering forms a merge function of a cluster generated and displayed in a form of a dendrogram including a plurality of nodes, wherein each internal node of the plurality of nodes represents a respective gating domain, wherein the hierarchical clustering uses a distance function according to an equation;

wherein

$d<br><br>\left(f,g\right)\equiv <br><br>1-\frac{<br><br>f·<br><br>g<br><br>+<br><br>{\forall <br><br>}_s<br><br>f·<br><br>g<br><br>}{2<br><br><br><br>f+g<br><br>},$

f denotes a first gating condition;

g denotes a second gating condition;

where ● and

+ are logical And and Or operators, respectively, ∥

is the size of an On-set of a function;

∀

sf ●

g denotes a conjunction of f and g where all variables s which are not in a support of both f and g are quantified out;

2|f+g| is a normalizing term;

assigning to each gating domain a merit value according to a power consumption profile of the gating domain using a merit function according to an equation;

M (g)≡

|g|●

Pr(f_g)−

C_LCB,

f_g denotes the gating function of group g;

Pr(f_g) denotes a gating probability of f_g; and

C_LCB denotes an expression reflecting a cost of adding LCBs for gating the group;

partitioning the cluster into gating groups using the dendrogram to construct a directed acyclic graph and determining a longest path from a source to a sink on the directed acyclic graph in order to determine a partition which maximizes an overall power saving; and

if any gating group size exceeds a predetermined local clock buffer threshold, further partitioning the gating group that exceeds the predetermined local buffer threshold by selecting and assigning a lowest internal node of the selected gating group which has leaves equivalent to the predetermined local clock buffer threshold as a new gating domain, and iteratively repeating on any remaining nodes of the selected gating group said steps of performing hierarchical clustering to generate said dendrogram, assigning, and partitioning.