A1 — Placement legalization

# 1 Problem background

The layout process can be divided into three stages: Global Placement, Legalization, and Detailed Placement. Place the cells in the appropriate locations in the global layout, ignoring overlapping cells. Legalization puts units on rows and eliminates overlap between units.

The main factors affecting layout quality include:

● Line length: In the Placement stage, the area can be appropriately optimized based on utilization. ● Power consumption: In designs that pay attention to power consumption, standard units can be divided into three types according to voltage (HVT, LVT, SVT). ● Performance: The standard unit position affects the CTS process (ie, the delay of the clock signal), and also affects the line length (ie, the delay of the data signal). ● Routability: Local ground congestion should be evaluated to ensure successful routing. ● Manufacturability: As processes continue to evolve, more and more constraints need to be considered in the DP stage.

# 2 Problem description

After given the layout specifications, the designer needs to place the modules and standard units within the Die. It meets the requirements of non-overlapping units, row alignment and site alignment, optimizing line length, timing, power consumption, and routability.

1、Implement requirements: We legalize the results of the global layout, referring to the existing legalization implementation method of iEDA - the interface design and logical interaction in the Abacus[1] algorithm (iEDA/src/operation/iPL/source/module/legalizer/method/abacus). We need to implement the Tetris[2] algorithm or use other legalization methods for legalization.

Currently, the iEDA project has been packaged in factory mode. Students need to create tetrisContents under iEDA/src/operation/iPL/source/module/legalizer/methodContents to implement the Tetris algorithm or other algorithms.

● Algorithm constraints: The unit is within the chip area; there is no overlap between units. ● Algorithm goal: minimal change in global layout results. ● Main challenges: need to ensure global vision; high algorithm complexity requirements.

# 3 input and output

# Algorithm input

Def file stores the results of the completed global layout, including the position coordinates of all units in the circuit design that have been roughly placed.

The specific data structure design is as follows (for details, please see: iEDA/src/operation/iPL/source/module/legalizer/database):

● LGCell: Legalization unit, which is the smallest unit in the layout process. It usually represents a square or rectangular area.

● LGInstance: A chip is usually composed of multiple functional modules or circuit units, such as processor cores, storage units, input and output interfaces, etc. Each functional module can be represented as an instance.

● LGInterval: Interval. Due to the existence of immovable units such as macro units, the layout area may be divided into multiple discontinuous intervals.

● LGLayout: Layout data structure, the process of placing various components, connections and other structures in a circuit design on the chip in accurate locations.

● LGRegion: Divide the chip into different areas and specify layout constraints for each area to better manage and optimize the placement and routing of related instances during the layout process

● LGSite: The physical structure of the chip is divided into a grid, which consists of a series of horizontal and vertical cells. Each cell is called a site and represents a specific location where a component, wire, or other functional element can be placed.

● LGRow: a horizontal arrangement method in chip layout

● AbacusCluster: Legalized clustering. When there is no overlap, the optimal position of each unit is the current position. When there is overlap, the optimal position must be assigned to each overlapping unit. We call the collection of these overlapping units a Cluster, and each "Cluster" can be placed and routed independently to meet the constraints and optimization goals among the instances in the collection.

● LGDatabase: Legalization database definition

# algorithm output

Def file, verilog file, legalized results, including coordinates of legal units, etc.

# 4 Evaluation indicators

The sum of the vertical movement distances of all units and their future horizontal movement distances is the smallest. The key to algorithm design is how to reduce the future horizontal movement distance. The assessment requirements are as follows:

● The program will run normally with reasonable running time and memory, and the Def file will be output. All standard unit layouts are legal. ● Upper limit of running time: If the program running time exceeds 10 minutes, the program is considered to be in an infinite loop and the implementation fails. ● Upper limit of running memory: If the running memory exceeds 10G, the implementation will fail. ● For the source code, the following aspects will be inspected: ○ Whether the code style is beautiful, whether the organizational structure is clear, and whether the readability is good ○ Is there a good modular design? ○ Are the naming style and programming conventions good? ● The output experimental report must be clearly organized, appropriately detailed, and clear and easy to read. The content should include the following aspects: ○ Algorithm principle, test results ○ Time/space complexity analysis ○ Other highlights in code design (if any), such as architecture design, module reuse, some best practices, etc.

# 5 Reference implementation

# Algorithm 1: Abacus algorithm (iEDA has implemented this algorithm)

Currently, the layout legalization algorithm implemented in src/operation/iPL/source/module/legalizer/method/abacusContents of the iEDA project is the Abacus algorithm.

1. Main steps of Abacus algorithmAs follows (Dynamic programming algorithm will move legalized units):

●**Units scattered to rows**: Sort each unit according to its abscissa. Each time a cell is processed, the cell is first moved to the nearest row; ●**Intra-row legalization**: Calculate the cost of the unit in this row, as well as the cost of moving above and below the row, where the constraint is to place all units in each row so that their total movement is minimal and does not overlap. The cost calculation is to calculate all unit clusters in a row and the optimal position of the cluster, and rely on the optimal position of the cluster to obtain the optimal coordinates of each unit in the cluster and the cost of the cluster; the cost of all clusters in a row is the total cost of the row;

●**Unit placement**: Place the unit in the row with the lowest cost, update the cluster at the same time, and update the coordinates of all units in the row according to the coordinates of the optimal cluster after the unit is moved.

