Sequential delay analysis by placement engines

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.

1 - 19 . (canceled) 
     
     
         20 . A method for designing an integrated circuit (IC), the method comprising:
 receiving a specification of a particular path between a source node and a target node in the IC, the particular path comprises a set of computational elements and a set of clocked elements;   attributing a positive combinational delay to each of the computational elements and a negative combinational delay to each of the clocked elements, wherein the negative combinational delay attributed to each clocked element is based on a clock period for operating the clocked element;   computing a sequential delay for the particular path by adding the combinational delays attributed to the clocked elements and the computational elements; and   determining whether the sequential delay of the particular path meets a timing requirement.   
     
     
         21 . The method of  claim 20  further comprising retiming the clocked elements between computation elements to make the delays between each two adjacent clocked element less than or equal to the clock period. 
     
     
         22 . The method of  claim 21 , wherein the cumulative delay being less than one clock period indicates that there exists a retiming of the clocked elements such that all elements in the particular path meet their required timing. 
     
     
         23 . The method of  claim 20 , wherein each clocked element in the set of clocked elements is a retimable clocked element. 
     
     
         24 . The method of  claim 20 , wherein the IC comprises a plurality of reconfigurable circuits, each reconfigurable circuit reconfigurable each cycle to implement a computational element. 
     
     
         25 . The method of  claim 20  further comprising increasing the clock period when the particular path fails to meet the timing requirement. 
     
     
         26 . The method of  claim 20  further comprising decreasing the clock period when the particular path successfully meets the timing requirement. 
     
     
         27 . The method of  claim 20 , wherein the set of clocked elements in the particular path comprises a latch. 
     
     
         28 . The method of  claim 20 , wherein the specification of the particular path is provided by a netlist. 
     
     
         29 . A method for designing an integrated circuit (IC), the method comprising:
 receiving a specification of a particular path between a source node and a target node in the IC, the particular path comprises a set of computational elements and a set of clocked elements, wherein each computational elements is attributed a positive timing delay and each clocked element is attributed a negative delay that is based on a clock period for operating the clocked element;   computing a cumulative timing delay from the source node to the target node by adding the timing delays attributed to the set of computational elements and the set of clocked elements; and   determining whether the particular path meets a timing requirement at the target node based on the computed cumulative timing delay.   
     
     
         30 . The method of  claim 29  further comprising retiming the clocked elements between computation elements to make the delays between each two adjacent clocked element less than or equal to the clock period. 
     
     
         31 . The method of  claim 30 , wherein the cumulative delay being less than one clock period indicates that there exists a retiming of the clocked elements such that all elements in the particular path meet their required timing. 
     
     
         32 . The method of  claim 29 , wherein each clocked element in the set of clocked elements is a retimable clocked element. 
     
     
         33 . The method of  claim 29 , wherein the IC comprises a plurality of reconfigurable circuits, each reconfigurable circuit reconfigurable each cycle to implement a computational element. 
     
     
         34 . The method of  claim 29  further comprising increasing the clock period when the particular path fails to meet the timing requirement. 
     
     
         35 . The method of  claim 29  further comprising decreasing the clock period when the particular path successfully meets the timing requirement. 
     
     
         36 . The method of  claim 29 , wherein the set of clocked elements in the particular path comprises a latch. 
     
     
         37 . The method of  claim 29 , wherein the specification of the particular path is provided by a netlist. 
     
     
         38 . A non-transitory computer readable medium storing a program for execution by one or more processing units, the program comprising sets of instructions for:
 receiving a specification of a particular path between a source node and a target node in the IC, the particular path comprises a set of computational elements and a set of clocked elements;   attributing a positive combinational delay to each of the computational elements and a negative combinational delay to each of the clocked elements, wherein the negative combinational delay attributed to each clocked element is based on a clock period for operating the clocked element;   computing a sequential delay for the particular path by adding the combinational delays attributed to the clocked elements and the computational elements; and   determining whether the sequential delay of the particular path meets a timing requirement.   
     
     
         39 . The non-transitory computer readable medium of  claim 39 , wherein the program further comprising a set of instructions for retiming the clocked elements between computation elements to make the delays between each two adjacent clocked element less than or equal to the clock period.