# CHIP: Clustering Hotspots in Layout Using Integer Programming

Authors: Rohit Reddy Takkala; Chris Chu
Journal: Journal of Electrical and Computer Engineering
 (2019)

---

## Abstract

Clustering algorithms have been explored in recent years to solve hotspot clustering problems in integrated circuit design. With various applications in design for manufacturability flow such as hotspot library generation, systematic yield optimization, and design space exploration, generating good quality clusters along with their representative clips is of utmost importance. With several generic clustering algorithms at our disposal, hotspots can be clustered based on the distance metric defined while satisfying some tolerance conditions. However, the clusters generated from generic clustering algorithms need not achieve optimal results. In this paper, we introduce two optimal integer linear programming formulations based on triangle inequality to solve the problem of minimizing cluster count while satisfying given constraints. Apart from minimizing cluster count, we generate representative clips that best represent the clusters formed. We achieve a better cluster count for both formulations in most test cases as compared to the results published in the literature in the ICCAD 2016 contest benchmarks as well as the reference results reported in the ICCAD 2016 contest website.


---

## Body

## 1. Overview

As the feature size decreases rapidly, the problem of manufacturability in integrated circuits increases due to limitations in lithographic wavelength used during the fabrication stage. These problems identified as hotspots are a set of problematic patterns in the layout that have printing issues. These are detected either using traditional lithographic simulations or machine learning-based detection methods that have been proposed in recent years. When such defects are found, finding patterns of similar kind is of high interest. It becomes useful to cluster these clips of interest into groups and process them together. This is called layout pattern classification [1] or hotspot clustering. Layout pattern classification has been utilized in recent years in design for manufacturability flow for various applications. Few examples of such applications are hotspot library generation [2], hierarchical data storage [3], and systematic yield optimization. With several applications in the DFM stage, finding good quality clusters is important.Few works such as [4] use pattern classification within their tool flow. They use a modified version of incremental clustering where they update the representative of the clusters formed. Wu et al. [5] have worked on a modified problem statement, where they consider dummy fills during hotspot classification, can therefore accurately identify the process hotspots in the layout with dummification in EUVL. An interesting approach is adopted [6] where they shift the clips to expand the solution space while satisfying given constraints, thereby reducing the cluster count. The minimal cluster count is achieved for the ICCAD 2016 benchmark suite in their approach. Different distance metric instead in of the XOR logic is explored in [7, 8] to encapsulate rotations/mirroring and other topological features. However, using these metrics is a trade-off between computational cost and quality of the clusters generated. There are several other works such as [9–12] which focus on hotspot detection frameworks, whereas hotspot clustering has been rarely explored but plays an important role in various applications in the design for manufacturability flow.In previous work [2, 13, 14], a few generic clustering algorithms such as k-means clustering [14], hierarchical and incremental clustering [2], and Markov clustering [13, 15] were explored to solve this problem. In k-means clustering, the value of k needs to be provided by the user, but the user may not know the cluster count a priori. Therefore, it does not solve the purpose of finding good quality clusters automatically. In the hierarchical clustering algorithm, starting from each data point as a cluster, the data are hierarchically grouped together based on different types of linkages. Since hierarchical clustering finds groups of data in a hierarchical manner, it is again user dependent to get the clusters. In incremental clustering, in the order of processing data, either new clusters are created or existing clusters are grown incrementally. This algorithm depends on the order of processing data and therefore does not produce good quality solutions. Markov clustering [15] is known to find good quality clusters in a short time, but the clustering depends on fine tuning several parameters in the algorithm. There are several other clustering algorithms in the literature to cluster any kind of data; however, the problem formulations of those algorithms are different from that of the hotspot clustering problem. Therefore, a postprocessing step is required while using those algorithms to regroup clusters in order to satisfy the given constraints.In this paper, we discuss our tool called CHIP which solves the given hotspot clustering problem optimally. We formulate two integer linear programs to solve for the optimal number of clusters, i.e., the objective of both formulations is to minimize cluster count. With some tolerance given by area constraint or edge constraint, our tool classifies given clips into clusters without assuming that the representative clips must be from the given data set. Since the representative clip is not required to be one of the given clips, we generate the representative clip based on the cluster data and the tolerance provided. This framework can achieve optimal cluster count while satisfying the constraints as per the results from ICCAD 2016 Contest Problem C-Pattern Classification for Integrated Circuit Design Space Analysis [1].The paper is further organized as follows: In Section2, we describe the problem, define the terminology, and elaborate the two modes in clustering. In Section 3, we discuss the overview of our tool flow. In Section 4, we define our integer linear programming formulations which exactly represent the problem statement, and in Section 5, the framework to generate representative clips is elaborated. Furthermore, in Section 6, we report the results of the formulation and compare with existing algorithms. We conclude the work in Section 7.


## 2. Problem Description

### 2.1. Overview

This problem is taken from the ICCAD 2016 Contest-Problem C. Given a GDS file with markers and clip size and the constraints as inputs, the hotspot classification tool has to cluster the clips formed around the markers and output the corresponding cluster identities and a set of representative clips which represent the clusters. There are two types of constraints given to the tool, i.e., area constraint (a) and edge constraint (e). Based on the type of constraint, the tool has to perform clustering in the respective mode. The tool takes either area constraint or edge constraint but not both as the input.Figure1 depicts a sample layout where the polygons (in yellow) are the interconnects of a circuit indicated in a layer. On this layer, there are several markers placed at various locations throughout the layout. Given these input data, clips centered at the markers should be extracted according to the given dimensions. Note that the center of the clip can be anywhere inside the marker.Figure 1
Sample layout.We define the terminology used in the problem description as follows:Definition 1.
Marker: a marker is a polygon which locates the presence of a hotspot in the layout. These markers are placed on a different layer other than the design layer. For practical purposes, these markers are picked to be small—about the height & width of minimum width allowed in the layout.Definition 2.
Clip: a clip is defined as a set of polygons extracted from the layout, based on the position of the marker. These set of polygons are extracted by a bounding polygon (widthw and height h) with its center anywhere inside the marker. A sample clip is shown in Figure 2. For practical purposes, the center of the clip can be assumed to be the center of the marker.Figure 2
Sample clip.Definition 3.
Cluster: a cluster is a set of clips which are grouped together based on the similarity metric defined.Definition 4.
Representative clip: a representative clip is defined for each cluster which is similar to all its clips, where the degree of similarity is constrained by a tolerance parameter given as input. For practical purposes, representative clips can be chosen from existing clips for each cluster. But it need not necessarily exist in the layout.


#### 2.1.1. Additional Specifications

