CN114861590A - An indexing method applied to large-scale layout data - Google Patents

Abstract

The invention discloses an indexing method applied to large-scale layout data, which comprises the following steps: classifying input layout data according to different layout layers, and abstracting each module into a plurality of two-dimensional plane polygons; then, each layer of the layout is divided into planes in a recursive manner by adopting a quadtree independently; traversing each partitioned sub-region by using a space filling curve, and allocating an index value to each module according to the sequence of each polygon on the curve; and finally, storing the index values in a B + tree form. The invention can flexibly and quickly construct indexes for large-scale layout data and efficiently perform incremental updating of the layout data with lower system overhead. Based on the index structure obtained by the index method, the layout data at the corresponding two-dimensional coordinates can be quickly searched in the two-dimensional plane range of the layout.

Description

An indexing method applied to large-scale layout data

technical field

The invention relates to an indexing method applied to large-scale layout data, in particular to incremental update and point search for layout data.

Background technique

EDA technology is a computer software system developed on the basis of electronic CAD technology. With the help of EDA tools, integrated circuits can develop at a legendary speed, continuing the myth of Moore's Law.

At the same time, the development of integrated circuits and the continuous progress of technology have also brought the following impacts:

1. As the process size continues to shrink, the number of transistors integrated in the chip continues to increase. Therefore, under the advanced technology, the size of the layout data of the chip is also expanded several times.

2. With the continuous shrinking of the process size, advanced processes will bring new design rules, which not only increase the complexity of chip design, but also increase the size of the layout data of the chip.

3. As the size of the process continues to shrink, the advanced process will also introduce new design tools, resulting in a sharp expansion of the size of the layout data, which increases linearly with the size of the layout.

At present, the data of large-scale layout through photomask has reached the scale of hundreds of GB. Whether it is in the back-end layout and wiring of the chip or the physical verification stage, the most demanded is to search for a specific location in the massive layout data. Layout data at . However, some original indexing methods applied to layout data are not continuously updated with the development of integrated circuits, so the actual use efficiency after indexing the layout data is low, and the system overhead is high. And when the local data of the layout changes, the index structure formed based on these indexing methods cannot complete the update efficiently, which also leads to the low efficiency of incremental update of the layout data.

Therefore, it is necessary to design a layout index method suitable for large-scale layouts, so that EDA tools can efficiently read local information data in the layout with this method, which is convenient for subsequent processing of these layout data, and also facilitates subsequent layouts. Incremental updates after data changes.

SUMMARY OF THE INVENTION

In view of this, the object of the present invention is to provide a kind of indexing method applied to large-scale layout data, in order to solve the problem that when EDA tools deal with large-scale layout data, the index construction efficiency is low, the data search speed is slow and the system overhead is large during incremental update. The problem.

In order to achieve the above object, the present invention adopts the following technical solutions:

An indexing method applied to large-scale layout data, the method includes:

Step S1, read the layout data of the integrated circuit, and analyze the stream data according to the data format; extract the vertex coordinates of each module, abstract each module into a polygon on a two-dimensional plane, and analyze the data according to the layout of the original module. Layers layer these polygons, so that the modules located in the same layer of the layout, the corresponding abstracted polygons are still in the same layer;

Step S2, for the multi-layer two-dimensional plane after the abstraction process in step S1, take the layer as a unit, independently use the recursive division method for each layer of two-dimensional plane to quarterly divide the area, according to the internal The number of polygons determines whether the sub-area needs to be further divided until the number of polygons in each sub-area does not exceed the preset threshold; wherein, while dividing the area, each sub-area is traversed in the order of the Hilbert curve, and at the same time Allocate a unique index value, named CellId, to establish the mapping relationship between the abstracted polygon and the index value;

Step S3, if the area division in a certain sub-area has ended and is about to start dividing another area, then all the index values in the sub-area that are currently divided are the key values, and all the polygon information in the area corresponding to the index values. For the data, build a B+ tree; if there is already a B+ tree, insert the index value into the tree and adjust the structure to maintain the characteristics of the B+ tree;

