Enhanced OP3 algorithms for net cuts, net joins, and probe points for a digital design

• US 20070283308A1
• Filed: 08/11/2006
• Published: 12/06/2007
• Est. Priority Date: 06/05/2006
• Status: Active Grant

• Current Assignee: DCG Systems Incorporated (Thermo Fisher Scientific Incorporated)
• Original Assignee: DCG Systems Incorporated (Thermo Fisher Scientific Incorporated)
• Inventors: Basu, Tamal, Malik, Tahir, Suri, Hitesh, Gupta, Saurabh
• Granted Patent: US 7,539,966 B2
• Time in Patent Office: Days
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

Enhanced algorithms are provided for finding circuit edit locations which utilize automated conversions from circuit schematic to physical layout design. The enhanced algorithms further include a user interface enabling the user to provide preferences, limitations, and constraints in order to bias the search to be conducted, as well as using the provided design data in order to locate the best positions for particular edit schemes, including net cuts and net joins.

Claims

1. A method of automating the determination of the optimal edit location on an integrated circuit for the purpose of making layout structural changes while maintaining logic design integrity, comprising the method steps of:

a. providing a database for said integrated circuit, said database including functional unit placement and connectivity data including conducting net data, and building blocks of different functional units and features in layout form, said database containing said functional unit placement and connectivity data, and said building block data of different functional units and features being in polygon form;

b. providing layer-by-layer layout information for said integrated circuit;

c. providing an interface with said database to acquire all feature polygons on a given integrated circuit design;

d. applying user defined constraints and limitations to optimize edit location searches;

e. using enhanced algorithms to find, from said database and said layout information, the optimal at least one edit location under said user defined constraints; and

f. reporting said optimal at least one edit location to said user.

2. The method of claim 1, wherein:

said functional unit placement and connectivity data comprises a Design Exchange Format file (DEF);

said building blocks of different functional units in layout form comprise a Library Exchange (LEF) file; and

said layer-by-layer layout information for said integrated circuit comprises a Gridded Data Set (GDS).

3. The method of claim 1, wherein said edit location is a net cut location.

4. The method of claim 1, wherein said edit location is a net join location.

5. The method of claim 1, wherein said method step of providing an interface with said database file to acquire all feature polygons on a given integrated circuit design includes the method steps of:

a) getting all the polygons which relate to a particular net within said integrated circuit design;

b) getting all the polygons which relate to a particular field of view;

c) getting all polygons which relate to a particular wild card search based on a hierarchical naming convention.

6. The method of claim 1, wherein said method step of applying user defined constraints and limitations to optimize edit location searches comprises providing the user with an interface which enables the user to:

a) specify a set of rules governing edit location searches;

b) determine the order in which said rules are applied;

c) determine the weights of said rules such that the results returned from that cycle of evaluation are biased one way or another;

d) utilize rule bypass options in order to prevent evaluation of results from a search based on an inappropriate or unsuitable rule;

e) specify threshold values to ensure that only those results meeting a predetermined quality level are returned; and

f) determine the maximum number of results to be reported.

7. The method of claim 1, wherein said method step of using enhanced algorithms to find the optimal at least one edit location under said user defined constraints includes at least one of:

a) given a net and a particular set of evaluation rules, evaluating all locations of the net in order to establish which are the best locations on the net to place a probe point;

b) given two nets or a net and a functional unit, finding the best schemes which can be used to logically link the two;

c) given a net, or a net and a functional unit, deciding which are the best schemes of isolating the net from the functional unit, or isolating any given two points on the net;

d) iteratively extending the isolation of two points on the net to the isolation of two sets of points on the same net, and returning a set of edits, subject to a maximum number if required, which would achieve said isolation of two sets of points on the same net.

8. The method of claim 1, wherein said method step of reporting said optimal at least one edit location to said user includes the method steps of:

connecting the system housing the enhanced algorithms to a layout display system;

subject to the number of results requested by the user, displaying all edit suggestions to the user;

said user viewing each said suggestion, its characteristics and scores, and selecting the preferred suggestion.

9. The method of claim 1, wherein said edit location is a FIB edit location.