Mirroring of clips is allowed, i.e., 180° rotation along the axes passing through the clip’s center. Therefore, there are 4 possible combinations for each clip. This is depicted in Figure3. Also, since the clip’s center need not be at the center of the marker, clip shifting can be performed to generate a set of clips for one marker. A sample set of possible clips are depicted in Figure 4 by shifting a clip’s center. In this work, for simplicity, we consider the center of the clip to be at the center of the marker, i.e., we only consider the clip in Figure 4(a).Figure 3
Four possible configurations of a clip.
(a)
(b)
(c)
(d)Figure 4
A sample set of configurations of a clip (with shifting) [6].
(a)
(b)
(c)
(d)In general, clustering algorithms require pairwise similarity relation of data points in order to group the data into clusters. Pairwise distances of data points are one of the ways to establish the similarity measure, i.e., the greater the distance, the greater the dissimilarity. There are various types of distances used for different applications such as L1 norm for images, L2 norm for anyd-dimensional set of points, and Hamming distance for distance between two strings.In hotspot classification, each clip (xi) is represented as a w×h dimensional data point, i.e., xi∈Rd, where d=w×h. For any two clips x1 and x2, XORx1,x2 produces a clip which depicts the dissimilarity between the given two clips. Furthermore, based on the two constraints—area-constrained clustering and edge-constrained clustering—the distance metric is defined for each mode by imposing the respective constraints on the resultant clip. In the following subsections, the two constraint-based clustering modes are explained in detail.


### 2.2. Constrained Clustering

#### 2.2.1. Area-Constrained Clustering

In area-constrained clustering (ACC), the distance metric is computed based on the area of the resultant clip from exclusive OR operation applied to two clipsx1 and x2:(1)Dx1,x2=areaXORx1,x2.For example, in Figure5, two clips are overlapped against each other whose dissimilarity is depicted through arrows. In Figure 6, the resultant XOR of the two clips is shown. The distance of the clips is therefore the area of the polygons (rectangles in this case) in Figure 6, i.e., Dx1,x2=areaXORx1,x2.Figure 5
Two clips overlapped with each other [1].Figure 6
XOR of the two clips [1].Given this distance function between a pair of clips, ACC constrains the distance between any clipS in a cluster and its representative clip R as follows:(2)DR,Sw×h≤1−a,where w×h is the area of the clip and 0≤a≤1. Here, a is the parameter given to the tool which constraints the distance between the clips.Ifa=1, the tool has to perform exact clip matching. For practical purposes, a is close to 1. This constraint need not enforce two clips to be clustered together if they satisfy it. However, if two clips do not satisfy the constraint, then they cannot be clustered together.


#### 2.2.2. Edge-Constrained Clustering

In edge-constrained clustering (ECC), the distance between two clipsx1 and x2 is given by the maximum shift along an edge either inward or outward in clip x1 with respect to clip x2; that is, if ei is ith shift along one edge out of all possible edge shifts in clip x1 with respect to the clip x2, then Dx1,x2=maxe1,e2,…. An example pair of clips with edge shifts is shown in Figure 5.For any clipS in a cluster and its representative clip R, then according to ECC, the following should be satisfied:(3)DR,S≤e,where e is given as a parameter. Here, e is a nonnegative real number. For practical purposes, e is close to 0. Similar to ACC, ECC does not enforce the clips to be clustered together if they satisfy the constraint. If the clips do not satisfy the constraint, they should not be clustered together.


## 2.1. Overview

This problem is taken from the ICCAD 2016 Contest-Problem C. Given a GDS file with markers and clip size and the constraints as inputs, the hotspot classification tool has to cluster the clips formed around the markers and output the corresponding cluster identities and a set of representative clips which represent the clusters. There are two types of constraints given to the tool, i.e., area constraint (a) and edge constraint (e). Based on the type of constraint, the tool has to perform clustering in the respective mode. The tool takes either area constraint or edge constraint but not both as the input.Figure1 depicts a sample layout where the polygons (in yellow) are the interconnects of a circuit indicated in a layer. On this layer, there are several markers placed at various locations throughout the layout. Given these input data, clips centered at the markers should be extracted according to the given dimensions. Note that the center of the clip can be anywhere inside the marker.Figure 1
Sample layout.We define the terminology used in the problem description as follows:Definition 1.
Marker: a marker is a polygon which locates the presence of a hotspot in the layout. These markers are placed on a different layer other than the design layer. For practical purposes, these markers are picked to be small—about the height & width of minimum width allowed in the layout.Definition 2.
Clip: a clip is defined as a set of polygons extracted from the layout, based on the position of the marker. These set of polygons are extracted by a bounding polygon (widthw and height h) with its center anywhere inside the marker. A sample clip is shown in Figure 2. For practical purposes, the center of the clip can be assumed to be the center of the marker.Figure 2
Sample clip.Definition 3.
Cluster: a cluster is a set of clips which are grouped together based on the similarity metric defined.Definition 4.
Representative clip: a representative clip is defined for each cluster which is similar to all its clips, where the degree of similarity is constrained by a tolerance parameter given as input. For practical purposes, representative clips can be chosen from existing clips for each cluster. But it need not necessarily exist in the layout.


### 2.1.1. Additional Specifications

Mirroring of clips is allowed, i.e., 180° rotation along the axes passing through the clip’s center. Therefore, there are 4 possible combinations for each clip. This is depicted in Figure3. Also, since the clip’s center need not be at the center of the marker, clip shifting can be performed to generate a set of clips for one marker. A sample set of possible clips are depicted in Figure 4 by shifting a clip’s center. In this work, for simplicity, we consider the center of the clip to be at the center of the marker, i.e., we only consider the clip in Figure 4(a).Figure 3
Four possible configurations of a clip.
(a)
(b)
(c)
(d)Figure 4
A sample set of configurations of a clip (with shifting) [6].
(a)
(b)
(c)
(d)In general, clustering algorithms require pairwise similarity relation of data points in order to group the data into clusters. Pairwise distances of data points are one of the ways to establish the similarity measure, i.e., the greater the distance, the greater the dissimilarity. There are various types of distances used for different applications such as L1 norm for images, L2 norm for anyd-dimensional set of points, and Hamming distance for distance between two strings.In hotspot classification, each clip (xi) is represented as a w×h dimensional data point, i.e., xi∈Rd, where d=w×h. For any two clips x1 and x2, XORx1,x2 produces a clip which depicts the dissimilarity between the given two clips. Furthermore, based on the two constraints—area-constrained clustering and edge-constrained clustering—the distance metric is defined for each mode by imposing the respective constraints on the resultant clip. In the following subsections, the two constraint-based clustering modes are explained in detail.


## 2.1.1. Additional Specifications

Mirroring of clips is allowed, i.e., 180° rotation along the axes passing through the clip’s center. Therefore, there are 4 possible combinations for each clip. This is depicted in Figure3. Also, since the clip’s center need not be at the center of the marker, clip shifting can be performed to generate a set of clips for one marker. A sample set of possible clips are depicted in Figure 4 by shifting a clip’s center. In this work, for simplicity, we consider the center of the clip to be at the center of the marker, i.e., we only consider the clip in Figure 4(a).Figure 3
Four possible configurations of a clip.
(a)
(b)
(c)
(d)Figure 4
A sample set of configurations of a clip (with shifting) [6].
(a)
(b)
(c)
(d)In general, clustering algorithms require pairwise similarity relation of data points in order to group the data into clusters. Pairwise distances of data points are one of the ways to establish the similarity measure, i.e., the greater the distance, the greater the dissimilarity. There are various types of distances used for different applications such as L1 norm for images, L2 norm for anyd-dimensional set of points, and Hamming distance for distance between two strings.In hotspot classification, each clip (xi) is represented as a w×h dimensional data point, i.e., xi∈Rd, where d=w×h. For any two clips x1 and x2, XORx1,x2 produces a clip which depicts the dissimilarity between the given two clips. Furthermore, based on the two constraints—area-constrained clustering and edge-constrained clustering—the distance metric is defined for each mode by imposing the respective constraints on the resultant clip. In the following subsections, the two constraint-based clustering modes are explained in detail.


