CN-122021546-A - Hybrid bond terminal global dynamic matching method and computer program product

CN122021546ACN 122021546 ACN122021546 ACN 122021546ACN-122021546-A

Abstract

The global dynamic matching method of the hybrid bonding terminal and the computer program product comprise the steps of obtaining pin connection configuration information, obtaining position information of a plurality of grid points on a hybrid bonding interface, determining optimization nodes, constructing a priority grid point array corresponding to each optimization node based on the optimization nodes, for each optimization node, selecting one grid point from the priority grid point array to start to visit until the visited grid point only belongs to one priority grid point array, stopping forming a grid point set by the initial grid point, the end grid point and all grid points visited in the visit process, updating the priority grid point array in the process of determining the end grid point, and matching unique grid points for each optimization node in a mode of iteratively searching the shortest augmentation path. Since the solution space is dynamically expanded from local in the process of searching the shortest amplification path, invalid traversal is reduced, the peak memory required by the algorithm in operation is reduced, and the overall matching efficiency is improved on the premise of keeping global optimum.

Inventors

TANG XING
Zhang Xueken
ZHAO QI
WANG LEI

Assignees

深圳鸿芯微纳技术有限公司
上海鸿芯科纳科技有限公司

Dates

Publication Date: 20260512
Application Date: 20260409

Claims (10)

1. The global dynamic matching method of the hybrid bonding terminal is applied to a 3D stacked integrated circuit, and is characterized by comprising the following steps of: Acquiring pin connection configuration information, wherein the pin connection configuration information is used for determining a first pin and a second pin in each pin connection group when a first chip and a second chip are connected, the first pin is a pin on the first chip, the second pin is a pin on the second chip, and each pin connection group comprises at least one first pin and at least one second pin; Acquiring position information of a plurality of grid points on a hybrid bonding interface between the first chip and the second chip; Determining an optimized node for a topology convergence point when the first pin and the second pin in each pin connection group are connected based on the first pin and the second pin in each pin connection group; Based on the position information of the grid points and the optimized nodes corresponding to each pin connection group, constructing a priority grid point array corresponding to each optimized node, wherein the number of grid points in each priority grid point array is smaller than that of the grid points; for each optimizing node, selecting one grid point from the prior grid point array according to a first predefined rule to start access until the accessed grid point is only assigned to one prior grid point array, and integrating the initial grid point, the end grid point and all grid points accessed in the access process into a grid point set, wherein in the process of determining the end grid point, updating the prior grid point array according to a second predefined rule; Based on each optimizing node and the corresponding lattice point set, a unique lattice point is matched for each optimizing node in a mode of iteratively searching the shortest amplifying path, wherein the lattice point matched by each optimizing node is used for connecting a first pin and a second pin in a corresponding pin connection group.
2. The hybrid bond terminal global dynamic matching method of claim 1, wherein the plurality of grid points are arranged in a plurality of rows and a plurality of columns, wherein grid points of a same row are collinear and each row is parallel to each other, grid points of a same column are collinear and each column is parallel to each other.
3. The global dynamic matching method of hybrid bond terminals of claim 2, wherein each of said optimized node's corresponding priority lattice point arrays is an array of lattice points nearest to said optimized node and all lattice points adjacent to said nearest lattice point.
4. The hybrid bond terminal global dynamic matching method of claim 3, wherein the first predefined rule is to access grid points from a sequence of small to large half perimeter values of grid points in the prioritized grid point array.
5. The hybrid bond terminal global dynamic matching method of claim 4, wherein the second predefined rule is to divide, when accessing a current grid point, grid points that are adjacent to the current grid point and that are not divided in a current priority grid point array to the priority grid point array.
6. The method of claim 5, wherein the matching a unique lattice point for each of the optimized nodes by iteratively searching for a shortest augmented path based on each of the optimized nodes and the corresponding set of lattice points comprises: For each lattice point set, constructing a cost array with the same length as the lattice point set, wherein the initial value of each element in the cost array is set to be a preset maximum value larger than the total cost of any legal augmentation path, each element in the cost array uniquely corresponds to one lattice point in the lattice point set, and the element is used for representing the path cost value when the corresponding optimization node is used as a starting point and the corresponding lattice point is used as an end point as an augmentation path; the path cost value in each cost array is updated successively in a mode of searching the shortest amplifying path through the iteration; After updating the path cost values in the cost arrays, selecting an effective augmented path set with the minimum total cost of the whole path as a global optimal lattice point matching scheme based on the constraint condition that one optimization node can only be matched with one lattice point and one lattice point can only be matched with one optimization node, so that each optimization node is matched with a unique lattice point.
7. The hybrid bond terminal global dynamic matching method of claim 6, wherein said iteratively searching for a shortest augmented path successively updates path cost values in each cost array comprises: starting from any optimized node, and starting to access from one lattice point in a lattice point set corresponding to the any optimized node according to the first predefined rule; If the accessed current grid point is not matched, judging that a path from the any optimized node to the accessed current grid point serving as an end point is an augmented path, and updating elements in a cost array corresponding to the accessed current grid point; If the accessed current grid point is already matched, marking the accessed current grid point, and as an optimization node corresponding to the accessed current grid point, re-matching the grid point with the path cost value smaller than the path cost value when the accessed current grid point is taken as the end point from unlabeled grid points in a grid point set corresponding to the current corresponding optimization node; if the matching of the path cost value is smaller than the path cost value when the accessed current lattice point is taken as the end point, taking the re-matched lattice point as the end point of the corresponding optimized node, and updating the corresponding element in the corresponding cost array; and if the path cost value is not matched with the lattice point with the path cost value smaller than the path cost value when the accessed current lattice point is taken as the end point, taking the accessed current lattice point as the end point of the corresponding optimization node, and continuing to match the lattice point for any optimization node.
8. The global dynamic matching method of a hybrid bond terminal according to claim 7, wherein the path cost value is calculated by adding a half perimeter value corresponding to a current lattice point to a minimum cost of a current path cost and subtracting a current signal connection dual variable and a current lattice point dual variable.
9. The hybrid bond terminal global dynamic matching method of any of claims 1-8, wherein said determining an optimized node for a topology convergence point when the first pin and the second pin in each of the pin connection groups are connected based on the first pin and the second pin in each of the pin connection groups comprises: when the number of the first pins and the number of the second pins in the pin connection group are respectively one, the optimization node is a midpoint of a connection point of the first pins and the second pins; When the number of the first pins and/or the number of the second pins in the pin connection group is greater than one, the optimization node is a Steiner point with the smallest variance of Manhattan distance between the first pins and the second pins in the pin connection group on a right-angle Steiner tree constructed based on the first pins and the second pins.
10. A computer program product comprising software code portions for performing the steps of the hybrid bond terminal global dynamic matching method according to any of claims 1 to 9 when said product is run on said computer.

