Method for electronic memory management during estimation of average power consumption of an electronic circuit

Claim 2

In a computer system, a computer implemented improved method for managing the use of electronic memory in the course of estimating average power consumption of an electronic circuit represented as a netlist comprising the computer implemented steps of: (a) ranking, in the electronic memory, primary outputs of the netlist with respect to each other in an order that depends upon the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) performing a depth-first traversal of the netlist, in the electronic memory, that follows the primary output ranking order, wherein said step (b) comprises the steps of: (b1) constructing, in the electronic memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) computing a respective switching activity value for each respective constructed BDD; and (b3) releasing a respective BDD from the electronic memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.

Claim 3

The method of claim 1, wherein the step of constructing produces in the electronic memory at least one respective BDD for a deeper level netlist node that serves as a basis for construction of at least one respective BDD for a shallower logic level netlist node.

Claim 4

The method of claim 1, wherein the step of constructing produces in the electronic memory a first BDD for a deeper level netlist node that both serves as a basis for construction of a second BDD for a second shallower logic level netlist node and also serves as a basis for construction of a third BDD for a third shallower logic level netlist node; wherein the step of releasing includes releasing the first constructed BDD from the electronic memory when the second BDD and the third BDD have been constructed in the electronic memory.

Claim 5

The method of claim 1, wherein the step of constructing produces in the electronic memory a first BDD for a deeper level netlist node that both serves as a basis for construction of a second BDD for a second shallower logic level netlist node and also serves as a basis for construction of a third BDD for a third shallower logic level netlist node; and further including the steps of: storing in the electronic memory a fanout status for the first deeper logic level netlist node; and in the course of performing the depth-first traversal, adjusting the fanout status when the second BDD and the third BDD are constructed; wherein the step of releasing includes releasing the first constructed BDD from the electronic memory when the fanout status is adjusted.

Claim 6

The method of claim 1, wherein the step of constructing produces in the electronic memory a first BDD for a deeper logic level netlist node that both serves as a basis for construction of a second BDD for a second shallower logic level netlist node and also serves as a basis for construction of a third BDD for a third shallower logic level netlist node; and further including the step of: storing in the electronic memory a fanout count for the first deeper logic level netlist node; and in the course of performing the depth-first traversal, decrementing the fanout count when the second BDD is constructed; and decrementing the fanout count when the third BDD is constructed; wherein the step of releasing includes releasing the first constructed BDD from the electronic memory when the fanout count has been twice decremented.

Claim 7

The method of claim 1, wherein the step of constructing produces in the electronic memory a first BDD for a deeper logic level netlist node that both serves as a basis for construction of n BDDs for n shallower logic level netlist nodes; and further including the steps of: storing in the electronic memory a fanout count for the first deeper logic level netlist node; and in the course of performing the depth-first traversal, decrementing the fanout count each time one of the n BDDs is constructed; wherein the step of releasing includes releasing the first BDD from the electronic memory when the fanout count has been decremented n times.

Claim 8

The method of claim 1 including the steps of: in the course of performing the depth-first traversal, constructing in the electronic memory a respective BDD for each respective netlist node that feeds a second primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such second primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such second primary output.

Claim 9

The method of claim 1 including the steps of: in the course of performing the depth-first traversal, constructing in the electronic memory a respective BDD for each respective netlist node that feeds a second primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such second primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such second primary output, wherein a respective BDD constructed for a deeper logic level netlist node that feeds the second primary output may serve as a basis for construction of a respective BDD for a shallower logic level netlist node that feeds the second primary output.

Claim 10

The method of claim 1 including the steps of: in the course of performing the depth-first traversal, constructing in the electronic memory a respective BDD for each respective netlist node that feeds a second primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such second primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such second primary output; and constructing in the electronic memory a respective BDD for each respective netlist node that feeds a third primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such third primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such third primary output.

Claim 11