## 2.2. Constrained Clustering

### 2.2.1. Area-Constrained Clustering

In area-constrained clustering (ACC), the distance metric is computed based on the area of the resultant clip from exclusive OR operation applied to two clipsx1 and x2:(1)Dx1,x2=areaXORx1,x2.For example, in Figure5, two clips are overlapped against each other whose dissimilarity is depicted through arrows. In Figure 6, the resultant XOR of the two clips is shown. The distance of the clips is therefore the area of the polygons (rectangles in this case) in Figure 6, i.e., Dx1,x2=areaXORx1,x2.Figure 5
Two clips overlapped with each other [1].Figure 6
XOR of the two clips [1].Given this distance function between a pair of clips, ACC constrains the distance between any clipS in a cluster and its representative clip R as follows:(2)DR,Sw×h≤1−a,where w×h is the area of the clip and 0≤a≤1. Here, a is the parameter given to the tool which constraints the distance between the clips.Ifa=1, the tool has to perform exact clip matching. For practical purposes, a is close to 1. This constraint need not enforce two clips to be clustered together if they satisfy it. However, if two clips do not satisfy the constraint, then they cannot be clustered together.


### 2.2.2. Edge-Constrained Clustering

In edge-constrained clustering (ECC), the distance between two clipsx1 and x2 is given by the maximum shift along an edge either inward or outward in clip x1 with respect to clip x2; that is, if ei is ith shift along one edge out of all possible edge shifts in clip x1 with respect to the clip x2, then Dx1,x2=maxe1,e2,…. An example pair of clips with edge shifts is shown in Figure 5.For any clipS in a cluster and its representative clip R, then according to ECC, the following should be satisfied:(3)DR,S≤e,where e is given as a parameter. Here, e is a nonnegative real number. For practical purposes, e is close to 0. Similar to ACC, ECC does not enforce the clips to be clustered together if they satisfy the constraint. If the clips do not satisfy the constraint, they should not be clustered together.


## 2.2.1. Area-Constrained Clustering

In area-constrained clustering (ACC), the distance metric is computed based on the area of the resultant clip from exclusive OR operation applied to two clipsx1 and x2:(1)Dx1,x2=areaXORx1,x2.For example, in Figure5, two clips are overlapped against each other whose dissimilarity is depicted through arrows. In Figure 6, the resultant XOR of the two clips is shown. The distance of the clips is therefore the area of the polygons (rectangles in this case) in Figure 6, i.e., Dx1,x2=areaXORx1,x2.Figure 5
Two clips overlapped with each other [1].Figure 6
XOR of the two clips [1].Given this distance function between a pair of clips, ACC constrains the distance between any clipS in a cluster and its representative clip R as follows:(2)DR,Sw×h≤1−a,where w×h is the area of the clip and 0≤a≤1. Here, a is the parameter given to the tool which constraints the distance between the clips.Ifa=1, the tool has to perform exact clip matching. For practical purposes, a is close to 1. This constraint need not enforce two clips to be clustered together if they satisfy it. However, if two clips do not satisfy the constraint, then they cannot be clustered together.


## 2.2.2. Edge-Constrained Clustering

In edge-constrained clustering (ECC), the distance between two clipsx1 and x2 is given by the maximum shift along an edge either inward or outward in clip x1 with respect to clip x2; that is, if ei is ith shift along one edge out of all possible edge shifts in clip x1 with respect to the clip x2, then Dx1,x2=maxe1,e2,…. An example pair of clips with edge shifts is shown in Figure 5.For any clipS in a cluster and its representative clip R, then according to ECC, the following should be satisfied:(3)DR,S≤e,where e is given as a parameter. Here, e is a nonnegative real number. For practical purposes, e is close to 0. Similar to ACC, ECC does not enforce the clips to be clustered together if they satisfy the constraint. If the clips do not satisfy the constraint, they should not be clustered together.


## 3. Overview of the Tool

The proposed tool flow is discussed in this chapter. Figure7(a) shows our proposed tool flow with the steps. In the layout data processing step, we convert all the polygons into rectangles for easier data processing. We then handle the layout data (in rectangles) using a grid structure in order to speed up the process of clip extraction. In distance computation step, we reorient all clips in a canonical way to consider mirroring of the clips. Exact pattern matching is performed to reduce data size, and therefore, redundant computations are avoided in the subsequent steps.Figure 7
Overview of the tool and preprocessing step. (a) An overview of the tool. (b) Layout data processing.
(a)
(b)Then, we compute the pairwise distances between these reduced data according to the constraint type. Using this distance matrix (D) and given tolerance (Dc, which is determined by either a or e depending on the constraint type), in the clustering step, an optimizer is called to solve the optimization problem based on the formulations discussed in Section 4 and an optimal solution is arrived along with the cluster indices. Furthermore, since we assume each cluster need not have its representative amongst given data, we use ILP formulation again to search feasible solution space to generate the representative clip. The following subsections and chapters discuss each step in our proposed flow in detail.


### 3.1. Layout Data Processing

In this step, firstly, the polygons are converted into rectangles using a standard algorithm. Note that this conversion need not be optimal in nature. Then, the entire layout is divided into a grid structure where each unit is of widthw and height h as shown in Figure 7(b). With this grid structure, the rectangles overlapping each grid are stored in a data structure. While extracting the clip for a given marker, we use the information stored in the data structure to take relevant rectangles to form the clip. This process avoids scanning all rectangles and finding intersection between them and the clips of interest. This is illustrated in Figure 7(b). At most 4 grid structures and correspondingly the rectangles present in them are scanned for any clip to be extracted.


### 3.2. Distance Computation

#### 3.2.1. Reorientation