Step S4, when the layout data changes, perform incremental update of the index structure, which includes:

For the B+ tree constructed in step S3, query whether the number of polygons in the relevant area after the modification exceeds the threshold;

If it does not exceed, update the polygon information in the corresponding node in the B+ tree. If it exceeds, the area is divided into quarters, and the relevant nodes are adjusted in the B+ tree;

Step S5, when it is necessary to query the layout data at the specified coordinates, calculate the index value through the specified coordinate value, so as to locate the node corresponding to the area containing the coordinates in the B+ tree, and traverse each polygon in the node by traversing each polygon. And determine the positional relationship with the specified coordinates, and obtain the corresponding layout data information.

Further, in the step S1, the layout data of the read-in integrated circuit specifically includes:

Step S101, input the data stream of the GDSII file;

Step S102, for this data stream, intercept its 16-bit binary number successively to obtain the current module length and the current module type;

Step S103, judging whether the obtained module is the required module, if not, then perform the operation of moving the pointer backward, and skip the current module; if it is required, then perform step S104;

Step S104, translate and record the polygon information in the current module, while moving the pointer backwards according to the known length;

Step S105 , judging whether the data stream has ended, if not, go back to step S102 ; if it has ended, output the set of polygon information.

Further, in the step S105, the polygon information includes vertex information of each polygon, and also includes the layer number where each polygon is located, so as to distinguish the polygons according to the layer number.

Further, in the step S2, the following method is used to divide the area into quarters:

A Hilbert curve is adopted, which is a fractal curve, and a low-order Hilbert curve is extended to a high-order Hilbert curve through iteration. For the lowest-order Hilbert curve, the center points of the four square grid cells are connected in series to form the Hilbert curve. , the four square grid cells form a square plane;

When a Hilbert curve of a certain order is iterated to a higher-order Hilbert curve, a recursive division method similar to the quadtree is adopted; that is, each time on the basis of the previous one, according to the density of the graph, the original grid is divided One or more of the units are divided again, each grid unit is equally divided into four smaller grid units, and the dividing is stopped until the number of polygons in each grid unit is lower than a preset threshold.

Further, in the step S4, the updating of the polygon information in the corresponding nodes in the B+ tree specifically includes:

Step S401, for the polygon information that has changed, determine whether it needs to be divided, if not, then divide the area according to the order of the Hilbert curve; if necessary, execute step S402;

Step S402, generating a corresponding CellId in the new area, where the CellId stores relevant polygon information;

Step S403, determine whether there is a value related to the new CellId in the existing index, if so, merge the old and new CellId and related polygon information; if not, input the polygon information into CellId, and insert CellId into the B+ tree;

Step S404, outputting the updated index structure.

Further, in the step S5, the node corresponding to the region containing the coordinates is located in the B+ tree, which specifically includes:

Step S501, input two-dimensional point coordinates;

Step S502, calculating the minimum CellId that just covers the point;

Step S503, input CellId to B+ tree;

Step S504, find out the node covering the CellId;

Step S505, traverse all polygon information in the node;

Step S506, execute judgment, judge whether there is a polygon containing the coordinate point, if so, summarize relevant polygon information, if not, there is no layout data at the coordinate point;

Step S507, output the search result.

The beneficial effects of the present invention are:

1. The method of the present invention can calculate and update the index value in the process of dividing the layout area, thereby improving the construction efficiency of the index structure of the layout data;

2. The method of the present invention can build an index structure for layout data, thereby improving the efficiency of finding layout data at specified coordinates;

3. The method of the present invention supports incremental update of layout data.

Description of drawings

1 is a schematic flowchart of an indexing method applied to large-scale layout data provided in Embodiment 1;

Fig. 2 is the sample diagram of the simple layout provided in embodiment 1;

FIG. 3 is a schematic flowchart of abstracting layout data in step 1;

Fig. 4 is the schematic flow chart of carrying out regional division to the layout in step 2 and allocating index value simultaneously;

