Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1999-07-02
2003-04-29
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S013000, C703S022000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C702S119000, C705S007380, C705S002000, C705S014270, C705S037000
Reexamination Certificate
active
06556962
ABSTRACT:
FIELD
This invention relates generally to domino circuits, and more particularly to reducing network costs for domino circuits.
BACKGROUND
The speeds at which electronic circuits are required to perform is constantly increasing. As the overall processor speed becomes faster, the need for faster internal circuitry has increased. The need for high speed circuits is not limited to processors, but applies everywhere from cellular phones to digital broadcast receiver systems. Many hand held devices use application specific integrated circuits (ASICs) and they must approach microprocessor frequency targets but have an even tighter area budget. A way to increase the speed of a circuit is to use domino circuits (dynamic logic circuits) instead of static CMOS circuits. A domino circuit includes one or more domino gates. A typical domino gate has a precharge transistor, an evaluate transistor, and an inverting buffer. Domino circuits are generally faster than circuits implemented in CMOS static circuits. For example, domino circuits typically account for thirty percent of the logic transistors of a microprocessor.
Domino circuits have a number of network costs which designers desire to reduce. Some of these costs are power consumption and area.
The use of domino circuits in high-performance microprocessor design is an efficient way of meeting demanding circuit speeds without exorbitant area penalty and high clock-loading implied by static CMOS implementations. One kind of Domino logic style allows a single clock to precharge and evaluate a cascade of dynamic logic blocks where a static CMOS inverting buffer or latch appears at the output of each dynamic logic gate. Despite various area and speed advantages, the safest and the fastest domino design styles can only implement logic networks without invertors because of the inherent monotonic nature of domino circuits. However, this fundamental constraint of implementing logic functions without any intermediate inversions implies significant area overhead from logic duplication for generating both the negative and positive signal phases—the so-called “dual-rail” implementations.
CMOS static logic is synthesized using the flexibility of manipulating inverters in the logic network. The inverter-free constraint in domino logic design limits this flexibility since it may require logic duplication because of the inverter-free constraint. This constraint implies that all logic inversions should be performed at the primary inputs or primary outputs where the inverters can be absorbed in registers.
Currently, a way to convert a logic circuit into an inverter free domino logic circuit is to convert the logic circuit into AND, OR, and NOT gates only. Then, the inverters can be propagated back from the primary outputs towards the inputs by applying simple De Morgan's laws. Some inverters may not be capable of being propagated all the way to a primary input and will be trapped. Since these inverters cannot be removed, the gate at which the inverter is trapped requires duplication to be implemented. This duplication generally causes substantial area, power consumption, timing, and reliability penalties.
There are some ways to reduce this duplication penalty. Considering a combinational logic function, the process of propagating an inverter forward is similar to choosing an implementation phase or polarity of the outputs that eliminates this inverter. This process can be very complex with exponential possibilities. Moreover, some inverters may need to be propagated back and some invertors get trapped and can only be removed by fanin cone duplication alluded to above. Since there are
2
n
possible phase assignments for implementing n primary outputs, it is difficult to find an ideal output phase assignment to minimize area or other network costs, a matter further complicated by design constraints related to the availability of only some input polarities and the need for particular polarities at specific primary outputs, etc. Arbitrarily choosing phase assignments can result in substantial network costs and synthesis quality.
If the various network costs associated with domino circuits could be reduced, processors and ASICs could be produced that are faster and cheaper. Any use of domino circuits could be improved. What is needed is a way to reduce the network costs associated with domino logic.
SUMMARY
One embodiment of the present invention provides a method for reducing a network cost of a domino circuit. The domino circuit is represented as a mixed integer linear program. The mixed integer linear program is solved to determine an implementation that includes determining a final phase assignment that reduces the network cost.
Other embodiments are described and claimed.
REFERENCES:
patent: 4697109 (1987-09-01), Honma et al.
patent: 5331568 (1994-07-01), Pixley
patent: 5453708 (1995-09-01), Gupta et al.
patent: 5502646 (1996-03-01), Chakradhar et al.
patent: 5543735 (1996-08-01), Lo
patent: 5568062 (1996-10-01), Kaplinsky
patent: 5602753 (1997-02-01), Fukui
patent: 5657256 (1997-08-01), Swanson et al.
patent: 5661675 (1997-08-01), Chin et al.
patent: 5668732 (1997-09-01), Khouja et al.
patent: 5671151 (1997-09-01), Williams
patent: 5731983 (1998-03-01), Balakrishnan et al.
patent: 5748012 (1998-05-01), Beakes et al.
patent: 5796282 (1998-08-01), Sprague et al.
patent: 5815005 (1998-09-01), Bosshart
patent: 5825208 (1998-10-01), Levy et al.
patent: 5831990 (1998-11-01), Queen et al.
patent: 5847966 (1998-12-01), Uchino et al.
patent: 5886540 (1999-03-01), Perez
patent: 5892372 (1999-04-01), Ciraula et al.
patent: 5896046 (1999-04-01), Bjorksten et al.
patent: 5896399 (1999-04-01), Lattimore et al.
patent: 5986399 (1999-04-01), Lattimore et al.
patent: 5942917 (1999-08-01), Chappell et al.
patent: 6002272 (1999-12-01), Somasekhar et al.
patent: 6002292 (1999-12-01), Allen et al.
patent: 6049231 (2000-04-01), Bosshart
patent: 6052008 (2000-04-01), Chu et al.
patent: 6060910 (2000-05-01), Inui
patent: 6086619 (2000-07-01), Hausman et al.
patent: 6087855 (2000-07-01), Frederick, Jr. et al.
patent: 6090153 (2000-07-01), Chen et al.
patent: 6104212 (2000-08-01), Curran
patent: 6108805 (2000-08-01), Rajsuman
patent: 6132969 (2000-10-01), Stouhton et al.
patent: 6133759 (2000-10-01), Beck et al.
patent: 6204696 (2001-03-01), Krishnamurthy et al.
patent: 2001/0014875 (2001-08-01), Young et al.
patent: 0954101 (1999-03-01), None
patent: 59-039124 (1984-03-01), None
patent: 04-239221 (1992-08-01), None
Puri et al., “Logic optimization by output phase assignment in dynamic logic synthesis”, IEEE/ACM International Conference on Computer-Aided design, 1996.*
Xun Liu et al., “Minimizing sensitivity to delay vatriations in high performance synchronous circuits”, Design, Automation and Test in Europe Confrerence, Mar. 1999.*
Bryant, R.E., “Graph-Based Algorithms for Boolean Function Manipulation”,IEEE Transactions on Computers, C-35(8), 677-691 (1986).
Chakradhar, S.T., et al., “An Exact Algorithm for Selecting Partial Scan Flip-Flops”,Proceedings, 31st Design Automation Conference, San Diego, California, 81-86 (1994).
Chakravarty, S., “On the Complexity of Using BDDs for the Synthesis and Analysis of Boolean Circuits”,27th Annual Allerton Conference on Communication, Control, and Computing, Allerton House, Monticello, Illinois., 730-739 (1989).
Patra, P., et al., “Automated Phase Assignment for the Synthesis of Low Power Domino Circuits”,Proceedings of the 36th ACM/IEEE Conference on Design Automation Conference, 379-384 (1999).
Puri, et al., “Logic Optimization by Output Phase Assignment in Dynamic Logic Synthesis”,International Conference on Computer Aided Design, (1996).
Thompson, S., et al., “Dual Threshold Voltages and Substrate Bias: Keys to High Performance, Low Power, 0.1 um Logic Designs”,1997 Symposium on VLSI Technology Digest of Technical Papers, 69-70 (1997).
Broda Samuel
Intel Corporation
Schwegman Lundberg Woessner & Kluth P.A.
Thangavelu K
LandOfFree
Method for reducing network costs and its application to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for reducing network costs and its application to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for reducing network costs and its application to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3096083