Since we consider reflections alongx-axis or y-axis or both, in this step, before computing distances between the clips based on area or edge constraint, we perform reorientation of the clips in a canonical way. We compute the center of mass (COM) for a given clip and divide the clip into 4 quadrants. Here, center of mass metric is defined as follows.Letai be a clip which is mapped to a R2 space with w×h number of data points, with the range −w/2 to w/2 on the x-axis, −h/2 to h/2 on the y-axis, and the center of the clip at (0, 0). With this mapping, if there is a pixel at x,y, then its value is 1, i.e., aix,y=1 and 0 otherwise. Let xc,yc represent the center of mass of this notation. Therefore,(4)xc=∑x=−w/2w/2∑y=−h/2h/2aix,y∗x∑x=−w/2w/2∑y=−h/2h/2aix,y,yc=∑x=−w/2w/2∑y=−h/2h/2aix,y∗y∑x=−w/2w/2∑y=−h/2h/2aix,y.Then, we orient all the clips such that every clip’s COM is in a fixed quadrant, e.g., lower-left quadrant as shown in Figure8. This preprocessing step enables us to find exact clip matching patterns. In Figures 8(a)–8(d), all possible reflections along the axes are indicated, and Figure 8(e) is the canonical representation of all orientations. Note that in case the center of mass is closer to the origin, then a higher order metric can be computed to shift the COM away from the origin.Figure 8
Reorientation of the clip.
(a)
(b)
(c)
(d)
(e)


#### 3.2.2. Clip Matching

Once the clips are reoriented in a canonical way, clip matching step is performed in order to merge exact clips in the given data. In an IC with millions of gates, it is most likely to find identical patterns in the layout, and hence, this step would reduce the amount of data to be processed. Exact clip matching can be performed with pattern matching algorithms or by string comparison if each clip is encoded into a string as proposed in [4].In this work, exact clip matching is performed in two levels. First, the given data are divided into different bins, where a bin contains all the clips of same area. Then, the clips in each of the bins are iterated through, with new clusters formed whenever there is a mismatch with the existing clusters in the bin; that is, incremental clustering is performed, where two or more clips are clustered together if the pairwise distance between them is zero.To compute the distance between the two clips, each clip is divided into a nonuniform grid where the grid lines are along the boundaries of the polygons on the two clips. Therefore, each grid in the clip is either completely covered by a polygon or completely empty and, hence, can now be represented by a binary value. As a result, the distance of the two clips can be easily computed based on the binary values for each grid and its corresponding area, as shown in Figure9.Figure 9
Grid data structure to compute distance.
(a)
(b)
(c)
(d)


#### 3.2.3. Distance Computation

In this final step, pairwise distances are computed between the reduced set of clips. To compute the distance between the two clips, each clip is divided into nonuniform grids where the grid lines are along the boundaries of the polygons on the two clips as discussed in the Section3.2.2. Therefore, the distance between a pair of clips can be easily computed based on the binary values for each grid and its corresponding area, as shown in Figure 9.


## 3.1. Layout Data Processing

In this step, firstly, the polygons are converted into rectangles using a standard algorithm. Note that this conversion need not be optimal in nature. Then, the entire layout is divided into a grid structure where each unit is of widthw and height h as shown in Figure 7(b). With this grid structure, the rectangles overlapping each grid are stored in a data structure. While extracting the clip for a given marker, we use the information stored in the data structure to take relevant rectangles to form the clip. This process avoids scanning all rectangles and finding intersection between them and the clips of interest. This is illustrated in Figure 7(b). At most 4 grid structures and correspondingly the rectangles present in them are scanned for any clip to be extracted.


## 3.2. Distance Computation

### 3.2.1. Reorientation

Since we consider reflections alongx-axis or y-axis or both, in this step, before computing distances between the clips based on area or edge constraint, we perform reorientation of the clips in a canonical way. We compute the center of mass (COM) for a given clip and divide the clip into 4 quadrants. Here, center of mass metric is defined as follows.Letai be a clip which is mapped to a R2 space with w×h number of data points, with the range −w/2 to w/2 on the x-axis, −h/2 to h/2 on the y-axis, and the center of the clip at (0, 0). With this mapping, if there is a pixel at x,y, then its value is 1, i.e., aix,y=1 and 0 otherwise. Let xc,yc represent the center of mass of this notation. Therefore,(4)xc=∑x=−w/2w/2∑y=−h/2h/2aix,y∗x∑x=−w/2w/2∑y=−h/2h/2aix,y,yc=∑x=−w/2w/2∑y=−h/2h/2aix,y∗y∑x=−w/2w/2∑y=−h/2h/2aix,y.Then, we orient all the clips such that every clip’s COM is in a fixed quadrant, e.g., lower-left quadrant as shown in Figure8. This preprocessing step enables us to find exact clip matching patterns. In Figures 8(a)–8(d), all possible reflections along the axes are indicated, and Figure 8(e) is the canonical representation of all orientations. Note that in case the center of mass is closer to the origin, then a higher order metric can be computed to shift the COM away from the origin.Figure 8
Reorientation of the clip.
(a)
(b)
(c)
(d)
(e)


### 3.2.2. Clip Matching

Once the clips are reoriented in a canonical way, clip matching step is performed in order to merge exact clips in the given data. In an IC with millions of gates, it is most likely to find identical patterns in the layout, and hence, this step would reduce the amount of data to be processed. Exact clip matching can be performed with pattern matching algorithms or by string comparison if each clip is encoded into a string as proposed in [4].In this work, exact clip matching is performed in two levels. First, the given data are divided into different bins, where a bin contains all the clips of same area. Then, the clips in each of the bins are iterated through, with new clusters formed whenever there is a mismatch with the existing clusters in the bin; that is, incremental clustering is performed, where two or more clips are clustered together if the pairwise distance between them is zero.To compute the distance between the two clips, each clip is divided into a nonuniform grid where the grid lines are along the boundaries of the polygons on the two clips. Therefore, each grid in the clip is either completely covered by a polygon or completely empty and, hence, can now be represented by a binary value. As a result, the distance of the two clips can be easily computed based on the binary values for each grid and its corresponding area, as shown in Figure9.Figure 9
Grid data structure to compute distance.
(a)
(b)
(c)
(d)


### 3.2.3. Distance Computation

In this final step, pairwise distances are computed between the reduced set of clips. To compute the distance between the two clips, each clip is divided into nonuniform grids where the grid lines are along the boundaries of the polygons on the two clips as discussed in the Section3.2.2. Therefore, the distance between a pair of clips can be easily computed based on the binary values for each grid and its corresponding area, as shown in Figure 9.


## 3.2.1. Reorientation

Since we consider reflections alongx-axis or y-axis or both, in this step, before computing distances between the clips based on area or edge constraint, we perform reorientation of the clips in a canonical way. We compute the center of mass (COM) for a given clip and divide the clip into 4 quadrants. Here, center of mass metric is defined as follows.Letai be a clip which is mapped to a R2 space with w×h number of data points, with the range −w/2 to w/2 on the x-axis, −h/2 to h/2 on the y-axis, and the center of the clip at (0, 0). With this mapping, if there is a pixel at x,y, then its value is 1, i.e., aix,y=1 and 0 otherwise. Let xc,yc represent the center of mass of this notation. Therefore,(4)xc=∑x=−w/2w/2∑y=−h/2h/2aix,y∗x∑x=−w/2w/2∑y=−h/2h/2aix,y,yc=∑x=−w/2w/2∑y=−h/2h/2aix,y∗y∑x=−w/2w/2∑y=−h/2h/2aix,y.Then, we orient all the clips such that every clip’s COM is in a fixed quadrant, e.g., lower-left quadrant as shown in Figure8. This preprocessing step enables us to find exact clip matching patterns. In Figures 8(a)–8(d), all possible reflections along the axes are indicated, and Figure 8(e) is the canonical representation of all orientations. Note that in case the center of mass is closer to the origin, then a higher order metric can be computed to shift the COM away from the origin.Figure 8
Reorientation of the clip.
(a)
(b)
(c)
(d)
(e)


## 3.2.2. Clip Matching

Once the clips are reoriented in a canonical way, clip matching step is performed in order to merge exact clips in the given data. In an IC with millions of gates, it is most likely to find identical patterns in the layout, and hence, this step would reduce the amount of data to be processed. Exact clip matching can be performed with pattern matching algorithms or by string comparison if each clip is encoded into a string as proposed in [4].In this work, exact clip matching is performed in two levels. First, the given data are divided into different bins, where a bin contains all the clips of same area. Then, the clips in each of the bins are iterated through, with new clusters formed whenever there is a mismatch with the existing clusters in the bin; that is, incremental clustering is performed, where two or more clips are clustered together if the pairwise distance between them is zero.To compute the distance between the two clips, each clip is divided into a nonuniform grid where the grid lines are along the boundaries of the polygons on the two clips. Therefore, each grid in the clip is either completely covered by a polygon or completely empty and, hence, can now be represented by a binary value. As a result, the distance of the two clips can be easily computed based on the binary values for each grid and its corresponding area, as shown in Figure9.Figure 9
Grid data structure to compute distance.
(a)
(b)
(c)
(d)


## 3.2.3. Distance Computation

In this final step, pairwise distances are computed between the reduced set of clips. To compute the distance between the two clips, each clip is divided into nonuniform grids where the grid lines are along the boundaries of the polygons on the two clips as discussed in the Section3.2.2. Therefore, the distance between a pair of clips can be easily computed based on the binary values for each grid and its corresponding area, as shown in Figure 9.


## 4. ILP Formulations

One of the objectives of the problem is to minimize the cluster count while satisfying the tolerance in terms of ACC/ECC. In the following formulations, we define the objective of the ILP as minimizing the number of clusters. Therefore, the optimizer solves for the optimal number of clusters for a given constraint. Also, we leverage the idea of triangle inequality, as defined in Proposition 1, in order to generate the minimal cluster count; that is, the representative clip need not be chosen from the given clips, and therefore, we explore the solution space without unnecessary restrictions while satisfying the given constraints. We formulate two integer linear programming approaches describing the given problem in different ways. Both these formulations are described in the following subsections.


### 4.1. CHIP Node

In this formulation, we describe the clustering problem using nodes as variables, where each node is assigned a cluster identity based on the distance metric and the constraints. We defineCi as the variable representing each data point i, and its value indicates the cluster index of that data point:(5)Ci=Cj⟺i,j∈same  cluster,Ci≠Cj⟺i,j∉same  cluster,∀i,j=1,2,…n,where n=number  of  data  points.Here, the variablesCi are upper bounded by another variable, K, representing the cluster count, i.e., 1≤Ci≤K, ∀i=1,2,…,n and K≥1. With this setup, the objective to minimize the cluster count is to minimize K in our formulation.LetDi,j be the distance between ith clip and jth clip and the constrained distance be Dc.Proposition 1.
Triangle inequality for clustering: given a cluster of clips and the distance constraintDc, if Di,j≤2×Dc, ∀i,j∈samecluster, then ∃ r such that Di,r≤Dc⋅∀i.ILP Formulation:
Objective: minimizeK.
Constraints: ∀i≠j(6)Ci≥Cj+1−2DcDi,j−Sij×H,Ci≤Cj−1−2DcDi,j+1−Sij×H.Here,His a huge constant,Ciisinteger∀iandSijis0or1∀i,j.
Bounds: 1≤Ci≤K∀iThe above two constraints enforce the condition that if the distance between two clips (i and j) Di,j>2Dc, then the two clips (nodes) cannot be clustered together, i.e., Ci≠Cj. However, the constraints can be ignored whenever the distance constraint is satisfied; that is, the clips can be either clustered together or not. This is elaborated in the following two cases:Case 1.
IfDi,j>2Dc:Constraints:(7)Ci≥Cj+ϵ−Sij×H,Ci≤Cj−ϵ+1−Sij×H⟹Ci≠Cj.
Note: Here,ε is a small value.Case 2.
IfDi,j≤2Dc:Constraints:Ci≤Cj or Ci≥Cj depending on the value of Sij.
Note that a preprocessing step elaborated in Section3.2.2 is applied to eliminate exactly the matched patterns. Hence, Di,j will never be zero in this formulation.


#### 4.1.1. Area-Constrained Clustering

In the case of area-constrained clustering,Di,j=areaXORxi,xj as defined in Section 2.2.1 and Dc=w×h×1−a, where a is the area constraint ranging between 0 and 1. Notice that, for a = 1, Dc=0⟹Ci≠Cj, ∀i,j.


#### 4.1.2. Edge-Constrained Clustering

In the case of edge-constrained clustering,Di,j=maxe1,e2,… as defined in Section 2.2.2 and Dc=e, where e is the given edge constraint (in nm).


### 4.2. CHIP Edge

In the 2nd formulation, we describe the clustering problem using edges, where two nodes connected by an edge are clustered together. We define that the objective of the ILP is to minimize the number of clusters. Similar to the previous formulation, we leverage the idea of triangle inequality in order to generate minimal cluster count; that is, the representative clip need not be chosen from the given clips, and therefore, we explore the solution space without unnecessary restrictions while satisfying the given constraints.We define a graph where the nodes are clips and the edges between them indicate whether the clips can be clustered together. We definesij as a variable indicating whether two clips i and j are clustered together, i.e., sij=1 if i, j are clustered together and 0 otherwise ∀i,j.In other words,(8)sij=1⟺i,j∈same  cluster,sij=0⟺i,j∉same  cluster,∀i,j=1,2,…,n.Thesesij variables are given as input (constant value = 0) if two clips cannot be clustered together. Else, they can take either 0 or 1 (variable in the formulation). This is based on the condition that two clips cannot be clustered together if the distance constraint is not satisfied. However, they can either be clustered or not, if the distance constraint is satisfied.ILP Formulation:Objective: minimize n−∑i<jtijConstraints:(9)tij≤sij∀i<j,(10)tij≤2−ski−skj∀k<i<j,(11)sij+sjk−2×sik≤1,∀i,jandkwhere1≤i,j,k≤n,i≠j≠k.Here, constraint (11) enforces the condition that if i and j are in the same cluster and j and k are in same the cluster, then i and k has to be in the same cluster.Apart fromsij, binary variables tij are introduced.Constraint (9) implies that tij must be 0 if sij is 0. Even if sij=1, if there exists k such that k<i<j and both ski and skj are 1, then tij must be 0 too. Therefore, tij can be 1 if i<j is the node with the smallest index in the cluster defined by s = 1 containing the edge ij.As the sum,∑i,jtij is maximized, the edges with tij=1 will define a spanning forest (i.e., collection of trees) which is a subgraph of the graph defined by the edges with sij=1.Here, the summation,∑i,jtij, indicates the summation of [number of cluster members − 1] of all the clusters. Therefore, it can be observed that the objective n−∑i<jtij=K, where K is the number of clusters as per the 1st formulation.Example for CHIP Edge. Let there be 9 clips (nodes). Given, a pairwise distance relation amongst these 9 clips, the graph formed (with sij as edges) at an instance during the optimization is shown in Figure 10. According to the constraints, the variables tij take the values 0 or 1. The resultant graph with tij as edges is shown in Figure 11. From this figure, the objective value can be computed, which is 9−2+3+1=9−6=3 (=number of clusters).Figure 10
Example for the CHIP edge formulation (withsij as edges).
(a)
(b)
(c)Figure 11
Example for the CHIP edge formulation (withtij as edges).
(a)
(b)
(c)


