Method and system for timing optimization with detour prediction

• US 10,268,795 B2
• Filed: 04/20/2017
• Issued: 04/23/2019
• Est. Priority Date: 04/20/2017
• Status: Active Grant

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Inventors: Chuang, Yi-Lin, Chang, Chih-Tien, Su, Kuan-Hua, Huang, Szu-Ju
• Primary Examiner(s): Alam, Mohammed
• Application Number:
  US15/492,326
• Publication Number:
  US 20180307790A1
• Time in Patent Office: 733 Days
• Field of Search: 716126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• 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
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

A method for timing optimization is disclosed. The method includes obtaining information on detour locations of a chip by performing a routing operation, establishing, through machine learning, a model that describes a relationship between an image map and the detour locations, generating predicted detour locations based on the model and the image map, determining the probability of detouring in a region of the predicted detour locations, determining a predicted detour net for a path in a region having a high probability of detour, and determining sensitivity of the path.

Claims

1. A method implemented in an electronic design automation system, comprising the steps of:

performing a routing operation to generate routing and detour location data for a chip;

generating a data model in response to a machine learning process that describes a relationship between an image map of the chip and the detour location data;

determining predicted detour locations based on the data model and the image map;

determining the probability of detouring in a region of the predicted detour locations;

determining a predicted detour net for a path in a region having a high probability of detour;

determining sensitivity of predicted detour nets along the path; and

routing a detour net for the chip in response to the determined sensitivity of the predicted detour nets, wherein

the step of generating the data model further comprises;

receiving the routing and detour location data;

receiving a map of circuit element placement derived from placement data; and

converting the map into the image map, and

the map includes a congestion map, and the step of converting further comprises;

obtaining information on the number of nets available in a region each in a first direction and in a second direction different from the first direction; and

obtaining information on the number of nets actually routed in the region each in the first direction and in the second direction.

2. The method according to claim 1 further comprising:

determining a grayscale value of a pixel in the congestion map based on a summation of the number of actually routed nets in both the first and second directions and a summation of the number of available nets in both the first and second directions.

3. The method according to claim 1 further comprising:

determining a grayscale value of a pixel in the congestion map based on the number of actually routed nets in the first direction and the number of available nets in the first direction, and generating a first image map; and

determining a grayscale value of a pixel in the congestion map based on the number of actually routed nets in the second direction and the number of available nets in the second direction, and generating a second image map.

4. The method according to claim 1 further comprising:

sorting the congestion map by pitch, resulting in a number of pitch maps; and

converting each of the pitch maps into the image map.

5. The method according to claim 1 further comprising:

sorting the congestion map by interconnection layer, resulting in a number of layer maps; and

converting each of the pitch maps into the image map.

6. The method according to claim 1, wherein the map includes at least one of a pitch map or a pin shape map.

7. The method according to claim 1, wherein the determining the probability of detouring further comprises:

determining net boxes in the region that each contains a detour net; and

identifying an overlapped region of the net boxes.

8. The method according to claim 1, wherein the sensitivity is function of the length of the predicted detour net.

9. The method according to claim 1 further comprising:

routing a predicted detour net having a smaller sensitivity prior to a predicted detour net having a larger sensitivity.

10. The method according to claim 1 further comprising:

routing a predicted detour net having a smaller sensitivity via a higher interconnection layer than that of a predicted detour net having a larger sensitivity.

11. A method implemented in an electronic design automation system, comprising:

performing a placement operation to generate placement data of a chip;

determining the number of nets available for a global routing cell in a map of the chip including information on the placement data;

determining the number of nets actually routed for the global routing cell in the map including information on the placement data;

converting the chip map into a grayscale image based on information on the number of available nets and the number of actually routed nets;

feeding the converted chip map to a machine learning system; and

routing a detour net for the chip in response to the machine learning system processing the converted chip map, wherein the step of converting further comprises;

determining a grayscale value of a pixel in the chip map based on the number of actually routed nets in a vertical direction and the number of available nets in the vertical direction, and generating a first image map;

determining a grayscale value of a pixel in the chip map based on the number of actually routed nets in a horizontal direction and the number of available nets in the horizontal direction, and generating a second image map;

sorting the chip map by pitch, resulting in a number of pitch maps; and

converting each of the pitch maps into a grayscale image.

12. The method according to claim 11, wherein the converting further comprises:

determining a grayscale value of a pixel in the map based on a summation of the number of actually routed nets in both a vertical direction and a horizontal direction and a summation of the number of available nets in both the vertical direction and the horizontal direction.

13. The method according to claim 11, wherein the converting further comprises:

sorting the map by interconnection layer, resulting in a number of layer maps; and

converting each of the pitch maps into a grayscale image.

14. The method according to claim 11, wherein the converting further comprises:

sorting the map by interconnection layer, resulting in a number of layer maps; and

converting each of the pitch maps into a grayscale image.

15. An electronic design automation system, comprising one or more processors and one or more programs including instructions which, when executed by the one or more processors, cause the system to:

perform a routing operation to generate placement data of a chip;

generate a data model in response to a machine learning process that describes a relationship between an image map of the chip and the detour locations;

generate predicted detour locations based on the data model and the chip image map;

determine the probability of detouring in a region of the predicted detour locations;

determine a predicted detour net for a path in a region having a high probability of detour;

determine sensitivity of predicted detour nets along the path; and

route a detour net for the chip in response to the determined sensitivity of the predicted detour nets, wherein

the generating of the data model further comprising;

receiving the routing and detour location data;

receiving a map of circuit element placement derived from placement data; and

converting the map into the image map, and

the map includes a congestion map, and the converting of the map further comprising;

obtaining information on the number of nets available in a region each in a first direction and in a second direction different from the first direction; and

obtaining information on the number of nets actually routed in the region each in the first direction and in the second direction.

16. The system according to claim 15, further comprising instructions which, when executed by the one or more processors, cause the system to:

route a predicted detour net having a smaller sensitivity prior to a predicted detour net having a larger sensitivity.

17. The system according to claim 15 further comprising instructions which, when executed by the one or more processors, cause the system to:

route a predicted detour net having a smaller sensitivity via a higher interconnection layer than that of a predicted detour net having a larger sensitivity.