Method and apparatus for removing dummy features from a data structure

• US 7,765,517 B2
• Filed: 10/24/2007
• Issued: 07/27/2010
• Est. Priority Date: 07/06/2005
• Status: Active Grant

• Current Assignee: TechInsights, Inc. (M3, Inc.)
• Original Assignee: Semiconductor Insights Incorporated (Informa PLC)
• Inventors: Ouali, Mohammed, Abt, Jason, Zavadsky, Vyacheslav, Keyes, Edward
• Primary Examiner(s): Levin; Naum B
• Application Number:
  US11/976,409
• Publication Number:
  US 20080059920A1
• Time in Patent Office: 1,007 Days
• Field of Search: 716/2, 716 19- 21, 703/2, 430/5, 382144-145, 382/154, 382/218
• US Class Current: 716/132
• CPC Class Codes: G06F 18/2113 by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

A method and apparatus to reduce occurrences of electrically non-functional elements, known as dummy features, from a source data structure is described. The source data structure may be image data, a vector based data structure or some other data format. Dummy features in the source data structure are detected and then deleted. Dummy features may be detected by selecting a representative dummy feature, using it as a reference pattern or polygon and comparing it to features in the source data structure. The step of comparing the selected reference to the comprises selecting a cut-off correlation threshold value, and computing the correlation coefficients between the reference and the feature. Features are selectively removed based on a comparison between their correlation coefficients and the selected cut-off correlation threshold value. This threshold value may require updating to remove all dummy features in the source data structure. When different shaped dummy features in the same data structure are encountered, a further reference feature may be selected and the process repeated.

Claims

1. A method of producing a processed data structure representation from an image based source data structure of an IC layout with reduced occurrences of dummy features comprising the steps of:

(a) examining a portion of the source data structure and selecting a dummy feature pattern to be used as a reference pattern in a computerized processing system;

(b) selecting a cut-off correlation threshold value to be used in the computerized processing system;

(c) computing, in the computerized processing system, correlation coefficients between feature patterns in the source data structure and the reference pattern to detect dummy features; and

(d) removing the detected dummy features from the source data structure.

2. The method according to claim 1 wherein step (c) comprises computing the correlation coefficients based on gray scale values.

3. The method according to claim 1 wherein step (b) comprises:

(b)(1) framing the dummy feature reference pattern by a pixel matrix of m×

n pixels; and

(b)(2) selecting the cut-off correlation threshold value which is based on gray scale values from the reference dummy feature pattern.

4. The method according to claim 1 wherein step (c) comprises calculating the correlation coefficient using a sum of squared differences calculation:

$\mathrm{SSD}<br><br>\left(i,j\right)=\underset{k=1}{\overset{n}{\sum <br><br>}}<br><br>\underset{c=1}{\overset{m}{\sum <br><br>}}<br><br>{\left[I<br><br>\left(i+k,j+c\right)-P<br><br>\left(k,c\right)\right]}^2$

where;

I (i, j) is the image array;

P is the reference pattern array;

SSD (i, j) is the correlation coefficient,

(i, j) are the coordinates in the image array.

5. The method according to claim 1 further comprising the steps of:

(e) examining the source data structure with the removed dummy features; and

(f) updating the cut-off correlation threshold value; and

(g) repeating steps e. and f. if necessary.

6. The method according to claim 5 wherein step (e) comprises examining the source data structure with the removed dummy features to determine if further dummy features remain.

7. The method according to claim 5 wherein step (e) comprises examining the source data structure with the removed dummy features to determine if non-dummy features have been removed.

8. The method according to claim 5 further comprising the step of:

(h) repeating steps e., f. and g. if necessary.

9. The method according to claim 8 further comprising the steps of:

(j) storing the source data structure with the removed dummy features in a memory;

(k) storing the dummy feature reference pattern in a memory; and

(l) storing the last selected cut-off correlation threshold in a memory.

10. The method according to claim 1 comprising the steps of:

(m) examining the source data structure with the removed dummy features to determine if a significant number of dummy features have been removed; and

(n) selecting another dummy feature pattern if a significant number of dummy features have not been removed.

11. The method according to claim 1, wherein steps c. and d. are implemented automatically by a dummy feature removal algorithm programmed in the computerized processing system.