US6006023A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of optimizing a logic circuit
Assignee: Renesas Electronics Corp
•
Filing: 1996-11-06
•
Granted: 1999-12-21
•
Expires: 2016-11-06
Abstract
Abstract Buffer trees are detected in an inputted logic circuit and sets of driver gates included in the respective buffer trees are made (in Step 102). A set of gates relating to more than one buffer tree, i.e., a group of gates to be optimized, is detected (in Step 103). The groups of gates to be optimized are classified according to the symmetry in logic structure (in Step 104). Each group of gates to be optimized is extracted (in Step 105). The buffer trees are restructured so as to be in a symmetrical relation with each other (In Step 106). Through the above process, the buffer trees are optimized to be in a symmetrical relation of logic structure. Thus, the method of optimizing the logic circuit to ensure reduction in routing area, total length of interconnections and delay of the layout after placement is accomplished.
Inventors
- 👤 Motoki Higashida
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 00:07
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
132 words
A method of optimizing a logic circuit having a plurality of first buffer trees, comprising steps of: (a) detecting a symmetry in logic structure of said logic circuit, said symmetry consisting of said plurality of first buffer trees and a plurality of sub-circuits connected respectively to said plurality of first buffer trees, each of said plurality of sub-circuits being connected to all of said plurality of first buffer trees; and (b) restructuring said plurality of first buffer trees so as to be in a symmetrical relation on the basis of said detected symmetry by exchanging connections of said plurality of sub-circuits to said plurality of first buffer trees to form a plurality of second buffer trees, said plurality of second buffer trees having configuration identical to said plurality of first buffer trees.
Claim 2
Independent Claim
132 words
A method of optimizing a logic circuit having a plurality of first buffer trees, comprising steps of: (a) detecting a symmetry in logic structure of said logic circuit, said symmetry consisting of said plurality of first buffer trees and a plurality of sub-circuits connected respectively to said plurality of first buffer trees, each of said plurality of sub-circuits being connected to all of said plurality of first buffer trees; and (b) restructuring said plurality of first buffer trees so as to be in a symmetrical relation on the basis of said detected symmetry by exchanging connections of said plurality of sub-circuits to said plurality of first buffer trees to form a plurality of second buffer trees, said plurality of second buffer trees having configuration identical to said plurality of first buffer trees.
Claim 3
Dependent Claim
233 words
The method of claim 1, wherein said step (a) includes steps of (a-1) detecting said plurality of first buffer trees in said logic circuit; (a-2) detecting a plurality of parent gates driven based on said plurality of first buffer trees; (a-3) detecting a plurality of groups of gates which exist on passes from said plurality of parent gates to a plurality of first roots of said plurality of first buffer trees, wherein each one of said plurality of groups includes at least one gate other than a driver gate of one of said plurality of first buffer trees; and (a-4) detecting said symmetry of logic structure, wherein said symmetry of logic structure consists of a plurality of graphs, said plurality of graphs including at least one of said plurality of groups, said at least one of said plurality of groups consisting of a plurality of gates, each one of said plurality of gates having identical features with each other one of said plurality of gates, and said step (b) includes a step of (b-1) exchanging driver gates between at least two of said plurality of graphs so that driver gates of said at least two of said plurality of graphs and driver gates of graphs other than said at least two of said plurality of graphs become identical, to exchange said plurality of first buffer trees for said plurality of second buffer trees.
Claim 4
Dependent Claim
24 words
The method of claim 1, further comprising a step of: obtaining a same delay in said logic circuit before and after said step (b).
Claim 5
Dependent Claim
27 words
The method of claim 2, wherein only said driver gates on the same stage from said roots of said buffer trees are exchanged in said step (b-1).
Claim 6
Dependent Claim
52 words
The method of claim 2, wherein only driver gates on a same stage from said plurality of first roots of said plurality of first buffer trees and a plurality of second roots of said plurality of second buffer trees and having an equal number of fanouts are exchanged in said step (b-1).
Claim 7
Dependent Claim
33 words
The method of claim 2, wherein said plurality of gates having identical features with each other one of said plurality of gates in said step (a-4) include a gate having a logical symmetry.
Claim 8
Dependent Claim
32 words
The method of claim 6, wherein said gate having said logical symmetry has a plurality of inputs and logic of said gate remains unchanged by exchanging connections of said plurality of inputs.
Claim 9
Dependent Claim
38 words
The method of claim 7, further comprising a step of: developing a compound logic gate into at least one of said gate having said logical symmetry if said compound logic gate is included in said plurality of groups.
Claim 10
Dependent Claim
23 words
The method of claim 2, wherein said step (b) further includes a step of placing said plurality of groups in a predetermined order.
Claim 11
Dependent Claim
41 words
The method of claim 2, which is incorporated in a logic synthesis tool which receives a logic description and synthesizes said logic circuit in correspondence with said logic description, so as to use a circuit information in said logic synthesis tool.
Claim 12
Independent Claim
149 words
A method of optimizing a logic circuit having a plurality of first buffer trees, comprising the steps of: (a) creating said logic circuit having said plurality of first buffer trees; (b) detecting a symmetry in logic structure of said logic circuit created in step (a), said symmetry consisting of said plurality of first buffer trees and a plurality of sub-circuits connected respectively to said plurality of first buffer trees, each of said plurality of sub-circuits being connected to all of said plurality of first buffer trees; and (c) restructuring said plurality of first buffer trees so as to be in a symmetrical relation on the basis of said detected symmetry by exchanging connections of said plurality of sub-circuits to said plurality of first buffer trees to form a plurality of second buffer trees, said plurality of second buffer trees having configuration identical to said plurality of first buffer trees.
Claim 13
Independent Claim
149 words
A method of optimizing a logic circuit having a plurality of first buffer trees, comprising the steps of: (a) creating said logic circuit having said plurality of first buffer trees; (b) detecting a symmetry in logic structure of said logic circuit created in step (a), said symmetry consisting of said plurality of first buffer trees and a plurality of sub-circuits connected respectively to said plurality of first buffer trees, each of said plurality of sub-circuits being connected to all of said plurality of first buffer trees; and (c) restructuring said plurality of first buffer trees so as to be in a symmetrical relation on the basis of said detected symmetry by exchanging connections of said plurality of sub-circuits to said plurality of first buffer trees to form a plurality of second buffer trees, said plurality of second buffer trees having configuration identical to said plurality of first buffer trees.
Claim 14
Dependent Claim
143 words
The method of claim 11, wherein said step (b) includes steps of (b-1) detecting said plurality of first buffer trees in said logic circuit; (b-2) detecting a parent gate driven directly or passing through other gates by a plurality of driver gates included in said plurality of first buffer trees; (b-3) detecting a sub-circuit consisting of at least one gate which exists on passes from said plurality of driver gates in said plurality of first buffer trees detected in said step (b-1) to said parent gate detected in said step (b-2); and (b-4) detecting a symmetry of logic structure of a plurality of said sub-circuit detected in said step (b-3), and said step (c) includes a step of (c-1) exchanging a first group of said plurality of driver gates in said plurality of said sub-circuit having said symmetry detected in said step (b-4).
Claim 15
Dependent Claim
24 words
The method of claim 11, further comprising a step of: obtaining a same delay in said logic circuit before and after said step (c).
Claim 16
Dependent Claim
29 words
The method according to claim 12, wherein only driver gates on the same stage from roots of said plurality of first buffer trees are exchanged in said step (c-1).
Claim 17
Dependent Claim
28 words
The method of claim 11, wherein said step (b) further comprises detecting a symmetry in logic structure of said logic circuit using at least one logic structure graph.
Claim 18
Dependent Claim
35 words
The method of claim 12, wherein only driver gates on the same stage from roots of said plurality of first buffer trees and having an equal number of fanouts are exchanged in said step (c-1).
Claim 19
Dependent Claim
25 words
The method according to claim 12, wherein said step (c) further includes a step of placing said plurality of said sub-circuit in a predetermined order.
Claim 20
Dependent Claim
42 words
The method according to claim 12, which is incorporated in a logic synthesis tool which receives a logic description and synthesizes said logic circuit in correspondence with said logic description, so as to use a circuit information in said logic synthesis tool.
References Cited (Backward Citations)
JPH0324763A
Cited
JPH05152438A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-20 | 2003-06-21 | 2003-12-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-20 | 2007-06-21 | 2007-12-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-20 | 2011-06-21 | 2011-12-21 | $7700.00 | Window Closed / Lapsed |