Placing partitioned circuit designs within iterative implementation flows

• US 7,590,960 B1
• Filed: 04/18/2007
• Issued: 09/15/2009
• Est. Priority Date: 04/18/2007
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Kong, Raymond, Selvakkumaran, Navaratnasothie, Chaudhary, Kamal
• Primary Examiner(s): Do; Thuan
• Assistant Examiner(s): Doan; Nghia M
• Application Number:
  US11/787,925
• Time in Patent Office: 881 Days
• Field of Search: 716 4- 5, 716 7- 12, 716 16- 17
• US Class Current: 716/124
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method of placing circuit elements of a partitioned circuit design on a target programmable logic device (PLD) can include mapping circuit elements of the circuit design to corresponding partitions of the circuit design, selecting a circuit element of the circuit design, and selecting a candidate location within a logic boundary on the target PLD. The method also can include validating the candidate location for the selected circuit element, at least in part, according to whether the selected circuit element belongs to a same partition of the circuit design as at least one other circuit element already placed within the logic boundary. The selected circuit element can be selectively placed at the candidate location according to the validation.

Claims

1. A computer-implemented method of placing circuit elements of a partitioned circuit design on a target programmable logic device (PLD), the method comprising:

executing a program by a computer system to perform functions including;

mapping circuit elements of the circuit design to corresponding partitions of the circuit design;

defining a plurality of logic boundaries on the target PLD, wherein each logic boundary is defined by a plurality of logic cells directly connected to a routing matrix that is programmable to connect the logic cells;

selecting a circuit element of the circuit design;

selecting a candidate location within a logic boundary on the target PLD;

wherein the candidate location is one the logic cells connected the routing matrix of the logic boundary;

validating the candidate location for the selected circuit element, at least in part, according to whether the selected circuit element belongs to a same partition of the circuit design as at least one other circuit element already placed within the logic boundary;

selectively placing the selected circuit element at the candidate location according to the validation;

repeating the steps of selecting a circuit element, selecting a candidate location, validating, and selectively placing for each unplaced circuit element, wherein a placed circuit design is generated once all circuit elements have been placed; and

outputting the placed circuit design.

2. The method of claim 1, wherein validating the candidate location for the selected circuit element comprises determining that no other circuit elements of the circuit design have been placed within the logic boundary, and wherein selectively placing the selected circuit element at the candidate location places the selected circuit element at the candidate location.

3. The method of claim 1, wherein validating the candidate location for the selected circuit element comprises identifying at least one other circuit element of the circuit design previously placed within the logic boundary.

4. The method of claim 3, wherein validating the candidate location for the selected circuit element further comprises comparing the partition of the selected circuit element with a partition of the at least one other circuit element previously placed within the logic boundary.

5. The method of claim 4, wherein selectively placing the selected circuit element at the candidate location further comprises placing the selected circuit component at the candidate location when the partition of the selected circuit element is the same partition to which the at least one other circuit element previously placed within the logic boundary belongs.

6. The method of claim 4, wherein selectively placing the selected circuit element at the candidate location further comprises rejecting the candidate location when the partition of the selected circuit element is not the same partition to which the at least one other circuit element previously placed within the logic boundary belongs.

7. The method of claim 1, wherein validating the candidate location for the selected circuit element comprises determining whether or not the partition of the selected circuit element is the same as a partition of each other circuit element previously placed within the logic boundary, and the selectively placing places the selected circuit element at the candidate location in response to the partition of the selected circuit element being the same as the partition of each other circuit element previously placed within the logic boundary, and the selectively placing does not place the selected circuit element at the candidate location in response to the partition of the selected circuit element being different from the partition of each other circuit element previously placed within the logic boundary.

8. The method of claim 1, further comprising processing further circuit elements and candidate locations to generate a placed circuit design.

9. A computer-implemented method of placing circuit elements of a partitioned circuit design on a target programmable logic device (PLD), the method comprising:

executing a program by a computer system to perform functions including;

