Search

CN-122021530-A - Buffer insertion method for local density perception

CN122021530ACN 122021530 ACN122021530 ACN 122021530ACN-122021530-A

Abstract

The invention relates to a buffer insertion method for local density sensing, belonging to the field of very large scale integrated circuits. The method comprises the steps of uniformly dividing a physical design area of a chip into a plurality of rectangular grids, traversing and calculating local layout density values of all the grids to form a digital density map, identifying high-density areas by adopting a density-based clustering algorithm based on the digital density map, marking each identified high-density area as a density obstacle, generating an interconnection tree capable of avoiding all the density obstacles aiming at a target wire network, generating a series of buffer insertion candidate points on a path of the interconnection tree, searching in a candidate point set formed by the buffer insertion candidate points by adopting an improved dynamic programming algorithm, and determining the final buffer insertion position and type by taking signal time sequence and local density cost caused by buffer insertion as optimization targets. The invention realizes the full-flow density perception optimization from global planning to local decision.

Inventors

  • LI CHEN

Assignees

  • 福州立芯科技有限公司

Dates

Publication Date
20260512
Application Date
20260127

Claims (10)

  1. 1. A method of local density aware buffer insertion comprising: Establishing a density map, namely uniformly dividing a physical design area of a chip into a plurality of rectangular grids, traversing and calculating local layout density values of all the grids to form a digital density map which covers the whole chip and reflects the distribution compactness of units in each area; Generating high-density area barriers, namely identifying high-density areas by adopting a density-based clustering algorithm based on a digital density map, and marking each identified high-density area as a density barrier; Generating an interconnection tree capable of avoiding all density obstacles and a series of buffer insertion candidate points on the path of the interconnection tree aiming at a target network, wherein the positions of partial candidate points are finely adjusted according to the local layout density values of the positions of the partial candidate points; And inserting the buffer, namely searching in a candidate point set formed by buffer insertion candidate points by adopting an improved dynamic programming algorithm, and determining the final buffer insertion position and type by taking the signal time sequence and the local density cost caused by buffer insertion as optimization targets.
  2. 2. A method of local density aware buffer insertion according to claim 1, wherein the local layout density value of each grid is obtained by calculating the ratio of the total footprint of all actual layout cells within the grid to the theoretical receivable area of the grid.
  3. 3. The method for inserting a buffer of local density perception according to claim 1, wherein the density-based clustering algorithm is a DBSCAN algorithm, which defines a grid with a local layout density value exceeding a preset threshold in the digitized density map as a high-density grid for clustering, and generates a minimum circumscribed rectangle surrounding each high-density cluster as a density obstacle.
  4. 4. The method for inserting the buffer perceived by the local density according to claim 1, wherein an algorithm adopted for generating an interconnection tree for avoiding density obstacles is a right-angle Steiner minimum tree algorithm for avoiding obstacles, and the optimization target is to find a right-angle wiring topology which is connected with all pins of a target wire mesh and has the minimum total Manhattan wire length on the premise of avoiding all the density obstacles.
  5. 5. The method of claim 1, wherein the step of generating buffer insertion candidate points on the interconnection tree comprises uniformly cutting trunk and branch line segments of the interconnection tree to obtain cut points as initial candidate points, and trimming the initial candidate points falling in a region with a local layout density value higher than a predetermined value to an adjacent legal position with an acceptable local layout density value along a direction perpendicular to the current line segment.
  6. 6. The method of claim 1, wherein the modified dynamic programming algorithm maintains a set of states for each candidate point when traversing the interconnect tree, each state including at least a load capacitance C seen downstream from the current point, a worst arrival time T of signals from the current point to all endpoints downstream therefrom, and an estimated value D of local density cost incurred by the buffer inserted downstream from the current point, and wherein the modified dynamic programming algorithm performs a subsequent traversal in the electrical connection direction with a root node of the interconnect tree as a starting point and a leaf node as an ending point when traversing the interconnect tree.
  7. 7. The method according to claim 6, wherein during the state transition of the modified dynamic programming algorithm, the load capacitor C seen downstream is reset according to the buffer model, and the cell delay and the line delay of the buffer itself are accumulated, the arrival time T is updated, and the accumulated evaluation value D of the local density cost is determined by the cell area of the buffer and the density sensitivity coefficient of the grid where the corresponding candidate point is located.
  8. 8. The method of claim 6, wherein the modified dynamic programming algorithm performs pruning for two states (C1, T1, D1) and (C2, T2, D2) that reach the same candidate point, the latter state being pruned if C1C 2, T1T 2 and D1D 2 are simultaneously true, wherein 1 and 2 represent two states, respectively.
  9. 9. The method of claim 6, wherein the objective function used in selecting the final solution from the state set obtained at the root node by the modified dynamic programming algorithm is a weighted sum of T and D, α+β+β, where α and β are configurable weight coefficients.
  10. 10. The method for local density aware buffer insertion of claim 1, wherein the method is applied to a physical design flow of a very large scale integrated circuit for timing optimization and density optimization.

