Sequential delay analysis by placement engines

• US 8,863,067 B1
• Filed: 02/06/2008
• Issued: 10/14/2014
• Est. Priority Date: 02/06/2008
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Caldwell, Andrew, Teig, Steven
• Primary Examiner(s): TAT, BINH C
• Application Number:
  US12/027,260
• Time in Patent Office: 2,442 Days
• Field of Search: 716132-135
• US Class Current: 716/132
• CPC Class Codes: G06F 30/3312 Timing analysis
• 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

Some embodiments provide a method of designing an integrated circuit (IC). The design is expressed as a graph that includes several nodes that represent several IC components. The nodes include a first set of nodes that represent a set of clocked elements. The method creates a second set of nodes by removing all nodes in the first set from the nodes that represent the IC components. The method identifies a set of edges that connect two nodes in the second set without encompassing a third node in the second set. The method assigns an event time to each node in the second set. The method assigns a cost function based on the event times of the nodes connected by each edge and the number of nodes in the first set encompassed by each edge. The method optimizes the cost function and places the components based on the cost function optimization.

Claims

1. A method of designing an integrated circuit (IC), the IC design expressed as a graph comprising a plurality of edges and a plurality of nodes representing a plurality of IC components, each edge connecting two nodes without encompassing a third node, the method comprising:

defining a cost function that has a component for each edge that is based on (i) a spatial relationship comprising a difference in horizontal and vertical coordinates of the two nodes of the edge and (ii) a temporal relationship comprising a difference between event times of the two nodes of the edge;

optimizing, by a computer, the IC design by changing at least one of an event time and a coordinate of a node and modifying the IC design to satisfy a set of constraints on each component of the cost function such that, for each edge, a difference between the event times of the nodes connected by the edge is not less than a signal propagation delay caused by the spatial relationship between the two nodes connected by the edge; and

placing the IC components based on the optimized IC design.

2. The method of claim 1, wherein the IC includes at least one reconfigurable circuit that reconfigures during an operation of the IC.

3. The method of claim 2, wherein at least one reconfigurable circuit is for reconfiguring at a first clock rate that is faster than a second clock rate specified for a particular design of the IC.

4. The method of claim 3, wherein the second clock comprises a clock cycle comprising a plurality of sub-cycles, wherein placing the IC components comprises assigning each node in the second set of nodes to a particular sub-cycle of the second clock.

5. A method of designing an integrated circuit (IC), wherein the IC design is expressed as a graph comprising a plurality of edges and a plurality of nodes representing a plurality of IC components, each edge connecting two nodes without encompassing a third node, the method comprising:

assigning an event time to each node in the graph, each event time associated with availability of a signal at a corresponding node;

defining a cost function that has a cost expression for each edge that is based on the event times of the nodes connected by the edge and a spatial distance between the nodes connected by the edge, wherein the spatial distance is based on horizontal and vertical coordinates of the two nodes of the edge;

identifying, by a computer, a placement solution for the IC components by changing at least one of an event time and a coordinate of a node in the cost function and modifying the IC design to satisfy a set of constraints on each component of the cost function such that, for each edge, a difference between the event times of the nodes connected by the edge is not less than a signal propagation delay caused by the spatial relationship between the two nodes connected by the edge; and

placing the IC components based on the identified placement solution.

6. The method of claim 5, wherein the placement solution is identified by changing at least one of an event time and a coordinate of a node.

7. The method of claim 5, wherein the IC is one of an application-specific integrated circuit (ASIC), a structured ASIC, a field-programmable gate array (FPGA), a programmable logic device (PLD), a complex programmable logic device (CPLD), a system on chip (SOC), a system-in-package (SIP), and a reconfigurable IC.

8. The method of claim 5, wherein the identified placement solution meets a timing requirement on the cost expression of the cost function for each edge such that a difference between the event times of the nodes connected by the edge is not less than a signal propagation delay caused by the spatial distance.

9. A method of designing an integrated circuit (IC), wherein the IC design is expressed as a graph comprising a plurality of nodes representing a plurality of IC components, the plurality of nodes comprising a first set of nodes representing a set of clocked elements, the method comprising:

identifying a second set of nodes that comprises nodes in the plurality of nodes that are not in the first set of nodes, the second set of nodes not comprising any node from the first set of nodes;

identifying a set of edges, each identified edge connecting two nodes in the second set of nodes while encompassing at least one node from the first set of nodes;

assigning an event time to each node in the second set of nodes;

defining a cost function that has a component for each edge that is based on (i) the event times of the two nodes connected by the edge, (ii) a spatial distance based on a difference in horizontal and vertical coordinates of the two nodes connected by the edge, and (iii) a number of nodes in the first set encompassed by the edge;