#### 4.2.1. Area-Constrained Clustering

In the case of area-constrained clustering,Di,j=areaXORxi,xj as defined in Section 2.2.1 and Dc=w×h×1−a, where a is the area-constraint ranging between 0 and 1.


#### 4.2.2. Edge-Constrained Clustering

In the case of edge-constrained clustering,Di,j=maxe1,e2,… as defined in Section 2.2.2 and Dc=e, where e is the given edge constraint (in nm).


## 4.1. CHIP Node

In this formulation, we describe the clustering problem using nodes as variables, where each node is assigned a cluster identity based on the distance metric and the constraints. We defineCi as the variable representing each data point i, and its value indicates the cluster index of that data point:(5)Ci=Cj⟺i,j∈same  cluster,Ci≠Cj⟺i,j∉same  cluster,∀i,j=1,2,…n,where n=number  of  data  points.Here, the variablesCi are upper bounded by another variable, K, representing the cluster count, i.e., 1≤Ci≤K, ∀i=1,2,…,n and K≥1. With this setup, the objective to minimize the cluster count is to minimize K in our formulation.LetDi,j be the distance between ith clip and jth clip and the constrained distance be Dc.Proposition 1.
Triangle inequality for clustering: given a cluster of clips and the distance constraintDc, if Di,j≤2×Dc, ∀i,j∈samecluster, then ∃ r such that Di,r≤Dc⋅∀i.ILP Formulation:
Objective: minimizeK.
Constraints: ∀i≠j(6)Ci≥Cj+1−2DcDi,j−Sij×H,Ci≤Cj−1−2DcDi,j+1−Sij×H.Here,His a huge constant,Ciisinteger∀iandSijis0or1∀i,j.
Bounds: 1≤Ci≤K∀iThe above two constraints enforce the condition that if the distance between two clips (i and j) Di,j>2Dc, then the two clips (nodes) cannot be clustered together, i.e., Ci≠Cj. However, the constraints can be ignored whenever the distance constraint is satisfied; that is, the clips can be either clustered together or not. This is elaborated in the following two cases:Case 1.
IfDi,j>2Dc:Constraints:(7)Ci≥Cj+ϵ−Sij×H,Ci≤Cj−ϵ+1−Sij×H⟹Ci≠Cj.
Note: Here,ε is a small value.Case 2.
IfDi,j≤2Dc:Constraints:Ci≤Cj or Ci≥Cj depending on the value of Sij.
Note that a preprocessing step elaborated in Section3.2.2 is applied to eliminate exactly the matched patterns. Hence, Di,j will never be zero in this formulation.


### 4.1.1. Area-Constrained Clustering

In the case of area-constrained clustering,Di,j=areaXORxi,xj as defined in Section 2.2.1 and Dc=w×h×1−a, where a is the area constraint ranging between 0 and 1. Notice that, for a = 1, Dc=0⟹Ci≠Cj, ∀i,j.


### 4.1.2. Edge-Constrained Clustering

In the case of edge-constrained clustering,Di,j=maxe1,e2,… as defined in Section 2.2.2 and Dc=e, where e is the given edge constraint (in nm).


## 4.1.1. Area-Constrained Clustering

In the case of area-constrained clustering,Di,j=areaXORxi,xj as defined in Section 2.2.1 and Dc=w×h×1−a, where a is the area constraint ranging between 0 and 1. Notice that, for a = 1, Dc=0⟹Ci≠Cj, ∀i,j.


## 4.1.2. Edge-Constrained Clustering

In the case of edge-constrained clustering,Di,j=maxe1,e2,… as defined in Section 2.2.2 and Dc=e, where e is the given edge constraint (in nm).


## 4.2. CHIP Edge

In the 2nd formulation, we describe the clustering problem using edges, where two nodes connected by an edge are clustered together. We define that the objective of the ILP is to minimize the number of clusters. Similar to the previous formulation, we leverage the idea of triangle inequality in order to generate minimal cluster count; that is, the representative clip need not be chosen from the given clips, and therefore, we explore the solution space without unnecessary restrictions while satisfying the given constraints.We define a graph where the nodes are clips and the edges between them indicate whether the clips can be clustered together. We definesij as a variable indicating whether two clips i and j are clustered together, i.e., sij=1 if i, j are clustered together and 0 otherwise ∀i,j.In other words,(8)sij=1⟺i,j∈same  cluster,sij=0⟺i,j∉same  cluster,∀i,j=1,2,…,n.Thesesij variables are given as input (constant value = 0) if two clips cannot be clustered together. Else, they can take either 0 or 1 (variable in the formulation). This is based on the condition that two clips cannot be clustered together if the distance constraint is not satisfied. However, they can either be clustered or not, if the distance constraint is satisfied.ILP Formulation:Objective: minimize n−∑i<jtijConstraints:(9)tij≤sij∀i<j,(10)tij≤2−ski−skj∀k<i<j,(11)sij+sjk−2×sik≤1,∀i,jandkwhere1≤i,j,k≤n,i≠j≠k.Here, constraint (11) enforces the condition that if i and j are in the same cluster and j and k are in same the cluster, then i and k has to be in the same cluster.Apart fromsij, binary variables tij are introduced.Constraint (9) implies that tij must be 0 if sij is 0. Even if sij=1, if there exists k such that k<i<j and both ski and skj are 1, then tij must be 0 too. Therefore, tij can be 1 if i<j is the node with the smallest index in the cluster defined by s = 1 containing the edge ij.As the sum,∑i,jtij is maximized, the edges with tij=1 will define a spanning forest (i.e., collection of trees) which is a subgraph of the graph defined by the edges with sij=1.Here, the summation,∑i,jtij, indicates the summation of [number of cluster members − 1] of all the clusters. Therefore, it can be observed that the objective n−∑i<jtij=K, where K is the number of clusters as per the 1st formulation.Example for CHIP Edge. Let there be 9 clips (nodes). Given, a pairwise distance relation amongst these 9 clips, the graph formed (with sij as edges) at an instance during the optimization is shown in Figure 10. According to the constraints, the variables tij take the values 0 or 1. The resultant graph with tij as edges is shown in Figure 11. From this figure, the objective value can be computed, which is 9−2+3+1=9−6=3 (=number of clusters).Figure 10
Example for the CHIP edge formulation (withsij as edges).
(a)
(b)
(c)Figure 11
Example for the CHIP edge formulation (withtij as edges).
(a)
(b)
(c)


