US5513124A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Logic placement using positionally asymmetrical partitioning method
Assignee: Xilinx Inc
•
Filing: 1993-03-12
•
Granted: 1996-04-30
•
Expires: 2013-03-12
Abstract
Abstract A modified partitioning method for placement of a circuit design into a programmable integrated circuit device having a specific distribution of physical resources along a horizontal or vertical line in the device. The circuit design includes a plurality of circuit elements, for example three-state buffers which feed a common bus, or registers which receive a common clock signal. Such elements should or must be placed along a single horizontal or vertical line. One method includes the step of weighting connecting lines (nets) which join circuit elements to be placed along a common line with different weights for the horizontal and vertical directions. Alternatively, elements to be placed along the line are marked to be kept in line during partitioning. A min-cut algorithm then tends to or is required to avoid separating particular elements from a common line. The group containing the circuit elements with the line requirement is then partitioned such that the area and location of the group corresponds to the horizontal or vertical line.
Inventors
- 👤 Stephen M. Trimberger
- 👤 Mon-Ren Chene
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 08:40
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
156 words
A partitioning method for placing a circuit design into a programmable integrated circuit device having a distribution of physical resources along a horizontal or vertical line, the circuit design comprising a plurality of circuit elements, some of which are to be distributed to said physical resources along a horizontal or vertical line, the method comprising: identifying specific circuit elements of the plurality of circuit elements to be placed along a horizontal or vertical line; attaching weights to lines connected to said circuit elements identified as elements to be placed along a horizontal or vertical line, said weights related to the disadvantage of placing said elements on opposite sides of a cut line parallel to said horizontal or vertical line; and partitioning the plurality of circuit elements according to a min-cut procedure such that a cost of crossing said cut line is determined using those of said weights which are attached to lines crossing said cut line.
Claim 2
Dependent Claim
156 words
A partitioning method for placing a circuit design into a programmable integrated circuit device having a distribution of physical resources along a horizontal or vertical line, the circuit design comprising a plurality of circuit elements, some of which are to be distributed to said physical resources along a horizontal or vertical line, the method comprising: identifying specific circuit elements of the plurality of circuit elements to be placed along a horizontal or vertical line; attaching weights to lines connected to said circuit elements identified as elements to be placed along a horizontal or vertical line, said weights related to the disadvantage of placing said elements on opposite sides of a cut line parallel to said horizontal or vertical line; and partitioning the plurality of circuit elements according to a min-cut procedure such that a cost of crossing said cut line is determined using those of said weights which are attached to lines crossing said cut line.
Claim 3
Dependent Claim
17 words
A partitioning method as in claim 1 in which said programable integrated circuit device is field programmable.
Claim 4
Dependent Claim
17 words
A partitioning method as in claim 1 in which said programmable integrated circuit device is mask programmable.
Claim 5
Dependent Claim
45 words
A partitioning method as in claim 3 in which said programmable integrated circuit device is formed from at least two metal layers, one of which is manufactured before said partitioning method is used, and one of which is manufactured after said partitioning method is used.
Claim 6
Dependent Claim
141 words
A partitioning method for placing a circuit design into a programmable integrated circuit device having a distribution of physical resources along a horizontal line, the circuit design comprising a plurality of circuit elements, some of which are to be distributed to said physical resources along a horizontal line, the method comprising: identifying specific circuit elements of the plurality of circuit elements to be placed along a horizontal line; attaching constraints to lines connected to said circuit elements identified as elements to be placed along a horizontal line, said constraints identifying elements to be moved if the horizontal line is moved; and partitioning the plurality of circuit elements according to a min-cut procedure such that when a member of a marked group is moved across a horizontal cut line, other members of the group are also moved across the horizontal cut line.
Claim 7
Dependent Claim
141 words
A partitioning method for placing a circuit design into a programmable integrated circuit device having a distribution of physical resources along a horizontal line, the circuit design comprising a plurality of circuit elements, some of which are to be distributed to said physical resources along a horizontal line, the method comprising: identifying specific circuit elements of the plurality of circuit elements to be placed along a horizontal line; attaching constraints to lines connected to said circuit elements identified as elements to be placed along a horizontal line, said constraints identifying elements to be moved if the horizontal line is moved; and partitioning the plurality of circuit elements according to a min-cut procedure such that when a member of a marked group is moved across a horizontal cut line, other members of the group are also moved across the horizontal cut line.
Claim 8
Dependent Claim
203 words
A partitioning method for placing a circuit design into a programmable integrated circuit device having a plurality of types of physical resources distributed along horizontal or vertical lines, the circuit design comprising a plurality of circuit elements, the method comprising the following steps: identifying and assigning to single cells those elements of said plurality of circuit elements associated with one of said plurality of types of physical resources; partitioning said circuit design during a first phase until all of said single cells are in their own groups and all of said circuit elements which are not part of said single cells are in their own groups; decomposing said single cells into source circuit elements from which they were composed and marking said source circuit elements to indicate a type of said plurality of types of physical resources with which they are associated; adjusting X ranges and Y ranges of said source circuit elements to reflect alignments of said types of physical resources with which said source circuit elements are associated; and partitioning said circuit design during a second phase, wherein partitioning of said source circuit elements is restricted according to said alignments of said types of physical resources with which they are associated.
Claim 9
Dependent Claim
203 words
A partitioning method for placing a circuit design into a programmable integrated circuit device having a plurality of types of physical resources distributed along horizontal or vertical lines, the circuit design comprising a plurality of circuit elements, the method comprising the following steps: identifying and assigning to single cells those elements of said plurality of circuit elements associated with one of said plurality of types of physical resources; partitioning said circuit design during a first phase until all of said single cells are in their own groups and all of said circuit elements which are not part of said single cells are in their own groups; decomposing said single cells into source circuit elements from which they were composed and marking said source circuit elements to indicate a type of said plurality of types of physical resources with which they are associated; adjusting X ranges and Y ranges of said source circuit elements to reflect alignments of said types of physical resources with which said source circuit elements are associated; and partitioning said circuit design during a second phase, wherein partitioning of said source circuit elements is restricted according to said alignments of said types of physical resources with which they are associated.
Claim 10
Dependent Claim
40 words
A partitioning method as in claim 6 wherein said step of identifying and assigning includes assigning to said single cells those elements of said plurality of circuit elements not associated with one of said plurality of types of physical resources.
Claim 11
Dependent Claim
16 words
A partitioning method as claim 6 in which said programmable integrated circuit device is field programmable.
Claim 12
Dependent Claim
16 words
A partitioning method as in claim 6 in which said programmable circuit device is mask programmable.
Claim 13
Dependent Claim
45 words
A partitioning method as in claim 9 in which said programmable integrated circuit device is formed from at least two metal layers, one of which is manufactured before said partitioning method is used, and one of which is manufactured after said partitioning method is used.
References Cited (Backward Citations)
US3617714A
Cited
US4870302A
Cited
US4706216A
Cited
US4890238A
Cited
US4908772A
Cited
US4967367A
Cited
US5189628A
Cited
US5341308A
Cited
US5224056A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-30 | 1999-10-30 | 2000-04-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-30 | 2003-10-30 | 2004-04-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-30 | 2007-10-30 | 2008-04-30 | $7700.00 | Window Closed / Lapsed |