CN-115796109-B - Chip standard unit legalization method and system considering adjacent diffusion effect

CN115796109BCN 115796109 BCN115796109 BCN 115796109BCN-115796109-B

Abstract

The invention provides a chip standard cell legalization method and system considering adjacent diffusion effect, relating to the field of electronic design automation, and specifically comprising the steps of constructing a minimum spanning tree based on cell layout and left and right diffusion heights; decomposing and reconnecting the minimum spanning tree to generate a Hamiltonian path; the invention designs a Hamiltonian-based algorithm to calculate new locations of cells by moving cells on a single layout row so that neighboring cells have the same diffusion height, reducing NDE violations to near optimal minimum and minimizing maximum cell movement without any area overhead, while achieving better real run time.

Inventors

GUO LONGKUN
SUN HAO
ZHANG XIAOYAN
Jia Chaoqi

Assignees

齐鲁工业大学

Dates

Publication Date: 20260505
Application Date: 20221128

Claims (4)

1. A method of chip standard cell legalization taking into account the effect of neighbor diffusion, comprising: constructing an auxiliary graph based on the cell layout and the left-right diffusion height; Reordering the units of the auxiliary graph by means of the minimum spanning tree and Hamiltonian path to obtain a unit arrangement sequence; Calculating the site position of the unit on the layout row according to the unit arrangement sequence and the unit width; The construction auxiliary graph specifically comprises the following steps: Three vertexes are constructed for each cell, a cell vertex, a left diffusion height vertex and a right diffusion height vertex; an edge is arranged between each unit vertex and the left diffusion height vertex, and an edge is arranged between each unit vertex and the right diffusion height vertex; An edge is arranged between the diffusion height vertexes of different units with the same diffusion height; The reordering of the units of the auxiliary graph is specifically as follows: obtaining a minimum spanning tree of the auxiliary graph; Decomposing the minimum spanning tree into a plurality of vertex disjoint paths; reconnecting the plurality of vertex disjoint paths to a hamilton path; Obtaining the sequence of units according to the vertex sequence in the Hamiltonian path; the minimum spanning tree for obtaining the auxiliary graph is specifically: (1) Setting the weight of an edge between two vertexes in the auxiliary graph as the sum of the degrees of the two vertexes; (2) Removing the edges with the maximum weight and the auxiliary graph without isolated vertexes after the removal, and if two edges with the maximum weight and the same weight exist, optionally removing one edge; Repeating the steps (1) and (2) until the auxiliary graph becomes a tree; Decomposing the minimum spanning tree into a plurality of vertex disjoint paths, namely decomposing and reconnecting the minimum spanning tree by adopting the idea of Hamiltonian, so as to form a plurality of vertex disjoint paths; Reconnecting the plurality of vertex disjoint paths into a hamilton path, wherein the method specifically comprises the following steps: (1) Is provided with For the number of paths that the vertices do not intersect, And For the range of maximum cell displacement, Setting the maximum number of NDE violations allowed to occur And a maximum number of allowed exceeding maximum displacement units ; (2) Order the ; (3) Adding The bar weights are as small as possible The vertex disjoint paths are connected end to end, and standard units corresponding to the vertices connected by the edges have the same diffusion height; (4) Optionally add The bar weights are as small as possible Is connected with the rest end points; (5) After the addition is completed Breaking one side in Hamiltonian loop formed after the side to enable As the starting point of the Hamiltonian path, and calculate that the weight in the formed Hamiltonian path is greater than Number of edges of (a) ; (6) If it is Then ; If it is Then ; If it is Step (8) is performed (7) Repeating steps (2) - (6); (8) Outputting the Hamiltonian path in the step (5); the site position of the computing unit on the layout row is specifically: Calculating the number of occupied sites according to the width of the unit; the units are placed in sequence at the next site location of the site occupied by the previous unit.
2. A chip standard cell legalization system considering the adjacent diffusion effect, which is characterized in that the chip standard cell legalization method considering the adjacent diffusion effect according to claim 1 comprises an auxiliary graph construction module, a cell ordering module and a position calculation module: An auxiliary graph construction module configured to construct an auxiliary graph based on the cell layout and the left-right diffusion height; the unit ordering module is configured to reorder units of the auxiliary graph by means of the minimum spanning tree and the Hamiltonian path to obtain a unit ordering sequence; and a position calculation module configured to calculate site positions of the cells on the layout row according to the cell arrangement order and the cell width.
3. A computer readable storage medium having stored thereon a program, characterized in that the program when executed by a processor realizes the steps in a chip standard cell legitimization method taking into account the effect of contiguous diffusion as claimed in claim 1.
4. An electronic device comprising a memory, a processor and a program stored on the memory and executable on the processor, wherein the processor performs the steps of a chip standard cell legitimization method taking into account the effect of contiguous diffusion as claimed in claim 1.

