Method for restructuring physical design images into hierarchical data models

• US 5,533,148 A
• Filed: 09/30/1993
• Issued: 07/02/1996
• Est. Priority Date: 09/30/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sayah, John Y., Rozwod, Robert A.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): ANDERSON, DAVID
• Application Number:
  US08/129,926
• Time in Patent Office: 1,006 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 382/143, 382/144, 382/145, 382/147, 382/240, 382/243, 382/305, 382/176
• US Class Current: 382/240
• 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: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

A method for restructuring information stored in physical design image form, such as an image of a layer in a semiconductor package, into a hierarchical area specification model useful in automated design applications. The restructuring results in recognizing identical patterns in the image and storing common information about the patterns in a single location to decrease storage space required and improve access efficiency by design application programs needing the information. Parameters controlling the method can be adjusted to produce a hierarchical model that is particularly suited to the needs of a particular application program.

Claims

1. A method for restructuring a physical design image into a data model comprising the steps of:

providing a physical design image;

identifying leaf areas in the physical design image;

classifying the leaf areas as being of one or more types according to a characteristic of the leaf areas;

grouping adjacent leaf areas of equivalent type into one or more area arrays;

recognizing equivalent adjacent and non-adjacent area arrays and forming a set of one or more unique area arrays;

partitioning each unique area array into one or more partition areas;

recognizing equivalent partition areas and forming a set of one or more unique partition areas; and

generating area specifications for each unique partition area and for each unique leaf area.

2. A method for restructuring an image into a data model according to claim 1 wherein the step of grouping adjacent leaf areas of equivalent type into one or more area arrays comprises the steps of:

scanning the image in a first direction;

grouping leaf areas of equivalent type that are adjacent in the first direction to form one dimensional area arrays;

scanning the image in a second direction; and

grouping equivalent one dimensional area arrays that are adjacent in the second direction to form the area arrays.

3. A method for restructuring an image into a data model according to claim 1 wherein the step of partitioning each unique area array comprises partitioning each unique area array into a hierarchical array of one or more partition areas.

4. A method for restructuring an image into a data model according to claim 3 further comprising the step of organizing the unique area specifications into a hierarchical area specification model.

5. A method for restructuring an image into a data model according to claim 1 wherein the step of partitioning comprises recursively partitioning each unique area array according to desired partitioning criteria to form a hierarchical array of one or more partition areas.

6. A method for restructuring an image into a data model according to claim 5 wherein the partitioning criteria are selected to produce a model for use by a particular application.

7. A method for restructuring an image into a data model according to claim 5 wherein regular partition areas are created that can be specified in a step and repeat fashion.

8. A method for restructuring an image into a data model according to claim 5 wherein partition areas that are as close to a square form as possible are created.

9. A method for restructuring an image into a data model according to claim 5 wherein the number of different types of partition areas are reduced by identifying identical patterns of leaf areas to reduce the number of different area specifications.

10. A method for restructuring an image into a data model according to claim 1 wherein the step of identifying leaf areas includes the step of flattening the hierarchy and creating leaf areas if the image has been previously organized into a hierarchy.

11. A method for restructuring an image into a data model according to claim 1 wherein the step of classifying the leaf areas as being of one or more types ignores different characteristics between areas provided that such areas have common characteristics relevant to an application.

12. A method for restructuring an image into a data model according to claim 1 further comprising the steps of storing the data model and generating an area tree from the stored data model whenever desired.

13. A method for restructuring an image into a data model comprising the steps of:

providing an image;

identifying leaf areas in the image;

classifying the leaf areas as being of one or more types according to a characteristic of the leaf areas;

grouping adjacent leaf areas of equivalent type into one or more area arrays;

recognizing equivalent area arrays and forming a set of one or more unique area arrays;

recursively partitioning each unique area array by desired partitioning criteria to form a hierarchical array of one or more partition areas according to a sequence of steps including;

(a) exiting the sequence of steps if an area of N_x by N_y leaf areas has a number of leaf areas within it that is within a predetermined Desired Number of Leaf Areas Range;

(b) creating a set of area slices of size New N_x, by New N_y leaf areas by slicing the area of N_x by N_y leaf areas;

(c) recognizing equivalent slices from the set of area slices and removing redundant slices to form a set of unique area slices;

(d) identifying slices from the set of unique area slices that have previously been assigned an area specification and removing such slices from the set of unique area slices; and

(e) for every remaining distinct slice in the set of unique area slices performing the steps of;

(i) creating a new area specification, and

(ii) repeating the sequence of steps substituting New N_x and New N_y for N_x and N_y ;

recognizing equivalent partition areas and forming a set of one or more unique partition areas; and

generating area specifications for each unique partition area and for each unique leaf area.

14. A method for restructuring an image into a data model according to claim 13 wherein the step of creating a set of area slices by slicing the area of N_x by N_y, comprises dividing the area array of size N_x by N_y into slices of size New N_x by New N_y, the direction of the slices and the number of slices being selected according to predetermined partitioning criteria.

15. A method for restructuring an image into a data model according to claim 14 wherein the direction of the slices is determined by a partitioning criterion equal to Desired Minimum Number of Children in One Direction at Leaf Level, the slicing being performed in a direction such that N_x or N_y will not be sliced if below the Desired Minimum Number of Children in One Direction at Leaf Level.

16. A method for restructuring an image into a data model according to claim 15 wherein the number of slices is determined by a partitioning criterion equal to Desired Number of Children at Higher Levels Max and the number of slices is equal to 2 to maximum of the Desired Number of Children at Higher Level.

17. A method for restructuring an image into a data model according to claim 13 further comprising the step of post-processing grouping to reduce the number of area specifications at higher levels of the model.