Detailed placement with search and repair

• US 8,984,464 B1
• Filed: 11/19/2012
• Issued: 03/17/2015
• Est. Priority Date: 11/21/2011
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Teig, Steven, Mihal, Andrew C.
• Primary Examiner(s): Thompson, A. M.
• Application Number:
  US13/681,179
• Time in Patent Office: 848 Days
• Field of Search: None
• US Class Current: 716/122
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/3312 Timing analysis
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking
• 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
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

A method of detailed placement for ICs is provided. The method receives an initial placement and iteratively builds sets of constraints for placement of different groups of cells in the IC design and uses a satisfiability solver to resolve placement violations. In some embodiments, the constraints include mathematical expressions that express timing requirements. The method in some embodiments converts the mathematical expressions into Boolean clauses and sends the clauses to a satisfiability solver that is only capable of solving Boolean clauses. In some embodiments, the method groups several cells in the user design and several sites on the IC fabric and uses the satisfiability solver to resolve all placement issues in the group. The satisfiability solver informs placer after each cell is moved to a different site. The method then dynamically builds more constraints based on the new cell placement and sends the constraints to the satisfiability solver.

Claims

1. A method for placement of a plurality of cells of a user design on an integrated circuit (IC), the method comprising:

sending a first placement of the plurality of cells on a plurality of sites on the IC to a satisfiability solver;

by a computer, building a set of timing constraints for the first placement of the plurality of cells, the first placement violating at least one timing constraint in the set of timing constraints;

sending the first placement and the set of timing constraints to a satisfiability solver; and

receiving a second placement that satisfies the set of timing constraints for the plurality of cells from the satisfiability solver.

2. The method of claim 1, wherein when the satisfiability solver finds a placement that satisfies all timing constraints, the satisfiability solver does not attempt to find a more optimized placement.

3. The method of claim 1, wherein building the set of timing constraints comprises:

identifying a set of source and destination cells;

making a table lookup to determine a path between each corresponding pair of source and destination cells in the set of source and destination cells;

determining a delay for a signal to travel through each determined path from the source cell to the corresponding destination cell; and

building a timing constraint to ensure that a required time of the signal at an input of each destination cell is greater than or equal to an arrival time of the signal at an output of the corresponding source cell plus the determined delay for the signal to travel through the path between the source and destination cells.

4. The method of claim 1, wherein the set of timing constraints is a first set of timing constraints, the method further comprising:

after receiving the placement that satisfies the first set of timing constraints, determining whether a set of user design goals for a set of user design clock domains are satisfied;

increasing a target frequency of at least one user design clock domain when the set of user design goals for the set of user design clock domains are not satisfied;

building a second set of timing constraints based on the increased target frequency;

sending the second set of timing constraints to the satisfiability solver; and

receiving a placement for the plurality of cells from the satisfiability solver that satisfies the second set of timing constraints built based on the increased target frequency.

5. The method of claim 4, wherein increasing the target frequency comprises increasing target frequencies of all user design clock domains in the set of user design clock domains by a same multiplier.

6. The method of claim 4, wherein increasing the target frequency comprises increasing target frequencies of each user design clock domain in the set of user design clock domains independent of the target frequency of other user design clock domains.

7. A method for placement of a plurality of cells of a user design on an integrated circuit (IC), the method comprising:

by a computer, building a plurality of timing constraints for placement of the plurality of cells on a plurality of sites on the IC, wherein building the plurality of timing constraints comprises;

making a table lookup to determine a path between each corresponding pair of source and destination cells in the plurality of cells;

determining a delay for a signal to travel through each determined path from the source cell to the corresponding destination cell; and

building a timing constraint to ensure that a required time of the signal at an input of the destination cell is greater than or equal to an arrival time of the signal at an output of the source cell plus the determined delay for the signal to travel through the path between the source and destination cells;

sending the plurality of timing constraints to a satisfiability solver;

when there is a placement solution that satisfies the plurality of timing constraints, receiving the placement solution as the placement for the plurality of cells; and

when there is no placement solution that satisfies the plurality of timing constraints, receiving an identification of a set of constraints in the plurality of timing constraints that made the plurality of timing constraints unsatisfiable.

8. A non-transitory machine readable medium storing a program for placement of a plurality of cells of a user design on an integrated circuit (IC), the program executable by at least one processing unit, the program comprising:

a set of instructions for building a set of timing constraints for placement of the plurality of cells on a plurality of sites on the IC;

a set of instructions for sending the set of timing constraints to a satisfiability solver;

a set of instructions for receiving a placement that satisfies the set of timing constraints for the plurality of cells from the satisfiability solver wherein the set of timing constraints is a first set of timing constraints;

a set of instructions for determining after receiving the placement that satisfies the first set of timing constraints, whether a set of user design goals for a set of user design clock domains are satisfied;

a set of instructions for increasing a target frequency of at least one user design clock domain when the set of user design goals for the set of user design clock domains are not satisfied;

a set of instructions for building a second set of timing constraints based on the increased target frequency;

a set of instructions for sending the second set of timing constraints to the satisfiability solver; and

a set of instructions for receiving a placement for the plurality of cells from the satisfiability solver that satisfies the second set of timing constraints built based on the increased target frequency.

9. The non-transitory machine readable medium of claim 8, wherein when the satisfiability solver finds a placement that satisfies all timing constraints, the satisfiability solver identifies the placement without attempting to find a more optimized placement.

10. The non-transitory machine readable medium of claim 8, wherein the set of instructions for building the set of timing constraints comprises:

a set of instructions for identifying a path between a set of source and destination cells;

a set of instructions for making a table lookup to determine a path between each corresponding pair of source and destination cells in the set of source and destination cells;

a set of instructions for determining a delay for a signal to travel through each determined path from the source cell to the corresponding destination cell; and

a set of instructions for building a timing constraint to ensure that a required time of the signal at an input of each destination cell is greater than or equal to an arrival time of the signal at an output of the corresponding source cell plus the determined delay for the signal to travel through the path between the source and destination cells.

11. The non-transitory machine readable medium of claim 8, wherein the set of instructions for increasing the target frequency comprises a set of instructions for increasing target frequencies of all user design clock domains by a same multiplier.

12. The non-transitory machine readable medium of claim 8, wherein the set of instructions for increasing the target frequency comprises a set of instructions for increasing target frequencies of each user design clock domain independent of the target frequency of other user design clock domains.

13. A non-transitory computer readable medium storing a program for placement of a plurality of cells of a user design on an integrated circuit (IC), the program executable by at least one processing unit, the program comprising:

a set of instructions for sending a first placement of the plurality of cells on a plurality of sites on the IC to a satisfiability solver;

a set of instructions for building a set of timing constraints for the first placement of the plurality of cells, the first placement violating at least one timing constraint in the set of timing constraints;

a set of instructions for sending the first placement and the set of timing constraints to a satisfiability solver; and

a set of instructions for receiving a second placement that satisfies the set of timing constraints for the plurality of cells from the satisfiability solver.

14. The non-transitory computer readable medium of claim 13, wherein when the satisfiability solver finds a placement that satisfies all timing constraints, the satisfiability solver does not attempt to find a more optimized placement.

15. The non-transitory computer readable medium of claim 13, wherein the set of instructions for building the set of timing constraints comprises:

a set of instructions for identifying a set of source and destination cells;

a set of instructions for making a table lookup to determine a path between each corresponding pair of source and destination cells in the set of source and destination cells;

a set of instructions for determining a delay for a signal to travel through each determined path from the source cell to the corresponding destination cell; and

a set of instructions for building a timing constraint to ensure that a required time of the signal at an input of each destination cell is greater than or equal to an arrival time of the signal at an output of the corresponding source cell plus the determined delay for the signal to travel through the path between the source and destination cells.

16. The non-transitory computer readable medium of claim 13, wherein the set of timing constraints is a first set of timing constraints, the program further comprising:

a set of instructions for determining, after receiving the placement that satisfies the first set of timing constraints, whether a set of user design goals for a set of user design clock domains are satisfied;

a set of instructions for increasing a target frequency of at least one user design clock domain when the set of user design goals for the set of user design clock domains are not satisfied;

a set of instructions for building a second set of timing constraints based on the increased target frequency;

a set of instructions for sending the second set of timing constraints to the satisfiability solver; and

a set of instructions for receiving a placement for the plurality of cells from the satisfiability solver that satisfies the second set of timing constraints built based on the increased target frequency.

17. The non-transitory computer readable medium of claim 16, wherein the set of instructions for increasing target frequency comprises a set of instructions for increasing target frequencies of all user design clock domains in the set of user design clock domains by a same multiplier.

18. The non-transitory computer readable medium of claim 16, wherein the set of instructions for increasing the target frequency comprises a set of instructions for increasing target frequencies of each user design clock domain in the set of user design clock domains independent of the target frequency of other user design clock domains.