Description

Chip standard unit legalization method and system considering adjacent diffusion effect Technical Field The invention belongs to the field of electronic design automation, and particularly relates to a chip standard unit legalization method and system considering an adjacent diffusion effect. Background The statements in this section merely provide background information related to the present disclosure and may not necessarily constitute prior art. With the impact of photolithography and the expansion of devices in advanced technology, device performance depends not only on geometry independent parameters but also on Layout Dependent Effects (LDEs), where performance degradation can be as high as 10% or more, where LDEs are used, where the adjacent diffusion effect (Neighbor diffusion effectNDE) is an important type of LDE, where NDE is caused by the different diffusion heights (fin numbers) between two adjacent cells, it is worth mentioning that each cell has two diffusion heights on the left and right sides, which are not necessarily the same, where the performance of the transistor is reduced due to the mismatch in diffusion heights between adjacent transistors, which impact has become critical to be addressed with advanced technology. In the conventional chip standard cell legalization, only the situation that the diffusion heights at two sides of the cell are equal is often considered, however, with the continuous development of devices and photoetching technology in a chip, standard cells with the same diffusion heights at two sides cannot meet the performance requirements of the devices of the chip, and the influence of the adjacent diffusion effect NDE on the performance of the chip is more serious, but the conventional standard cell layout method cannot meet the increasing requirements. In addition to reducing NDE violations and minimizing maximum cell movement, the cell must also meet the following hard constraints: (1) Standard cells must be placed within the chip area; (2) The standard units cannot be overlapped; (3) Standard cells must be placed on sites of a layout row; Therefore, on the premise of meeting the hard constraint, how to accurately control the different diffusion heights of the units to realize the optimal chip standard unit legalization is a subject worthy of research. Disclosure of Invention To overcome the above-mentioned shortcomings of the prior art, the present invention provides a method and system for chip standard cell legalization considering the effect of adjacency diffusion, which designs a new position of a cell based on Hamiltonian algorithm, by moving cells on a single layout row to make adjacent cells have the same diffusion height, reduce NDE violations to near optimal minimum and minimize maximum cell movement without any area overhead, while achieving better real run time. To achieve the above object, one or more embodiments of the present invention provide the following technical solutions: the first aspect of the present invention provides a chip standard cell legalization method considering an adjacent diffusion effect; A method of chip standard cell legalization taking into account the effect of neighbor diffusion, comprising: constructing an auxiliary graph based on the cell layout and the left-right diffusion height; Reordering the units of the auxiliary graph by means of the minimum spanning tree and Hamiltonian path to obtain a unit arrangement sequence; The site positions of the cells on the layout row are calculated based on the cell arrangement order and the cell width. Further, the construction auxiliary graph specifically comprises: Three vertexes are constructed for each cell, a cell vertex, a left diffusion height vertex and a right diffusion height vertex; an edge is arranged between each unit vertex and the left diffusion height vertex, and an edge is arranged between each unit vertex and the right diffusion height vertex; there is an edge between the diffusion height vertices of different cells having the same diffusion height. Further, the reordering of the units of the auxiliary graph is specifically as follows: obtaining a minimum spanning tree of the auxiliary graph; Decomposing the minimum spanning tree into a plurality of vertex disjoint paths; reconnecting the plurality of vertex disjoint paths to a hamilton path; the order of the units is found from the order of the vertices in the hamiltonian path. Further, the obtaining the minimum spanning tree of the auxiliary graph specifically includes: (1) Setting the weight of an edge between two vertexes in the auxiliary graph as the sum of the degrees of the two vertexes; (2) The edges with the greatest weight and the isolated vertexes of the auxiliary graph will not appear after the removal, if two edges with the greatest weight and the same weight are present, one removal is selected. Repeating the steps (1) and (2) until the auxiliary graph becomes a tree. Further, the decomposition of the