Source: http://www.google.com/patents/US5392221?dq=5815142
Timestamp: 2017-03-27 03:51:50
Document Index: 657727462

Matched Legal Cases: ['art 300', 'art 325', 'art 325', 'art 350', 'art 400', 'art 350']

Patent US5392221 - Procedure to minimize total power of a logic network subject to timing ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA method and apparatus for minimizing the total power of a logic network subject to timing constraints. The method describes a procedure to assign power and/or delay to each circuit in a logic network such that the total power is minimized and the arrival time requirement at the outputs of the logic...http://www.google.com/patents/US5392221?utm_source=gb-gplus-sharePatent US5392221 - Procedure to minimize total power of a logic network subject to timing constraintsAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS5392221 APublication typeGrantApplication numberUS 07/714,027Publication dateFeb 21, 1995Filing dateJun 12, 1991Priority dateJun 12, 1991Fee statusLapsedPublication number07714027, 714027, US 5392221 A, US 5392221A, US-A-5392221, US5392221 A, US5392221AInventorsWilm E. Donath, Wing K. Luk, Donald T. TangOriginal AssigneeInternational Business Machines CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (6), Non-Patent Citations (20), Referenced by (38), Classifications (8), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetProcedure to minimize total power of a logic network subject to timing constraints
US 5392221 AAbstract
A method and apparatus for minimizing the total power of a logic network subject to timing constraints. The method describes a procedure to assign power and/or delay to each circuit in a logic network such that the total power is minimized and the arrival time requirement at the outputs of the logic network is met. A subset of circuits in the logic network are powered up and powered down in repeated succession in order to minimize the total power of the logic network.
1. A computer-based method for minimizing the total power of a logic network, containing one or more circuit elements, subject to timing constraints, the computer-based method comprising the steps of:(a) powering down the network such that an overall network delay is increased by DELTA and a total first order power decrease is maximized; and (b) powering up the network such that said overall network delay is decreased by said DELTA and said total first order power increase is minimized. 2. The computer-based method of claim 1, wherein step (a) is executed before step (b).
3. The computer-based method of claim 1, wherein step (b) is executed before step (a).
4. The computer-based method of claim 1, further comprises the steps of:(c) measuring the total power; (d) if said total power remains the same, then reducing said DELTA; and (e) repeating steps (a) through (d) until said DELTA is at or below some lower limit. 5. The computer-based method of claim 4, further comprising the step of trading-off said overall network delay for said total power, whereby the logic network's circuit elements operate at minimal total power.
6. The computer-based method of claim 1, further comprising the step of initializing delay-segments of the network by assigning power and/or delay values to said delay-segments so that a given required arrival time is met, and edge-segments are at their largest possible delay.
7. The computer-based method of claim 1, further comprising the step of checking whether a given required arrival time (RAT) can be met, and if not, adjust RAT.
8. The computer-based method of claim 7, where the step of checking further comprises the steps of:(i) setting edge-segments to the smallest possible delay; (ii) testing the network to determine a network delay. (iii) comparing said given RAT to said determined network delay; and (iv) increasing said given RAT for sinks that fail to meet said given RAT. 9. The computer-based method of claim 1, further comprises the steps of:(c) identifying a cut-set M containing at least one first element of the logic network and powering down said at least one first element; and (d) identifying a cut-set L containing at least one second element of the logic network, and powering up said at least one second element. 10. The computer-based method of claim 1, wherein the step (b) of powering up the circuit further comprises the steps of(i) determining the power, delay, and dP/dD at an operating point for each edge in a delay graph; (ii) establishing timing constraints for said edges; (iii) setting up boundary conditions for arrival times for source and sink nodes; and (iv) increasing power for each delay-segment to reduce the network delay by said DELTA(SINK) such that said total first order power increase is minimized. 11. The computer-based method of claim 1, wherein the step (a) of powering down the circuit further comprises the steps of(i) determining the power, delay, and dP/dD at an operating point for each edge in a delay graph; (ii) establishing timing constraints for said edges; (iii) setting up boundary conditions for arrival times for source and sink nodes; and (iv) decreasing power for each delay-segment to increase the network delay by said DELTA(SINK) such that said total first order power decrease is maximized. 12. A computer-based system for manufacturing integrated chips having one or more logic networks contained thereon, comprising a sub-system for minimizing the total power of the logic networks, the sub-system comprising:(1) means for checking whether a given RAT can be met; (2) means for initializing delay-segments; (3) storing means, for storing data indicative of conditions in the logic network; (4) means for setting up DELTA(SINK); (5) means for powering up the logic network such that an overall network delay is decreased by DELTA(sink) and a total first order power increase is minimized; (6) means for powering down the logic network such that said overall network delay is increased by DELTA(sink) and said total first order power decrease is maximized; (7) means for adjusting said DELTA(SINK) and iterating (3) and (4) until said total power of the network is minimized;and (8) means for measuring the total power. 13. The computer-based system of claim 12, further comprises means for assigning power and/or delay values to the logic network, whereby said assigned power and/or delay values are used to manufacture the integrated circuit.
14. A computer-based method for minimizing the total power of a logic network system, containing one or more circuit elements each of which consumes an independent resource and a dependent resource in an amount which is a nonlinear function of the amount of the independent resource consumed by the element, the computer-based method comprising the steps of:1. defining an object variable equal to the total amount of the dependent resource consumed by the system; 2. specifying at least one constraint on the allocation of the independent resource among resource-consuming elements of the system; 3. allocating, tentatively, the independent resource among said resource-consuming elements so as to satisfy said at least one constraint; 4. identifying a cut-set M containing at least a first element of the system which is subject to said at least one constraint; 5. perturbing said at least one constraint by perturbing the amount of the independent resource allocated to at least said first element in said set M, so as to improve the value of said object variable of the system by an amount Po ; 6. identifying a cut-set L containing at least a second element of the system which is subject to said at least one constraint; 7. restoring said perturbed at least one constraint to its original value by perturbing the amount of the independent resource allocated to at least said second element in said set L, so as to worsen the value of said object variable of the system by an amount less than Po. 15. The computer-based method of claim 14, further comprising:(a) said object variable has a first gradient representing the change in the value of the object variable for a unit change in the amount of the independent resource consumed by each element in said M cut-set before perturbing the constraint; (b) said object variable has a second gradient representing the change in the value of the object variable for a unit change in the amount of the independent resource consumed by each element in said L cut-set after perturbing the constraint. (c) the absolute value of the second gradient is less than the value of the first gradient. 16. The computer-based method of claim 14, wherein steps (4) and (5) comprise perturbing the amount of the independent resource allocated to the elements in the system to maximize the improvement in the value of said object variable; andwherein steps (6) and (7) comprise perturbing the amount of the independent resource allocated to the elements in the system to minimize the worsening of the value of said object variable. 17. The computer-based method of claim 14, further comprises the steps of:(8) repeating steps (1) through (7) until said dependent resource is minimized. 18. The computer-based method of claim 14, further comprises the steps of:(8) increasing said at least one constraint; and (9) repeating steps (1) through (8) . 19. The computer-based method of claim 14, further comprises the steps of:(8) decreasing said at least one constraint; and (9) repeating steps (1) through (8) . 20. A computer-based method for powering up a logic network, containing one or more circuit elements, subject to timing constraints, the computer-based method comprising the steps of:(i) assigning a value for DELTA(SINK); (ii) determining the power, delay, and dP/dD at an operating point for each edge in a delay graph; (iii) establishing timing constraints for said edges; (iv) setting up boundary conditions for arrival times for source and sink nodes; and (v) increasing power for each delay-segment to reduce the network delay by said DELTA(SINK) such that said total first order power increase is minimized. 21. A computer-based method for powering down a logic network, containing one or more circuit elements, subject to timing constraints, the computer-based method comprising the steps of:(i) assigning a value for DELTA(SINK); (ii) determining the power, delay, and dP/dD at an operating point for each edge in a delay graph; (iii) establishing timing constraints for said edges; (iv) setting up boundary conditions for arrival times for source and sink nodes; and (v) decreasing power for each delay-segment to increase the network delay by said DELTA(SINK) such that said total first order power decrease is maximized. Description
The present invention relates to the design and manufacture of integrated circuits, and more particularly to a method and apparatus for power minimization in a logic network.
Power consumption and signal delay are crucial to the design of high-performance very-large scale integrated (VLSI) circuits. In this patent application, the terms "VLSI circuits," "VLSI chips, " "logic networks," and "integrated circuits" are used interchangeably. The size and complexity of integrated circuits are increasing every day, and it is becoming increasingly important to minimize power consumption while simultaneously meeting timing constraints. VLSI chips may contain hundreds of thousands of transistors. The timing delay and power consumption associated with the VLSI chip is directly proportional to the complexity of the VLSI chip.
Each VLSI chip is made up of one or more interconnected circuit elements. These interconnected circuit elements form various logic combinations that perform specified logic functions. Each logic combinations may be identified as a logic block of some predetermined definition. Each circuit element within the logic block has both a power and delay values assigned to it. Logic blocks are provided by the manufacturer with the capability of being able to select an appropriate power level to achieve a predetermined system timing parameter.
In general, every circuit and/or network has distinctive conditions that can not be exceeded relative to power and delay. For example, the power can be continually increased until the intrinsic delay of the circuits is reached or the total power limit for the network is exceeded. If the timing requirement is violated, circuit/timing delay can be reduced by powering up the VLSI circuits until the required arrival time (RAT) is met or until the above conditions are reached, at which time the RAT cannot be met by increasing the power. Consequently, the timing requirement may be achieved in general at the expense of power. However, it is neither necessary nor desirable to set the power level of the individual circuits to their highest power level. Therefore, the problem is one of minimizing the total power for a given combination of logic blocks consistent with the overall timing constraints of the logic network.
Analytical power/timing techniques have been described for optimizing logic circuit designs, such as described in a paper entitled "Analytical Power/Timing Optimization Technique for Digital System", presented at the Fourteenth Design Automation Conference on Jun. 20-22, 1977, by A. E. Ruehli, P. K. Wolff, Sr., and G. Goertzel of the IBM Thomas J. Watson Research Center. This paper describes a method for logic gate delay assignment which achieves power minimization of digital logic while satisfying system timing. However, the method requires simplistic assumptions of the power/delay model in order to perform the analysis. These simplifications seriously reduces the accuracy of both the power minimization and the satisfaction of the delay constraints and the convergence stability of the underlying algorithm, making the approach inappropriate for large scale, high performance circuit design.
Other prior approaches primarily handled the problem of power minimization on a logic block to logic block basis. Very few prior approaches, if any, have handled the problem on a global basis.
Thus, there is a need to minimize the power level in VLSI circuits, while still maintaining the overall system timing requirements. The present invention achieves this result through application of the method and apparatus described herein.
The present invention provides a new and improved method and apparatus for minimizing the total power of a logic network subject to timing constraints. The method of the present invention is applicable for use in connection with logic blocks wherein the combination of logic blocks make up a logic network. The logic blocks consist of either a circuit element (for example, transistor or a logic gate) or a set of circuit elements. Signals are propagated from sources of the network to sinks of the network, and the signals should arrive at their respective sinks within a specified required arrival time (RAT). The problem of power minimization with timing constraints is to assign power to each logic block in the network, such that the RAT requirement is met and the total power consumed by the network is minimized.
The present invention operates by: (1) determining if the required arrival time can be met; (2) assigning delay to each delay-segment so that the arrival time requirement at the sinks is met and every edge-segment is at the largest possible delay; (3) powering down the network such that the overall network delay is increased by DELTA and the total first order power decrease is maximized; (4) powering up the network such that the overall network delay is decreased by DELTA and the total first order power increase is minimized; (5) checking to see if the total power remains the same, and if so reducing DELTA accordingly; and repeating the above steps (3)-(5) until DELTA equals zero.
FIG. 1 shows an environment for the present invention;
FIG. 2a shows in schematic form a first logic network;
FIG. 2b shows a directed delay-graph;
FIG. 3a shows a flow chart of a power minimization method of the present invention;
FIG. 3b shows a flow chart of a RAT check;
FIG. 3c shows a flow chart of initialization;
FIG. 4a shows a flow chart of a power down method of the present invention;
FIG. 4b shows a flow chart of a power up method of the present invention;
FIG. 5 shows a Power-Delay characteristic graph;
FIG. 6 shows in schematic form a second logic network.
FIG. 7a shows a flow chart of a power up method;
FIG. 7b shows a flow chart of a power down method; and
FIG. 8 shows a flow chart of the Delay-Power trade off procedure of the present invention.
I. Environment of the Present Invention
FIG. 1 illustrates an environment in which a preferred embodiment of the present invention operates. The preferred embodiment of the present invention includes an application program 102. The application program 102 represents power minimization software of the present invention.
The preferred embodiment of the present invention operates on a computer platform 104. The computer platform 104 includes certain hardware units 112 including one or more central processing unit (CPU) 116, a random access memory (RAM) 114, and an input/output interface 118. The computer platform 104 includes an operating system 108, and may include microinstruction code 110. A computer aided design automation system 103 and chip fabrication system 105. Various peripheral components may be connected to the computer platform 104, such as a terminal 126, a data storage device 130, and a printing device 134.
In a preferred embodiment of the present invention, the computer platform 104 is any International Business Machines (IBM) 3090 mainframe RS6000 workstation or the PS/2 personal system based on the Intel 80386 or 80486 microprocessor. The operating system is the IBM AIX operating system. The application program 102 is written in C programming language.
II. Description of the Underlying Technology and Theory Utilized by the Present Invention
Generally, a logic network includes a set of logic blocks. The logic blocks are made up of one or more circuit elements. Each logic block has a set of inputs and outputs. Typical logic blocks are transistors, AND-gates, OR-gates, inverters, multiplexers, registers, drivers, data-path and/or random logic macros. The logic blocks are interconnected from output to inputs to form the logic network.
The present invention is described with reference to FIG. 2a, which illustrates a representative logic network 200 having logic blocks labeled A 202a, B 202b,. . ., G 202g. Ai1 204a, Bi1 204b, Ci1 204c, Ci2 205c,...,Gi1 204g, Gi2 205g are inputs and Ao1 206a, Bo1 206b,..., Go1 206g are outputs of the logic blocks 202.
A delay-segment is an element whose power and delay can be adjusted. It can be either a circuit element or a set of circuit elements. External to the logic blocks 202, signals propagate from the outputs 206 to inputs 204 and 205 through external delay-segments, for example (Ao1 206a, Bi1 204b) and (Ao1 206a, Ci1 204c). In each logic block 202, signals also propagate internally through internal delay-segments. An internal delay-segment 216 (for example) in a logic block 202d goes from an input 205d to an output 206d that has logical dependency on the input 205d.
The internal and external delay-segments form a directed, acylic graph or delay graph. FIG. 2b shows an example of the delay graph 275 for the network shown in FIG. 2a. It should be pointed out that, without loss of generality, the delay graph is simplified (FIG. 2b) by excluding the delay-segments related to the REGISTER element 220. For purposes of explaining the directed graph 275 it is helpful to define source and sink nodes. The nodes 280 of the graph are inputs 204 and 205 or outputs 206 of the logic blocks 202, and the edges 290 through 299 are delay-segments (external or internal). The source nodes start from the primary inputs (for example the inputs 204a and 205c) of the logic network and register outputs, and the sink nodes end at the primary outputs of the logic network and register inputs (for example the outputs 206f and 206g). The directed graph 275 is also called a delay graph 275 of the logic network 200.
At each node 280 of the delay graph 275, an arrival time is assigned or allocated by a chip designer. The arrival time measures the time required for signals to travel from the left-most outputs to the right most inputs. Each edge 290 of the delay graph 275 is assigned a delay, which is the time to propagate a signal through the corresponding delay-segment.
For external connections of the logic blocks 202, to the first order, the delay of a delay-segment depends on the length, capacitance, and resistance of the connection, and the input capacitance of the successor circuits. To the second order, the delay depends on the power of a driving circuit and affects the transition time of the signals to the successor circuits, and hence the delay of the successor circuits. For internal delay-segment in a logic block 202, to the first order, the delay is governed by the gate delay, device size and power consumption of the underlying circuits of the logic block 202. To the second order, the delay depends on the loading at the output and the signal transition time at the input of the delay-segment, the delay also affects the delay of the output connections. To account for the second order effect, the delay of a delay-segment is computed in conjunction with the delay of the predecessor and successor delay-segments. If the capacitance and resistance of inter-block connections are given, the delay of a logic block depends on both the predecessor and the successor blocks, and thus only the delay-segment internal to the logic block must be considered.
To the first order, the delay-segments are treated independently with each other in terms of delay. The delay and power of a logic block or an internal delay-segment are modelled by a convex, monotonic decreasing function. The delay of the logic network 200 decreases as more power is applied to the underlying circuits/devices of the logic blocks 202, or the area of the underlying circuits/devices of the logic blocks 202 is increased. Power and area of the circuits may be considered proportional to each other. If the circuit devices are scaled in only one direction, then power and length (or width) may be considered proportional to each other. So minimizing power of a network 200 is directly related to area minimization, hence improving density, wiring and performance of the overall system. In addition, there is also a minimum intrinsic delay in each circuit device which is independent of the power.
The following equation may be used to represent the area-power-delay characteristic, where A, A' and B are constants.
power=A/(delay-B)                                          (1)
area=A'/(delay-B)                                          (2)
These equations are a useful representation of the power-delay relationship. Any convex function of power and delay, discrete tables of power and delay with interpolation and other similar forms can also be used to determine the power-delay relationship. Based on the trade-off of power-delay, a procedure according to the present invention to minimize the total power of a logic network subject to timing constraints is described below.
Generally, a delay graph 275 may be represented by the relationship GD =(VD,ED), where VD is the set of nodes and ED is the set of edges. For each directed edge in the delay graph 275, the arrival time (at) at a successor node (nsucc) should be at least the sum of the arrival time at a predecessor node (npred) plus the delay of the delay-segment represented by the edge=(npred, nsucc). Equation 3 represents this relationship:
at (nsucc)&#8806;at (npred)+delay (npred, nsucc),  (npred, nsucc)&#949; ED                                                   (3)
The boundary condition for the delay graph 275 is set up as follows: For each source (register outputs, for example 212, or logic network inputs, for example 204aand 205c), the arrival time is equal to a source arrival time (SAT) of the network 200. The required arrival time (RAT) is a constraint on the logic network 200. Each logic block 202 in the logic network 200 is allocated a specific delay in order to satisfy the constraint (RAT).
at(n)=SAT(n),  n &#949; SOURCE(GD)                 (4)
For each sink (register inputs, for example 208, or logic network outputs, for example 206f and 206g) the arrival time should be at most equal to the required arrival time (RAT) of the logic network 200.
at(n)&#8806;RAT(n), n &#949;SINK(GD)              (5)
The above |ED |+|SOURCE|+|SINK| equations specify the timing requirements of the logic network 200.
The power optimization objective is given by Equation 6:
min&#931;e power(e)=&#931;e power(delay(e)),e&#949;ED(6)
This is an optimization problem with a non-linear objective function and linear constraints.
III. Description of the Method of the Present Invention
FIG. 3a shows an overall logic flowchart 300 which describes, in general terms, the operation of a power minimization procedure of the present invention. This procedure 300 is embodied in the application program 102 and the computer aided design automation system 103. In general, the procedure 300 shown in FIG. 3a accepts data representing the current delay of the logic network 200 and the current power level of the logic network 200. The delay and power can be considered to be independent and dependent resources, respectively. The circuit elements in the logic network 200 consumes the independent resources and the dependent resource in an amount which is a nonlinear function of the amount of the independent resource consumed by the circuit elements. The procedure 300 then generates more efficient power delay operating points for the logic blocks in the logic network 200 in which the overall power of the network 200 is minimized, while still satisfying the established timing constraints.
In FIG. 3a, the procedure 300 begins with a start command 302, followed by two separate and distinct initialization steps 304 and 306. The first step 304 is the required arrival time (RAT) check.
FIG. 3b is a detailed flowchart 325 representing the operation of block 304 of FIG. 3a. The flowchart 325 outlines the operation of the RAT check 304. The RAT check 304 establishes whether the designer specified RAT can be satisfied.
In step 332, the designer of the network provides an ideal and/or preferred RAT or constraint for the logic network 200 as a whole, as well as for the individual sinks.
In step 334, every edge-segment is set to the smallest possible delay.
In step 338, a timing analysis is performed to determine whether this ideal or preferred RAT can be met.
In step 340, if the given RAT cannot be met, then in step 342 the RAT has to be modified in order to satisfy the timing requirement. The RAT check 325 is applied to the entire circuit as a whole, and only after it is determined in step 340 that the given RAT cannot be met is there, in step 342, a change to individual sinks in the logic network 200. Specifically, in step 342, the RAT is increased for the sinks that fail to meet their given unique RAT. The RAT is increased, for example, by an amount that is equal to the difference between the actual arrival time after administering the above check and the required arrival time. Any standard timing analysis procedure known to one skilled in the art of integrated chip design could be used with the present invention.
FIG. 3c is a detailed flowchart 350 representing the second initialization step shown in block 306. Step 360 entails allocating the independent resource among the resource consuming elements of the logic network 200, or in other words, assigning a delay to each delay-segment. Each delay-segment is assigned, for example, a delay so that the arrival time requirement at the sinks is met, for example at(n)≦RAT(n), n εSINK and Σe delay(e) is maximized. Initially, however, this amounts to setting every edge-segment to the largest possible delay possible, while still satisfying the RAT. If the delay for the delay-segments is unknown in step 360, then: at(nsucc)≧at(npred)+delay(e) , e=(npred, nsucc)εED ; at(n)=SAT(n) , nεSOURCE(GD); at(n)≦RAT(n), nεSINK(GD); and max Σe delay(e). If, however, the initial delay is given for each delay-segment, then change delay of some of the edges to just satisfy the RAT. Thus: at(nsucc)≧at(npred)+delay(e)+Δdelay(e), e=(npred, nsucc)εED ; at(n)=SAT(n), ΔnεSOURCE(GD); at(n)≦RAT(n), nεSINK(GD); and max Σe Δdelay(e).
In step 370, the value of DELTA is set. DELTA can be set at any value, but for illustration DELTA might be set at: DELTA=1/2 maxiεSOURCE, JεSINK (RAT(j)-SAT(i)).
From block 306, the procedure 300 proceeds to a further block 308, in which a procedure 450 of powering down the overall network is performed. The powering down procedure 308 is such that the overall network delay is increased by DELTA and the total first order power decrease Σe (dP/dD)D=d0(e) Δdelay(e), e.εED is maximized. (dP/dD)D=d0 (e) is the derivative at D=dO for delay-segment e on its power-delay characteristic, and Δdelay(e) is the delay increase from D=d0 for e. The power down procedure 450 is detailed below in conjunction with FIG. 4b. Procedure 308 can also viewed as perturbing the constraint (RAT) by an specified amount, for example DELTA. Thus, perturbing the amount of the independent resource in at least one of the resource consuming elements, such that the dependent resource is changed (improved) by a value Pdown =ΣeεEp Pe (d(e))-Pe (do (e))]≦0 where Ep is a set of perturbed resource consuming elements with delay increased, and d(e)≧do (e) .
The procedure 300 flows from block 308 to block 310, in which a procedure 400 for powering up the network is performed. The objective of the power up procedure 310 is the exact antithesis of the power down procedure 308. Accordingly, the overall network delay is decreased by DELTA, while the total first order power increase Σe (dP/dD)D=d0(e) Δdelay(e), e εED is minimized. (dP/dD)D=d0(e) is the derivative at D equal to dO for delay-segment e on its power-delay characteristic, and Δdelay(e) is the delay decrease from D equal to dO for e. The power up procedure 310 is detailed below in conjunction with FIG. 4a. Procedure 310 can also viewed as perturbing the constraint (RAT) by a specific amount. Similar to the power down procedure this amount could be, for example, equal to DELTA. Thus, perturbing the amount of the independent resource in at least one of the resource consuming elements, such that the dependent resource is changed (worsened) by a value Pup =Σe εEp [Pe (d(e))-Pe (do (e))]≧O when Ep is a set of perturbed resource consuming elements with delay decreased and d(e)≦do (e).
Part of the power down 308 and power up 310 procedures described above is defining an object variable equal to the dependent resource consumed by the logic network 200. In other words, the total power of the logic network, before the power down 308 and power up 310 procedure is administered, is saved. The power down procedure's 308 goal is to essentially improve the value of the object variable by an amount Pdown ; while the power up procedure's 310 goal is to worsen the value of the object variable by an amount Pup less than |Pdown |.
Thus, as seen in block 312, the total power of the logic network is measured. If the total power remains the same, DELTA is reduced. An example of such a reduction might be to reduce DELTA to DELTA/2. However, if the total power is not the same then the procedure 300 does not reduce DELTA, but traverses 313 to block 316.
The procedure flows to block 316, where it is determined whether DELTA has reached zero. In an alternative embodiment, the procedure determines whether DELTA has reached or is below some lower limit. If DELTA equals 0 then the procedure flows to 318; however, if DELTA does not equal 0 the procedure flows back 322 to block 308, and the procedure continues as described above. It will become apparent from the examples described in Section VII herein, that DELTA will always reach zero, and thus the procedure 300 will always end.
The procedure 300 iteratively traverses blocks 308 and 310, reducing the power while meeting the overall timing requirement.
Finally, the procedure flows to block 318. Once the procedure 300 has determined what the optimum power and delay values are for the logic network, each delay-segment of the network is assigned a power and delay value such that the total power is minimized and overall timing requirement is met. This step is an essential part of the chip manufacturing process. Once step 318 is finished the procedure 300 stops 320.
The order of blocks 308 and 310 is interchangeable. Consequently, the procedure works equally well regardless of which procedure - the power down 308 or power up 310 is executed first. FIG. 3a has the power down 308 sequence first only for illustrative purposes.
IV. The Power-Delay Trade-off
Given the logic network 200 of circuit connections as shown in FIG. 2a, the arrival time at each sink of the network can be reduced by increasing the power of a subset of circuits. The power up 310 and power down 308 procedure provide, respectively, a method to increase/decrease the power of a subset of circuits in the network 200 in a way to reduce/increase the arrival time at each of the network outputs by a specific amount. By considering the delay-power characteristic of the circuits the arrival time can be reduced in the direction of smallest total power increase. A typical scenario is: given a chip design that exceeds a target cycle time requirement, the procedure 310 can be applied to speed up a subset of the circuits in a way to meet the overall target cycle time.
A. Underlying theory for the Power Up Procedure
Generally, given a chip design where the timing of the network is off at each sink in SINK(GD) by an amount denoted by DELTA(n), nεSINK(GD), the designer/manufacturer may select a subset of the logic blocks or delay-segments and power them up to reduce the delay of the blocks, and subsequently reduce the network delay by the amount given by DELTA(SINK), hence meeting the timing requirement.
Let Δat be the decrease in arrival time, Δdelay be the decrease in delay in the delay-segments; the set of timing specifications that is required to reduce the network delay by at least DELTA(SINK) is given by:
&#916;at(nsucc)&#8806;&#916;at(npred)+&#916;delay(npred,nsucc), (npred, nsucc)&#949;ED                                    (7)
&#916;at(n)=0,  n &#949; SOURCE(GD)               (8)
&#916;at(n)&#8807;DELTA (n) , n&#949;SINK(GD)    (9)
It should be pointed out that Δdelay equals zero for external connections in this formulation.
The subset of the delay-segments selected for powering up (or reducing delay) is the set that minimizes the total first order power increase. As shown in FIG. 5, the first order power increase ΔP of a delay-segment is the derivative dP/dD at the delay operating point D equal to dO in the power-delay characteristic times the decrease in delay ΔD, as shown in Equation 10.
&#916;P=(dP/dD)D=d0 &#916;D                         (10)
The objective of powering up the network to meet the timing requirement is:
min&#931;(dP/dD)D=d0(e) &#916;delay(e), e &#949;ED(11)
The solution of Equation 11 gives the increase in power (or decrease in delay) for each delay-segment. The optimization problem can be solved using standard linear programming techniques, such as the simplex algorithm or the interior point techniques or heuristic to take advantage of the special matrix and network structure of this problem.
The present invention, however, contemplates the use of any form of presently known or future developed optimization technique used in combination with the disclosed invention.
B. The Power Up Procedure
FIG. 4a is a detailed flowchart 400 illustrating the operation of block 310 of FIG. 3a which outlines the operation of the procedure for powering up the network. In FIG. 4a, data arrives at block 406, in which the power, delay, and dP/dD are all calculated. These values are all calculated at the delay operating point D equal to d0 for each edge in the delay graph GD.
Next, the procedure flows to block 408, in which a timing constraint is set up for each edge in GD. The timing constraint is represented by Equation (7). Block 410 sets up the boundary conditions, Equations (8) and (9) above, for the arrival time for each SOURCE node and the required arrival time for each SINK node. Finally, Block 412 determines what the increase in power ΔP and/or decrease in ΔD for each delay-segment in order to reduce the network delay by DELTA(SINK) such that the total first order power increase in minimized.
The above description of the power up sequence is an illustration of how the procedure 400 would be implemented if done in accord with the minimization of power procedure 300. However, it is possible to use the power up procedure independently of the minimization of power procedure 300. The power up procedure is shown is FIG. 7a. The procedure 700 is exactly the same as procedure 400, however Blocks 702 704, 706, 715 and 716 are added.
The procedure begins with a start command 702. Block 704 represents the step of performing a timing analysis on the network. The logic proceeds from block 704 to block 706, in which the amount of arrival time being exceeded at each individual sink is calculated. This value is represented by DELTA(SINK). From this point on, the procedure 700 is exactly the same as that described in connection with FIG. 4a. At block 715, the new values of power and delay are assigned to each edge-segment of the network.
C. Underlying Theory for the Power Down procedure
In the case of slowing down the network by DELTA(SINK) in order to lower the power, the above procedure 400 is applied with a slight modification. Let Δat be the increase in arrival time, Δdelay be the increase in delay in the delay-segments; the set of timing specifications that is required to slow down the network delay by at most DELTA(SINK) is given by:
&#916;at(nsucc)&#8807;&#916;at(npred)+&#916;delay (npred, nsucc);(12)
&#916;at(n)=0,  n &#949; SOURCE(GD)               (13)
&#916;at(n)&#8806;DELTA(n), n &#949; SINK(GD)    (14)
The subset of the delay-segments selected for powering down (or increasing delay) is the set that maximizes the total first order power decrease. The first order power decrease ΔP of a delay-segment, as shown in FIG. 5, is the derivative dP/dD at the delay operating point D=d0 in the power-delay characteristic times the increase in delay ΔD, as shown in Equation 15.
&#916;P=(dP/dD)D=d0 &#916;D                         (15)
The objective of powering down the network to meet the timing requirement is:
max&#931;e (dP/dD)D=d0 (e) &#916;delay(e), e&#949;ED(16)
Hence, for each delay-segment the total first order power is maximized.
As stated above for the power up procedure, the optimization problem can be solved using standard linear programming techniques, such as the simplex algorithm, the interior point techniques, or heuristic. The solution gives the decrease in power (or increase in delay) for each delay-segment.
D. The Power Down Procedure
FIG. 4b is a detailed flowchart 350 illustrating the operation of block 308 of FIG. 3a, which outlines the operation of the procedure for powering down the network.
The procedure for powering down the network is exactly the same as for powering up the network, described above in FIG. 4a and accompanying text, except for Blocks 458, 460, and 462. Block 458 sets up the timing constraint: Δat(nsucc)≧Δat(npred)+Δdelay(npred,nsucc) for each edge in the delay graph GD. Block 460 sets up the boundary conditions based on equations (13) and (14). Block 462 determines what the decrease in power ΔP and/or increase in delay ΔD is for each delay-segment in order to increase the network delay by DELTA(SINK) such that the total first order power decrease in maximized.
Analogous to the independent power up procedure 700, the power down procedure can be used independently from the minimization of power procedure 300. The independent power down procedure is shown in FIG. 7b. Once again, the only difference between the power down procedure 450 and the independent power down procedure 750 is blocks 752, 754, 756, 765 and 766. These blocks are exactly the same as that described above for the independent power up procedure 700.
V. Power optimization and Cut-Sets
The subsets used in the power up and power down procedures, respectively, are typically different subsets. This characteristic is what allows the above described procedure 300 to ultimately decrease and minimize the power used on the overall logic network. The subsets used in the power up 308 and power down 310 procedures described above are ascertained as set forth below. The present invention contemplates the use of any form of presently known or future developed technique for determining the subsets used in combination with the disclosed invention.
Generally, from the inputs to the outputs of a logic network there are a plurality of different paths. Each path contains a collection of different circuits elements. Among all the different paths, the largest path delay determines the total delay of the logic network. The path delay for each unique path is the sum of the delay in each delay-segment present in that path.
A cut-set is a set of circuits that cuts every path once. The power-optimization procedure uses two types of cut-sets: (1) an L set and (2) an M set. The L and M sets are a more general means of performing the power minimization procedure described above. The L set is the set of circuits or set of delay-segments that are powered up and the M set is the set of circuits that are powered down. The L set cuts each path in the logic network at least once, while the M set cuts each path in the logic network at most once.
For illustration purposes consider the power down procedure 450. Powering down is equivalent to allowing the delay to increase. Since one of the objectives of the present invention is to meet the given RAT, the network can not afford to increase every critical path more than once. Delay will inherently increase when powering down the network. Hence, there is no need to increase delay in every particular circuit more than once. On the other hand, when you power up you do not mind if some paths have to be reduced in terms of delay more than once. Lc is a L-cut set that minimizes Σe (∂P/∂D)(e)ΔDe =πL ≧0; Mc is a M-cut set that maximizes Σe (∂P/∂D)(e)ΔDe =πM ≧0; and ΔP=πL+ πM.
The basic concept is that during the power up and power down procedures described above there is a trade-off of one set of subsets for another, such that the delay remains the same while the total power is minimized.
A linear programming technique is implemented to ascertain the L and M sets. The above procedure works well when the logic network is relatively small. However, when the network becomes larger (for example, approximately 10,000 delay segments), compute times increase. Therefore, heuristic or other developed algorithms are the preferred method of isolating the subsets for larger networks.
VI. Delay-Power Trade-off of an Entire Logic Network
Finally, there can be one last step as shown in FIG. 8. At times there might exist a network that can benefit dramatically by an increase/decrease in the RAT at a savings/increase in power. The step 810 includes increasing/decreasing the RAT and repeating the minimization procedure 300 shown in FIG. 3 for this new RAT. This brings the present invention full circle by checking to see if an increase/decrease in delay will produce a significant savings/minimal increase in power for the entire logic network. This has the effect of trading off delay for power, as opposed to the above procedure 300 that basically trades off power for delay.
As a result, one can obtain a faster network (smaller RAT) with the smallest increase in power, or a slower network (larger RAT) with a largest decrease in power.
VII. Two Illustrations of the Present Invention
Table 1 shows the results of performing the above described iterations of power up and power down on the logic network shown in FIG. 6. These iterations produce successively smaller power levels. The first column (Delta arrTime) shows that the initial value of DELTA is set at 190. Increasing the delay is analogous to power down and decreasing the delay is analogous to power up. Consequently, a plus (+) sign in front of the DELTA value signifies the power down operation and a minus (-) sign signifies the power up operation.
TABLE 1______________________________________Delta                            totalarrTime  a1 . . . a8            b1 . . . b4                     c1 . . . c2                            power   RAT______________________________________  100       100      100    155704  380+190   290       100      100     95384  570-190   100       100      100    155704  380+95    195       100      100    110056  475-95    100       100      100    155704  380+47    147       100      100    125028  427-47    147       100      53     149496  380+23    147       100      76     133288  403-23    124       100      76     145064  380+11    135       100      76     138896  391-11    135       100      65     144956  380 +5    135        95      75     141974  385 -5    135        95      70     144538  380 +2    133        95      72     143424  382 -2    133        97      72     144498  380 +1    133        97      71     143952  381 -1    133        96      71     144484  380                            (-7.77%)______________________________________
Columns 2,3, and 4 (a,b, and c) shows the delay in each individual logic block 602a through 602g. Column 5 (power) shows the total power in the network. The total power goes up and down depending upon whether the procedure is in the power up or power down mode. The delay in each external inter-logic block connection is 20.
Column 6 (RAT) shows the required arrival time at each iteration step. In this example the overall RAT is set to 380. During the power down mode, the overall network delay is increased by DELTA. A typical starting DELTA is the RAT divided in half. Consequently, as shown in the first power down sequence of TABLE 1, DELTA is set at 190 and the overall network delay is increased to 570 (380+190), and the total first order power decrease is maximized. It should be noted, however, that any value that is less then the given RAT could be used for the starting DELTA. The total first order power drops from 155704 to 95384.
The procedure continues by decreasing the overall network delay by DELTA (190) during the first power up sequence, resulting in the minimization of any increase in the total first order power. This procedure is continued until DELTA is equal to zero, at which time the total power is minimized and the overall timing requirement is met. In this case the total power has been decreased by 7.77% and the RAT of 380 was met.
It should also be noted that the procedure shown in FIG. 3 calls for determining if the power level remains the same 312. In the example shown in TABLE 1, it appears that the power level never remained the same within a given DELTA. However, the iteration where the power remained the same was removed from the table for the sake of brevity (thus, the power up and power down iteration with DELTA equal to ±190 was repeated and the power remained the same).
The example shown in TABLE 1 indicates the results after completing the procedure at one particular starting point (delay=(100, 100, 100)). The decrease in power was 7.77%. The final delay, as shown in TABLE 1, is (133, 96, 71).
The percentage decrease in power that might be realized is dependent upon the starting point. However, the final power level will be relatively consistent regardless of the starting point. It is possible to start with a very poor design which might initially result in the total power being very high. For example, if the starting point was initially set at delay=(278, 11, 11), for each logic block (a,b,c) in FIG. 6., respectively. The total power improvement would be from 6029998 to 144480, a savings of 4073%. However, the final total power remains almost the same or to within a negligible round-off error. The exact optimal solution for the simple network in FIG. 6 can be shown, by mathematical computation, to be (132.3, 96.5, 71.2). For more complex circuits, however, the optimum solution can not be calculate by hand, and thus the need for the present invention.
TABLE 2 demonstrates the use of subsets (cut-sets) through an example of performing both the power up and power down sequence once. The logic blocks represented in TABLE 2 refer to those shown in FIG. 2a and delay graph shown in FIG. 2b.
The upper portion of Table 2 shows the power down sequence with the M-set of delay-segments marked with an X. Only this set of delay-segments is powered down, and thus the delay in each individual delay-segments in the set is increased.
DELTA is set to 10. The table shows the delay D before the power down sequence, as well as the delay D' after the power down sequence. As the table indicates the power was lowered from 366081 to 330282, while the M-set of delay-segments each increased in delay by 10.
The bottom portion of Table 2 shows the power up sequence with the L-set of delay-segments marked with an X. Once again, only this group of delay-segments are powered up. It should be noted, that this set is different from the M-set used in the power down procedure. However, in general, the L-set and M-set may have common elements. Table 2 indicates that the power was increased from 330282 to 348060, while the selected delay-segments each decreased their respective delay by 10.
TABLE 2__________________________________________________________________________ArrTime: Ai1, Bi2 = 0, RAT: Fo1, Go1 = 300, WireDelay = 20, power =106 /(delay-10)            a  b  c1 c2 d1 d2 e1 e2 f  g1 g2 power__________________________________________________________________________Powering Down (DELTA = +10)delay            40 50 50 110                        30 30 80 30 30 30 130                                             366081dP/dD            1111               625                  625                     100                        2500                           2500                              204                                 2500                                    2500                                       2500                                          69M-cut                        x  x  x           xDelay D;         40 50 50 110                        40 40 90 30 30 30 140                                             330282Powering Up (DELTA = -10)delay D          40 50 50 110                        40 40 90 30 30 30 140                                             330282dP/dD            1111               625                  625                     100                        1111                           1111                              156                                 2500                                    2500                                       2500                                          59L-cut               x  x  xdelay D'         40 40 40 100                        40 40 90 30 30 30 140                                             348060__________________________________________________________________________
This one sequence of power up and power down demonstrates how the total power is reduced (366081 to 348060) while the timing delay of the entire network remains the same as when the above procedure started.
The above sequence would be performed a plurality of times. The iterations would continue until there was no further reduction in power, at which time DELTA would be decreased and the above procedure would start all over again.
TABLE 3______________________________________iteration    delDelay    delPower   total Power______________________________________0                               3660811        150         -790950    2634751        -150        15150      3660812        75          -395475    2765392        -75         21975      3660813        37          -195101    2942633        -37         27417      3660814        18          -94914     3147024        -18         21798      3668975        18          -127656    3147025        -18         21798      3668976        9           -63828     3299776        -9          12321      3459077        9           -45540     3143667        -9          14094      3322928        9           -24408     3150358        -9          12276      3322929        4           -10848     3231449        -4          7720       33229210       2           -5424      32732910       -2          4456       33208211       2           -5372      32703211       -2          4524       33197912       2           -5408      32703212       -2          4524       33197913       1           -2704      32939613       -1          2376       33194714       1           -2526      32939614       -1          2376       331846______________________________________
TABLE 4__________________________________________________________________________Power lmprovement: (-10.3%)Delaya b c1 c2 d1 d2               e1 e2                    f g1                        g2 power__________________________________________________________________________initial40  50    50 110          30 30               80 30                    30                      30                        130                           366081optimized31  39    40 91 40 39               91 31                    39                      39                        149                           331846__________________________________________________________________________Power Improvement: Random starting point (-1721%)Delaya b c1 c2 d1 d2               e1 e2                    f g1                        g2 power__________________________________________________________________________initial11  11    136       167          136             11               167                  11                    11                      11                         73                           6044613optimized31  39    40 91 40 39               91 31                    39                      39                        149                           331846__________________________________________________________________________Power Improvement: Another starting point (-131%)Delaya b c1 c2 d1 d2               e1 e2                    f g1                        g2 power__________________________________________________________________________initial50  50    50 120          15 15               50 15                    50                      50                        120                           768310optimized31  39    40 91 40 39               91 31                    39                      39                        149                           331846__________________________________________________________________________
Table 3 shows another illustration of a complete run through the power minimization procedure 300 of the present invention on the logic network shown in FIG. 2a and delay graph in FIG. 2b . Column 1 indicates which iteration is being performed. Column 2 indicates the DELTA being used during that particular iteration. Column 3 shows that difference in power that particular iteration produced. Finally, Column 4 indicates the total power .for the logic network 200. As shown, the iterations 1 through 14 produce successively smaller power levels. As discussed earlier, sometimes the same DELTA is used more then once. For example, iterations 6, 7 and 8 all use DELTA equal to 9. Increasing the delay is analogous to powering down and decreasing the delay is analogous to powering up. The total decreasing power of the logic network can be seen in the last column.
TABLE 4 shows the results of the procedure with three separate and distinct starting points. Consequently, there are three different values for the power improvement in terms of percentage depending on which starting point was used (for example, for a randomly selected starting point, the improvement obtained is 1721%). However, the procedure 300 resulted in the final power of the logic network being the same regardless of the starting point.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3702003 *Oct 9, 1970Oct 31, 1972Marathon Oil CoAlgorithm to minimize iterative computation in a process for the analysis or design of a physical systemUS4263651 *May 21, 1979Apr 21, 1981International Business Machines CorporationMethod for determining the characteristics of a logic block graph diagram to provide an indication of path delays between the blocksUS4698760 *Jun 6, 1985Oct 6, 1987International Business MachinesMethod of optimizing signal timing delays and power consumption in LSI circuitsUS4811237 *Jun 24, 1987Mar 7, 1989General Electric CompanyStructured design method for generating a mesh power bus structure in high density layout of VLSI chipsUS4827428 *Nov 15, 1985May 2, 1989American Telephone And Telegraph Company, At&T Bell LaboratoriesTransistor sizing system for integrated circuitsUS4882690 *Sep 25, 1986Nov 21, 1989Hitachi, Ltd.Incremental logic synthesis method* Cited by examinerNon-Patent CitationsReference1"Analytical Power/Timing Optimization Technique for Digital System" by Ruehli et al., IEEE 14th Design Automation Conf., 1977, pp. 142-146.2"Analytical Power/Timing Optimization Technique for Digital System", Ruehli, et al., 1977.3"Optimization of Digital MOS VLSI Circuits", Matson, 1985.4"PHILO-A VLSI Design System" by R. Donze et al., IEEE 19th Design Automation Conf., 1982, pp. 163-169.5"Processing for Selecting Circuits with Optimum Power and Area Requirements", Linville, et al., 1975.6"Signal Delay in General RC Networks with Application to Timing Simulation of Digital Integrated Circuits" by Lin et al., IEEE 1984 Conf. on Advanced Research in VLSI, M.I.T., pp. 93-99.7"Signal Delay in General RC Networks with Application to Timing Simulation of Digital Integrated Circuits", Lin et al., 1984.8"Tilos: A Posynomial Programming Approach to Transistor Sizing", Fishburn et al.9"Timing Analysis for ηMOS VSI", Jouppi, 1983.10 *Analytical Power/Timing Optimization Technique for Digital System , Ruehli, et al., 1977.11 *Analytical Power/Timing Optimization Technique for Digital System by Ruehli et al., IEEE 14th Design Automation Conf., 1977, pp. 142 146.12 *J. Mavor et al., Introduction to MOS LSI Design, Chapter 3, Addison Wesly Publication Company, 1983, pp. 79 85.13J. Mavor et al., Introduction to MOS LSI Design, Chapter 3, Addison-Wesly Publication Company, 1983, pp. 79-85.14 *Optimization of Digital MOS VLSI Circuits , Matson, 1985.15 *PHILO A VLSI Design System by R. Donze et al., IEEE 19th Design Automation Conf., 1982, pp. 163 169.16 *Processing for Selecting Circuits with Optimum Power and Area Requirements , Linville, et al., 1975.17 *Signal Delay in General RC Networks with Application to Timing Simulation of Digital Integrated Circuits , Lin et al., 1984.18 *Signal Delay in General RC Networks with Application to Timing Simulation of Digital Integrated Circuits by Lin et al., IEEE 1984 Conf. on Advanced Research in VLSI, M.I.T., pp. 93 99.19 *Tilos: A Posynomial Programming Approach to Transistor Sizing , Fishburn et al.20 *Timing Analysis for MOS VSI , Jouppi, 1983.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5475607 *Apr 12, 1994Dec 12, 1995International Business Machines CorporationMethod of target generation for multilevel hierarchical circuit designsUS5515302 *Nov 7, 1994May 7, 1996Motorola, Inc.Method for identifying excessive power consumption sites within a circuitUS5517649 *Apr 19, 1994May 14, 1996Maxtor CorporationAdaptive power management for hard disk drivesUS5535145 *Feb 3, 1995Jul 9, 1996International Business Machines CorporationDelay model abstractionUS5598348 *Sep 22, 1994Jan 28, 1997Sun Microsystems, Inc.Method and apparatus for analyzing the power network of a VLSI circuitUS5663888 *Apr 29, 1996Sep 2, 1997Nec Usa, Inc.Redesign of sequential circuits to reduce clock periodUS5673200 *Jun 20, 1996Sep 30, 1997Matsushita Electric Industrial Co., Ltd.Logic synthesis method and logic synthesis apparatusUS5682519 *Apr 24, 1995Oct 28, 1997Cadence Design Systems, Inc.Method for reducing power consumption of switching nodes in a circuitUS5764530 *Mar 6, 1995Jun 9, 1998Fujitsu LimitedApparatus and method for generating circuit net list from mask pattern dataUS5764531 *Mar 14, 1996Jun 9, 1998Kabushiki Kaisha ToshibaSizing apparatus for active devices of integrated circuits and sizing method thereforUS5764532 *Jul 5, 1995Jun 9, 1998International Business Machines CorporationAutomated method and system for designing an optimized integrated circuitUS5787008 *Apr 10, 1996Jul 28, 1998Motorola, Inc.Simulation corrected sensitivityUS5787011 *Jan 19, 1995Jul 28, 1998Texas Instruments IncorporatedLow-power design techniques for high-performance CMOS circuitsUS5790415 *Apr 10, 1996Aug 4, 1998Pullela; SatyamurthyComplementary network reduction for load modelingUS5841673 *Jan 30, 1996Nov 24, 1998Nec CorporationSystem and method for processing graphic delay data of logic circuit to reduce topological redundancyUS5983007 *May 30, 1997Nov 9, 1999Lucent Technologies Inc.Low power circuits through hazard pulse suppressionUS6212666 *Nov 4, 1996Apr 3, 2001Synopsys, Inc.Graphic representation of circuit analysis for circuit design and timing performance evaluationUS6345378 *Mar 23, 1995Feb 5, 2002Lsi Logic CorporationSynthesis shell generation and use in ASIC designUS6434729 *Apr 4, 2000Aug 13, 2002International Business Machines CorporationTwo moment RC delay metric for performance optimizationUS6453446Apr 2, 1998Sep 17, 2002Magma Design Automation, Inc.Timing closure methodologyUS6523154 *Dec 14, 2000Feb 18, 2003International Business Machines CorporationMethod for supply voltage drop analysis during placement phase of chip designUS6553550 *Mar 3, 2000Apr 22, 2003Peter MenegayMethod and apparatus for computing delay correlation effects in digital circuitsUS6658634 *May 7, 1998Dec 2, 2003International Business Machines CorporationLogic power optimization algorithmUS6725438Apr 24, 2002Apr 20, 2004Magma Design Automation, Inc.Timing closure methodologyUS6816994 *Jun 21, 2002Nov 9, 2004Micron Technology, Inc.Low power buffer implementationUS6941526 *Jul 26, 2004Sep 6, 2005Micron Technology, Inc.Low power buffer implementationUS7093208 *May 10, 2004Aug 15, 2006International Business Machines CorporationMethod for tuning a digital design for synthesized random logic circuit macros in a continuous design space with optional insertion of multiple threshold voltage devicesUS7162402 *Oct 31, 2002Jan 9, 2007Kimotion Technologies, Inc.Posynomial modeling, sizing, optimization and control of physical and non-physical systemsUS7489638 *Apr 8, 2004Feb 10, 2009Alcatel-Lucent Usa Inc.Scheduling with delayed graphs for communication networksUS8621403Apr 19, 2004Dec 31, 2013Synopsys, Inc.Timing closure methodology including placement with initial delay valuesUS9337845 *Jun 16, 2014May 10, 2016International Business Machines CorporationSolving constraint satisfaction problems using a field programmable gate arrayUS20030237056 *Jun 21, 2002Dec 25, 2003Aaron SchoenfeldLow power buffer implementationUS20040230924 *May 10, 2004Nov 18, 2004International Business Machines CorporationMethod for tuning a digital design for synthesized random logic circuit macros in a continuous design space with optional insertion of multiple threshold voltage devicesUS20050114803 *Jul 26, 2004May 26, 2005Aaron SchoenfeldLow power buffer implementationUS20050120319 *Apr 19, 2004Jun 2, 2005Van Ginneken Lukas P.Timing closure methodologyUS20050226214 *Apr 8, 2004Oct 13, 2005Isaac KeslassyScheduling with delayed graphs for communication networksUS20050251373 *Oct 31, 2002Nov 10, 2005Walter DaemsPosynomial modeling, sizing, optimization and control of physical and non-physical systemsWO1996034353A1 *Apr 18, 1996Oct 31, 1996Cadence Design Systems, Inc.Method for reducing power consumption of switching nodes in a circuit* Cited by examinerClassifications U.S. Classification716/113, 716/133International ClassificationH03K19/0185, H01L21/82, G06F17/50Cooperative ClassificationG06F2217/78, G06F17/505European ClassificationG06F17/50D2Legal EventsDateCodeEventDescriptionJun 12, 1991ASAssignmentOwner name: INTERNATIONAL BUSINESS MACHINES CORPORATIONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:DONATH, WILM E.;LUK, WING K.;TANG, DONALD T.;REEL/FRAME:005747/0888;SIGNING DATES FROM 19910513 TO 19910524Jun 19, 1998FPAYFee paymentYear of fee payment: 4Sep 10, 2002REMIMaintenance fee reminder mailedFeb 21, 2003LAPSLapse for failure to pay maintenance feesApr 22, 2003FPExpired due to failure to pay maintenance feeEffective date: 20030221RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services