Method and apparatus for approximating diagonal lines in placement

Abstract

Some embodiments of the invention provide a method for placing circuit modules in an integrated circuit (“IC”) layout. The method computes a placement metric for the IC layout. In some embodiments, computing the placement metric includes partitioning a region the IC layout into several sub-regions by using a cut graph, where the cut graph is an approximation of a diagonal cut line. These embodiments then generate congestion-cost estimates by measuring the number of nets cut by the cut graph. In some embodiments, the cut graph is a staircase cut graph. These staircase cut graphs include several horizontal and vertical cut lines. In some embodiments, the cut graph is a cut arc.

1 - 19 . (canceled) 
     
     
         20 . An automated method for placing a set of circuit modules in an integrated circuit (“IC”) layout, the method comprising:
 computing a placement metric for the IC layout, wherein computing the placement metric comprises:
 partitioning a region of the IC layout into a plurality of sub-regions by using a set of cut graphs that comprises a staircase cut graph, said staircase cut graph comprising horizontal and vertical segments, wherein a plurality of said horizontal and vertical segments do not intersect any other cut graphs; and 
 generating congestion-cost estimates by measuring a number of nets cut by the set of cut graphs; and 
 
 by a computer, determining a placement for the set of circuit modules based on the computed placement metric. 
 
     
     
         21 . The automated method of  claim 20 , wherein the staircase cut graph is an approximation of a diagonal cut line. 
     
     
         22 . The automated method of  claim 20 , wherein the set of cut graphs comprises a plurality of horizontal cut lines. 
     
     
         23 . The automated method of  claim 20 , wherein the set of cut graphs comprises a plurality of vertical cut lines. 
     
     
         24 . The automated method of  claim 20 , wherein computing the placement metric further comprises recursively partitioning the region of the IC layout into a plurality of sub-regions. 
     
     
         25 . The automated method of  claim 24 , wherein a first staircase cut graph is used during a first recursive partitioning of the region of the IC layout. 
     
     
         26 . The automated method of  claim 25 , wherein a second staircase cut graph is used during a second recursive partitioning of the region of the IC layout. 
     
     
         27 . The automated method of  claim 26 , wherein the first staircase cut graph comprises a first set of horizontal and vertical segments, wherein a plurality of said horizontal and vertical segments do not intersect any other cut graphs, wherein the second staircase cut graph comprises a second set of horizontal and vertical segments, wherein a plurality of said horizontal and vertical segments do not intersect any other cut graphs, wherein a length of each of the first set of segments is different than a length of each of the second set of segments. 
     
     
         28 . The automated method of  claim 20 , wherein a length of each of said plurality of said vertical segments is different than a length of each of said plurality of said horizontal segments. 
     
     
         29 . A non-transitory computer readable medium storing a computer program for placing a set of circuit modules in an integrated circuit (“IC”) layout, the computer program executable by at least one processor, the computer program comprising sets of instructions for:
 computing a placement metric for the IC layout, wherein the set of instructions for computing the placement metric comprises sets of instructions for:
 partitioning a region of the IC layout into a plurality of sub-regions by using a set of cut graphs that comprise a staircase cut graph, said staircase cut graph comprising horizontal and vertical segments, wherein a plurality of said horizontal and vertical segments do not intersect any other cut graphs; and 
 generating congestion-cost estimates by measuring a number of nets cut by the set of cut graphs; and 
 
 determining a placement for the set of circuit modules based on the computed placement metric. 
 
     
     
         30 . The non-transitory computer readable medium of  claim 29 , wherein each net comprises a plurality of pins, wherein the set of instructions for measuring the number of nets cut by the staircase cut graph comprises sets of instructions for iteratively, for each net in the region:
 selecting each pin in the net;   identifying a sub-region for each pin based on the staircase cut graph; and   determining that the net is cut when at least one pin is identified in a first sub-region and at least one pin is identified in a second sub-region, wherein the first sub-region and the second sub-region are different sub-regions.   
     
     
         31 . The non-transitory computer readable medium of  claim 30 , wherein the set of instructions for identifying a sub-region of a pin based on the staircase cut graph comprises a set of instructions for:
 identifying a first horizontal cut line segment having a closest y coordinate that is greater than a y coordinate of the pin;   identifying a second horizontal cut line segment having a closest y coordinate that is not greater than a y coordinate of the pin;   identifying a vertical cut line segment that is coupled between the first and second identified horizontal cut line segments;   determining whether an x coordinate of the pin is greater than an x coordinate of the vertical cut line segment;   determining that the pin is in the first sub-region of the IC layout when the x coordinate of the pin is greater than the x coordinate of the vertical cut line segment and determining that the pin is in the second sub-region of the IC layout when the x coordinate of the pin is not greater than the x coordinate of the vertical line segment.   
     
     
         32 . An automated method for placing a set of circuit modules in an integrated circuit (“IC”) layout, wherein the set of circuit modules comprises a plurality of pins, the method comprising:
 computing a placement metric for the IC layout, wherein computing the placement metric comprises partitioning a region of the IC layout by using a cut arc, wherein the cut arc comprises a curve, wherein said curve does not include any straight segments; and 
 by a computer, determining a placement for the set of circuit modules based on the computed placement metric. 
 
     
     
         33 . The automated method of  claim 32 , wherein computing a placement metric for the IC layout further comprises generating congestion-cost estimates by measuring a number of nets cut by the cut arc, wherein generating the congestion-cost estimates comprises:
 computing a distance between a pin in the IC layout and a center of a circle that defines the cut arc; and   determining whether the distance between the pin and the center of the circle is greater than a radius of the circle.   
     
     
         34 . The automated method of  claim 33 , wherein generating the congestion-cost estimates further comprises specifying that the pin is in a first region when the distance is greater than the radius. 
     
     
         35 . The automated method of  claim 34 , wherein generating the congestion-cost estimates further comprises specifying that the pin is in a second region when the distance is not greater than the radius. 
     
     
         36 . The automated method of  claim 32 , wherein computing the placement metric further comprises recursively partitioning the region of the IC layout into a plurality of sub-regions. 
     
     
         37 . The automated method of  claim 32 , wherein the cut arc is a curved approximation of a diagonal cut line. 
     
     
         38 . The automated method of  claim 32 , wherein the cut arc is defined by a circle with a radius that is less than a sum of a height and a width of the region of the IC layout.