FIG. 5 is a schematic diagram of the Hilbert curve traversing the sub-region in step 2, wherein, the a graph in FIG. 5 is represented as a first-order Hilbert curve, and the b graph in FIG. 5 is represented as a second-order Hilbert curve;

FIG. 6 is a schematic diagram of the structure of the index value named CellId in step 2 and a sample diagram thereof, wherein the picture a in FIG. 6 is a schematic diagram of the structure of the index value of CellId, and the picture b in FIG. 6 is a schematic diagram of the structure of the index value of CellId A sample image of the index value of CellId;

FIG. 7 is a sample diagram of assigning index values in step 2, wherein the a graph in FIG. 7 represents the assignment of CellId on the first-order Hilbert curve, and the b graph in FIG. 7 represents the CellId on the second-order Hilbert curve distribution on the curve;

FIG. 8 is a schematic diagram of four different basic Hilbert curves, wherein, the a graph in FIG. 8 represents the unit Hilbert curve in standard order, and the b graph in FIG. The c diagram of is represented as a unit Hilbert curve that is upside down, and the d diagram in FIG. 8 is represented as a unit Hilbert curve whose axis is rotated left and right inverted;

Fig. 9 is a sample diagram of the B+ tree to be constructed in step 3;

10 is a schematic flowchart of the incremental update of the layout data provided in Embodiment 1;

FIG. 11 is a schematic flowchart of searching layout data at arbitrary coordinates based on the index structure formed by the method of Embodiment 1.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

Example 1

Referring to FIG. 1 to FIG. 11 , this embodiment provides an indexing method applied to large-scale layout data. The flow of the method is shown in FIG. 1 , and the method specifically includes:

Step S1, read the layout data of the integrated circuit, and analyze the stream data according to the data format; extract the vertex coordinates of each module, abstract each module into a polygon on a two-dimensional plane, and analyze the data according to the layout of the original module. The number of layers layers these polygons, so that the modules located in the same layer of the layout, the corresponding abstracted polygons are still in the same layer.

Specifically, in this embodiment, step S1 is the operation of reading and abstracting layout data. In this embodiment, a simple layout is shown in FIG. 2 , and the layout data describes the positions and sizes of these elements. and other related information, it is described and stored in binary format. Therefore, in this embodiment, the layout data is read in accordance with the flow shown in FIG. 3 , that is, according to the format of the stored information used by the layout data known in advance, the program is written to read in the layout data in the form of a data stream. file, and obtain information about each module of the layout through hex conversion.

More specifically, in this embodiment, the read-in operation of the layout data specifically includes:

Step S101, input the data stream of the GDSII file;

Step S102, for this data stream, intercept its 16-bit binary number successively to obtain the current module length and the current module type;

Step S103, judging whether the obtained module is the required module, if not, then perform the operation of moving the pointer backward, and skip the current module; if it is required, then perform step S104;

Step S104, translate and record the polygon information in the current module, while moving the pointer backwards according to the known length;

Step S105 , judging whether the data stream has ended, if not, go back to step S102 ; if it has ended, output the set of polygon information.

After the above-mentioned read-in operation is performed, the layout data is abstracted, that is, each module is abstracted into a polygon on a two-dimensional plane, which is subsequently output to the index construction algorithm. Since the layout usually contains multiple layers, the output polygon information includes not only the vertex information of each polygon, but also the layer number where each polygon is located, which is convenient for mass polygons according to the layer number. differentiate.

Step S2, taking the layer as a unit, independently recursively divide the two-dimensional plane of each layer in a manner similar to a quadtree, until the number of polygons in each sub-region does not exceed a preset threshold; At the same time, each sub-region is traversed in the order of the Hilbert curve, and a unique index value is assigned, which is named CellId here.

Specifically, in this embodiment, step S2 is an operation of constructing an index relationship. In this step, while the layout plane is divided into regions, an index value is assigned to each region, so as to complete the abstraction The mapping relationship between the polygon and the index value, so as to realize the construction of the index relationship. The specific process of this step S2 includes:

Step S201, for the set of polygon information obtained in step S105, perform area division according to the order of the Hilbert curve;

Step S202, for the new area after the division is completed, update the CellId;

Step S203, update the polygon number information in each CellId;

Step S204, outputting the CellId set.

More specifically, in this embodiment, region division is performed on the layout, which includes:

It can be seen from Fig. 5a and Fig. 5b that the above-mentioned Hilbert curve is a fractal curve, which can be realized by iteration. Lower-order Hilbert curves can be iteratively extended to higher-order curves. The Hilbert curve in Figure 5a is the lowest-order basis form, with only four points connected, numbered 0-3. At the same time, it can be found that if the entire square plane is equally divided into four square grid cells, then these four points are located at the center of each grid cell. Figure 5b is generated on the basis of Figure 5a. For each grid element in Fig. 5a, a first-order Hilbert curve as shown in Fig. 5a is used to replace it, thereby constructing a second-order Hilbert curve as shown in Fig. 5b. Similar to Figure 5a, the second-order Hilbert curve connects a total of 16 points. If the entire square plane is equally divided into 16 grid cells, then each point is the center point of the grid cell where it is located. So for the Hilbert curve, the ith-order curve can be realized by replacing each mesh element in the first-order base curve with the ith-1th-order curve. Eventually, as i approaches infinity, the Hilbert curve can connect all points in space.

To sum up, the layout area division method used in the indexing method of this embodiment should adopt a recursive division method similar to that of the quadtree. That is, on the basis of the previous time, one or more of the original grid cells are divided again according to the density of the graphics, and each grid cell is equally divided into four smaller grid cells. The division will not stop until the number of polygons in each grid cell is lower than a preset threshold.

More specifically, in this embodiment, the index value used by the index relationship includes:

Since each iteration of the Hilbert curve will divide each of the original grid cells once, and then connect and number the center points of these grid cells in linear order. So each iteration, the number of grid cells is 4 times the original. Therefore, once the division is over, the number of each grid cell is uniquely determined. If you want to divide it further later, then each grid cell must be renumbered, which will not only slow down the speed of area division, but also increase the overhead of program runtime.

In order to make up for this shortcoming, this embodiment uses a special key value named CellId as the index value, and the following is the related introduction.

Figure 6a is a schematic diagram of the structure of such an index value named CellId, and Figure 6b is an example of a CellId, which has a total of 64 binary digits. Here, they are divided into three categories in order from high to low:

Bits 0 to 6: Flag bits. These five bits of data indicate which layer on the layout the CellId is located. Because it uses 7 binary bits to represent data, it can represent values ranging from 0 to 127. Therefore, the maximum number of layers of input layout data supported by this index structure is 128.

Bits 7 to n: data bits, where 8≤n≤63. The value expressed by these data bits is the number value of the CellId on the Hilbert curve. Because it can represent data with up to 56 binary bits, it can represent values of size 0 to 2 ⁵⁶ -1.

Bits n to 63: cutoff bits. The cutoff bit follows the data bit, and the first digit at the beginning of the cutoff bit is 1, and the remaining digits are filled with 0 to indicate the end of the data bit of CellId.

More specifically, in this embodiment, the allocation and update of index values include:

For the initial first-order Hilbert curve, it divides the plane into 4 regions, so only the 7th to 8th data bits are needed to assign the four numbers 00, 01, 10, and 11 to these 4 regions, respectively. At this time, the 9th to 63rd bits are all cut-off bits, and the numbering of the relevant index values is shown in Figure 7a.

After one iteration of this order Hilbert curve to obtain the second order Hilbert curve, the original 4 regions are divided into 16 regions, then only the 7th to 10th data bits are needed to assign numbers to these 16 regions respectively. 7a, it can be seen that the regions numbered 0 in the first-order curve are numbered 0 to 3 in the second-order curve, and the regions numbered 0 to 15 in the third-order curve. Therefore, it is assumed that two data bits are used to represent the regions numbered 0 to 3 in the first-order Hilbert curve, then their values are 00, 01, 10, and 11, respectively. Simply pick out the area numbered 00 for observation, then the number 0 to 3 of this area on the second-order Hilbert curve can be represented by 4 data bits, respectively 0000, 0001, 0010, 0011, the number of the relevant index value The situation is shown in Figure 7b.

