JPH0782505B2 - Layout structure recognition method - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a layout structure recognition method suitable for structure recognition of a layout result of a layout system using a parallel computer, and more particularly to a layout structure recognition method capable of extracting parasitic elements caused by electronic circuit layout. Regarding Also, check unwiring in electronic circuit layout, room layout, three-dimensional layout in building, piping CA in nuclear power plant.
It can also be used for D and the like. Further, since the present invention is suitable for a large-scale search problem, it can be applied to recognition in fields such as image processing and three-dimensional processing.

[0002]

2. Description of the Related Art Hierarchical circuit extraction system HICE and the like are known as circuit recognition systems, and wiring capacitance extraction and the like have been reported (for example, 1990 Spring National Convention of the Institute of Electronics, Information and Communication Engineers A-126-). 128).

[0003]

An electronic circuit layout will be described as an example. The circuit diagram is a logical set of artificially created symbols, but the layout result is directly mapped on silicon as a three-dimensional structure, so that it is strongly related to physical phenomena. A typical problem is the problem of parasitic elements.
The parasitic element is an element which is not planned in the circuit diagram and is generated as a result of the layout. Wiring capacitance, resistance,
Examples are various parasitic capacitances of transistors. Parasitic elements, such as wiring capacitance, are uniquely determined by designating an arrangement (unary relation), and those such as thyristors that combine multiple arrangements to generate unexpected parasitic elements (multinomial relation) ) There is. If the parasitic elements can be automatically extracted from the layout result, the electrical characteristics can be predicted in advance and the reliability of the design can be improved.

In the prior art, the recognition of one-term relations such as extraction of wiring capacitance has been mainly performed. For the recognition of multinomial relations such as automatic recognition of parasitic thyristors, due to the complexity of the problem, such a solution has not yet been obtained.
Further, in order to solve the problem, it takes a lot of time for calculation.

An object of the present invention is to solve these conventional problems and to provide a layout structure recognizing method which efficiently realizes not only uniary relations but also polynomial relations.

[0006]

In order to achieve the above object, the layout structure recognition method of the present invention is (a) a processing step of inputting a recognition target structure in a parallel computer system, a layout result, and obtained data. It is characterized in that it includes a processing step of reading, a processing step of converting data into a network structure, a processing step of extracting a recognition target structure by solving a search problem, and a processing step of displaying an extraction result. (B) In the layout structure recognition method described above, a processing step of dividing the layout surface data into unit surface data, a processing step of generating a process corresponding to each unit surface data, and each process as a node It is also characterized in that it includes processing steps for creating a network. Also,
(C) In the layout structure recognition method described above, a processing step for solving the shortest path problem, a processing step for collecting only data in the vicinity of the start point node, and a processing step for performing optimization when the same diffusion layer data continues. It is also characterized in that it includes a processing step for searching the recognition target structure. In addition, (d) the layout structure recognition method described above is also characterized in that it includes a processing step of activating all the nodes as start point nodes. (E) In the layout structure recognition method described above, when the layout plane data is divided into unit plane data, the layout plane data is divided into a grid pattern. In addition, (f) the layout structure recognition method described above is characterized in that the potential condition is determined when the search problem is solved. Further, (g) the layout structure recognition method described above is characterized in that each node holds data of each corresponding division plane. Also,
(H) The layout structure recognition method described above is also characterized in that each node has a local memory. Also,
(I) The layout structure recognition method described above is also characterized in that a network is generated by placing a bidirectional stream between each node due to the adjacency relationship of each node. In addition, (n) the layout structure recognition method described above is characterized in that the shortest path problem is solved and the path to the start point node and the distance to the start point node are provided only to the nodes adjacent to the start point node. Also (Le)
The layout structure recognition method described above is also characterized in that when the layout plane data is divided into unit plane data, the layout plane data is divided into diffusion layers. Further, (2) the layout structure recognition method described above is characterized in that a search is performed using a plurality of indexes. In addition, (W) the layout structure recognition method described above is characterized in that all the nodes hold the structure to be searched. Also,
(F) The layout structure recognition method described above is also characterized in that the search is performed in consideration of the average value of the potential and the fluctuation range. In addition, (yo) the layout structure recognition method described above is characterized in that each step of structure recognition is executed in parallel. In addition, (a) the layout structure recognition method described above is characterized in that a three-dimensional structure network is generated. Further, (i) the layout structure recognition method described above is characterized in that the direction of the search is retained when solving the search problem. Also (So)
The layout structure recognition method described above is also characterized in that the recognition result is displayed back to the layout diagram and the circuit diagram. (T) In the layout structure recognition method described above, each node has an attribute. (E) The layout structure recognition method described above is also characterized in that the data in the local memory is optimized every time a message flows in the stream. (A) In the layout structure recognition method described above, each node data may be assigned to a different processor element (PE) PE, and the search problem may be solved by message communication between PEs. There are features. In addition, (a) the layout structure recognition method described above is characterized in that each node data is assigned to the PE depending on the structure of the original layout surface.