### 4.2.1. Area-Constrained Clustering

In the case of area-constrained clustering,Di,j=areaXORxi,xj as defined in Section 2.2.1 and Dc=w×h×1−a, where a is the area-constraint ranging between 0 and 1.


### 4.2.2. Edge-Constrained Clustering

In the case of edge-constrained clustering,Di,j=maxe1,e2,… as defined in Section 2.2.2 and Dc=e, where e is the given edge constraint (in nm).


## 4.2.1. Area-Constrained Clustering

In the case of area-constrained clustering,Di,j=areaXORxi,xj as defined in Section 2.2.1 and Dc=w×h×1−a, where a is the area-constraint ranging between 0 and 1.


## 4.2.2. Edge-Constrained Clustering

In the case of edge-constrained clustering,Di,j=maxe1,e2,… as defined in Section 2.2.2 and Dc=e, where e is the given edge constraint (in nm).


## 5. Representative Clip Generation

In this section, we discuss the framework to generate representative clips for the clusters formed in the clustering step. Firstly, each cluster is checked whether there exists any clip among the cluster members that satisfies the constraints to be a representative clip. If a representative clip does not exist amongst the given clips, then we proceed to the following steps: (1) data preprocessing; (2) MILP formulation; and (3) representative clip generation, and these steps are discussed in the following subsections.


### 5.1. Data Preprocessing

In this step, we build a grid data structure formed along the edges of polygons of all the clips in the cluster. This structure is similar to that used in distance computation in Section3.2.2, where only two clips are used to form the grid data structure as compared to considering all the clips in the cluster in this step. Using this structure, we can represent each clip in the cluster using a vector where each dimension represents the area covered by a polygon in a particular grid. Each grid data structure is unique with respect to the clusters.


### 5.2. MILP Formulation

Using the grid data structure, we formulate a mixed integer linear program to find a feasible solution that satisfies the given constraints. This feasible solution is then used to generate the representative clip.Formulation:Letc1,c2,c3,…,cq be a set of clips which belong to a cluster and cr be its representative clip. Therefore, as per the clustering formulations, ∃cr such that Dcr,ci≤Dc,∀i=1,2,…,n where Dc is the given constraint.Let the number of grids in the grid data structure of a particular cluster bed; that is, the given clips and the representative clip of the cluster can be represented by a d-dimensional vector with corresponding areas Aj as upper bound for each dimension. Let the vector be represented by(12)ci=ci1,ci2,ci3,…,cid,where each cij≤Aj,∀j.For a cluster, we define anotherd-dimensional vector called the area vector (A) where A=A1,A2,A3,…,Ad; that is, each Ai is the area of a grid in the grid data structure.Based on the grid structure formulation, each given clip in the cluster can be represented by either 0 (empty) orAj (filled) ∀j. Therefore, distance between cr and ci can be written as a linear function.For example, let area vector of a cluster beA=10020015050 and one of the clips c1 be 100200050⟹Dcr,c1=100−cr1+200−cr2+cr3+50−cr4.Objective: No objectiveConstraints: ∀i(13)Dcr,ci≤Dc.Bounds: crj≤AjAs per the constraints and bounds, each variablecrj takes values from 0 to Aj∀j; that is, it takes continuous values rather than discrete. These values are then used to fill the grids using heuristics discussed in the next subsection.Finding feasible solution step can be further sped up by removing redundant dimensions (grids) which are either always empty or always filled in all the clips of a cluster.


### 5.3. Representative Clip Generation

In this subsection, a heuristic is proposed to generate the representative clip as described in Algorithm1. From the feasible solution of MILP formulation, we obtain a solution vector of continuous variables, where each dimension is in the range [0, Aj]. Let the result vector be represented by cr=cr1,cr2,cr3,…,crd.Algorithm 1: Representative clip generation.
(1)
function CLIPGENERATION (cr,c)
(2)
for each dimension in grid data structure do
(3)
if crj=Aj then
(4)
fill the grid completely
(5)
if crj<Aj then
(6)
if PREFERENCE (l, r, t, b) = xthen
(7)
while fill<crj do
(8)
fill the grid with horizontal rows of pixels
(9)
if PREFERENCE (l, r, t, b) = ythen
(10)
while fill<crj do
(11)
fill the grid with vertical rows of pixels
(12)
function PREFERENCE (l, r, t, b)
(13)
neighbors=crl,crr,crt,crb;
(14)
sort theneighbors vector in descending order;
(15)
if most filled cell is left or right then return y
(16)
else return xIn Algorithm1, crl, crr, crt, and crb represent the neighboring grids (left, right, top, and bottom, respectively) of a grid in cr. In this algorithm, if crj=Aj, we fill the grid entirely. If crj<Aj, then the grid has to be filled partially. This can either be done along the x-axis or y-axis, until the condition is satisfied. For uniformity, we design a heuristic function (PREFERENCE in Algorithm 1) to capture the local neighborhood and fill the grid accordingly.


## 5.1. Data Preprocessing

In this step, we build a grid data structure formed along the edges of polygons of all the clips in the cluster. This structure is similar to that used in distance computation in Section3.2.2, where only two clips are used to form the grid data structure as compared to considering all the clips in the cluster in this step. Using this structure, we can represent each clip in the cluster using a vector where each dimension represents the area covered by a polygon in a particular grid. Each grid data structure is unique with respect to the clusters.


## 5.2. MILP Formulation

Using the grid data structure, we formulate a mixed integer linear program to find a feasible solution that satisfies the given constraints. This feasible solution is then used to generate the representative clip.Formulation:Letc1,c2,c3,…,cq be a set of clips which belong to a cluster and cr be its representative clip. Therefore, as per the clustering formulations, ∃cr such that Dcr,ci≤Dc,∀i=1,2,…,n where Dc is the given constraint.Let the number of grids in the grid data structure of a particular cluster bed; that is, the given clips and the representative clip of the cluster can be represented by a d-dimensional vector with corresponding areas Aj as upper bound for each dimension. Let the vector be represented by(12)ci=ci1,ci2,ci3,…,cid,where each cij≤Aj,∀j.For a cluster, we define anotherd-dimensional vector called the area vector (A) where A=A1,A2,A3,…,Ad; that is, each Ai is the area of a grid in the grid data structure.Based on the grid structure formulation, each given clip in the cluster can be represented by either 0 (empty) orAj (filled) ∀j. Therefore, distance between cr and ci can be written as a linear function.For example, let area vector of a cluster beA=10020015050 and one of the clips c1 be 100200050⟹Dcr,c1=100−cr1+200−cr2+cr3+50−cr4.Objective: No objectiveConstraints: ∀i(13)Dcr,ci≤Dc.Bounds: crj≤AjAs per the constraints and bounds, each variablecrj takes values from 0 to Aj∀j; that is, it takes continuous values rather than discrete. These values are then used to fill the grids using heuristics discussed in the next subsection.Finding feasible solution step can be further sped up by removing redundant dimensions (grids) which are either always empty or always filled in all the clips of a cluster.


