Line path determining method and delay estimating method

Details Line path determining method and delay estimating method Line path determining method and delay estimating method

1999-01-11

2001-09-18

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06292928

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a layout design technique for integrated circuits, and more particularly, it relates to methods of determining a line path and estimating delay in rough routing of semi-custom LSIs such as an ASIC.
In the recent manufacturing technique for semiconductor integrated circuits, transistors and lines have been more and more refined. In accordance with the refinement, the delay time of a transistor itself tends to be decreased. However, since the capacitance between adjacent lines is increased due to the refinement of the lines, the output load capacitance of a cell cannot be always decreased, and hence, the proportion of delay depending upon the line capacitance is relatively increased in the delay of the entire integrated circuit.
Accordingly, in order to guarantee an operation timing, the recent layout design for an integrated circuit requires a method of precisely estimating a line capacitance in consideration of an adjacent line and definitely determining a line path that satisfies a timing constraint.
Conventional methods of determining a line path include the following:
As a first conventional method, after a routing pattern is generated on the basis of detailed routing for determining lines in detail, an adjacent routing pattern is searched for with regard to each line so as to calculate a line capacitance generated between the adjacent lines (Japanese Laid-Open Patent Publication No. 6-120343).
As a second conventional method, in a rough routing procedure, a delay time of each line is estimated on the basis of a virtual line length and a line capacitance attained when the line is assumed to be allocated to an interconnect layer having the maximum line capacitance per unit length (hereinafter referred to as the “unit capacitance”), so as to extract a net against a timing constraint, and this net is allocated to another interconnect layer for satisfying the timing constraint (Japanese Laid-Open Patent Publication No. 5-143692).
However, the conventional methods of determining a line path have the following problems:
In the first conventional method, since a line capacitance is calculated in consideration of the influence of an adjacent line after completely generating the routing pattern in detail on the basis of the detailed routing, when there is a timing error, it is very difficult to remove the timing error by modifying the routing. Specifically, the amount of data to be dealt with for modifying the routing is so large that the process takes a long period of time, and in some cases, the calculating process cannot be converged and the routing cannot be modified.
Alternatively, in the second conventional method, since a line is assumed to be allocated to an interconnect layer with the maximum unit capacitance in the net against the timing constraint, the line capacitance is likely to be excessively estimated. Also, since an adjacent line is not considered in the estimation of the line capacitance, even when no timing error is caused in the rough routing process, a timing error can be occasionally caused due to an adjacent line after detailed routing. Accordingly, a netlist itself should be changed for the modification for eliminating the timing error.
SUMMARY OF THE INVENTION
The object of the invention is providing a line path determining method in which line paths can be determined in rough routing with a timing error eliminated through estimation of a line capacitance in consideration of the influence of adjacent lines.
In order to achieve this object, according to this invention, paying attention to estimation of probability of existence of adjacent lines on the basis of a line density in rough routing, delay is calculated through estimation of a line capacitance based on the estimated existence probability of the adjacent lines, and a line path in a net against a timing constraint is determined based on the obtained delay.
Specifically, the line path determining method of this invention for determining line paths between cells placed in an integrated circuit designed at a cell level comprises a rough routing step of dividing a routing area of the integrated circuit into plural partial areas, generating a routing graph in which a cell terminal belonging to each of the partial areas is represented by one node and adjacent nodes are connected through edges, and initially determining, on the routing graph, line paths of cell-to-cell lines on the basis of a passage cost set with regard to each of the edges; a line density estimating step of obtaining, as a line density of each of the edges of the routing graph, the number of cell-to-cell lines passing through each edge; and a line capacitance estimating step of obtaining, with regard to each of the edges of the routing graph, a line-to-line distance on the basis of the line density obtained in the line density estimating step, obtaining a line capacitance on the basis of the line-to-line distance, and estimating a line capacitance of each of the line paths initially determined in the rough routing step, on the basis of the line capacitance of each edge, as a sum of line capacitances of edges included in each line path, wherein a delay time of each of the line paths is estimated on the basis of the line capacitance of each line path estimated in the line capacitance estimating step, and line paths are determined on the basis of the estimated delay time so as to make the integrated circuit satisfy a predetermined timing constraint.
In this method, with regard to the routing graph generated from a target integrated circuit in the rough routing step, the number of cell-to-cell lines passing through each edge is obtained as the line density in the line density estimating step. Then, in the line capacitance estimating step, the line-to-line distance is obtained from the line density of each edge, and the line capacitance is obtained from the line-toline distance. As a result, the line capacitance of each line path initially determined in the rough routing step is estimated. On the basis of this line capacitance, delay of each line path is estimated, and on the basis of the estimated delay, line paths are determined so as to make the integrated circuit satisfy the predetermined timing constraint. Accordingly, the line paths can be determined with a timing error eliminated on the basis of the result of the path search in the rough routing through estimation of the line capacitance in consideration of the influence of the adjacent lines by using the line density. Therefore, timing errors can be predicted and avoided to some extent in the path search in the rough routing, and hence, layout modification which can be accompanied with large modification of the routing pattern if conducted after the detailed routing can be largely reduced.
In the line path determining method, when the integrated circuit does not satisfy the predetermined timing constraint, the method preferably further comprises a rough re-routing step of adding, as a parameter of the passage cost set with regard to each of the edges, the line capacitance of each edge obtained in the line capacitance estimating step, and re-determining, on the routing graph, line paths of the cell-to-cell lines on the basis of the passage cost set with regard to each of the edges.
In this manner, since an alternate path with a smaller line capacitance is searched for, in the rough re-routing step, with regard to a line path causing a timing error, a timing error can be efficiently avoided.
Furthermore, in the line path determining method, in the routing graph, plural edges respectively corresponding to interconnect layers available for routing c an be set between adjacent nodes, and when the integrated circuit does not satisfy the predetermined timing constraint, the method can further comprise a n interconnect layer changing step of changing a edge included in a line path not satisfying the timing constraint to a edge connecting the same nodes and corresponding to an interconnect layer with a smaller unit capacitance.
In this

Affiliated with

Also associated with

Rating

Line path determining method and delay estimating method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Line path determining method and delay estimating method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Line path determining method and delay estimating method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2541282