The method of claim 1 including the steps of: in the course of performing the depth-first traversal, constructing in the electronic memory a respective BDD for each respective netlist node that feeds a second primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such second primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such second primary output, wherein a respective BDD constructed for a deeper logic level netlist node that feeds the second primary output may serve as a basis for construction of a respective BDD for a shallower logic level netlist node that feeds the second primary output; and constructing in the electronic memory a respective BDD for each respective netlist node that feeds a third primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such third primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such third primary output, wherein a respective BDD constructed for a deeper logic level netlist node that feeds the third primary output may serve as a basis for construction of a respective BDD for a shallower logic level netlist node that feeds the third primary output.

Claim 12

The method of claim 1 including the step of: constructing in the electronic memory a respective BDD for each respective netlist node that feeds a second primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such second primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such second primary output; wherein the steps of constructing produce in the electronic memory a first constructed BDD for a deeper level netlist node that both feeds the first primary input and that also feeds the second primary input and that both serves as a basis for a shallower logic level netlist node that feeds the first primary input and also serves as a basis for a shallower logic level netlist node that feeds the second primary input.

Claim 13

The method of claim 1 including the step of: constructing in the electronic memory a respective BDD for each respective netlist node that feeds a second primary output of the netlist by constructing a respective BDD for each deeper logic level netlist node feeding such second primary output prior to constructing a respective BDD for a shallower logic level netlist node feeding such second primary output; wherein the steps of constructing produce in the electronic memory a first BDD for a deeper level netlist node that both feeds the first primary input and that also feeds the second primary input and that both serves as a basis for construction of a second BDD for a shallower logic level netlist node that feeds the first primary input and also serves as a basis for construction of a third BDD for a shallower logic level netlist node that feeds the second primary input; and wherein the step of releasing includes releasing the first constructed BDD from the electronic memory when both the second BDD and the third BDD have been constructed in the electronic memory.

Claim 14

The method of claim 1 wherein the step of computing involves computing a respective static probability and a respective toggle rate for each respective constructed BDD.

Claim 15

In a computer system, a computer implemented improved method for managing the use of computer readable memory in the course of estimating average power consumption of an electronic circuit represented as a netlist comprising the computer implemented steps of: (a) ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order that depends upon the number of logic levels between respective primary outputs and respective primary inputs that feed into such respective primary outputs; and (b) performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said step (b) comprises the steps of: (b1) constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) releasing each respective deeper logic level BDD from the computer readable memory for which a respective shallow logic level BDD has been constructed for each respective fanout of a respective netlist node associated with such respective released BDD; (b3) storing in the computer readable memory identification of the respective frontier BDD which are nonreleased BDDs produced in the computer readable memory; (b4) determining when the amount of computer readable memory used exceeds a defined limit; and (b5) releasing from the computer readable memory a first frontier BDD when the amount of computer readable memory used exceeds the defined limit.

Claim 16

In a computer system, a computer implemented improved method for managing the use of computer readable memory in the course of estimating average power consumption of an electronic circuit represented as a netlist comprising the computer implemented steps of: (a) ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order that depends upon the number of logic levels between respective primary outputs and respective primary inputs that feed into such respective primary outputs; and (b) performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said step (b) comprises the steps of: (b1) constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) releasing each respective deeper logic level BDD from the computer readable memory for which a respective shallow logic level BDD has been constructed for each respective fanout of a respective netlist node associated with such respective released BDD; (b3) storing in the computer readable memory identification of the respective frontier BDD which are nonreleased BDDs produced in the computer readable memory; (b4) determining when the amount of computer readable memory used exceeds a defined limit; and (b5) releasing from the computer readable memory a first frontier BDD when the amount of computer readable memory used exceeds the defined limit.

Claim 17

The method of claim 14 wherein said step (b) comprises the further step of: substituting a first pseudo-primary input for the first frontier BDD released from the computer readable memory.

Claim 18

The method of claim 14 wherein said step (b) comprises the further step of: computing a respective switching activity value for each respective constructed BDD.

Claim 19

The method of claim 14 wherein said step (b) comprises the further step of: computing a respective toggle rate and a respective static probability for each respective constructed BDD.

Claim 20

The method of claim 14 wherein the step of (b4) determining when the amount of computer readable memory used exceeds a defined limit involves determining when the amount of computer readable memory occupied by BDDs exceeds the defined limit.

Claim 21

