Frequency driven layout and method for field programmable gate arrays

• US 5,659,484 A
• Filed: 05/04/1995
• Issued: 08/19/1997
• Est. Priority Date: 03/29/1993
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Manaker, Walter A. Jr., Stern, Carl M., Troxel, William R., Bennett, David Wayne, Dellinger, Eric Ford, Young, Jay Thomas
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/434,794
• Time in Patent Office: 838 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 340/825.83, 340/825.86, 340/825.87, 326/38, 326/39, 326/41, 326/47, 326/101
• US Class Current: 716/113
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/3312 Timing analysis
• 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/343 Logical level
• 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

Abstract

A device independent, frequency driven layout system and method for field programmable gate arrays ("FPGA") which allow for a circuit designer to specify the desired operating frequencies of clock signals in a given design to the automatic layout system to generate, if possible, a physical FPGA layout which will allow the targeted FPGA device to operate at the specified frequencies. Actual net, path and skew requirements are automatically generated and fed to the place and route tools. The system and method of the present invention evaluates the frequency constraints, determines what delay ranges are acceptable for each electrical connection and targets those ranges throughout the layout.

Claims

1. A layout process for constructing an electronic circuit from a programmable logic device, said device including a plurality of programmable logic cells having programmable connections therebetween, said process comprising the steps of:

mapping said circuit into logical elements capable of implementation by said programmable logic cells wherein said circuit contains a plurality of paths each comprising a plurality of connections;

receiving timing preferences for said device;

storing said timing preferences in a timing preferences file;

assigning a maximum delay for each of said plurality of paths based upon said timing preferences;

generating a calculated delay for each of a plurality of predetermined connections of said plurality of connections;

generating a predicted delay for each of a plurality of proposed connections of said plurality of connections;

summing said calculated delays for said predetermined connections and said predicted delays for said proposed connections to determine a delay of each of said plurality of paths;

determining an amount by which the delay of each of said plurality of paths exceeds its maximum delay;

routing said plurality of proposed connections to produce transformed paths;

determining an amount by which each of said transformed paths exceeds its maximum delay; and

comparing amounts by which said plurality of paths exceed their maximum delays with amounts by which said transformed paths exceed their maximum delays to determine whether to use said transformed paths.

2. The layout process of claim 1 further comprising the steps of:

ordering said programmable connections in accordance with connection constraints of each connection; and

routing each connection in order as determined by said ordering step.

3. A system for constructing an electronic circuit from a programmable logic device, said device including a plurality of programmable logic cells having programmable connections therebetween, said system comprising:

means for mapping said circuit into logical elements and combining said logical elements into logical blocks capable of implementation by said programmable logic cells;

means for specifying timing preferences for said device and enumerating a plurality of paths of said circuit, each of said plurality of paths including a plurality of connections;

means for storing said timing preferences in a timing preferences file;

means for generating a calculated delay for each of a plurality of predetermined connections of said plurality of connections;

means for generating a predicted delay for each of a plurality of proposed connections of said plurality of connections;

means for assigning a maximum delay for each of said plurality of connections based upon said timing preferences;

means for determining an amount by which a delay of each of said plurality of connections exceeds its maximum delay;

means for moving one or more of the programmable logic cells to produce one or more transformed paths

means for determining an amount by which a delay of each connection of said transformed paths exceeds its maximum delay; and

means for comparing the amount by which said connection delay of each of said plurality of paths exceeds said maximum delay with the amount by which a connection delay of each of said transformed paths exceeds said maximum delay to determine whether to use said transformed paths.

4. The system of claim 3 further comprising:

means for ordering said programmable connections in accordance with connection constraints of each connection; and

means for routing each connection in order as determined by said means for ordering.

5. A method for laying out an electronic circuit in a programmable logic device including a plurality of programmable logic cells having programmable connections therebetween, said method comprising the steps of:

receiving specifications relating to a specified minimum operating frequency of the circuit;

converting said specifications to timing specifications that include minimum and maximum acceptable connection delays for each path in the circuit;

mapping the circuit into logical elements for implementation by said programmable logic cells;

placing the logical elements of the mapped circuit into specific programmable logic cells within the device;

routing the circuit a first time via said programmable connections to achieve a first routing;

calculating a first overall score for said first routing indicative of an extent to which the circuit is completely routed in said first routing and of an extent to which said first routing meets said specifications;

routing the circuit a second time via said programmable interconnects to achieve a second routing;

