Logic placement using positionally asymmetrical partitioning method

• US 5,513,124 A
• Filed: 03/12/1993
• Issued: 04/30/1996
• Est. Priority Date: 10/30/1991
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Chene, Mon-Ren, Trimberger, Stephen M.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US08/030,517
• Time in Patent Office: 1,145 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/116
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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.

Claims

1. 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.

2. A partitioning method as in claim 1 in which said programable integrated circuit device is field programmable.

3. A partitioning method as in claim 1 in which said programmable integrated circuit device is mask programmable.

4. 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.

5. 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.

6. 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.

7. 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.

8. A partitioning method as claim 6 in which said programmable integrated circuit device is field programmable.

9. A partitioning method as in claim 6 in which said programmable circuit device is mask programmable.

10. 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.