Description

Hybrid bond terminal global dynamic matching method and computer program product Technical Field The invention relates to the field of integrated circuit computer aided design counting, in particular to a global dynamic matching method of hybrid bonding terminals and a computer program product. Background A 3D stacked integrated circuit (IC, INTEGRATED CIRCUIT) is a very potential solution beyond moore's law, where the die are linked by hybrid bond terminals, the location of which can significantly impact layout routing performance. In addition, due to the number and density limitations of hybrid bond terminals, there is resource competition between all cross-chip signal connections, and in advanced process nodes where the metal pitch is significantly smaller than the bond pitch, matching of the cross-chip signal connections and hybrid bond terminals is critical to achieving optimal design performance. In the related art, when hybrid bonding terminal matching is performed through cross-chip signal connection, a traditional bipartite graph matching algorithm is adopted to perform hybrid bonding terminal matching, and when matching is performed, a complete bipartite graph structure comprising all nodes and candidate edges is required to be constructed in advance through the traditional bipartite graph matching algorithm. When complex scenes (such as large-scale nodes, high-density connection constraints and the like) are processed, the whole solution space is huge in scale, and the overall access causes the peak memory occupation during algorithm operation to be too high, so that the matching efficiency is low. Disclosure of Invention The invention mainly solves the technical problems that a complete bipartite graph structure needs to be constructed in advance when the traditional bipartite graph matching algorithm is matched, the complete solution space is huge in scale when complex scenes are processed, and the overall access causes the peak memory occupation of the algorithm to be too high during the operation, so that the matching efficiency is low. According to a first aspect, in one embodiment of the present application, there is provided a hybrid bonding terminal global dynamic matching method applied to a 3D stacked integrated circuit, the hybrid bonding terminal global dynamic matching method including: Acquiring pin connection configuration information, wherein the pin connection configuration information is used for determining a first pin and a second pin in each pin connection group when a first chip and a second chip are connected, the first pin is a pin on the first chip, the second pin is a pin on the second chip, and each pin connection group comprises at least one first pin and at least one second pin; Acquiring position information of a plurality of grid points on a hybrid bonding interface between the first chip and the second chip; Determining an optimized node for a topology convergence point when the first pin and the second pin in each pin connection group are connected based on the first pin and the second pin in each pin connection group; Based on the position information of the grid points and the optimized nodes corresponding to each pin connection group, constructing a priority grid point array corresponding to each optimized node, wherein the number of grid points in each priority grid point array is smaller than that of the grid points; for each optimizing node, selecting one grid point from the prior grid point array according to a first predefined rule to start access until the accessed grid point is only assigned to one prior grid point array, and integrating the initial grid point, the end grid point and all grid points accessed in the access process into a grid point set, wherein in the process of determining the end grid point, updating the prior grid point array according to a second predefined rule; Based on each optimizing node and the corresponding lattice point set, a unique lattice point is matched for each optimizing node in a mode of iteratively searching the shortest amplifying path, wherein the lattice point matched by each optimizing node is used for connecting a first pin and a second pin in a corresponding pin connection group. In one embodiment, the plurality of grid points are arranged in a plurality of rows and a plurality of columns, wherein the grid points of a same row are collinear and the rows are parallel to each other, and the grid points of a same column are collinear and the columns are parallel to each other. In one embodiment, the priority lattice point array corresponding to each optimizing node is an array composed of the lattice point nearest to the optimizing node and all lattice points adjacent to the nearest lattice point. In one embodiment, the first predefined rule is to access the grid points from a sequence of smaller half perimeter values of the grid points in the priority grid point array. In an embodiment, the second predefined rule