Frequency driven layout system and method for field programmable gate arrays

• US 5,648,913 A
• Filed: 02/06/1995
• Issued: 07/15/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/383,647
• Time in Patent Office: 890 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 326/37, 326/39, 326/41, 326/47, 326/101, 340/825.83, 340/825.85, 340/825.86, 340/825.87
• 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 system for establishing a predicted routing delay in an electronic circuit connection between a driver and a load element to be constructed from a programmable logic device having a plurality of programmable logic cells and a number of heterogeneous routing resources including at least a first and a second type of interconnect having respective predetermined delays thereof, said system comprising:

means for firstly estimating a first routing delay based upon a possible routing of said electronic circuit connection utilizing a horizontally disposed one of said first interconnects and a calculated number of vertically disposed ones of said second interconnects;

means for secondly estimating a second routing delay based upon a possible routing of said electronic circuit connection utilizing a vertically disposed one of said first interconnects and a calculated number of horizontally disposed ones of said second interconnects;

means for thirdly estimating a third routing delay based upon a possible routing of said electronic circuit connection utilizing a horizontally and a vertically disposed ones of said first interconnects;

means for fourthly estimating a fourth routing delay based upon a possible routing of said electronic circuit connection utilizing a calculated number of horizontally and vertically disposed ones of said second interconnects; and

means for determining a least routing delay of said first, second, third and fourth routing delays; and

means for utilizing said least routing delay as said predicted routing delay between said driver and load elements.

2. The system of claim 1 further comprising:

means for determining a type of said driver element of said electronic circuit connection; and

means for alternatively utilizing a fixed estimate of said routing delay as said predicted routing delay instead of said least routing delay if said driver element is of a predetermined type.

3. The system of claim 1 further comprising:

means for determining a location on said logic device of said driver element of said electronic circuit connection with respect to a vertically disposed input/output pin of said programmable logic device; and

means for alternatively utilizing a horizontally disposed first interconnect delay and a predetermined number of vertically disposed second interconnect delays of said driver element from said load element of said electronic circuit connection as said predicted routing delay instead of said least routing delay.

4. The system of claim 1 further comprising:

means for determining a location on said logic device of said load element of said electronic circuit connection with respect to a horizontally disposed input/output pin of said programmable logic device; and

means for alternatively utilizing a vertically disposed first interconnect delay and a predetermined number of horizontally disposed second interconnect delays of said load element from said driver element of said electronic circuit connection as said predicted routing delay instead of said least routing delay.

5. The system of claim 4 further comprising:

means for establishing if said driver element and said load element of said electronic circuit connection are connected by a single arc;

means for determining a type of said driver element of said electronic circuit connection if said driver element and said load element are connected by a single arc; and

means for alternatively utilizing a fixed estimate of said routing delay associated with said single arc plus a fanout delay of said electronic circuit connection as said predicted routing delay instead of said least routing delay if said driver element is of a predetermined type.

6. A system as defined in claim 5 wherein said predicted routing delay between a driver and a load element is established in conjunction with the establishment of predicted routing delays between other drivers and load elements;

and

means wherein said utilizing means includes considering the availability of said routing resources and the requirements of routing delays of predicted routing delays between other drivers and load elements and utilizing one of the estimated routing delays other than the least routing delay when necessary to satisfy said requirements.

7. A system as defined in claim 5 wherein said first type of interconnect is a global interconnect and said second type of interconnect is a local interconnect.

8. A method for establishing a predicted routing delay of an electronic circuit connection between a driver and a load element to be constructed from a programmable logic device having a plurality of programmable logic cells and a number of heterogeneous routing resources including at least a first and a second type of interconnect having respective predetermined delays thereof, said method comprising the steps of:

estimating a first routing delay based upon a possible routing of said electronic circuit connection utilizing a calculated number of horizontally disposed ones of said first interconnects and a calculated number of vertically disposed ones of said second interconnects;

estimating a second routing delay based upon a possible routing of said electronic circuit connection utilizing a calculated number of vertically disposed ones of said first interconnects and a calculated number of horizontally disposed ones of said second interconnects;

estimating a third routing delay based upon a possible routing of said electronic circuit connection utilizing a calculated number of horizontally and vertically disposed ones of said first interconnects;

estimating a fourth routing delay based upon a possible routing of said electronic circuit connection utilizing a calculated number of horizontally and vertically disposed ones of said second interconnects; and

determining a least routing delay of said first, second, third and fourth routing delays; and

utilizing said least routing delay as said predicted routing delay between said driver and load elements.

9. A method as defined in claim 8, further including the steps of:

determining a location on said logic device of said driver element of said electronic circuit connection with respect to a vertically disposed input/output pin of said programmable logic device; and

alternatively utilizing a horizontally disposed first interconnect delay and a predetermined number of vertically disposed second interconnect delays of said driver element from said load element of said electronic circuit connection as said predicted routing delay instead of said least routing delay.

10. A method as defined in claim 8, further including the steps of:

determining a location on said logic device of said load element of said electronic circuit connection with respect to a horizontally disposed input/output pin of said programmable logic device; and

alternatively utilizing a vertically disposed first interconnect delay and a predetermined number of horizontally disposed second interconnect delays of said load element from said driver element of said electronic circuit connection as said predicted routing delay instead of said least routing delay.

11. A method as defined in claim 10, further including the steps of:

establishing if said driver element and said load element of said electronic circuit connection are connected by a single arc;

determining a type of said driver element of said electronic circuit connection if said driver element and said load element are connected by a single arc; and

alternatively utilizing a fixed estimate of said routing delay associated with said single arc plus a fanout delay of said electronic circuit connection as said predicted routing delay instead of said least routing delay if said driver element is of a predetermined type.

12. A method as defined in claim 8 wherein said predicted routing delay between a driver and a load element is established in conjunction with the establishment of predicted routing delays between other drivers and load elements;

and

wherein said utilizing step includes considering the availability of said routing resources and the requirements of routing delays of predicted routing delays between other drivers and load elements and utilizing one of the estimated routing delays other than the least routing delay when necessary to satisfy said requirements.

13. A method as defined in claim 8 wherein said first type of interconnect is a global interconnect and said second type of interconnect is a local interconnect.

14. A method as defined in claim 8, further including the steps of:

determining a type of said driver element of said electronic circuit connection; and

alternatively utilizing a fixed estimate of said routing delay as said predicted routing delay instead of said least routing delay if said driver element is of a predetermined type.