defining a plurality of logic boundaries on the target PLD, wherein each logic boundary is defined by a plurality of logic cells directly connected to a routing matrix that is programmable to connect the logic cells;

determining partition membership for circuit elements of the circuit design;

selecting a circuit element of the circuit design and a candidate location within a logic boundary on the target PLD;

wherein the candidate location is one the logic cells connected the routing matrix of the logic boundary;

determining whether the logic boundary comprises at least one previously placed circuit element belonging to a partition;

generating a placed circuit design by placing the circuit element at the candidate location when,

a partition to which the selected circuit element belongs is the same partition to which the at least one previously placed circuit element belongs, or

the logic boundary comprises no previously placed circuit elements; and

outputting the placed circuit design.

10. The method of claim 9, further comprising, when the logic boundary comprises at least one previously placed circuit element, comparing the partition of the at least one previously placed circuit element with the partition of the selected circuit element.

11. The method of claim 9, further comprising, when the logic boundary comprises at least one previously placed circuit element belonging to a partition that is not the same as the partition of the selected circuit element, rejecting the candidate location and selecting a different candidate location.

12. A computer program product, comprising:

a computer-usable storage device having computer-usable program code that generates a placed version of a circuit design having partitions for a target programmable logic device (PLD), the program code when executed by a processor causing the processor to perform the operations including;

mapping circuit elements of the circuit design to corresponding partitions of the circuit design;

defining a plurality of logic boundaries on the target PLD, wherein each logic boundary is defined by a plurality of logic cells directly connected to a routing matrix that is programmable to connect the logic cells;

selecting a circuit element of the circuit design;

selecting a candidate location within a logic boundary on the target PLD;

wherein the candidate location is one the logic cells connected the routing matrix of the logic boundary;

validating the candidate location for the selected circuit element, at least in part, according to whether the selected circuit element belongs to a same partition of the circuit design as at least one other circuit element already placed within the logic boundary;

selectively placing the selected circuit element at the candidate location according to the validation;

repeating the operations of selecting a circuit element, selecting a candidate location, validating, and selectively placing for each unplaced circuit element, wherein a placed circuit design is generated once all circuit elements have been placed; and

outputting the placed circuit design.

13. The computer program product of claim 12, wherein the operation of validating the candidate location for the selected circuit element includes determining that no other circuit elements of the circuit design have been placed within the logic boundary, and wherein the computer-usable program code that selectively places the selected circuit element at the candidate location places the selected circuit element at the candidate location.

14. The computer program product of claim 12, wherein the operation of validating the candidate location for the selected circuit element includes identifying at least one other circuit element of the circuit design previously placed within the logic boundary.

15. The computer program product of claim 14, wherein the operation of validating the candidate location for the selected circuit element includes comparing the partition of the selected circuit element with a partition of the at least one other circuit element previously placed within the logic boundary.

16. The computer program product of claim 15, wherein the the operation of selectively placing the selected circuit element at the candidate location includes placing the selected circuit component at the candidate location when the partition of the selected circuit element is the same partition to which the at least one other circuit element previously placed within the logic boundary belongs.

17. The computer program product of claim 15, wherein the operation of selectively placing the selected circuit element at the candidate location includes rejecting the candidate location when the partition of the selected circuit element is not the same partition to which the at least one other circuit element previously placed within the logic boundary belongs.

18. The computer program product of claim 12, wherein the program code when executed by the processor further causes the processor to perform the operations of defining a plurality of logic boundaries on the target PLD, wherein each logic boundary is defined by a plurality of logic cells directly connected to a routing matrix.

19. The computer program product of claim 12, wherein the operation of validating the candidate location for the selected circuit element includes determining whether or not the partition of the selected circuit element is the same partition to which each other circuit element previously placed within the logic boundary belongs, and the operation of selectively placing places the selected circuit element at the candidate location, in response to the partition of the selected circuit element being the same as the partition of each other circuit element previously placed within the logic boundary, and the selectively placing does not place the selected circuit element at the candidate location in response to the partition of the selected circuit element being different from the partition of each other circuit element previously placed within the logic boundary.