Method and apparatus for performing incremental compilation on field programmable gate arrays

• US 7,191,426 B1
• Filed: 09/01/2004
• Issued: 03/13/2007
• Est. Priority Date: 09/01/2004
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Brown, Stephen, Chan, Kevin, Singh, Deshanand
• Primary Examiner(s): Kik; Phallaka
• Application Number:
  US10/931,953
• Time in Patent Office: 923 Days
• Field of Search: 716/16, 716/5, 716/18, 716/10, 716/13
• US Class Current: 716/104
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

A method for designing a system on a target device utilizing field programmable gate arrays (FPGAs) includes generating a first design for the system that includes a first netlist describing a first logical design, and placement and routing of the first logical design. A second design for the system is generated that includes a second netlist describing a second logical design. Changes made to the first design in the second design are identified. Placement is performed on the changes made to the first design on the second design.

Claims

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

generating a first design for the system that includes a first netlist describing a first logical design, and placement and routing of the first logical design;

generating a second design for the system that includes a second netlist describing a second logical design;

identifying changes made to the first design in the second design;

performing placement on the changes made to the first design on the second design;

determining whether the placement on the changes made satisfies timing constraints on the second design; and

performing incremental routing in response to determining that the placement satisfies the timing constraints.

2. The method of claim 1, wherein identifying the changes comprises determining whether a first node in the first design is equivalent to a second node in the second design.

3. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes have similar timing constraints.

4. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes have similar placement constraints.

5. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes have a similar number of input connections.

6. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes have a similar number of outputs.

7. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes have matching logic unit table (LUT) masks.

8. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes are surrounded by same neighbors.

9. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes are of matching type.

10. The method of claim 2, wherein determining whether the first node in the first design is equivalent to the second node in the second design comprises determining whether the first and second nodes have a same name.

11. The method of claim 1, wherein performing placement on the changes made to the first design comprises:

placing new logic elements (LEs) at preferred locations;

resolving illegalities in placement of the new LEs.

12. The method of claim 11, wherein resolving illegalities in the placement of the new LEs comprises:

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.

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

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

15. The method of claim 12, 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.

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

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

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

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

20. The method of claim 11, further comprising:

determining whether placement on the identified changes made to the first design satisfies timing constraints; and

performing logic array block and logic element moves if the timing constraints are not satisfied.

21. The method of claim 1, further comprising utilizing placement information of nodes in the first design that have not changed in the second design.

22. The method of claim 1, wherein determining whether the placement on the changes made satisfies timing constraints comprises performing timing analysis on the placement of the system.

23. The method of claim 1, wherein performing incremental routing comprises utilizing routing resources identified for a first node in the first design for an equivalent second node in the second design having equivalent sources and destinations.

24. The method of claim 1, wherein performing incremental routing comprises utilizing routing resources identified for a first node in the first design for an equivalent second node in the second design having equivalent sources and destinations when valid routing can be performed.

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

identifying changes made to a first design in a second design by determining whether a first node in the first design is equivalent to a second node in the second design by comparing timing constraints of the first and second nodes;

performing placement on the changes made to the first design in the second design; and

utilizing placement information from the first design for nodes that have not changed in the second design.

26. The method of claim 25, wherein identifying the changes further comprises comparing placement constraints on the first and second nodes.

27. The method of claim 25, further comprising performing incremental routing in response to determining that the placement satisfies timing constraints of the second design.

28. The method of claim 27, wherein performing incremental routing comprises utilizing routing resources identified for a first node in the first design for an equivalent second node in the second design having equivalent sources and destinations.

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

generating a first design for a system that includes a first netlist describing a first logical design, and placement and routing of the first logical design;

generating a second design for the system that includes a second netlist describing a second logical design;

identifying changes made to the first design in the second design by determining whether a first node in the first design is equivalent to a second node in the second design by determining whether the first and second nodes have matching logic unit table (LUT) masks that are bit strings that represent truth tables for functions; and

performing placement on the changes made to the first design on the second design.

30. The machine-readable medium of claim 29, further including sequences of instructions that when executed by the processor causes to processor to perform utilizing placement information from the first design for nodes that have not changed in the second design.

31. The machine-readable medium of claim 29, further comprising performing incremental routing in response to determining that the placement satisfies timing constraints of the second design.

32. The machine-readable medium of claim 31, wherein performing incremental routing comprises utilizing routing resources identified for a first node in the first design for an equivalent second node in the second design having equivalent sources and destinations.