## 5.3. Representative Clip Generation

In this subsection, a heuristic is proposed to generate the representative clip as described in Algorithm1. From the feasible solution of MILP formulation, we obtain a solution vector of continuous variables, where each dimension is in the range [0, Aj]. Let the result vector be represented by cr=cr1,cr2,cr3,…,crd.Algorithm 1: Representative clip generation.
(1)
function CLIPGENERATION (cr,c)
(2)
for each dimension in grid data structure do
(3)
if crj=Aj then
(4)
fill the grid completely
(5)
if crj<Aj then
(6)
if PREFERENCE (l, r, t, b) = xthen
(7)
while fill<crj do
(8)
fill the grid with horizontal rows of pixels
(9)
if PREFERENCE (l, r, t, b) = ythen
(10)
while fill<crj do
(11)
fill the grid with vertical rows of pixels
(12)
function PREFERENCE (l, r, t, b)
(13)
neighbors=crl,crr,crt,crb;
(14)
sort theneighbors vector in descending order;
(15)
if most filled cell is left or right then return y
(16)
else return xIn Algorithm1, crl, crr, crt, and crb represent the neighboring grids (left, right, top, and bottom, respectively) of a grid in cr. In this algorithm, if crj=Aj, we fill the grid entirely. If crj<Aj, then the grid has to be filled partially. This can either be done along the x-axis or y-axis, until the condition is satisfied. For uniformity, we design a heuristic function (PREFERENCE in Algorithm 1) to capture the local neighborhood and fill the grid accordingly.


## 6. Experimental Results

We implemented our approach using C++ programming language with STL and Boost libraries. We use IBM CPLEX Optimizer [17] to solve the integer linear program. We performed the experiments based on the benchmarks provided by ICCAD 2016 Contest as shown in Table 1. A 1.7 GHz dual-core system with a memory of 8 GB is used to perform the evaluation. Since the results reported in contest and the papers are based on experiments conducted in different platforms (8 Core 2.3 GHz KVM Processors and with 64 GB memory), the runtime reported here is used to get a rough estimation but not to be compared with the previous results. In some test cases, we found the optimization to exceed the time limit of 2 hours as per the contest. Therefore, for practical purposes, linear/binary search is performed for the minimal k value, where each iteration of the optimization is limited by time threshold. Without such time threshold, the optimization may consume more than 2 hours.Table 1
Benchmarks from ICCAD 2016.
Test case
No. of markers
No. of polygons
Clip size
1
16
77
200
×
200
2
200
845
200
×
200
3
5068
9779
200
×
200
4
264824
147764
250
×
250From Table2, it can be observed that the ILP formulations, which solve the constrained clustering problem, scale well for the test cases, due to the reduction in data size after exact pattern matching is performed in prior steps. Also, we observe that default case (exact pattern matching) takes majority of the runtime (from Table 3). It can be easily reduced with the parallelization of the exact pattern matching tasks. In future work, the preprocessing steps could be further optimized in order to reduce the bottleneck of our tool and therefore achieve even faster overall runtime for the tool.Table 2
Constrained clustering—comparison of CHIP v/s others (runtime (s)).
Test case
Constraints
Reference [1] (Te+Tc)
iClaire [13] (Tc)
GRASP [18] (Te+Tc)
Chen et al. [6] (Tc)
CHIP node (Tc)
CHIP edge (Tc)
1
acc = 0.95e = 4
1.808
0.004
0.001
0.01
0.01
0.08
1.324
0.004
0.001
0.03
0.02
0.06
2
acc = 0.9e = 4
1.168
0.006
0.014
0.05
0.09
2.6
0.874
0.007
0.017
0.19
0.09
0.68
3
acc = 0.85e = 8
1.232
0.020
0.159
0.15
1.09
28.4
1.311
0.040
0.161
1.04
6.44
25.1
4
acc = 0.99e = 2
4.740
0.1
2.352
21
15.1
35.3
4.364
0310
2.428
39
13.4
29.7Table 3
Exact pattern matching (default constraint).
Test case
iClaire [13]
Our approach
#Clusters (CC)
Runtime,Te (s)
#Clusters (CC)
Runtime,Te (s)
1
8
0.001
8
0.012
2
26
0.004
26
0.047
3
70
0.060
70
0.760
4
72
4.170
72
125.2Based on Table4, we achieve better results in most of the test cases in terms of the cluster count as compared to previous work. Since we perform a search for the minimal k value, where each iteration of the optimization is limited by time threshold (for practical run times), optimality is not seen in some of the test cases. Also, due to this search, different cluster counts are seen for CHIP node and CHIP edge, which should otherwise return the same optimal cluster count, i.e., both CHIP node and CHIP edge are optimal in theory. It is also observed that CHIP node is better in practice as compared to CHIP edge in both runtime and cluster count. Even though we do not adopt clip shifting, we achieve results that are comparable to the results in [6], which are best in terms of the cluster count so far but employ clip shifting. Also, clip shifting could be easily added to our formulations to further reduce the cluster count.Table 4
Constrained clustering—comparison of CHIP v/s others (cluster count).
Test case
Constraints
Reference [1]
iClaire [13]
GRASP [18]
Chen et al. [6]
CHIP node
CHIP edge
1
acc = 0.95e = 4
4
3
3
3
3
3
5
5
5
5
5
5
2
acc = 0.9e = 4
10
7
11
4
4
5
18
18
18
13
18
18
3
acc = 0.85e = 8
26
13
13
8
8
10
52
37
47
34
39
39
4
acc = 0.99e = 2
31
24
24
17
21
21
57
46
52
44
48
48


## 7. Conclusion

In this paper, we introduce the problem of layout pattern classification in the integrated circuit design. With several applications in design for manufacturability flow such as hotspot library generation, hierarchical data storage, and systematic yield optimization, clustering the hotspots optimally with good quality representative hotspots is important.We formally introduce the hotspot clustering problem and briefly discuss the overview of our proposed tool. Then, we introduce the two integer linear program formulations which solve for optimal clusters for the pattern classification problem in IC layout, subject to constraints given by ACC or ECC. Apart from minimizing cluster count, we generate representative clips that best represent the clusters.We achieve better results in majority of the test cases as compared to the existing results published in the literature and the reference results reported in ICCAD 2016 contest website. Although the runtime of the ILP is more than the other methods, our main focus in this work is to develop a generic framework to cluster the hotspots in a layout optimally. These formulations describe the given problem exactly unlike other works in the literature which try to adapt the existing clustering algorithms to this problem, with some postprocessing steps. In future work, clip shifting can be adopted to the tool flow to increase the solution space and thereby further reduce the cluster count.



---

*Source: 9430593-2019-01-17.xml*