The first-order Hilbert curve is a unit Hilbert curve, as the name implies, it is the basic unit that composes a higher-order Hilbert curve. The second-order Hilbert curve is formed by connecting the three element Hilbert curves of axis rotation, up and down inversion, and axis rotation left and right inversion in a certain order.

In order to save the information of the Hilbert curves of these four elements, it can be found that the difference between the Hilbert curves of each element lies in the order in which they connect the four grid elements, so they can be saved in the form of arrays.

The following describes how to represent these four element Hilbert curves in array form:

First, the horizontal and vertical coordinates can be set as shown in Figure 8a, then the coordinates of the four grid cells are, respectively, use 0 to represent (0,0), 1 to represent (0,1), and 2 to represent (1,0), Use 3 to represent (1,1).

The standard order is shown in Figure 8a: connect in the order of (0,0), (0,1), (1,0), (1,1), so the unit Hilbert curve representing the standard order with an array is [0, 1,3,2];

The axis rotation is shown in Figure 8b: in the order of (0,0), (1,0), (1,1), (0,1), the corresponding array is [0,2,3,1];

Upside down as shown in Figure 8c: in the order of (1,1), (1,0), (0,0), (0,1), the corresponding array is [3,2,0,1];

The axis rotation is inverted left and right as shown in Figure 8d: in the order of (1,1), (0,1), (0,0), (1,0), the corresponding array is [3,1,0,2] .

The iteration of the Hilbert curve has its fixed algorithm, so if the shape of the initial first-order Hilbert curve is determined, then the shape of the Hilbert curve of all subsequent orders is determined. Therefore, during the iteration process, the shape of the Hilbert curve after the next iteration is saved at the same time. The lower right corner of each grid in Figures 8a to 8d shows the shape of the Hilbert curve in the grid at the next iteration.

After the original shape information is stored, four numbers of 00, 01, 10 and 11 can be used to represent the four types of unit Hilbert curves in FIGS. 8 a to 8 d, respectively. Next, we will introduce how to generate a second-order Hilbert curve with the help of known element Hilbert curve information based on the first-order Hilbert curve.

First construct an auxiliary matrix [1,0,0,3] with one row and four columns, which is [01,00,00,11] in binary numbers.

Taking Fig. 8c as an example, it is known that the first-order Hilbert curve is an upside-down type element Hilbert curve, which can be represented by 10. XORing 10 with each element in the auxiliary matrix gives:

[01,00,00,11]^10=[11,10,10,01]

The unit Hilbert curve of the upside-down type mentioned above is represented by an array as [3,2,0,1], that is, according to (1,1), (1,0), (0,0), (0,1) order, so match each item of these two matrices with one row and four columns, we can see:

(1,1) The cell numbered 11 is filled with the Hilbert curve of the cell in the shape of Figure 8d;

The cell (1,0) is filled with the cell numbered 10, that is, the Hilbert curve in the shape of Figure 8c;

The (0,0) cell is filled with the cell number 10, that is, the cell Hilbert curve as shown in Figure 8c;

The (0,1) cell is filled with the cell Hilbert curve numbered 01, which is shaped like Figure 8b.

The process of iterating the second-order Hilbert curve to the third-order Hilbert curve is also the same.

Step S3, if the area division in a certain sub-area has ended and is about to start dividing another area, then all the index values in the sub-area that are currently divided are the key values, and all the polygon information in the area corresponding to the index values. For the data, build a B+ tree; if there is already a B+ tree, insert the index value into the tree and adjust the structure to maintain the characteristics of the B+ tree.