10. The method of claim 7, wherein said method step of, given a net, or a net and a functional unit, deciding which are the best schemes of isolating a net from a functional unit, or isolating any given two points on the net comprises isolating a net from a functional unit, said method comprising the method steps of:

a) said user providing

1) the name of the net which needs to be isolated from the functional unit;

2) the functional unit which is to be isolated from the net, said net driving an input or an output of said functional unit;

3) a locality to restrict a search for polygons to said locality;

4) rules and optional rule weights and optional rule application orders to determine suitability of points for cutting;

5) the process type;

said process type being selected from frontside process and backside process;

6) non flexible parameters of the edit;

7) a maximum number of cuts; and

8) a number of results to be returned by the algorithm;

b) said enhanced algorithms querying the database to obtain the bounding box and input and output pins of said functional unit, and to obtain all polygons of the net which needs to be isolated from the functional unit, within said locality, including the polygon connected to one of said input and output pins of said functional unit, and dividing all said polygons of the net which needs to be isolated from the functional unit into steps;

c) said enhanced algorithms building a connectivity matrix of all said polygons of the net which need to be isolated from the functional unit, and converting the complete said net into a tree structure wherein each node contains all the steps situated between two bifurcating or trifurcating polygonal connections;

d) said enhanced algorithms computing a probe point suitability score for each step of each said node according to said rules and rule weights, all said steps having scores below a minimum value being removed;

e) said enhanced algorithms determining all possible combinations of cuts on said nodes of said tree structure which will isolate said functional unit from said net, subject to said maximum cut number, each said combination of cuts on said nodes of said tree structure which will isolate said functional unit from said net comprising a cut set, and said enhanced algorithms further determining the relative scores of all said cut sets, each said score of said cut set comprising the sum of the scores of the best scoring step of each node being cut in said cut set, and

f) said enhanced algorithms reporting said possible combinations of cuts to the user.

11. The method of claim 10, wherein said all said steps are of substantially equal size, of one of square and rectangular shape.

12. The method of claim 11, wherein said steps have a dimension in the range between 45×

45 nm and 90×

90 nm.

13. The method of claim 10, wherein said method step of determining all possible combinations of cuts on said nodes of said tree structure which will isolate said functional unit from said net utilizes a tree traversal scheme.

14. The method of claim 7, wherein said method step of, given two nets or a net and a functional unit, finding the best schemes which can be used to logically link the two comprises the method steps of:

a) said user providing

1) the name of the first net which needs to be joined;

2) the name of the second net which needs to be joined;

3) a locality to restrict a search for polygons to said locality;

4) rules and optional rule weights and optional rule application orders to determine suitability of points for joining;

5) the process type;

said process type being selected from frontside process and backside process;

6) non flexible parameters of the edit;

7) a join calculation method; and

8) a number N of results to be returned by the algorithm;

b) said enhanced algorithms querying the database to obtain the polygons related to said first and second nets in said locality;

c) said enhanced algorithms dividing each said polygon related to said first net and said second net into steps; and

d) said enhanced algorithm determining the top N pairs of steps as net join suggestions, and reporting said top N pairs of steps to the user.

15. The method of claim 14, wherein said method step of said enhanced algorithm determining the top N pairs of steps as net join suggestions, and reporting said top N pairs of steps to the user comprises the method steps of:

a) said enhanced algorithms determining probe point suitability scores for each said step of said first and second nets;

b) said enhanced algorithms choosing the steps having a top portion of said probe point suitability scores for each of said first and second nets;

c) said enhanced algorithms calculating the distances from each of said steps having said top portion of said probe scores for said first net and each of said steps having said top portion of said probe scores for said second net;

d) said enhanced algorithms determining from said distances and said probe point scores the top N pairs of steps, and reporting said top N pairs of steps as join suggestions to said user.

16. The method of claim 15, wherein said top portion is the top 25%.

17. The method of claim 14, wherein said method step of said enhanced algorithm determining the top N pairs of steps as net join suggestions, and reporting said top N pairs of steps to the user comprises the method steps of:

a) said enhanced algorithms determining the central point of each said polygon of said first and second nets in said locality;