2. Analysis of advantages and disadvantages：

● Advantages: The quality is greatly improved compared to Tetris. ● Disadvantages: The quality is not stable enough and depends on the order of traversal. When there is a large width difference, the results will be significantly worse and the speed will be slower.

3. Method to legalize Abacus layout by running iEDA：

(1) Taking gcd design as an example, the sky130 process is used to run the point tools of layout planning (iFP), fan-out optimization (iNO_fix_fanout) and layout (iPL)

● sky130 process library location: iEDA/scripts/foundry/sky130 ● Main entrance to run script: iEDA/scripts/design/sky130_gcd/run_iEDA.py ● Netlist file designed by gcd: iEDA/scripts/design/sky130_gcd/result/verilog/gcd.v ● sdc constraint file: iEDA/scripts/foundry/sky130/sdc/gcd.sdc ● Run command: ○ Enter the iEDA project: cd [iEDA project parent Contents]/iEDA ○ Update the code to the latest code: git pull ○ Compile and build the project: bash[build.sh](https://build.sh) ○ Copy the executable file to the sample Contents: cp bin/iEDA scripts/design/sky130_gcd/ ○ Enter the sample Contents: cd scripts/design/sky130_gcd ○ Modify the file and comment out lines 23 to the end of the file: vim[run_iEDA.py](https://run_iEDA.py) ○ Run script: python[run_iEDA.py](https://run_iEDA.py) ○ Analysis of running results: Before detailed layout, the result of layout legalization will be checked. If legalization fails, "Design Instances before detail placement are not legal" will be printed, and detailed layout cannot be executed.

# Algorithm 2: Tetris algorithm (iEDA does not implement this algorithm)

The idea of ​​the Tetris algorithm comes from the classic Tetris game. Its goal is to find a suitable position for each unit and put the logical unit to be placed into the physical space of the chip.

1. Main steps of Tetris algorithmAs follows (greedy algorithm, legalized units will not be moved):

●**Candidate space selection**: First, arrange all units in the order of the abscissa, and select the leftmost blank area in each row in order as a candidate space. ●**Unit Placement**: For each unit, pick the closest one among all candidate spaces and place the unit. After the logical unit is placed, the occupied grid information is updated and the corresponding grid is marked as occupied. Place the remaining units one by one until all units are placed.

2. Analysis of advantages and disadvantages：

● Advantages: It is a heuristic algorithm and is very fast. ● Disadvantages: The quality is unstable, good results are obtained locally, there is no guarantee that the global optimal solution can be found, but the overall results are poor.

3. Operation results：

Let’s take the execution of the design gcd in the skywater 130nm process as an example:

Table 1 Examples of comparison results of key parameter indicators of methods

4. Algorithm variants：

● Row density expansion: rows greater than a certain density are not selected; ● Expansion of row selection: closer to the starting row; ● Partial expansion: Divide the entire layout area into k parts and legalize them locally

# Algorithm 3: Other algorithms

Please research other references or design your own.

References:

[1] P. Spindler, U. Schlichtmann, and F. M. Johannes. Abacus: fast legalization of standard cell Circuits with minimal movement. In Proceedings of ACM International Symposium on Physical Design, pp. 47–53, 2008. 【Abacus】

[2] Method and system for high speed detailed placement of cells within an integrated circuit design Inventor: Dwight Hill Application number: US09273809, Publication date: 2002.04.09. 【Tetris】

[3] E. M. Gertz and S. J. Wright. Object-oriented software for quadratic programming. ACM Transactions on Mathematical Software, 29(1), pp. 58–81, 2003.

[4] G.Wu and C.Chu. Detailed placement algorithm for VLSI design with double-row height standard cells. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 35(9):1569–1573, September 2016.

[5] W.-K. Chow, C.-W. Pui, and E.F.Y. Young. Legalization algorithm for multiplerow height standard cell design. In Proceedings of ACM/IEEE Design Automation Conference, 2016.

[6] C.-H. Wang, Y.-Y. Wu, J. Chen, Y.-W. Chang, S.-Y. Kuo, W. Zhu, and G. Fan. An e_ective legalization algorithm for mixed-cell-height standard cells. In Proceedings of IEEE/ACM Asia and South Paci_c Design Automation Conference, 2017.

[7] J. Chen, Z. Zhu, W. Zhu, and Y.-W. Chang. Toward optimal legalization for mixed-cell-height circuit designs. In Proceedings of ACM/IEEE Design Automation Conference, June 2017.

[8] Y. Lin, B. Yu, X. Xu, J.-R. Gao, N. Viswanathan, W.-H. Liu, Z. Li, C. J. Alpert, and D. Z. Pan. MrDP: multiple-row detailed placement of heterogeneous-sized cells for advanced nodes. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 7:1–7:8, 2016.

[9] J. Chen, Z. Zhu, W. Zhu, and Y.-W. Chang. Toward optimal legalization for mixed-cell-height circuit designs. In Proceedings of ACM/IEEE Design Automation Conference, 2017.

[10] H.Liopen in new window,W.-K.Chow, G.Chen, E. F. Y. Young, and B. Yu. Routability-driven and fence-aware legalization for mixed-cell-height circuits. In Proceedings of ACM/IEEE Design Automation Conference, 2018.

# 6 Evaluation Ranking