# US 2021/0240904 A1 · Method of analyzing and detecting critical cells

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0240904 A1
- Document ID: US20210240904A1
- Status: Published application
- Kind: A1
- Application number: 17/025,449
- Filed: 2020-09-18
- Published: 2021-08-05
- Earliest claimed: 2020-01-30
- Assignees: Taiwan Semiconductor Manufacturing Company, Ltd.
- Applicants: Taiwan Semiconductor Manufacturing Co., Ltd.
- Inventors: Anurag VERMA; Meng-Kai HSU; Chih-Wei CHANG
- Web page: https://patentgrep.com/patent/US20210240904A1

## CPC

- 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)
- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method includes obtaining a feature vector for each cell in a group of cells. The feature vector for a cell includes a score value for each feature in a set of features selected for characterizing the group of cells. The method includes clustering cells in the group into a selected number of clusters, based on distances between end points of feature vectors of the cells. The method includes generating a list of ranked critical cells in the selected number of clusters based on a list of prioritized features associated with the set of features. The method includes outputting the list of ranked critical cells for use in adjusting cell layouts based on the ranked critical cells.

## Claims

### Claim 1

A method comprising:
obtaining a feature vector for each cell in a group of cells, wherein the feature vector for a cell includes a score value for each feature in a set of features selected for characterizing the group of cells;
clustering cells in the group into a selected number of clusters, based on distances between end points of feature vectors of the cells;
generating a list of ranked critical cells in the selected number of clusters based on a list of prioritized features associated with the set of features; and
outputting the list of ranked critical cells for use in adjusting cell layouts based on the ranked critical cells.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
clustering the cells in the group into the selected number of clusters with a k-means clustering algorithm.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
clustering the cells in the group into the selected number of clusters with a k-means clustering algorithm based upon a distance function that is related to the distances between end points of feature vectors.

### Claim 4 (depends on 1)

The method of claim 1, wherein generating the list of ranked critical cells comprises:
ranking the clusters based on the list of prioritized features.

### Claim 5 (depends on 4)

The method of claim 4, wherein generating the list of ranked critical cells comprises:
ranking cells in at least one or more ranked clusters to generate the list of ranked critical cells.

### Claim 6 (depends on 1)

The method of claim 1, wherein the group of cells is collected from an Auto Place and Route (APR) database that includes Design Rule Check (DRC) violations identified for at least a portion of cells in the APR database.

### Claim 7 (depends on 1)

The method of claim 1, wherein the feature vector for a cell includes one or more elements related to Design Rule Check (DRC) violations.

### Claim 8 (depends on 7)

The method of claim 7, wherein the one or more elements related to Design Rule Check (DRC) violations includes a number of times the cell falls directly on top of a DRC marker, a number of times the cell is adjacent to another cell which is directly on top of a DRC marker, or a number of times the cell is adjacent to another cell which is directly on top of a DRC marker at a horizontal or a vertical edge that is closest to the DRC marker.

### Claim 9 (depends on 1)

The method of claim 1, wherein the feature vector for a cell includes one or more elements related to a pin density of the cell in the APR database.

### Claim 10 (depends on 1)

The method of claim 1, wherein the feature vector for a cell includes one or more elements related to a placement density of the cell in the APR database.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
determining the selected number for clustering the cells.

### Claim 12

A computer program code stored on a non-transitory computer-readable medium, the computer program code is configured to cause a system having at least one processor to execute:
obtaining a feature vector for each cell in a group of cells, wherein the feature vector for a cell includes a score value for each feature in a set of features selected for characterizing the group of cells;
initializing a number k to an initial value; and
repetitively generating an incremental value of the number k until a stabilized condition is met, and for each value of the number k, clustering the cells into a total of k clusters and generating a list of top ranked critical cells in the k clusters.

### Claim 13 (depends on 12)

The computer program code of claim 12, wherein clustering the cells comprises:
clustering the cells into a total of k clusters with a k-means clustering algorithm

### Claim 14 (depends on 12)

The computer program code of claim 12, wherein generating the list of top ranked critical cells in the k clusters comprises:
generating a list of ranked critical cells in the k clusters based on a list of prioritized features associated with the set of features; and
selecting a predetermined number of top ranked critical cells from the list of ranked critical cells to form the list of top ranked critical cells.

### Claim 15 (depends on 12)

The computer program code of claim 12, wherein the stabilized condition is met when a comparison between a first list of top ranked critical cells for the number k and a second list of top ranked critical cells for a number k−1 indicates that the first list and the second list have identical critical cells.

### Claim 16 (depends on 12)

The computer program code of claim 12, wherein the stabilized condition is met when a comparison between a first list of top ranked critical cells for the number k and a second list of top ranked critical cells for a number k−1 indicates that the first list and the second list have no more than a threshold number of different critical cells.

### Claim 17

A computer program code stored on a non-transitory computer-readable medium, the computer program code is configured to cause a system having at least one processor to execute:
loading a list of prioritized features having priorities ordered by user inputs;
obtaining a feature vector for each cell in a group of cells, wherein the feature vector for a cell includes a score value for each feature in a set of features selected for characterizing the group of cells;
determining a selected number for clustering cells based on the list of prioritized features associated with the set of features;
clustering cells in the group into the selected number of clusters;
generating a list of ranked critical cells in the selected number of clusters based on the list of prioritized features associated with the set of features; and
outputting the list of ranked critical cells for use in adjusting cell layouts based on ranked critical cells.

### Claim 18 (depends on 17)

The computer program code of claim 17, wherein clustering the cells comprises:
clustering the cells into a total of k clusters with a k-means clustering algorithm

### Claim 19 (depends on 17)

The computer program code of claim 17, wherein determining the selected number for clustering cells comprises:
initializing a number k to an initial value;
repetitively generating an incremental value of the number k until a stabilized condition is met, and for each value of the number k, clustering the cells into a total of k clusters and generating a list of ranked critical cells in the k clusters; and
determining the list of ranked critical cells in the selected number of clusters from the list of ranked critical cells in the k clusters when the stabilized condition is met.

### Claim 20 (depends on 17)

The computer program code of claim 17, wherein generating the list of ranked critical cells in the selected number of clusters comprises:
ranking the clusters based on the list of prioritized features to generate a list of ranked clusters; and
ranking cells in each of one or more ranked clusters in the list of ranked clusters, based on the list of prioritized features, to generate the list of ranked critical cells.