Frequency driven layout and method for field programmable gate arrays

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.

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.

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.

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.

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.

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.

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.

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.

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.