optimizing, by a computer, the IC design; and

placing the IC components based on the optimized IC design by modifying the IC design to satisfy a set of constraints on each component of the cost function such that, for each edge, a difference between the event times of the nodes connected by the edge is not less than a signal propagation delay caused by the spatial relationship between the two nodes connected by the edge.

10. The method of claim 9, wherein optimizing the IC design comprises changing at least one of an event time and a coordinate of a node.

11. The method of claim 9, wherein the clocked elements represented by the first set of nodes are retimable clocked elements.

12. The method of claim 9, wherein the nodes in the second set comprise clocked elements that cannot be retimed.

13. The method of claim 9, wherein the nodes in the second set comprise input and output nodes of the graph.

14. The method of claim 9, wherein the nodes in the second set comprise nodes with timing constraints.

15. The method of claim 9, wherein the nodes in the second set comprise storage elements.

16. The method of claim 9, wherein the IC is one of an application-specific integrated circuit (ASIC), a structured ASIC, a field-programmable gate array (FPGA), a programmable logic device (PLD), a complex programmable logic device (CPLD), a system on chip (SOC), and a system-in-package (SIP).

17. The method of claim 9, wherein the IC includes at least one reconfigurable circuit that reconfigures during an operation of the IC.

18. The method of claim 17, wherein at least one reconfigurable circuit is for reconfiguring at a first clock rate that is faster than a second clock rate specified for a particular design of the IC.

19. The method of claim 18, wherein the second clock comprises a clock cycle comprising a plurality of sub-cycles, wherein placing the IC components comprises assigning each node in the second set of nodes to a particular sub-cycle of the second clock.

20. The method of claim 9, wherein optimizing the IC design comprises modifying the IC design to meet a timing requirement based on a relationship between the event times and the spatial distance for each edge.

21. A non-transitory computer readable medium storing a computer program for designing an integrated circuit (IC), the IC design expressed as a graph comprising a plurality of edges and a plurality of nodes representing a plurality of IC components, each edge connecting two nodes without encompassing a third node, the computer program for execution by at least one processor, the computer program comprising sets of instructions for:

defining a cost function that has a cost expression for each edge that is based on (i) a spatial relationship comprising a difference in horizontal and vertical coordinates of the two nodes of the edge and (ii) a temporal relationship comprising a difference between event times of the two nodes of the edge;

optimizing the IC design based by changing at least one of an event time and a coordinate of a node and modifying the IC design to satisfy a set of constraints on each component of the cost function such that, for each edge, a difference between the event times of the nodes connected by the edge is not less than a signal propagation delay caused by the spatial relationship between the two nodes connected by the edge; and

placing the IC components based on the optimized IC design.

22. The non-transitory computer readable medium of claim 21, wherein the IC includes at least one reconfigurable circuit that reconfigures during an operation of the IC.

23. The non-transitory computer readable medium of claim 22, wherein at least one reconfigurable circuit is for reconfiguring at a first clock rate that is faster than a second clock rate specified for a particular design of the IC.

24. The non-transitory computer readable medium of claim 23, wherein the second clock comprises a clock cycle comprising a plurality of sub-cycles, wherein the set of instructions for placing the IC components comprises a set of instructions for assigning each node in the second set of nodes to a particular sub-cycle of the second clock.

25. A method of designing an integrated circuit (“

IC”

), wherein the IC design is expressed as a graph comprising a plurality of edges and a plurality of nodes representing a plurality of IC components, each edge connecting two nodes without encompassing a third node, the method comprising;

defining a cost function that has a component for each edge that is based on (i) signal temporal values for the two nodes of the edge, and (ii) a spatial relationship comprising a difference between coordinates of the two nodes of the edge;

by a computer, iteratively examining different placement solutions by changing at least one of a signal temporal value and a coordinate of a node and modifying the IC design to satisfy a set of constraints on each component of the cost function such that, for each edge, a difference between the temporal values of the nodes connected by the edge is not less than a signal propagation delay caused by the spatial relationship between the two nodes connected by the edge; and

placing the IC components based on an optimal placement solution according to the cost function.

26. The method of claim 25, wherein the placing is performed only once after the examining of different placement solutions.

27. The method of claim 25, wherein the optimal placement solution is identified by satisfying a set of constraints on the component of the cost function for each edge.

28. The method of claim 27, wherein the set of constraints for an edge is satisfied when a difference between the signal temporal values of the nodes of the edge is not less than a signal propagation delay caused by a spatial distance between the two nodes of the edge.