Patent ID: 6292928
Filing Date: 2001-09-18
Classification: G06F

Abstract:
A method for determining line paths between cells placed in an integrated circuit designed at a cell level, comprising:a rough routing step of dividing a routing area of said integrated circuit into plural partial areas, generating a routing graph in which a cell terminal belonging to each of said partial areas is represented by one node and adjacent nodes are connected through edges, and initially determining, on said routing graph, line paths of cell-to-cell lines on the basis of a passage cost set with regard to each of said edges;a line density estimating step of obtaining, as a line density of each of said edges of said routing graph, the number of cell-to-cell lines passing through said each edge; anda line capacitance estimating step of obtaining, with regard to each of said edges of said routing graph, a line-to-line distance on the basis of said line density obtained in said line density estimating step, obtaining a line capacitance on the basis of said line-to-line distance, and estimating a line capacitance of each of said line paths initially determined in said rough routing step, on the basis of said line capacitance of each edge, as a sum of line capacitances of edges included in said each line path,wherein a delay time of each of said line paths is estimated on the basis of said line capacitance of said each line path estimated in said line capacitance estimating step, and line paths are determined on the basis of said estimated delay time so as to make said integrated circuit satisfy a predetermined timing constraint.