Patent US5854752A successfully refreshed from Google Patents.
US5854752A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Circuit partitioning technique for use with multiplexed inter-connections
Assignee: Mentor Graphics Corp
•
Filing: 1996-01-19
•
Granted: 1998-12-29
•
Expires: 2016-01-19
Abstract
Abstract A method for partitioning a logic circuit is provided for emulation under a virtual wires method using programmable logic devices. Because a virtual wires systems replace pin constraints by a corresponding gate constraint, partitioning for a virtual wires system applies novel constraints and algorithms. In one embodiment, partitioning is provided under a "flat mincut" approach in conjunction with a virtual wire cost constraint. In another embodiment, partitioning is provided under a "hierarchical mincut" in conjunction with a virtual wire cost constraint.
Inventors
- 👤 Anant Agarwal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 07:10
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/34; G06F30/347; G06F30/32; G06F30/33; G06F30/3308; G06F30/331; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
175 words
A method for emulating a logic circuit in a plurality of programmable logic devices, comprising the steps of: partitioning a representation of said logic circuit into a plurality of logic blocks, in accordance with a single cost constraint, said cost constraint including functions of the number of logic gates and the number of pins of each logic, each logic block having a plurality of logic gates and a plurality of pins for connecting said logic block with other logic blocks in said plurality of logic blocks; and assigning each of said logic blocks to be implemented on one of said programmable logic device; wherein said cost constraint is given by: ƒ(G.sub.i,cP.sub.i)≦G.sub.max where ƒ is a function of the quantities G i and cP i , G i being the number of logic gates in said logic block G max being said predetermined number of logic gates, c being a weighting factor expressing a cost of a pin in terms of a logic gate, and P i being the number of pins in said logic block.
Claim 2
Independent Claim
175 words
A method for emulating a logic circuit in a plurality of programmable logic devices, comprising the steps of: partitioning a representation of said logic circuit into a plurality of logic blocks, in accordance with a single cost constraint, said cost constraint including functions of the number of logic gates and the number of pins of each logic, each logic block having a plurality of logic gates and a plurality of pins for connecting said logic block with other logic blocks in said plurality of logic blocks; and assigning each of said logic blocks to be implemented on one of said programmable logic device; wherein said cost constraint is given by: ƒ(G.sub.i,cP.sub.i)≦G.sub.max where ƒ is a function of the quantities G i and cP i , G i being the number of logic gates in said logic block G max being said predetermined number of logic gates, c being a weighting factor expressing a cost of a pin in terms of a logic gate, and P i being the number of pins in said logic block.
Claim 3
Dependent Claim
49 words
A method as in claim 1, wherein said cost constraint compares a cost function against a predetermined number of logic gates, said cost function being, for each block, a function of the number of logic gates in said logic block and the number of pins in said logic block.
Claim 4
Dependent Claim
17 words
A method as in claim 1, wherein said cost constraint is given by: G.sub.i +cP.sub.i ≦G.sub.max. 4.
Claim 5
Dependent Claim
41 words
A method as in claim 1, wherein said pins in said logic block include both input pins and output pins, and wherein said cost function assigns a first cost to each input pin and a second cost to each output pin.
Claim 6
Dependent Claim
32 words
A method as in claim 4, wherein said cost assigned to said output pin is proportional to the number of input pins coupled to said output pin outside of said logic block.
Claim 7
Dependent Claim
39 words
A method as in claim 1, wherein when a pin carries a signal making a plurality of transitions within a reference clock period, said pin contributes a cost to said cost function in proportion to said plurality of transitions.
Claim 8
Dependent Claim
59 words
A method as in claim 1 wherein, prior to said step of partitioning, said method includes the step of preclustering logic elements of said representation into clusters of logic elements, each cluster being formed in accordance with a cluster size constraint on a cluster function, said cluster size constraint being expressed in terms of a number of logic gates.
Claim 9
Dependent Claim
17 words
A method as in claim 7, wherein said cluster function comprises a fraction of said cost function.
Claim 10
Dependent Claim
50 words
A method as in claim 1 wherein, prior to said step of partitioning, said method includes the step of optimizing timing, said step of optimizing timing identifying critical signal paths in said logic circuit and grouping logic elements in said critical path into logic modules having pins of minimized costs.
Claim 11
Dependent Claim
34 words
A method as in claim 1, wherein, for each pin, said cost function associates a cost to said pin in proportion to the number of unique logic blocks to which said pin is connected.
Claim 12
Dependent Claim
27 words
A method as in claim 1, further including the step of restructuring logic elements associated with said pins to minimize fan-out for output pins among said pins.
Claim 13
Dependent Claim
76 words
A method as in claim 1, wherein said cost function is a function of two or more variables associated with the number of logic circuit elements in a logic block, said variables selected from the group of: (a) the number of logic gates in said logic block, (b) the number of flip-flops in said logic block, (c) the number of pins in said logic block, and (d) the number of memory elements in said logic block.
Claim 14
Dependent Claim
19 words
A method as in claim 12, wherein said cost function is expressed in terms of multiples of logic gates.
Claim 15
Dependent Claim
23 words
A method as in claim 12, wherein said cost function associates with each of said memory elements a cost expressed in logic gates.
Claim 16
Dependent Claim
33 words
A method as in claim 12, wherein said cost function associates with each of said memory elements a cost proportional to the number of address and data lines coupled to said memory element.
Claim 17
Dependent Claim
51 words
A method as in claim 12, wherein said cost function associates with each of said memory elements a cost C(A,D) given by: C(A,D)=nA+mD where A and D are the number of address lines and the number of data lines coupled to said memory element, respectively, and n and m are constants.
Claim 18
Dependent Claim
28 words
A method as in claim 1, wherein said cost function assigns a higher cost to pins coupling said logic circuit to a circuit external to said logic circuit.
Claim 19
Dependent Claim
50 words
A method as in claim 1, wherein said logic circuit includes a number of timing domains, each timing domain receiving a different clock signal, said cost function assigning a different cost to pins connecting logic elements of different timing domains than pins connecting logic elements of the same timing domain.
Claim 20
Dependent Claim
20 words
A method as in claim 1, wherein said step of partitioning is performed in accordance with a flat mincut algorithm.
Claim 21
Dependent Claim
20 words
A method as in claim 1, wherein said step of partitioning is performed in accordance with a hierarchical mincut algorithm.
Claim 22
Dependent Claim
41 words
A method as in claim 20, wherein said hierarchical mincut algorithm applies a flat mincut algorithm to a given logic block not satisfying a termination constraint, prior to recursively applying said hierarchical mincut algorithm to portions of said given logic block.
Claim 23
Dependent Claim
13 words
A method as in claim 1 wherein said representation is a netlist representation.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-28 | 2002-06-29 | 2002-12-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-28 | 2006-06-29 | 2006-12-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-28 | 2010-06-29 | 2010-12-29 | $7700.00 | Window Closed / Lapsed |