background
Very Large Scale Integration (VLSI) integrates a large number of circuit units into a single chip. As design complexity increases, VLSI design today is inseparable from the support of Electronic Design Automation (EDA, Electronic Design Automation) tools. As an algorithm-intensive industry, EDA requires rapid design exploration of thousands of scenarios and is a key national technology field. Among them, the automatic layout of circuit units is one of the core issues in EDA research.
The automatic layout of circuit units aims to determine the positions of all circuit units within a rectangular layout area to minimize the total connection line length between units and avoid unit overlap. Since this is an NP-hard problem, it is usually divided into two steps: global layout and detailed layout. The global layout roughly determines the location of cells and allows overlap of cells; the detailed layout eliminates overlap and further optimizes it. This problem focuses on the global layout, treating circuit units as rectangles of different sizes. There are several connection interfaces scattered within the rectangle, and several sets of connection relationships are formed between circuit units through the connection interfaces. The goal of global layout is to minimize the total connection line length while satisfying the cell density constraints. The total connection wire length is equal to the sum of the wire lengths of each group of connected circuit units. Since the wiring has not yet been actually routed during the layout stage, the length of each group of wires can usually be estimated through Half-Perimeter Wirelength (HPWL) or Rectilinear Steiner Minimal Tree (RSMT), which requires that the wires be connected horizontally or vertically. HPWL is half of the perimeter of the rectangle surrounding the connecting interface, and RSMT is the sum of the lengths of line segments constructed by inserting Steiner points. Cell density constraints are calculated by meshing the rectangular layout area. The cell density of each grid is equal to the ratio of the circuit cell area that overlaps the grid and the grid area, limited to a certain threshold. Appendix 1 provides the intermediate state of the global layout, including each group of connected circuit units and their connection interface names, connection interface coordinates and corresponding HPWL and RSMT line lengths. Appendix 2 gives basic information about the layout area size, meshing granularity and density threshold, circuit unit size, coordinates and their connection interfaces.
Please establish a mathematical model to solve the following problems:
- Question 1 Figure 2 shows 3 groups of HPWL and RSMT line length estimation diagrams with different numbers of connection interfaces. RSMT is an ideal wire length representation in the layout stage, but constructing Steiner trees is an NP-hard problem. HPWL is simple and effective, but it is estimated to be too small for multi-wire interface scenarios. Based on the information provided in Appendix 1, please design a wire length evaluation model related to the coordinates of the circuit unit connection interface. This model should satisfy: (1) The difference between the estimated line length of each group and the corresponding RSMT is as small as possible; (2) It can be applied to evaluate the total connection line length in Appendix 1.
- Question 2 Figure 3 shows a schematic diagram of unit density calculation. Please use this to design a grid density evaluation model related to circuit unit coordinates. Apply the line length evaluation model constructed in Problem 1, integrate the density calculation, and establish a mathematical model with the goals of: (1) minimizing the total connection line length; (2) satisfying the unit density constraints. Based on the information provided in Appendix 1 and Appendix 2, apply this model to complete the global layout, output the total connection wire length (HPWL), and visualize the results (location of circuit units).
- Question 3 In addition to connection line length and unit density, wiring density is also one of the important indicators to measure layout quality. Analyze the mesh wiring density calculation model shown in Figure 4 to find out its existing problems. Provide improvement plans for the identified problems. Apply the improved routing density model to calculate the routing density for the updated global layout results in question 2 and visualize the results (grid routing density).
- Question 4 In addition to minimizing the total connection line length and satisfying the cell density constraints, it is hoped that the maximum value of the grid wiring density will be as small as possible. Please correct the mathematical model established in question 2 on the basis of question 3. According to the information provided in Appendix 1 and Appendix 2, apply the revised model to complete the global layout, output the total connection wire length (HPWL), and visualize the results (position of circuit units and grid wiring density).
File format description
Annex 1
(Please downloadAttachment 1.txt)
Group name, (circuit unit name: connection interface name), (corresponding connection interface coordinates), HPWL, RSMT
Group1,(Cell94:ZN,Cell11:A2,Cell7:A1),((22704,21807),(25499,24186),(25633,24095)),5308,5308
Group2,(Cell89:Z,Cell8:I,Cell5:A1),((31596,22332),(29577,24007),(28894,24037)),4407,4407
Group3,(Cell5:ZN,Cell97:A2,Cell96:A1,Cell11:A1,Cell7:A2),((28994,23885),(26971,
24240),(26971,24321),(25809,24078),(25878,24474)),3774,4017
……
Attachment 1.txt Explanation:
- There are five columns, namely: group name, (circuit unit name: connection interface name), (corresponding connection interface coordinates), HPWL, RSMT.
- Group name: Indicates the group of circuit units with connection relationships. The number of group numbers indicates the number of groups of circuit units with connection relationships. Each group can calculate the line length value through the line length evaluation model. The total connection line length is equal to the sum of the line length values of all groups.
- (Circuit unit name: Connection interface name): Indicates which unit’s connection interfaces constitute this group of connections. For example, (Cell94:ZN,Cell11:A2,Cell7:A1) means that the circuit unit name is Cell94 and there is a connection interface named ZN. Similarly, Cell11 has a connection interface named A2 and Cell7 has a connection interface named A1.
The three connection interfaces will form a set of connection relationships, and the connection direction can only be horizontal or vertical. - (Corresponding connection interface coordinates): corresponds to the second column one-to-one, indicating the position coordinates (x, y) of the corresponding circuit unit connection interface. For example, the coordinates corresponding to Cell94:ZN are (22704,21807), and the corresponding coordinates of Cell11:A2 are
The coordinates of Cell7:A1 are (25499,24186), and the corresponding coordinates of Cell7:A1 are (25633,24095). - HPWL: Indicates the connection length of this group of circuit units calculated using the HPWL line length model. Taking Group1 as an example, the width of the external rectangle formed by the connection interface is 25633-22704=2929, and the height is 24186-21807=2379, so HPWL=2929+2379=5308.
- RSMT: Indicates the connection length of this group of circuit units calculated using the RSMT line length model.
/home/lixingquan/OSCC/ieda-website/src/.vuepress/public/res/dataset/MCM_contest-24/appendix2.txt
Annex 2
(Please downloadAttachment 2.txt)
Layout area width, layout area height, horizontal grid number, vertical grid number, density threshold: 38080, 37800, 64, 60, 0.9
Circuit unit name, (X, Y coordinates of the lower left corner), width, height, (connection interface name), (corresponding to the offset coordinates of the connection interface relative to the lower left corner of the unit)
Cell1,(28431,23878), 1120, 1800,(A2,B,A1),((630, 1051),(910,870),(385,672))
Cell2,(29042,24255),560, 1800,(I),((205,860))
Cell3,(28483,24118),840, 1800,(A1,A2),((505, 1002),(195,880))
……
Attachment 2.txt Explanation:
divided into two parts
- Layout area information:
Indicates that the horizontal value range of the layout area is [0,38080], and the vertical value range is [0,37800]; the entire layout area is divided into 64*60 grids, the width of each grid is 38080/64=595, and the height is 37800/60=630; the unit density of each grid does not exceed 0.9. - Circuit unit information:
Take Cell1,(28431,23878), 1120, 1800,(A2,B,A1),((630, 1051),(910,870),(385,672)) as an example to explain the meaning. Circuit unit Cell1, the coordinates of the lower left corner of Cell1 are (28431, 23878), the width and height are 1120 and 1800 respectively. There are three connection interfaces named A2, B, and A1. The offsets between the coordinates of these three connection interfaces and the coordinates of the lower left corner of Cell1 are (630, 1051), (910,870), (385,672). Based on this, these three connection interfaces can be calculated respectively. The absolute coordinates of a connection interface, for example, the absolute coordinates of Cell1:A2 are (28431+630=29061,23878+1051=24929). Note that the offset of all wiring interfaces in the circuit unit is a fixed value and will not change with the position of the circuit unit; therefore, if the position of the circuit unit is known, its absolute coordinates can be calculated based on the offset of the wiring interface, and then the line length can be calculated.