CN116167321B - Protection ring generation method and device and related products - Google Patents
Protection ring generation method and device and related products Download PDFInfo
- Publication number
- CN116167321B CN116167321B CN202310119217.3A CN202310119217A CN116167321B CN 116167321 B CN116167321 B CN 116167321B CN 202310119217 A CN202310119217 A CN 202310119217A CN 116167321 B CN116167321 B CN 116167321B
- Authority
- CN
- China
- Prior art keywords
- convex hull
- points
- sorting
- hull sorting
- path
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
The application discloses a method and a device for generating a protection ring and related products, wherein the method comprises the following steps: determining the top points of the boundary boxes of the circuit components aiming at the circuit components to be protected by the same protection ring; based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes; performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points; for every two adjacent convex hull sequencing points along the convex hull sequencing direction, determining all optional paths capable of connecting the two adjacent convex hull sequencing points, wherein the Manhattan distance on each optional path is shortest; and generating the protection rings for the plurality of circuit components according to all the optional paths, thereby avoiding the area waste of the protection ring design in the prior art.
Description
Technical Field
The application belongs to the technical field of circuit design, and particularly relates to a protection ring generation method, a protection ring generation device and related products.
Background
Production practice shows that when the chip area is reduced by 10%, the die yield on each silicon chip can be improved by 15% -25%. Therefore, in the layout design, a designer desires to reduce the area of the layout as much as possible while conforming to the layout design of the process standard.
For example, in the layout design step, a guard ring (GuardRing) needs to be designed to realize isolation between devices to prevent noise influence between devices and to prevent LATCH-UP (LATCH-UP) of chips.
In the existing generation method of the protection ring (GuardRing), when a plurality of devices are surrounded to achieve the protection effect, guardRing is created according to the point column of the minimum circumscribed rectangle of the plurality of devices, so that the area waste condition can occur, the area of the layout is increased, and the area of a chip is larger.
Disclosure of Invention
The application provides a method and a device for generating a protection ring and related products, which are used for overcoming or relieving the defects of the prior art.
A method of generating a guard ring, comprising:
Determining the top points of the boundary boxes of the circuit components aiming at the circuit components to be protected by the same protection ring;
Based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes;
performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points;
for every two adjacent convex hull sequencing points along the convex hull sequencing direction, determining all optional paths capable of connecting the two adjacent convex hull sequencing points, wherein the Manhattan distance on each optional path is shortest;
According to the overlapping degree of the external expansion boundary frames of the circuit components, which correspond to all the selectable paths and each two adjacent convex hull sequencing points respectively, selecting one selectable path with the largest overlapping degree from the selectable paths as an effective path for connecting the two adjacent convex hull sequencing points;
the guard rings for the plurality of circuit components are generated based on the effective paths of all adjacent convex hull ordering points.
Optionally, the generating the guard ring for the plurality of circuit components based on the effective paths of all adjacent convex hull ordering points includes: and taking the communication paths of the effective paths of all adjacent convex hull sequencing points as the central line of the protection ring, and generating the protection ring for the plurality of circuit components based on the central line and the width of the protection ring.
Optionally, based on GRAHAMSCAN method, convex hull sorting is performed on the vertices of the external expansion bounding boxes of the circuit components to obtain convex hull sorting point columns.
Optionally, the determining all selectable paths that can connect each two adjacent convex hull sorting points along the direction of convex hull sorting includes:
Taking one of the convex hull sorting points as a starting point and the next convex hull sorting point along the convex hull sorting direction as an end point, and determining a forward optional path from the one of the convex hull sorting points to the next convex hull sorting point;
Switching one of the convex hull sorting points to the end point, switching the next convex hull sorting point along the convex hull sorting direction to the start point, and determining a reverse selectable path reaching the one of the convex hull sorting points from the next convex hull sorting point;
And determining all the alternative paths which can connect one convex hull sorting point to the next convex hull sorting point along the convex hull sorting direction according to the forward alternative path and the reverse alternative path, wherein the Manhattan distance of each alternative path is shortest.
Optionally, the determining all selectable paths that can connect each two adjacent convex hull sorting points along the direction of convex hull sorting includes:
carrying out layout grid point propagation on every two adjacent convex hull sorting points along the convex hull sorting direction, and determining layout grid points through which paths connecting the two adjacent convex hull sorting points can pass;
Backtracking the layout grid points in the direction opposite to the convex hull sorting direction, and determining the layout grid points through which a path connecting the two adjacent convex hull sorting points passes;
and determining all optional paths which can connect one convex hull sorting point to the next convex hull sorting point along the convex hull sorting direction according to all the traced-back layout grid points, wherein the Manhattan distance of each optional path is shortest.
Optionally, if it is determined that all the alternative paths that can connect the two adjacent convex hull sorting points meet an obstacle, the direction of the alternative path is adjustable based on a bounding box that can enable the alternative path to be along the obstacle, so as to avoid the obstacle.
Optionally, the determining all selectable paths that can connect each two adjacent convex hull sorting points along the direction of convex hull sorting further includes:
And determining all selectable paths capable of connecting every two adjacent convex hull sorting points according to the layout grid points between every two adjacent convex hull sorting points and the neighbor layout grid points of each layout grid point within the unit grid distance difference along each two adjacent convex hull sorting points in the convex hull sorting direction.
8. The method of claim 1, wherein said determining all alternative paths that connect each two adjacent convex hull ordering points along the direction of convex hull ordering, comprises: for every two adjacent convex hull sorting points along the convex hull sorting direction, carrying out propagation and backtracking of layout grid points based on the shortest Manhattan distance between the points to search path points capable of forming the optional path, and distributing labels for the searched path points; and connecting all path points allocated with the labels to form the optional path.
An electronic device comprising a memory for storing a computer executable program thereon, and a processor for running the computer executable program to implement any of the methods of the embodiments of the present application.
A computer program product having stored thereon computer executable instructions which when executed perform operations corresponding to the method according to any of the embodiments of the present application.
In the technical scheme provided by the application, the vertexes of the boundary boxes of the circuit components are determined by aiming at the circuit components to be protected by the same protection ring; based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes; performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points; for every two adjacent convex hull sequencing points along the convex hull sequencing direction, determining all optional paths capable of connecting the two adjacent convex hull sequencing points, wherein the Manhattan distance on each optional path is shortest; according to the overlapping degree of the external expansion boundary frames of the circuit components, which correspond to all the selectable paths and each two adjacent convex hull sequencing points respectively, selecting one selectable path with the largest overlapping degree from the selectable paths as an effective path for connecting the two adjacent convex hull sequencing points; based on the effective paths of all adjacent convex hull sequencing points, the protection rings aiming at the plurality of circuit components are generated, so that the area waste of the protection rings designed in the prior art is avoided, the area of a layout is reduced, and the area of a chip is smaller.
Drawings
Fig. 1 is a flow chart of a method for generating a protection ring according to an embodiment of the present application.
Fig. 2 is a schematic structural diagram of a protection ring generating device according to an embodiment of the present application.
Fig. 3 is a schematic structural diagram of an electronic device according to an embodiment of the application.
Fig. 4 is a schematic flow chart of a method for generating a protection ring according to an embodiment of the present application.
Fig. 5 is a schematic flow chart of a method for generating a protection ring according to an embodiment of the present application.
Fig. 6 is a flowchart of a method for generating a protection ring according to an embodiment of the present application.
Fig. 7 is a flowchart of a method for generating a protection ring according to an embodiment of the present application.
Fig. 8 is a schematic diagram of all alternative paths defined by 4 components isolated by the same guard ring.
Fig. 9 is a schematic view of the effective path determined on the basis of fig. 8.
Detailed Description
The technical solutions of the embodiments of the present application will be clearly described below with reference to the drawings in the embodiments of the present application, and it is apparent that the described embodiments are some embodiments of the present application, but not all embodiments. All other embodiments, which are obtained by a person skilled in the art based on the embodiments of the present application, fall within the scope of protection of the present application.
The terms first, second and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used may be interchanged, as appropriate, such that embodiments of the present application may be implemented in sequences other than those illustrated or described herein, and that the objects identified by "first," "second," etc. are generally of a type, and are not limited to the number of objects, such as the first object may be one or more. Furthermore, in the description and claims, "and/or" means at least one of the connected objects, and the character "/", generally means that the associated object is an "or" relationship.
Fig. 1 is a flow chart of a method for generating a protection ring according to an embodiment of the present application. As shown in fig. 1, it includes:
S101, aiming at a plurality of circuit components to be protected of the same protection ring, determining vertexes of a boundary frame of each circuit component;
s102, based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes;
S103, performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points;
The plurality of convex hull sorting points may be stored in a convex hull sorting point list, e.g. denoted as point_list, according to a convex hull sorting relative to each other, from which convex hull sorting points are obtained when executing the inventive solution.
S104, determining all optional paths capable of connecting every two adjacent convex hull sequencing points along the convex hull sequencing direction, wherein the Manhattan distance of each optional path is shortest;
S105, according to the overlapping degree of the external expansion bounding boxes of the circuit components, which correspond to all the selectable paths and each two adjacent convex hull sequencing points respectively, selecting one selectable path with the largest overlapping degree from the selectable paths as an effective path for connecting the two adjacent convex hull sequencing points;
S106, generating the protection rings for the circuit components based on the effective paths of all adjacent convex hull sequencing points.
In this embodiment, the processing in step S102 may be referred to as a preprocessing step. The process of step S103 described above may also be referred to as a point set ordering step. The process of step S104 described above may be also referred to as a path search step, which specifically includes the following processing of grid point propagation and grid point backtracking.
To this end, in another embodiment, the process of fig. 1 can be summarized as follows:
Pretreatment: determining the external expansion boundary boxes of a plurality of circuit components to be protected by the same protection ring;
A point set ordering step: performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points;
a path searching step: and carrying out path searching according to the convex hull sequencing points to generate the protection rings for the circuit components.
In the path searching step configured in the step S104, a path from the start point to the end point and a path from the end point to the start point are determined, so that a connection path of every two adjacent convex hull sorting points along the convex hull sorting direction can be realized as an optional path. For example, when two connection paths with the same Manhattan distance appear and the two connection paths are the same as the shortest Manhattan distance, the optimal alternative path is determined as the alternative path through the above screening step.
Optionally, in an embodiment, the generating the guard ring for the plurality of circuit components based on the effective paths of all adjacent convex hull ordering points includes: and taking the communication paths of the effective paths of all adjacent convex hull sequencing points as the central line of the protection ring, and generating the protection ring for the plurality of circuit components based on the central line and the width of the protection ring.
Optionally, in an embodiment, based on GRAHAMSCAN method, convex hull sorting is performed on the vertices of the outer expansion bounding box of each circuit component to obtain a convex hull sorting point column.
Optionally, in an embodiment, the determining all selectable paths that can connect each two adjacent convex hull ordering points along the direction of convex hull ordering includes:
Taking one of the convex hull sorting points as a starting point and the next convex hull sorting point along the convex hull sorting direction as an end point, and determining a forward optional path from the one of the convex hull sorting points to the next convex hull sorting point; to this end, based on the forward path, the distance values of all paths traversed from the start point to the end point may be updated.
Switching one of the convex hull sorting points to the end point, switching the next convex hull sorting point along the convex hull sorting direction to the start point, and determining a reverse selectable path reaching the one of the convex hull sorting points from the next convex hull sorting point;
And determining all the alternative paths which can connect one convex hull sorting point to the next convex hull sorting point along the convex hull sorting direction according to the forward alternative path and the reverse alternative path, wherein the Manhattan distance of each alternative path is shortest. Therefore, the method can screen out the path with the shortest Manhattan distance along the convex hull sorting direction according to the updated distance value, and the path is used as the optional path.
Optionally, in an embodiment, the determining all selectable paths that can connect each two adjacent convex hull ordering points along the direction of convex hull ordering includes:
carrying out layout grid point propagation on every two adjacent convex hull sorting points along the convex hull sorting direction, and determining layout grid points through which paths connecting the two adjacent convex hull sorting points can pass;
Backtracking the layout grid points in the direction opposite to the convex hull sorting direction, and determining the layout grid points through which a path connecting the two adjacent convex hull sorting points passes;
and determining all optional paths which can connect one convex hull sorting point to the next convex hull sorting point along the convex hull sorting direction according to all the traced-back layout grid points, wherein the Manhattan distance of each optional path is shortest.
Optionally, in an embodiment, if it is determined that all the alternative paths that can connect the two adjacent convex hull sorting points meet an obstacle, the direction of the alternative path is made adjustable based on a bounding box that can make the alternative path along the obstacle, so as to avoid the obstacle. Such as the frame of the circuit component being protected.
In addition, when the path is determined, if no obstacle exists, the path is prevented from turning as much as possible under the condition of correct direction.
Optionally, in an embodiment, the determining all selectable paths that can connect every two adjacent convex hull sorting points in the direction along which the convex hulls sort, further includes:
And determining all selectable paths capable of connecting every two adjacent convex hull sorting points according to the layout grid points between every two adjacent convex hull sorting points and the neighbor layout grid points of each layout grid point within the unit grid distance difference along each two adjacent convex hull sorting points in the convex hull sorting direction.
For example, for a certain grid point (x, y), the neighboring layout grid points of this point are the following four points (x-1, y), (x+1, y), (x, y-1), (x, y+1). Similarly, for convex hull rank points, neighbor layout grid points may also be determined in this manner.
Illustratively, the alternate path may be recorded in a path parameter all_path to facilitate determining the guard ring directly based on all_path.
Optionally, in an embodiment, the determining all selectable paths that can connect each two adjacent convex hull ordering points along the direction of convex hull ordering includes: for every two adjacent convex hull sorting points along the convex hull sorting direction, carrying out propagation and backtracking of layout grid points based on the shortest Manhattan distance between the points to search path points capable of forming the optional path, and distributing labels for the searched path points; and connecting all path points allocated with the labels to form the optional path.
The path points to which the labels are assigned may be recorded in the final result point column Q.
Illustratively, the Manhattan distance between points is recorded, such as by a two-dimensional array dist [ x ] [ y ], where [ x ] [ y ] is the coordinates of the points on the layout. For example, the coordinates of any convex hull sorting point in every two adjacent convex hull sorting points on the layout and the coordinates of the neighboring layout grid points on the layout can be used for determining the optional path.
Further, for any one of the grid points found in determining the alternative path, the manhattan distance of the grid point with respect to the starting point may be recorded by a data list H, such as specifically storing ((x, y), d) type data, (x, y) being coordinates of the grid point on the layout, d being the manhattan distance from the starting point to (x, y), the H being arranged in ascending order according to the d value. For this reason, the above-described alternative paths can be determined by directly giving a data list to be implemented, thereby improving the speed and efficiency of data processing.
Wherein the shortest manhattan distance may be recorded by another parameter, such as named best.
Fig. 2 is a schematic structural diagram of a protection ring generating device according to an embodiment of the present application. As shown in fig. 2, it includes:
A vertex determining unit configured to determine vertices of a bounding box of each circuit component for a plurality of circuit components to be protected by the same protection ring;
The boundary expanding unit is used for expanding the boundary frames of the circuit components according to the widths of the protection rings based on the vertexes of the boundary frames of the circuit components to obtain an expanded boundary frame;
The convex hull sorting unit is used for sorting convex hulls on the vertexes of the outer expansion boundary frames of the circuit components to obtain convex hull sorting point columns, and the convex hull sorting point columns comprise a plurality of convex hull sorting points;
A path searching unit, configured to determine, for each two adjacent convex hull sorting points in a direction along the convex hull sorting, all selectable paths that can connect the two adjacent convex hull sorting points;
The path screening unit is used for selecting one optional path with the largest overlapping degree from the overlapping degrees of the external expansion bounding boxes of the circuit components according to the overlapping degrees of all the optional paths and the external expansion bounding boxes of the circuit components corresponding to each two adjacent convex hull sorting points respectively as an effective path for connecting the two adjacent convex hull sorting points;
and the protection ring generating unit is used for generating the protection rings for the plurality of circuit components based on the effective paths of all adjacent convex hull sequencing points.
Exemplary explanations about the respective units described above may be referred to the embodiment of fig. 1 described above, and are not repeated here.
Fig. 3 is a schematic structural diagram of an electronic device according to an embodiment of the application. As shown in fig. 3, the electronic device includes a memory for storing a computer executable program thereon, and a processor for running the computer executable program to implement any of the methods of the embodiments of the present application.
Embodiments of the present application also provide a computer program product having stored thereon computer executable instructions that, when executed, implement operations corresponding to the method according to any of the embodiments of the present application.
Fig. 4 is a schematic flow chart of a method for generating a protection ring according to an embodiment of the present application. As shown in fig. 4, it includes:
S401, determining the top points of the boundary boxes of the circuit components aiming at the circuit components to be protected of the same protection ring;
S402, based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes;
s403, performing convex hull sorting on the vertices of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein the convex hull sorting point columns comprise a plurality of convex hull sorting points;
s404, generating the protection rings for the circuit components according to the convex hull sorting points.
Illustratively, generating the guard ring for the plurality of circuit components from the plurality of convex hull ordering points comprises:
for each two adjacent convex hull sorting points in a direction along the convex hull sorting, determining all selectable paths that can connect the two adjacent convex hull sorting points;
and generating the protection ring according to all the optional paths.
Illustratively, generating the guard ring according to all of the selectable paths includes:
Determining the central line of the protection ring according to all the optional paths;
and generating the protection ring according to the central line and the set protection ring width.
Illustratively, the determining the center line of the protection ring according to all the optional paths includes selecting one optional path with the largest overlapping degree from the overlapping degrees of the external expansion bounding boxes of the circuit components respectively corresponding to the two adjacent convex hull sorting points according to the all the optional paths as an effective path for connecting the two adjacent convex hull sorting points;
And determining the central line of the protection ring based on the effective paths of all adjacent convex hull sequencing points.
Fig. 5 is a schematic flow chart of a method for generating a protection ring according to an embodiment of the present application. As shown in fig. 5, it includes:
s501, generating an external expansion boundary frame corresponding to each circuit component aiming at a plurality of circuit components to be protected of the same protection ring;
S502, performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points;
S503, generating the protection rings for the circuit components according to the convex hull sorting points.
Illustratively, generating, for a plurality of circuit components to be protected by the same protection ring, an external expansion bounding box corresponding to each circuit component includes:
Determining the top points of the boundary boxes of the circuit components aiming at the circuit components to be protected by the same protection ring;
and (3) based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes.
Fig. 6 is a flowchart of a method for generating a protection ring according to an embodiment of the present application. As shown in fig. 6, it includes:
s601, determining a boundary box of each circuit component aiming at a plurality of circuit components to be protected of the same protection ring;
S602, performing convex hull sorting on the vertexes of the boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points;
S603, determining all optional paths capable of connecting every two adjacent convex hull sequencing points along the convex hull sequencing direction, wherein the Manhattan distance of each optional path is shortest;
s604, selecting one optional path with the largest overlapping degree from the overlapping degrees of the external expansion bounding boxes of the circuit components according to the overlapping degrees of all the optional paths and the external expansion bounding boxes of the circuit components respectively corresponding to each two adjacent convex hull sequencing points as an effective path for connecting the two adjacent convex hull sequencing points;
S605, generating the protection rings for the plurality of circuit components based on the effective paths of all adjacent convex hull sequencing points.
Illustratively, generating the guard ring for the plurality of circuit components based on the effective paths of all adjacent convex hull ordering points comprises: and taking the effective paths of all adjacent convex hull sequencing points as the inner boundary of the protection ring, and extending the inner boundary based on the set protection ring width to generate the protection ring.
Unlike the above-described embodiments, the process of the bounding box of each circuit component is omitted.
Fig. 7 is a flowchart of a method for generating a protection ring according to an embodiment of the present application. As shown in fig. 7, it includes:
S701, determining boundary boxes of all circuit components aiming at a plurality of circuit components to be protected of the same protection ring;
S702, performing convex hull sorting on the vertexes of the boundary boxes of each circuit component to obtain a convex hull sorting point column, wherein the convex hull sorting point column comprises a plurality of convex hull sorting points;
S703, searching an optional path according to the convex hull sorting points to generate the protection rings for the circuit components according to the optional paths.
Illustratively, the step S703 may include:
for every two adjacent convex hull sorting points along the convex hull sorting direction, determining all optional paths capable of connecting the two adjacent convex hull sorting points, wherein the Manhattan distance of each optional path is shortest;
According to the overlapping degree of the external expansion boundary frames of the circuit components, which correspond to all the selectable paths and each two adjacent convex hull sequencing points respectively, selecting one selectable path with the largest overlapping degree from the selectable paths as an effective path for connecting the two adjacent convex hull sequencing points;
the guard rings for the plurality of circuit components are generated based on the effective paths of all adjacent convex hull ordering points.
In the foregoing fig. 4-7, it is considered that in some scenarios, the steps in the embodiment shown in fig. 1 are not all necessary or the only implementation manner, so that a part of the steps are omitted or are generally described, and other steps similar to or the same as those in fig. 1 are the same as those in fig. 1, and detailed descriptions thereof are omitted herein.
The method for generating the protection ring is specifically applied to a scene, and schematic diagrams of the method are shown in fig. 8-9.
Referring to fig. 8, if 4 components are isolated by the same protection ring, it is determined that all the alternative paths corresponding to all the convex hull sequencing nodes are shown as light green line segments in the figure. As shown in fig. 9, the determined effective path is shown as a red line segment in the figure, that is, the red line segment can be connected together to serve as a center line (or an inner contour line) of the guard ring, so as to further combine the width of the guard ring to generate the guard ring.
The embodiments of the present application have been described above with reference to the accompanying drawings, but the present application is not limited to the above-described embodiments, which are merely illustrative and not restrictive, and many forms may be made by those having ordinary skill in the art without departing from the spirit of the present application and the scope of the claims, which are to be protected by the present application.
Claims (10)
1. The method for generating the protection ring is characterized by comprising the following steps:
Determining the top points of the boundary boxes of the circuit components aiming at the circuit components to be protected by the same protection ring;
Based on the vertexes of the boundary boxes of the circuit components, performing outward expansion on the boundary boxes of the circuit components according to the width of the protection ring to obtain outward expansion boundary boxes;
performing convex hull sorting on the vertexes of the outer expansion boundary boxes of the circuit components to obtain convex hull sorting point columns, wherein each convex hull sorting point column comprises a plurality of convex hull sorting points;
for every two adjacent convex hull sequencing points along the convex hull sequencing direction, determining all optional paths capable of connecting the two adjacent convex hull sequencing points, wherein the Manhattan distance on each optional path is shortest;
According to the overlapping degree of the external expansion boundary frames of the circuit components, which correspond to all the selectable paths and each two adjacent convex hull sequencing points respectively, selecting one selectable path with the largest overlapping degree from the selectable paths as an effective path for connecting the two adjacent convex hull sequencing points;
the guard rings for the plurality of circuit components are generated based on the effective paths of all adjacent convex hull ordering points.
2. The method of claim 1, wherein the generating the guard ring for the plurality of circuit components based on the effective paths of all adjacent convex hull ordering points comprises: and taking the communication paths of the effective paths of all adjacent convex hull sequencing points as the central line of the protection ring, and generating the protection ring for the plurality of circuit components based on the central line and the width of the protection ring.
3. The method of claim 1, wherein convex hull ordering is performed on vertices of the expanded bounding boxes of the respective circuit components based on GRAHAM SCAN method to obtain a convex hull ordering point column.
4. The method of claim 1, wherein said determining all alternative paths that connect each two adjacent convex hull ordering points along the direction of convex hull ordering, comprises:
taking one of the convex hull sorting points as a starting point and the next convex hull sorting point along the convex hull sorting direction as an end point, and determining a forward optional path from the one of the convex hull sorting points to the next convex hull sorting point;
Switching one of the convex hull sorting points to the end point, switching the next convex hull sorting point along the convex hull sorting direction to the start point, and determining a reverse selectable path reaching the one of the convex hull sorting points from the next convex hull sorting point;
And determining all the alternative paths which can connect one convex hull sorting point to the next convex hull sorting point along the convex hull sorting direction according to the forward alternative path and the reverse alternative path, wherein the Manhattan distance of each alternative path is shortest.
5. The method of claim 4, wherein said determining all alternative paths that connect each two adjacent convex hull ordering points along the direction of convex hull ordering, comprises:
carrying out layout grid point propagation on every two adjacent convex hull sorting points along the convex hull sorting direction, and determining layout grid points through which paths connecting the two adjacent convex hull sorting points can pass;
Backtracking the layout grid points in the direction opposite to the convex hull sorting direction, and determining the layout grid points through which a path connecting the two adjacent convex hull sorting points passes;
and determining all optional paths which can connect one convex hull sorting point to the next convex hull sorting point along the convex hull sorting direction according to all the traced-back layout grid points, wherein the Manhattan distance of each optional path is shortest.
6. The method according to claim 4 or 5, wherein if it is determined that all the alternative paths connecting the two adjacent convex hull sorting points meet an obstacle, the direction of the alternative path is made adjustable based on a bounding box corresponding to the obstacle along which the alternative path can be made to avoid the obstacle.
7. The method of claim 1, wherein the determining all alternative paths that connect each two adjacent convex hull ordering points along the direction of convex hull ordering, further comprises:
And determining all selectable paths capable of connecting every two adjacent convex hull sorting points according to the layout grid points between every two adjacent convex hull sorting points and the neighbor layout grid points of each layout grid point within the unit grid distance difference along each two adjacent convex hull sorting points in the convex hull sorting direction.
8. The method of claim 1, wherein said determining all alternative paths that connect each two adjacent convex hull ordering points along the direction of convex hull ordering, comprises: for every two adjacent convex hull sorting points along the convex hull sorting direction, carrying out propagation and backtracking of layout grid points based on the shortest Manhattan distance between the points to search path points capable of forming the optional path, and distributing labels for the searched path points; and connecting all path points allocated with the labels to form the optional path.
9. An electronic device comprising a memory for storing a computer executable program thereon and a processor for running the computer executable program to implement the method of any of claims 1-8.
10. A computer program product having stored thereon computer executable instructions which when executed perform the operations corresponding to the method of any of claims 1-8.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310119217.3A CN116167321B (en) | 2023-01-19 | 2023-01-19 | Protection ring generation method and device and related products |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310119217.3A CN116167321B (en) | 2023-01-19 | 2023-01-19 | Protection ring generation method and device and related products |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN116167321A CN116167321A (en) | 2023-05-26 |
| CN116167321B true CN116167321B (en) | 2024-07-26 |
Family
ID=86419564
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310119217.3A Active CN116167321B (en) | 2023-01-19 | 2023-01-19 | Protection ring generation method and device and related products |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN116167321B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107615481A (en) * | 2015-05-18 | 2018-01-19 | 索尼公司 | Semiconductor device and imaging device |
| CN114730353A (en) * | 2019-12-09 | 2022-07-08 | 美商新思科技有限公司 | Circuit design using cells with metal lines |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05151316A (en) * | 1991-11-26 | 1993-06-18 | Fujitsu Ltd | Wiring route determination method |
| US6480995B1 (en) * | 1996-04-15 | 2002-11-12 | Altera Corporation | Algorithm and methodology for the polygonalization of sparse circuit schematics |
| US6550047B1 (en) * | 2000-10-02 | 2003-04-15 | Artisan Components, Inc. | Semiconductor chip input/output cell design and automated generation methods |
| US9202000B1 (en) * | 2014-09-30 | 2015-12-01 | Cadence Design Systems, Inc. | Implementing designs of guard ring and fill structures from simple unit cells |
| JP2016177327A (en) * | 2015-03-18 | 2016-10-06 | 伸彦 井戸 | Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming |
| CN112711972B (en) * | 2019-10-26 | 2024-06-14 | 海思技术有限公司 | Target detection method and device |
| US11763060B2 (en) * | 2021-03-25 | 2023-09-19 | Taiwan Semiconductor Manufacturing Company, Ltd. | Automatic generation of layouts for analog integrated circuits |
-
2023
- 2023-01-19 CN CN202310119217.3A patent/CN116167321B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107615481A (en) * | 2015-05-18 | 2018-01-19 | 索尼公司 | Semiconductor device and imaging device |
| CN114730353A (en) * | 2019-12-09 | 2022-07-08 | 美商新思科技有限公司 | Circuit design using cells with metal lines |
Also Published As
| Publication number | Publication date |
|---|---|
| CN116167321A (en) | 2023-05-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5636129A (en) | Electrical routing through fixed sized module and variable sized channel grids | |
| US5361214A (en) | Method for automatically determining wiring routes | |
| US20010009031A1 (en) | Method and apparatus for global routing, and storage medium having global routing program stored therein | |
| JP2000222453A (en) | Method and device for compacting layout | |
| CN116167321B (en) | Protection ring generation method and device and related products | |
| US5399517A (en) | Method of routing three layer metal gate arrays using a channel router | |
| CN102270233B (en) | Searching method for convex hull | |
| CN111581701B (en) | BIM-based photovoltaic power station automatic arrangement method | |
| JP3157732B2 (en) | Interactive wiring pattern creation system | |
| US4905144A (en) | High speed path optimization co-processor | |
| CN116089557A (en) | Data processing method, device and storage medium | |
| CN103164551A (en) | Method of constructing low temperature subarray on reconfigurable very large scale integration (VLSI) array | |
| JPH04293177A (en) | Image processing method | |
| WO2021036424A1 (en) | Parallel efficient computing method for box filter | |
| JP3006156B2 (en) | Automatic wiring method | |
| Mata et al. | PCB Auto Routing Algorithm Based on Morphological Operations | |
| Banerjee et al. | Floorplanning in modern FPGAs | |
| Huang et al. | Deep Learning based Refinement for Package Substrate Routing | |
| JP3006244B2 (en) | Automatic wiring method | |
| CN113741143A (en) | Mask defect point sorting method and repairing method | |
| JPH03194950A (en) | Channel wiring equipment | |
| JPH07307448A (en) | Method for designing semiconductor integrated circuit device | |
| CN117949003A (en) | Path planning method based on geometric topological structure | |
| JPH09153083A (en) | Oblique line segment generation device and method for automatic wiring design system | |
| Chuquillanqui | Internal connection problem in large optimized PLAs |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |