Method and apparatus for performing incremental placement for layout-driven optimizations on field programmable gate arrays

• US 7,318,210 B1
• Filed: 08/16/2006
• Issued: 01/08/2008
• Est. Priority Date: 07/11/2003
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Singh, Deshanand P., Brown, Stephen D.
• Primary Examiner(s): Garbowski; Leigh M.
• Application Number:
  US11/505,038
• Time in Patent Office: 510 Days
• Field of Search: None
• US Class Current: 716/121
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• 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 for designing a system on a target device utilizing field programmable gate arrays (FPGAs) includes placing new logic elements (LEs) at preferred locations on a layout of an existing system. Illegalities in placement of the new LEs are resolved.

Claims

1. A method for designing a system on a target device utilizing field programmable gate arrays (FPGAs), comprising:

placing new logic elements (LEs) at preferred locations on a layout of an existing system; and

resolving illegalities in placement of the new LEs by generating a proposed move for an LE, generating cost function values for a current placement and a placement with the proposed move, and accepting the proposed move if its associated cost function value is better than the cost function value of the current placement.

2. A method for designing a system on a target device utilizing field programmable gate arrays (FPGAs), comprising:

placing new logic elements (LEs) at preferred locations on a layout of an existing system; and

resolving illegalities in placement of the new LEs by generating proposed moves for an LE,

generating cost function values for a current placement and placements with the proposed moves, and

accepting a proposed move if its associated cost function value is better than the cost function value for the current placement.

3. The method of claim 2, wherein generating the proposed moves comprises moving the LE to a logic-array block (LAB) that is a fanin of the LE.

4. The method of claim 2, wherein generating the proposed moves comprises moving the LE to a logic-array block (LAB) that is a fanout of the LE.

5. The method of claim 2, wherein generating the proposed moves comprises moving the LE to a logic-array block (LAB) that is a sibling of a LAB where the LE resides.

6. The method of claim 2, wherein generating the proposed moves comprises moving the LE to a logic-array block (LAB) that is adjacent to the LE.

7. The method of claim 2, wherein generating the proposed moves comprises moving the LE to any random free LE.

8. The method of claim 2, wherein generating the proposed moves comprises moving the LE in a direction of a critical vector.

9. The method of claim 2, wherein generating the cost function values comprises computing values using cluster legality as a parameter.

10. The method of claim 9, wherein the cluster legality is a function of a number of legal LEs in a LAB.

11. The method of claim 9, wherein the cluster legality is a function of a number of legal inputs in a LAB.

12. The method of claim 9, wherein the cluster legality is a function of a number of legal outputs in a LAB.

13. The method of claim 2, wherein generating the cost function values comprises computing values using timing cost as a parameter.

14. The method of claim 2, wherein generating the cost function values comprises computing values using wire length cost as a parameter.

15. The method of claim 2, further comprising modifying a cost function.

16. The method of claim 15, wherein modifying the cost function comprises increasing a penalty on a reoccurring illegality.

17. A method for designing a system on field programmable gate array (FPGAs), comprising:

determining placement of logic elements (LEs) for an existing system;

modifying a design for the existing system to improve performance by estimating routing delays for the existing system, and adding LEs to the existing system to reduce the routing delays;

placing new LEs from a modified design on the placement of LEs for the existing system; and

resolving illegalities in placement of the new LEs.

18. A method for designing a system on field programmable gate array (FPGAs), comprising:

determining placement of logic elements (LEs) for an existing system;

modifying a design for the existing system to improve performance;

placing new LEs from a modified design on the placement of LEs for the existing system; and

resolving illegalities in placement of the new LEs by generating proposed moves for an LE,

generating cost function values for a current placement and placements with the proposed moves, and

accepting a proposed move if its associated cost function value is better than a cost function value for the current placement.

19. The method of claim 18, wherein generating the cost function values comprises computing values using cluster legality as a parameter.

20. The method of claim 18, wherein generating the cost function values comprises computing values using timing cost as a parameter.

21. The method of claim 18, wherein generating the cost function values comprises computing values using wire length cost as a parameter.

22. The method of claim 18, further comprising modifying a cost function.

23. The method of claim 22, wherein modifying the cost function comprises increasing a penalty on a reoccurring illegality.

24. A machine-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions which, when executed by a processor, causes the processor to perform:

placing new logic elements (LEs) at preferred locations on a layout of an existing system; and

resolving illegalities in placement of the new LEs by generating proposed moves for an LE,

generating cost function values for a current placement and placements with the proposed moves, and

accepting a proposed move if its associated cost function value is better than the cost function value for the current placement.

25. The machine-readable medium of claim 24, wherein generating the cost function values comprises computing values using cluster legality as a parameter.

26. The machine-readable medium of claim 24, further comprising instructions, which when executed, causes the processor to further perform modifying a cost function by increasing a penalty on a reoccurring illegality.