calculating a second overall score for said second routing indicative of an extent to which the circuit is completely routed in said second routing and of an extent to which said second routing meets said specifications; and

comparing said first and said second overall scores to determine which of said first or said second routings to use.

6. A method as defined in claim 5 wherein said mapping and routing steps are performed in an iterative fashion until connection delays of each path in the circuit are within the range between said minimum and maximum acceptable delays for each connection in the circuit.

7. A method for evaluating a layout of a circuit design on a programmable logic device, comprising the steps of:

receiving a recommended connection delay for each of a plurality of connections of the design;

determining actual delays for connections of the circuit that are routed;

determining estimated delays for connections of the circuit that are not routed; and

producing a timing score for the layout, including;

multiplying an excess factor by a square of a time by which a delay of each connection exceeds an associated recommended connection delay to produce a timing score for each of the plurality of connections; and

combining timing scores for the plurality of connections.

8. A process for constructing an electronic circuit having predetermined operational frequency constraints from a programmable logic device, said circuit including a plurality of logical elements mapped into mapped logic blocks, said logic device including a plurality of programmable logic cells having programmable connections therebetween, said process comprising the steps of:

identifying paths between programmable logic cells of said logic device for implementing said electronic circuit, each of said paths comprising a plurality of said programmable connections;

converting said operational frequency constraints to maximum connection delays;

assigning said mapped logic blocks of said electronic circuit to specific programmable logic cell locations of said logic device;

routing said programmable connections between said specific programmable logic cells;

computing a first completion score representative of the extent to which the circuit is completely routed within the programmable logic device;

computing a first timing score representative of the extent to which the circuit as routed meets the operational frequency constraints;

routing said programmable connections between said specific programmable logic cells again to achieve a next routing, including unrouting and rerouting programmable connections that exceed associated maximum connection delays;

computing a second completion score representative of the extent to which the circuit is completely routed within the programmable logic device in said next routing;

computing a second timing score representative of the extent to which the circuit as routed in said next routing meets the operational frequency constraints;

comparing the first scores with the second scores, to determine whether to use said next routing.

9. The process of claim 8 further comprising the step of:

downloading interconnect programming to said logic device to turn "on" or "off" the programmable connections so that said logic device functions as said electronic circuit.

10. In a system for implementing a design of a circuit in a programmable logic device, a router comprising:

means for receiving timing specifications for the design;

means for using the timing specifications to determine minimum and maximum connection delays for each of a plurality of connections of each of a plurality of paths comprising the design;

means for assigning resource costs to a plurality of different possible routes for individual paths of the design, including costs for using certain resources of the programmable logic device and costs for making turns;

means for producing an initial routing of the design by routing as many of the plurality of connections as possible and minimizing resource costs;

means for determining whether each routed connection of the plurality of connections meets associated minimum and maximum delays; and

means for routing the design again by unrouting and rerouting connections that do not meet associated minimum and maximum delays.

11. The router of claim 10, further comprising:

means for identifying and recording sections of the initial routing that are congested;

means for assigning a cost to routing through one of the congested sections;

means for routing to avoid the congested sections.

12. The router of claim 11, further comprising:

means for routing a connection through one of the congested sections and moving connections occupying the congested section if the connection must go through the congested section to meet its associated minimum and maximum delays.

13. A system for constructing an electronic circuit having predetermined operational frequency constraints from a programmable logic device, said circuit including a plurality of logical elements, said logic device including a plurality of programmable logic cells having programmable connections therebetween, said system comprising:

means for converting said operational frequency constraints to maximum connection delays;

means for identifying a plurality of paths between programmable logic cells, each of said plurality of paths comprising a plurality of programmable connections;

means for mapping said logical elements of said electronic circuit to specific programmable logic cells to form mapped logic cells and assigning locations of mapped logic cells of said logic device;

means for routing each of said plurality of programmable connections;

means for computing a first completion score representative of the extent to which the circuit is completely routed within the programmable logic device;

means for computing a first timing score representative of the extent to which the circuit as routed meets the operational frequency constraints;

means for using said first completion score with said first timing score to obtain a first overall objective function;

means for routing said plurality of programmable connections again to achieve a second routing;

means for computing a second completion score representative of the extent to which the second routing is completely routed within the programmable logic device;

means for computing a second timing score representative of the extent to which the second routing meets the operational frequency constraints;

means for using said second completion score with said second timing score to obtain a second overall objective function for the second routing; and