[0007]

In the present invention, since a specific structure can be extracted from the layout diagram, a critical path or the like can be cut out from a large scale circuit. Further, since the layout data is converted into the network structure data, various search conditions can be dealt with by the same algorithm. In addition, high speed processing is possible by performing parallel network search processing. In addition, by considering the direction of the message in the search, each divided node can obtain information on the structure in the vicinity of itself, so that the current amplification factor can be calculated. Further, when searching, unnecessary messages are discarded each time, so that a memory-efficient system can be realized. Also, by activating all the nodes as the starting point nodes of the search, all solutions can be derived. Further, since each node has the position coordinates in the layout data, the recognized structure can be displayed on the layout diagram. Further, since the attribute (such as the base of the transistor) in the layout data is held in the local memory of each node, efficient structure recognition can be performed. Further, when each node data is assigned to a different PE depending on the structure of the original layout surface, the data of the node at a short distance is assigned to a nearby PE,
A very efficient system can be realized in the search in the vicinity of the start point node.

[0008]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a system block diagram showing an example of a parallel computer system to which the present invention is applied. As shown in FIG. 1, the computer system to which the layout structure recognition system of the present invention is applied includes a parallel processing device 11, a front end processor 12, a display device 13, a manual operation input device 14, etc. connected to a common bus 15. Become. The parallel processing device 11 is composed of a plurality of PEs 16. Figure 1
This is an example in which 16 PEs 16 are connected in a grid. Each PE
Reference numeral 16 includes a processing device and a memory (not shown). The front-end processor 12 is the parallel processing device 1
1 to control the operation. A screen is displayed on the display device 13 so that the user can confirm the execution result of the layout structure recognition system. Further, when the layout structure recognition system is executed, the designated information is input from the manual operation input device 14.

[First Embodiment] FIG. 2 is a functional block diagram of a layout system showing an embodiment of the present invention. The input / output process 24 reads the original data 21 in the form of a circuit net into the memory process 25. The problem solving inference process 26 performs placement / wiring with reference to the layout basic process 27, and the statuses thereof are stored in the memory process 25.
Write in. When the layout is completed in this way,
The input / output process 24 outputs the layout drawing 22. The present embodiment is characterized in that the structure recognition process 23 is newly provided in the input / output process 24.

The layout system shown in FIG. 4 is obtained as a result of laying out by inputting to the above layout system a circuit net representing the original circuit diagram consisting of the transistors and resistors shown in FIG. 41 is the chip surface, 101 is pn
A p-transistor and 102 are npn transistors, respectively.

FIG. 5 is a flow of structure recognition processing showing an embodiment of the present invention. First, a recognition target structure such as a thyristor is input (step 51), then the layout is performed as described above, the data obtained as a result of the layout is read (step 52), and then the data is obtained. The recognition target structure is extracted by converting the network structure (step 53) and then solving the search problem (step 54), and finally the extraction result is displayed (step 5).
5).

[Embodiment 2] FIG. 6 is a flow of data conversion processing showing an embodiment of the present invention. This corresponds to step 53 in the first embodiment. First, the layout surface data is divided into unit surface data (step 61), then the process corresponding to each unit surface data is generated (step 62), and finally, a network having each process as a node. Is created (step 63).

For example, as shown in FIG. 7, a layout surface 71 composed of two types of diffusion layers of p and n is divided by a dotted line 72 to generate the network shown in FIG. Twenty-one nodes 82 are connected in a network by a bidirectional stream 83 as a parallel process.

That is, in the network, the layout surface is divided into n, p, etc., and the divided nodes are used as nodes. At this time, each unit division plane is divided up to a level at which a plurality of types are not mixed. Then, they are networked based on the adjacency relationship. In the experimental program, each unit division surface was divided so that it had four adjacent surfaces. The layout tree generated as a result of layout does not have all the data necessary for extracting parasitic elements.
Appropriate data must be added when creating the network. Each node has additional data. As node information, node name, adjacent node information, diffusion layer type,
The potential of the section, the position coordinates in the layout diagram, the element name in the layout and its portion, and the like can be given.

FIG. 9 shows a search of p-n-p-n-p for the data networked as shown in FIG. The portion corresponding to p is shaded. 91
Limits the passage of each diffusion layer only once,
No. 92 allows the appearance of n up to 5 times in a row.

[Third Embodiment] In most cases, the actual layout is more complicated than that of the second embodiment. For example, the pnp transistor 101 and the npn transistor 102 in the first embodiment are divided as shown in FIG. FIG. 11 is a part of the node data example, in which each node has a node name, an adjacent node name, a distance to the adjacent node, a position on the layout diagram, an average value and a maximum value and a minimum value of the potential, and a diffusion. Each layer has information such as a layer type, a corresponding circuit element name and a part.