b) said enhanced algorithms calculating the straight-line distances between said central point of each polygon of said first net and said central point of each polygon of said second net, each said straight-line distance being a distance between polygon pairs;

c) said enhanced algorithms determining and recording a top portion of said polygon pairs, said polygon pairs being ranked according to having the shortest said straight-line distance;

d) said enhanced algorithms determining probe point suitability scores for each said step of said first and second nets, selecting the best said step for each said polygon of said top portion of said polygon pairs, and for each said polygon pair selecting the best step pair according to the sum of said probe point scores for said best said step for each said polygon in said polygon pair; and

e) said enhanced algorithms determining the top N pairs of steps, and reporting said top N pairs of steps as join suggestions to said user

18. The method of claim 17, wherein said top portion is the top 25%.

19. The method of claim 15, wherein the method step of said enhanced algorithms determining probe point suitability scores comprises the method steps of:

a) determining whether an edit if placed at a given step would violate any of said non-flexible parameters;

b) computing a probe point suitability subscore for each step for which no non-flexible parameters are violated, for each said rule;

c) applying any said optional rule weights to each said subscore to provide weighted subscores; and

d) combining said weighted subscores to produce said probe point suitability score for each said step of said first and second nets;

20. The method of claim 17, wherein the method step of said enhanced algorithms determining probe point suitability scores comprises the method steps of:

a) determining whether an edit if placed at a given step would violate any of said non-flexible parameters;

b) computing a probe point suitability subscore for each step for which no non-flexible parameters are violated, for each said rule;

c) applying any said optional rule weights to each said subscore to provide weighted subscores; and

d) combining said weighted subscores to produce said probe point suitability score for each said step of said first and second nets.

21. The method of claim 19, wherein said probe point suitability subscore is normalized to be between 0 and 1.

22. The method of claim 20, wherein said method step of selecting the best said step for each said polygon of said top portion of said polygon pairs comprises applying said rules in said rule application order.

23. The method of claim 22, wherein said method step of applying said rules in said rule application order includes the method steps of:

a) applying the first rule and any simultaneously applied rules to each said step and aggregating the scores;

b) selecting the steps having said top portion of said aggregated scores;

c) applying the second rule and any simultaneously applied rules to each said step and aggregating the scores with the previously aggregated scores;

d) repeating said method steps b) and c) until all the rules are applied or there is only one step remaining.

24. An automated system for determining edit locations, said system including:

a) a database for said integrated circuit, said database including functional unit placement and connectivity data including conducting net data, and building blocks of different functional units and features in layout form, said database containing said functional unit placement and connectivity data, and said building block data of different functional units and features being in polygon form;

b) layer-by-layer layout information for said integrated circuit;

c) an interface with said database to acquire all feature polygons on a given integrated circuit design;

said automated system configured to;

d) apply user defined constraints and limitations to optimize edit location searches;

e) use enhanced algorithms to find, from said database and said layout information, the optimal at least one edit location under said user defined constraints; and

f) report said optimal at least one edit location to said user.

25. The system of claim 24, wherein:

said functional unit placement and connectivity data comprises a Design Exchange Format file (DEF);

said building blocks of different functional units in layout form comprise a Library Exchange (LEF) file; and

said layer-by-layer layout information for said integrated circuit comprises a Gridded Data Set (GDS).

26. The system of claim 24, wherein said system being configured to use enhanced algorithms to find the optimal at least one edit location under said user defined constraints includes said system being configured for at least one of:

a) given a net and a particular set of evaluation rules, evaluating all locations of the net in order to establish which are the best locations on the net to place a probe point;

b) given two nets or a net and a functional unit, finding the best schemes which can be used to logically link the two;

c) given a net, or a net and a functional unit, deciding which are the best schemes of isolating the net from the functional unit, or isolating any given two points on the net;

d) iteratively extending the isolation of two points on the net to the isolation of two sets of points on the same net, and returning a set of edits, subject to a maximum number if required, which would achieve said isolation of two sets of points on the same net.

27. The system of claim 24, further including:

a layout display system connected to said automated system;

said layout display system, subject to the number of results requested by the user, displaying all edit suggestions to the user.