Specifically, in this embodiment, the step S3 is to perform the storage of the index value based on the B+ tree. In this step, it includes: after the above operations, the massive polygons are in the order of the Hilbert curve and approximate their positions with CellId. information to build an index relationship between abstract layout data and CellId. Here, we need to store the index value.

Assuming that it is currently on the 0th layer, each grid cell in the first-order and second-order Hilbert curves is numbered with CellId. Since the number of CellId digits is too long, the first 15 CellIds are intercepted for comparison:

The corresponding CellId of the region numbered 1 in the first-order Hilbert curve is:

000000000100000

The corresponding CellId of the area numbered 2 is:

000000001100000

The area is divided into four blocks by the second-order Hilbert curve, and the numbered values are from 5 to 8. The corresponding CellIds of these four areas are arranged in the order from small to large, respectively:

000000001001000…

000000001011000…

000000001101000…

000000001111000…

It can be seen that in the first-order Hilbert curve, the CellId value of the region numbered 1 is smaller than that of the region numbered 2. Therefore, if a division method similar to a quadtree is used in the future, that is, according to the density of the polygon, the local area, such as the area numbered 1, is continuously divided, then the CellId value constructed by all subsequent divisions in this area is smaller than the numbered area 2. CellId inside.

Therefore, if the index relationship is constructed according to the order in which the grid cells are traversed by the Hilbert curve, the final output of a series of CellIds is arranged in strict order from small to large. Therefore, for linear data, it is natural to think that these CellIds can be stored in the form of a B+ tree, as shown in FIG. 9 .

Step S4, when the layout data changes, incremental update of the index structure can be performed. Query the B+ tree whether the number of polygons in the relevant area exceeds the threshold after the modification. If it does not exceed, update the polygon information in the corresponding node in the B+ tree. If it exceeds, the area is divided into quarters, and the relevant nodes are adjusted in the B+ tree.

Specifically, in this embodiment, step S4 is to perform incremental update of the layout data. Specifically, in this step, after the index structure has been established, if the layout data is added, deleted, modified, etc. operation, then the index structure should be changed according to the changes of the layout data on the basis of the already constructed index structure. This can not only improve the efficiency of building the new index structure, but also reduce the overhead of the system. With the support of the data form of CellId as the index value, this embodiment can adjust the local index structure.

More specifically, the flowchart of incremental update in this embodiment is shown in FIG. 10 , which includes:

Step S401, for the polygon information that has changed, determine whether it needs to be divided, if not, then divide the area according to the order of the Hilbert curve; if necessary, execute step S402;

Step S402, generating a corresponding CellId in the new area, where the CellId stores relevant polygon information;

Step S403, judging whether there is a value related to the new CellId in the existing index, if so, merge the old and new CellId and related polygon information; if not, input the polygon information into CellId, and insert CellId into the B+ tree;

Step S404, outputting the updated index structure.

More specifically, for the above process, the most critical step is the process of inserting the new CellId into the old B+ tree. Because the CellIds in the B+ tree are stored strictly in ascending order. Although the lengths of the corresponding CellId data bits are different due to the different depths of division of each local area, all areas corresponding to the CellId will not overlap. For example, in FIG. 7a, the B+ tree does not store the area numbered 00 and the area 0010 at the same time, and the CellId corresponding to the 00 area and the CellId corresponding to the 0000 node cannot coexist.

Therefore, in order to ensure that the region corresponding to the pre-inserted CellId does not overlap with the regions corresponding to all CellIds in the B+ tree, it is necessary to convert the new CellId into an interval format, and search the B+ tree for any CellId that overlaps with the interval. For example, in FIG. 7a, the 00 area is divided into arbitrary depths, and the data bits of CellId are expanded by two bits each time the data bits are divided, and the existing data bits do not change. Therefore, the obtained CellId values are all located in the interval [00000000010...,00000000110...].

There are ultimately three possible scenarios:

(1) There is no CellId that intersects the grid cell of the new CellId. At this time, it is only necessary to insert the new CellId into the corresponding position of the B+ tree. In order to prevent the number of key values at the node from exceeding the preset value after insertion, it is necessary to fine-tune the B+ tree;