[Embodiment 4] FIG. 12 is a flow of a structure search showing an embodiment of the present invention. This corresponds to step 54 in the first embodiment. First, the shortest path problem is solved (step 121), then only the neighborhood data of the start point node is collected (for example, up to 10 nodes are searched) (step 122), and then the same diffusion layer data is continued. Optimization is carried out (if n-n continues, set to n, etc.)
(Step 123) Finally, a structure to be recognized is searched (for example, pnpnp is searched for a portion where the diffusion layers are arranged) (step 124).

FIG. 13 is an example of pn-pn structure recognition on the layout surface 41 in the first embodiment. In the figure, the shaded portion represents the n diffusion layer, and the non-hatched portion represents the p diffusion layer. A white circle represents the position of the start point node, and a dotted line 131 represents the recognized structure. FIG. 14 shows a trial in which the starting point node is changed. The dotted line 141 indicates the recognized structural portion.

[Embodiment 5] In addition, as a search condition, an example in which a rule that the same potential surface is not crossed more than once is added and all nodes are started as starting points will be described. Figure 15
Is an example of the extracted data. FIG. 16 is a diagram showing FIG. 15 on the layout diagram 41.
Multiple solutions were obtained, such as 2,163.

[Embodiment 6] Also, four directions of north, south, east, west, etc.
If the search is performed in consideration of the message flow direction, finer structure recognition can be performed. This is useful for obtaining the current amplification factor of the transistor.

Further, by considering the potential condition (for example, the potential difference between one diffusion layer and another diffusion layer is 0.7 V or more), it is possible to more accurately extract the structure parasitic such as the parasitic thyristor.

Thus, in this embodiment, (a)
The specified structure can be extracted from the layout result data. Further, (b) extraction of multiparasitic parasitics such as a parasitic thyristor, which has been difficult to find in the past, is possible in this embodiment. Furthermore, the search can be sped up by using (c) the parallel processing device.

As described above, according to the embodiment of the present invention, it is possible to extract a parasitic element such as a parasitic thyristor which has been difficult to find in the past.

In a parallel computer system, a processing step of inputting a recognition target structure, a processing step of reading data obtained as a layout result, a processing step of converting data into a network structure, and a recognition target by solving a search problem. By providing the processing step of extracting the structure and the processing step of displaying the extraction result, it is possible to extract the specific structure from the layout result data.

By providing the processing step of dividing the layout surface data into unit surface data, the processing step of generating a process corresponding to each unit surface data, and the processing step of forming a network having each process as a node, A system suitable for a parallel processor was obtained.

A processing step for solving the shortest path problem, a processing step for collecting only data in the vicinity of the starting point node, a processing step for optimizing when the same diffusion layer data continues, and a processing step for searching a recognition target structure. By providing, the diffusion layer structure on the chip surface can be extracted.

All the solutions can be obtained by activating all the nodes as the starting point nodes.

When the layout plane data is divided into unit plane data, the preprocessing for structure recognition can be easily performed by dividing the layout plane data into a grid pattern.

When the search problem is solved, the potential condition is determined, the average value of the potential and the fluctuation range are considered, and when the search problem is solved, the direction of the search is held. Realistic structural parasitics can be extracted.

Since each node holds the data of each corresponding division plane, and all nodes hold the structure to be searched, each node is allocated to a different PE of the parallel processing device, which is efficient. Can be executed.

Since each node has a local memory, each node data can be assigned to a different PE and operated in parallel.

Since the bidirectional stream is placed between the nodes due to the adjacency relationship between the nodes, a network is generated and a solution is generated by message communication between the nodes, so that the features of the parallel processing apparatus can be utilized.

The memory efficiency can be improved by solving the shortest path problem and providing the path to the start point node and the distance to the start point node only to the nodes adjacent to the start point node.

When the layout plane data is divided into unit plane data, the number of nodes generated can be suppressed by dividing into the diffusion layer standard.

Since it is possible to search using a plurality of indexes, it is possible to recognize a complicated structure in which the potential point and the current amplification factor are taken into consideration.

By executing each step of structure recognition in parallel, the processing speed can be increased.

By generating a three-dimensional structure network, structure recognition can be performed even for layout result data having a three-dimensional structure.

Since each node has an attribute, efficient structure recognition can be performed for each divided node.

Since the data in the local memory is optimized each time a message flows in the stream, a system with good memory efficiency can be realized.

Assigning each node data to a different PE,
Since the search problem is solved by message communication between PEs,
A high-speed system suitable for a parallel processing device can be realized.

Since each node data is assigned to the PE depending on the structure of the original layout surface, the neighborhood search can be efficiently performed.

[0043]

As described above, according to the present invention, not only the unary relation but also the polynomial relation can be efficiently recognized.

