Method and apparatus for locating short circuit faults in an integrated circuit layout
The method and apparatus in accordance with the present invention determines the locations of incorrectly connected polygons in a polygon representation of an integrated circuit layout. These incorrectly connected polygons result in short circuits, which often occur for major signal busses such as power and ground. It can be time-consuming to determine the exact location of the short. The invention includes the step of tessellating the polygon representation, including each conductive layer, into predetermined shapes such as triangles or trapezoids. Each of the triangles or trapezoids is then translated into a node for the development of a nodal network where nodes are connected directly to one another to represent shapes having edges adjacent to other shape edges. The current capacity of each connection between adjacent nodes is then specified. Two nodes that are electrically connected to the incorrectly connected polygons are selected and used as parameters for a network flow analysis algorithm. This algorithm determines the areas of high density where high flow is dictated by the triangle or trapezoid having the lowest current capacity. The areas of high density are flagged as points where short circuits may exist. These flagged points may then be investigated to confirm whether they are short circuits.
1. A method of determining a location of possible incorrectly connected polygons in a polygon representation of an integrated circuit having at least one conductive layer comprising steps of:
(a) tessellating the polygon representation into predetermined shapes;
(b) translating the predetermined shapes into nodes;
(c) developing a node network where the nodes are connected directly to one another as a representation of shapes having adjacent edges;
(d) identifying a current capacity between connected nodes for the nodes in the node network;
(e) selecting at least two nodes in the node network that are electrically connected to possible in correctly connected polygons;
(f) running a network flow analysis algorithm between the at least two selected nodes to determine areas of high current density based on the current capacities between adjacent nodes in the node network; and
(g) flagging the areas of high current density as points of the possible incorrectly connected polygons for further investigation.
2. The method as claimed in claim 1 wherein the step (d) includes determining a ratio of total used current capacity of each edge relative to the current capacity of said each edge for adjacent nodes, and the step (f) includes running the network flow analysis algorithm based on the ratios.
3. The method as claimed in claim 1 wherein the polygon representation includes one or more vias connecting adjacent conductive layers.
4. The method as claimed in claim 3 wherein the polygons in the polygon representation are signal buses.
5. The method as claimed in claim 1 wherein the network flow analysis algorithm is a Ford-Fulkerson algorithm.
6. The method as claimed in claim 1 wherein said predetermined shapes comprise triangles.
7. The method as claimed in claim 1 wherein said predetermined shapes comprise trapezoids.
8. The method as claimed in claim 1 wherein the current capacity is a function of width of signal buses and vias.
9. An apparatus for determining a location of possible incorrectly connected polygons in a polygon representation of an integrated circuit having at least one conductive layer comprising:
means for tessellating the polygon representation into predetermined shapes;
means for translating the predetermined shapes into nodes;
means for developing a node network where the nodes are connected directly to one another as a representation of shapes having adjacent edges;
means for identifying a current capacity between connected nodes for the nodes in the node network;
means for selecting at least two nodes in the node network that are electrically connected to the possible connected polygons;
means for running a network flow analysis algorithm between the at least two selected nodes to determine areas of high current density based on the current capacities between adjacent nodes in the node network; and
means for flagging the areas of high current density as points of the possible incorrectly connected polygons for further investigation.
10. The apparatus as claimed in claim 9 wherein the means for identifying current capacity includes means for determining a ratio of total used current capacity of each edge relative to the current capacity of said each edge for adjacent nodes, and wherein the means for running a network flow analysis algorithm includes means for running the network flow analysis algorithm based on the ratios.
11. The apparatus as claimed in claim 9 wherein the polygon representation includes one or more vias connecting two or more conductive layers.
12. The apparatus as claimed in claim 11 wherein the polygons in the polygon representation are signal buses.
13. The apparatus as claimed in claim 9 wherein the network flow analysis algorithm is a Ford-Fulkerson algorithm.
14. The apparatus as claimed in claim 9 wherein said predetermined shapes comprise triangles.
15. The apparatus as claimed in claim 9 wherein said predetermined shapes comprise trapezoids.
16. The apparatus as claimed in claim 9 wherein the current capacity is a function of width of signal buses and vias.