(2) There is a CellId whose corresponding grid unit completely covers the grid unit of the new CellId. Add the polygon in the new CellId to the CellId in the original B+ tree, and repeat the process in Figure 10;

(3) There is a CellId whose corresponding grid unit is completely covered by the grid unit of the new CellId. The grid cells of the new CellId are divided once, and the process in FIG. 10 is repeated.

Step S5, when it is necessary to query the layout data at the specified coordinates, the index value can be calculated by the specified coordinate value, so as to locate the node corresponding to the area containing the coordinates in the B+ tree, and by traversing each node in the node. Polygon and determine the positional relationship with the specified coordinates, and obtain the corresponding layout data information.

Specifically, in this embodiment, step S5 is to perform point search of layout data. Point search refers to a given two-dimensional coordinate on a certain layer of the layout, and all abstracted coordinates including the coordinate point are found. The layout data corresponding to the polygon, the related process is shown in Figure 11, which includes:

Step S501, input two-dimensional point coordinates;

Step S502, calculating the minimum CellId that just covers the point;

Step S503, input CellId to B+ tree;

Step S504, find out the node covering the CellId;

Step S505, traverse all polygon information in the node;

Step S506, execute judgment, judge whether there is a polygon containing the coordinate point, if so, summarize relevant polygon information, if not, there is no layout data at the coordinate point;

Step S507, output the search result.

More specifically, after the front end sends a point search request, the point can be approximately regarded as a very small rectangle, so as to generate a CellId corresponding to the smallest sub-region that can just cover its area.

The above part has already proposed that the index structure formed by the index method provided by this implementation is in the form of a B+ tree, and the index value at each node is CellId, so the coordinate point to be queried can be enlarged to For the area corresponding to the CellId, due to the limitation of the data bit length of the CellId, the error of this scaling is not very large, but the search efficiency can be improved by means of scaling. Then search for the relevant node with CellId in the B+ tree, take out all polygon information in the node, and determine the mutual positional relationship with the original two-dimensional coordinate point to be queried, and obtain the corresponding result.

To sum up, the present invention provides an indexing method applied to large-scale layout data, which uses an index value structure composed of flag bits, data bits and cutoff bits, and can be used in the process of region division. With the deepening of recursion, by expanding the length of data bits and reducing the length of cut-off bits, the index value is continuously updated from top to bottom to improve the efficiency of index construction. The density level adopts different area division depths, which improves the flexibility of the index structure.

After the present invention establishes an index structure based on the index method, whenever the layout data is changed, such as addition, deletion and modification, only the nodes corresponding to the changed local area can be updated on the basis of the original index structure. , so as to realize the incremental update of the layout data, which greatly saves the system overhead.

The parts that are not described in detail in the present invention are known techniques of those skilled in the art.

The preferred embodiments of the present invention have been described in detail above. It should be understood that those skilled in the art can make many modifications and changes according to the concept of the present invention without creative efforts. Therefore, any technical solutions that can be obtained by those skilled in the art through logical analysis, reasoning or limited experiments on the basis of the prior art according to the concept of the present invention shall fall within the protection scope determined by the claims.

Claims (6)