A computer readable memory containing instructions that when executed causing a computer system to implement a method for managing the use of computer readable memory in the course of estimating average power consumption of an electronic circuit represented as a netlist, said instructions comprising: (a) first code for ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order based on the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) second code for performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said second code comprises: (b1) third code for constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) fourth code for computing a respective switching activity value for each respective constructed BDD; and (b3) fifth code for releasing a respective BDD from the computer readable memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.

Claim 22

A computer readable memory containing instructions that when executed causing a computer system to implement a method for managing the use of computer readable memory in the course of estimating average power consumption of an electronic circuit represented as a netlist, said instructions comprising: (a) first code for ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order based on the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) second code for performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said second code comprises: (b1) third code for constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) fourth code for computing a respective switching activity value for each respective constructed BDD; and (b3) fifth code for releasing a respective BDD from the computer readable memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.

Claim 23

The computer readable memory of claim 19 wherein said second code comprises code for substituting a first pseudo-primary input for said first frontier BDD released from said computer readable memory.

Claim 24

The computer readable memory of claim 19 wherein said second code comprises code for computing a respective switching activity value for each respective constructed BDD.

Claim 25

The computer readable memory of claim 19 wherein said second code comprises code for computing a respective toggle rate and a respective static probability for each respective constructed BDD.

Claim 26

A computer readable memory containing instructions that when executed causing a computer system to implement a method for managing the use of said computer readable memory in the course of estimating average power consumption of a computer readable circuit represented as a netlist, said instructions comprising: (a) first code for ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order based on the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) second code for performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said second code comprises: (b1) third code for constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) fourth code for computing a respective switching activity value for each respective constructed BDD; and (b3) fifth code for releasing a respective BDD from the computer readable memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.

Claim 27

A computer readable memory containing instructions that when executed causing a computer system to implement a method for managing the use of said computer readable memory in the course of estimating average power consumption of a computer readable circuit represented as a netlist, said instructions comprising: (a) first code for ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order based on the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) second code for performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said second code comprises: (b1) third code for constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) fourth code for computing a respective switching activity value for each respective constructed BDD; and (b3) fifth code for releasing a respective BDD from the computer readable memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.

Claim 28

A computer readable memory as described in claim 23 wherein said second code comprises code for computing a respective static probability and a respective toggle rate for each respective constructed BDD.

Claim 29

In a computer system, a method for managing the use of a computer readable memory in the course of estimating average power consumption of an computer readable circuit represented as a netlist comprising the computer implemented steps of: (a) ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order based on the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said step (b) comprises the steps of: (b1) constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) computing a respective switching activity value for each respective constructed BDD, wherein said step of computing involves computing a respective static probability and a respective toggle rate for each respective BDD and wherein further said step (b2) of computing a respective static probability comprises the steps of: (i) grouping all Boolean difference of each BDD; and (ii) computing all static probabilities simultaneously; and (b3) releasing a respective BDD from the computer readable memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.

Claim 30

In a computer system, a method for managing the use of a computer readable memory in the course of estimating average power consumption of an computer readable circuit represented as a netlist comprising the computer implemented steps of: (a) ranking, in the computer readable memory, primary outputs of the netlist with respect to each other in an order based on the number of logic levels between respective primary outputs and respective primary inputs that feed into circuitry which generates said respective primary outputs; and (b) performing a depth-first traversal of the netlist, in the computer readable memory, that follows the primary output ranking order, wherein said step (b) comprises the steps of: (b1) constructing, in the computer readable memory, a respective binary decision diagram (BDD) for each respective netlist node that feeds a first primary output of the netlist by constructing a respective BDD for each respective deeper logic level netlist node feeding such first primary output prior to constructing a respective BDD for a respective shallower logic level netlist node feeding such first primary output; (b2) computing a respective switching activity value for each respective constructed BDD, wherein said step of computing involves computing a respective static probability and a respective toggle rate for each respective BDD and wherein further said step (b2) of computing a respective static probability comprises the steps of: (i) grouping all Boolean difference of each BDD; and (ii) computing all static probabilities simultaneously; and (b3) releasing a respective BDD from the computer readable memory when a respective BDD has been constructed for every respective fanout of the netlist node with such respective released BDD.