means for comparing the first overall objective function with the second overall objective function to determine whether to use the second routing.

14. The system of claim 13 further comprising:

means for downloading interconnect programming to said logic device to turn "on" or "off" the programmable connections so that said logic device functions as said electronic circuit.

15. A system for laying out an electronic circuit in a programmable logic device including a plurality of programmable logic cells having programmable connections therebetween, said system comprising:

means for receiving specifications relating to a specified minimum operating frequency of the circuit;

means for converting said specifications to timing specifications including minimum and maximum acceptable delays for each of a plurality of connections, each associated with a path in the circuit;

means for mapping the circuit into logical elements for implementation by said programmable logic cells;

means for placing the logical elements of the mapped circuit into specific programmable logic cells within the device; and

means for routing the circuit via said programmable connections such that said circuit operates within said specified minimum operating frequency.

16. A system as defined in claim 15 wherein said mapping and routing functions are performed in an iterative fashion until the connection delays for each path in circuit are within the range between said minimum and maximum acceptable delays.

17. A method for placing an electronic circuit having one or more logical functions with specified operational preferences within a programmable logic device having a plurality of programmable logic cells with programmable connections therebetween, said circuit including a plurality of paths, each path including a plurality of connections, said method comprising the steps of:

determining a delay requirement for each of said connections in accordance with said specified operational preferences;

calculating an actual connection delay for each of a plurality of routed connections of said plurality of connections;

producing an estimated connection delay for each of a plurality of unrouted connections of said plurality of connections;

comparing said actual connection delays and said estimated connection delays with said operational preferences to obtain a first overall delay difference;

moving a plurality of said programmable logic cells to produce a new placement and to produce new estimated connection delays;

comparing said actual connection delays and said new estimated connection delays with said operational preferences to obtain a second overall delay difference; and

comparing said first overall delay difference with said second overall delay difference to determine whether to use said new placement.

18. The method of claim 17, wherein the step of determining a path delay requirement includes the steps of:

producing a positive slack indication when a connection delay of a path is below a corresponding delay requirement;

producing a negative slack indication when a connection delay of a path is above a corresponding delay requirement;

distributing positive and negative slack among connections of path in proportion to delays corresponding to connections of the path.

19. A computer readable medium storing sequences of instructions which, when executed by a processor, cause the processor to perform the following steps:

receiving a description of a circuit design mapped to logic units and placed within particular sections of the programmable integrated circuit device;

receiving timing requirements for the circuit design;

determining a maximum delay for each of a plurality of connections of the circuit design based upon the timing requirements;

routing the circuit design a first time with the object of routing as many of the plurality of connections as possible;

routing the circuit a second time with the object of making the design as routed meet the timing requirements by making each of the plurality of connections meet an associated maximum delay;

determining if the design as routed the second time includes every connection routed, and if not;

routing the design a third time with the object of routing every connection of the design;

determining if the design as routed the second time meets the timing requirements and if not; and

routing the design a fourth time with the object of making the design as routed meet the timing requirements by making each of the plurality of connections meet an associated maximum delay.

20. The medium of claim 19, wherein the step of determining a maximum delay includes the steps of:

calculating a positive slack when a delay of a routed connection is below the maximum delay and producing a negative slack when a delay of a routed connection is above the maximum delay; and

distributing the negative slack and the positive slack among the connections in proportion to delays of the connections.

21. The medium of claim 19, wherein the steps of determining include the steps of:

calculating an overall objective score for the second routing based upon an extent to which the circuit design is completely routed and an extent to which the second routing meets the timing requirements;

calculating an overall objective score for the fourth routing based upon an extent to which the circuit design is completely routed and an extent to which the second routing meets the timing requirements; and

comparing an overall objective score for the second routing with the overall objective score for the fourth routing to determine whether to use the second or the fourth routing.

22. The medium of claim 21, wherein the steps of calculating an overall objective score include the steps of:

calculating a completion score representative of an extent to which the design is completely routed;

calculating a timing score representative of an extent to which the design meets the timing requirements; and

combining the completion score and the timing score to obtain an overall objective score.

23. The medium of claim 22, wherein the step of calculating a timing score include the steps of:

determining timing scores for each of a plurality of connections using the time by which a delay of each connection exceeds an associated maximum delay, a failure penalty for exceeding the associated maximum delay, and an excess factor; and

combining timing scores for the plurality of connections.