1. an indexing method applied to large-scale layout data, is characterized in that, this method comprises: Step S1, read the layout data of the integrated circuit, and analyze the stream data according to the data format; extract the vertex coordinates of each module, abstract each module into a polygon on a two-dimensional plane, and analyze the data according to the layout of the original module. Layers layer these polygons, so that the modules located in the same layer of the layout, the corresponding abstracted polygons are still in the same layer; Step S2, for the multi-layer two-dimensional plane after the abstraction process in step S1, take the layer as a unit, independently use the recursive division method for each layer of two-dimensional plane to quarterly divide the area, according to the internal The number of polygons determines whether the sub-area needs to continue to be divided until the number of polygons in each sub-area does not exceed the preset threshold; wherein, while dividing the area, each sub-area is traversed in the order of the Hilbert curve, and at the same time Allocate a unique index value, named CellId, to establish the mapping relationship between the abstracted polygon and the index value; Step S3, if the area division in a certain sub-area has ended and is about to start dividing another area, then all the index values in the sub-area that are currently divided are the key values, and all the polygon information in the area corresponding to the index values. For the data, build a B+ tree; if there is already a B+ tree, insert the index value into the tree and adjust the structure to maintain the characteristics of the B+ tree; Step S4, when the layout data changes, perform incremental update of the index structure, which includes: For the B+ tree constructed in step S3, query whether the number of polygons in the relevant area after the modification exceeds the threshold; If it does not exceed, update the polygon information in the corresponding node in the B+ tree. If it exceeds, the area is divided into quarters, and the relevant nodes are adjusted in the B+ tree; Step S5, when it is necessary to query the layout data at the specified coordinates, calculate the index value through the specified coordinate value, so as to locate the node corresponding to the area containing the coordinates in the B+ tree, and traverse each polygon in the node by traversing each polygon. And determine the positional relationship with the specified coordinates, and obtain the corresponding layout data information. 2. The indexing method applied to large-scale layout data according to claim 1, wherein, in the step S1, the layout data of the read-in integrated circuit specifically comprises: Step S101, input the data stream of the GDSII file; Step S102, for this data stream, intercept its 16-bit binary number successively to obtain the current module length and the current module type; Step S103, judging whether the obtained module is the required module, if not, then perform the operation of moving the pointer backward, and skip the current module; if it is required, then perform step S104; Step S104, translate and record the polygon information in the current module, while moving the pointer backwards according to the known length; Step S105 , judging whether the data stream has ended, if not, go back to step S102 ; if it has ended, output the set of polygon information. 3. An indexing method applied to large-scale layout data according to claim 2, characterized in that, in the step S105, the polygon information, which includes the vertex information of each polygon, also includes The layer number where each polygon is located, used to distinguish polygons by layer number. 4. a kind of indexing method applied to large-scale layout data according to claim 3, is characterized in that, in described step S2, adopts following method to carry out the quartering of the area: A Hilbert curve is adopted, which is a fractal curve, and a low-order Hilbert curve is extended to a high-order Hilbert curve through iteration. For the lowest-order Hilbert curve, the center points of the four square grid cells are connected in series to form the Hilbert curve. , the four square grid cells form a square plane; When a Hilbert curve of a certain order is iterated to a higher-order Hilbert curve, a recursive division method similar to the quadtree is adopted; that is, each time on the basis of the previous one, according to the density of the graph, the original grid is divided One or more of the units are divided again, each grid unit is equally divided into four smaller grid units, and the dividing is stopped until the number of polygons in each grid unit is lower than a preset threshold. 5. A kind of indexing method applied to large-scale layout data according to claim 4, is characterized in that, in described step S4, described updating the polygon information in the corresponding node in B+ tree, it specifically comprises: Step S401, for the polygon information that has changed, determine whether it needs to be divided, if not, then divide the area according to the order of the Hilbert curve; if necessary, execute step S402; Step S402, generating a corresponding CellId in the new area, where the CellId stores relevant polygon information; Step S403, judging whether there is a value related to the new CellId in the existing index, if so, merge the old and new CellId and related polygon information; if not, input the polygon information into CellId, and insert CellId into the B+ tree; Step S404, outputting the updated index structure. 6. A kind of indexing method applied to large-scale layout data according to claim 5, is characterized in that, in described step S5, described in the B+ tree locating the node corresponding to the area containing this coordinate , which specifically includes: Step S501, input two-dimensional point coordinates; Step S502, calculating the minimum CellId that just covers the point; Step S503, input CellId to B+ tree; Step S504, find out the node covering the CellId; Step S505, traverse all polygon information in the node; Step S506, execute judgment, judge whether there is a polygon containing the coordinate point, if so, summarize relevant polygon information, if not, there is no layout data at the coordinate point; Step S507, output the search result.

Images