Description

Buffer insertion method for local density perception Technical Field The invention belongs to the field of very large scale integrated circuits, and particularly relates to a buffer insertion method for local density sensing. Background As semiconductor process nodes continue to enter deep submicron and below, the scale and complexity of very large scale integrated circuits grows exponentially. The interconnect line delay (i.e., line delay) has replaced the transistor gate delay and has become a dominant factor in determining chip performance (timing). Buffer insertion has become a critical and widely used technique in physical design flows in order to meet increasingly stringent timing requirements (e.g., setup time, hold time). The method has the core effects of obviously reducing signal propagation delay, repairing timing violations and improving signal integrity by relaying and amplifying signals and driving long interconnection lines. Conventional buffer insertion techniques have a high degree of optimization focused on timing closure. Design automation tools (e.g., static timing analysis tools and place and route tools) may apply a series of algorithms (e.g., minimum delay buffering based on dynamic programming) to find the optimal location and type of insertion buffer on the timing path based on a given cell library and interconnect model to minimize the total path delay or eliminate timing violations. This process mainly pursues a globally optimal solution for timing optimization. In today's very large scale integrated circuit designs containing billions of transistors, the inherent defect of ignoring physical layout density is increasingly pronounced, mainly causing two serious problems: 1. Resulting in too high a local layout density, affecting the legal layout, the tool may "over-center" insert a large number of buffers near the timing critical area in order to maximize timing benefits. This can easily result in the sum of the cell areas of the localized areas exceeding the physical upper limit of the area that can be accommodated by the area (i.e., the density exceeds the standard). In the subsequent layout legitimization step, the tool must spread these "excess" cells to the surrounding area, which can not only destroy the optimized timing (because the cells are shifted and the interconnect line length is changed), but can also cause problems with complex cell overlap relief, layout legitimization difficulties, etc., and even result in a reversal of the optimization results. 2. Causing wiring congestion-the buffer itself needs to be connected to the power/ground and other signal lines. The insertion of too many buffers in a local area means that the number of pins (Pin) and vias (Via) that need to be routed in that area increases dramatically. This can drastically consume the limited routing channel resources of the area, resulting in routing congestion. The severe congestion forces the wire-wrapping tool to make long-distance wire-wrapping, rather increasing wire delay, counteracting timing gain from the buffer, and possibly even causing design failure due to failure to complete the routing. Disclosure of Invention The invention aims to provide a buffer insertion method for local density perception, which ensures that the final buffer insertion scheme is not only time sequence optimal, but also density friendly, and realizes the full-flow density perception optimization from global planning to local decision. In order to achieve the above object, the present invention provides a method for inserting a buffer for local density perception, comprising: Establishing a density map, namely uniformly dividing a physical design area of a chip into a plurality of rectangular grids, traversing and calculating local layout density values of all the grids to form a digital density map which covers the whole chip and reflects the distribution compactness of units in each area; Generating high-density area barriers, namely identifying high-density areas by adopting a density-based clustering algorithm based on a digital density map, and marking each identified high-density area as a density barrier; Generating an interconnection tree capable of avoiding all density obstacles and a series of buffer insertion candidate points on the path of the interconnection tree aiming at a target network, wherein the positions of partial candidate points are finely adjusted according to the local layout density values of the positions of the partial candidate points; And inserting the buffer, namely searching in a candidate point set formed by buffer insertion candidate points by adopting an improved dynamic programming algorithm, and determining the final buffer insertion position and type by taking the signal time sequence and the local density cost caused by buffer insertion as optimization targets. Further, the local layout density value of each grid is obtained by calculating the ratio of the total occupied area of a