Device to cluster Boolean functions for clock gating

• US 7,562,325 B1
• Filed: 09/24/2008
• Issued: 07/14/2009
• 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/236,543
• Time in Patent Office: 293 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 system for clustering Boolean functions for clock gating according to various exemplary embodiments can include a computer configured to identify 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; perform 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; assign to each gating domain a merit value according to a power consumption profile of the gating domain using a merit function; and partition 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 system for clustering Boolean functions for clock gating, the system comprising:

a computer configured to;

identify 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;

perform 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;

$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>},$

ƒ

denotes a first gating condition;

g denotes a second gating condition;

where · and

+ are logical And Or operators, respectively, ∥

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

∀

sf·

g denotes a conjunction of ƒ and

g where all variables s which are not in a support of both ƒ and

g are quantified out;

2|ƒ

+g| is a normalizing term;

assign 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(ƒ

_g)−

C_LCB,

where f_g denotes a 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;

partition the cluster into gating groups using the dendrogram to construct a directed acyclic graph and determine 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 partition 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 repeat on any remaining nodes of the selected gating group said hierarchical clustering to generate said dendrogram, assign, and partition.