[Brief description of drawings]

FIG. 1 is a system block diagram of a parallel computer system to which the present invention is applied.

FIG. 2 is a functional block diagram of an example of a layout system of the present invention.

FIG. 3 is a diagram of an example of a circuit net of the present invention.

FIG. 4 is an example of a layout diagram of the present invention.

FIG. 5 is a diagram showing a flow of structure recognition processing according to the first embodiment of the present invention.

FIG. 6 is a diagram showing a flow of data conversion processing according to the second embodiment of the present invention.

FIG. 7 is a diagram showing division of a planar structure according to a second embodiment of the present invention.

FIG. 8 is a diagram showing network creation according to the second embodiment of the present invention.

FIG. 9 is a diagram showing structure recognition in Example 2 of the present invention.

FIG. 10 is a diagram showing an example of division according to the third embodiment of the present invention.

FIG. 11 is a diagram showing an example of node data according to the third embodiment of the present invention.

FIG. 12 is a diagram showing a flow of a structure search according to the fourth embodiment of the present invention.

FIG. 13 is a diagram showing structure recognition in Example 4 of the present invention.

FIG. 14 is a diagram showing structure recognition in Example 4 of the present invention.

FIG. 15 is a diagram showing extracted data according to the fifth embodiment of the present invention.

FIG. 16 is a diagram showing structure recognition in Example 5 of the present invention.

[Explanation of symbols]

11 ... Parallel processing device, 12 ... Front-end processor, 13 ... Display device, 14 ... Manual operation input device, 15 ... Common bus, 21 ... Original data, 22 ... Output drawing, 23 ... Structure recognition process, 24 ... Input / output process , 25 ... Memory process, 26 ... Problem solving inference process, 27 ... Layout basic process, 41 ... Layout diagram, 71 ... Layout plane, 72 ... Layout plane division example, 82 ... Node,
83 ... Bidirectional stream, 91, 92, 131, 14
1, 161, 162, 163 ... Structure recognition example, 101 ... p
npn transistor structure example, 102 ... npn transistor structure example.

Claims (16)

[Claims] 1. In a parallel computer system, a processing step of inputting a structure to be recognized as a circuit net, a step of generating layout data based on the input circuit net, and the layout data being a network. −
Layout structure recognition, which includes the steps of converting into a network structure, extracting a structure to be recognized by searching a route for the network structure, and displaying an extraction result. Method. 2. The layout structure recognizing method according to claim 1, wherein said converting step divides layout plane data constituting layout data into unit plane data each consisting of one type of area. Layout structure recognition, which includes a step of creating a process, which is a processing unit corresponding to each unit surface data, and a step of creating a network having each process as a node. Method. 3. The layout structure recognition method according to claim 1, wherein said extracting step is a step of solving a shortest path problem for obtaining a shortest path from a starting node to each node, and based on the solved result. A step of collecting only the neighborhood data of the starting point node, a step of optimizing when the same kind of data continues, and a node according to the route obtained by the shortest route problem. And a layout structure recognizing method for searching the structure to be recognized by searching the layout structure. 4. The layout structure recognition method according to claim 1, further comprising a processing step of activating all nodes as starting point nodes. 5. The layout structure recognition method according to claim 1, wherein when the layout surface data is divided into unit surface data, the layout surface data is divided into a grid pattern. 6. The layout structure recognition method according to claim 1, wherein, when solving the shortest path problem, a path is searched by using an average value of the potential and a fluctuation range as potential conditions. 7. A layout structure recognizing method according to claim 1, wherein a network is generated by placing a bidirectional stream between each node according to the adjacency relation of each node. Layout structure recognition method. 8. The layout structure recognition method according to claim 1, wherein the route to the starting node and the distance to the starting node are determined based on the result of the shortest route problem. A layout structure recognition method characterized in that it is provided only to the code. 9. The layout structure recognition method according to claim 1, wherein, when the layout surface data is divided into unit surface data, the layout surface data is divided into diffusion layers. 10. The layout structure recognition method according to claim 1, wherein the route search is performed based on a plurality of indexes. 11. The layout structure recognition method according to claim 1, wherein all nodes hold a structure to be searched. 12. The layout structure recognition method according to claim 1, wherein each step of structure recognition is executed in parallel. 13. The layout structure recognition method according to claim 1 or 2, wherein a three-dimensional structure network is generated. 14. The layout structure recognition method according to claim 1, wherein the direction of the search is retained when solving the route search problem. 15. The layout structure recognition method according to claim 1, wherein each node data is assigned to each processor element constituting a parallel computer system, and a message between the processor elements is assigned. A layout structure recognition method characterized by solving a search problem by communication. 16. The layout structure recognizing method according to claim 15, wherein each node data is assigned to a processor element depending on a structure of an original layout surface. Recognition method.