Standard Cell Placement Optimization Using Quadratic Placement Algorithm ()
1. Introduction
Placement is the process of determining positions of standard cells and macros which has been synthesized. This is one of the most important and critical steps in IC design. Following few reasons are showing why optimal placement of standard cells is dramatically important for having good IC:
• Performance of a circuit―As technologies are becoming smaller, interconnect delays are increasing. This is leading to big power consumption. Hence, good placement of standard cells has huge impact on design performance
• Power disproportion―Badly placed cells can cause non-equal power consumption leading to congested heat point formulation, which can be source of many problems even damaging full chip functionality.
• Routability―Placement can cause routibility issues later on routing stage and be reason of long wires.
To achieve optimal placement of standard cells with standard placement algorithm, in every iterate cells, which need to be moved, will be moved to the most optimal place in that iteration. Ideally, this process must be repeated until all standard cells are placed in their proper places.
There exist multiple ways of reducing placement runtime for standard cell placement [1] [2] [3] . Most of the existing algorithms have complex implementation [4] .
As placement process is dealing with millions of macros and standard cells, it is very complex computational process. If considering that each cell can have multiple connections with other cells, computation complexity is increasing more and more.
The above-mentioned process will bring to high runtime with big designs (standard cell count > 5000). The most time-consuming part is the starting period where all connectivity for each standard cell mostly placed in (0, 0) coordinate. Above described algorithm will overcome the connectivity-based time consumption by logical excluding the cells connectivity which forces to cell stay near (0, 0) coordinates. The end part of the placement placer can make wary small movement which will not make huge impact in the standard cell placement.
To overcome upper mentioned difficulty, placement process is being divided into a few manageable steps―global placement, legalization, detailed placement.
This paper described algorithm can be used in global placement step. This is a very important step of placement as it has most impact on performance of IC.
The other two steps are for making placement of cells legal on placement grid and meeting placement constrains [5] .
In the global placement, small movement of standard cell will be ignored for speeding up placement process.
2. Global Placement
Global placement is the step of finding optimal placement of circuit modules, based on different factors like wire length, area, parasitic etc.
It is a challenge to design efficient placement algorithms for producing high quality placement solutions of circuits with millions of cells [6] .
Standard cell placement overall procedure using Hierarchical Alternating Linear Ordering can be described with Figure 1.
Algorithm is taking cell connectivity as its input and calculates mass center of cells. After some iterations, in-row placement is being performed for cells.
Standard cell connectivity netlist to in-row placement ordering can be simply described in Figures 2(a)-(d).
In Figure 2(a), initial netlist is given. This is the gate level netlist for placer. After gate-level netlist is read, placer places gates linary―keeping minimum wire length. After that is done, two virtual (left and right) groups are created, in
![]()
Figure 1. Hierarchical alternating linear ordering procedure flow.
![]()
Figure 2. Standard cell connectivity netlist to in-row placement ordering.
which cells have approximately same sum of area (Figure 2(c)). After left and right groups are created, these are also being divided into small sub-groups (Figure 2(c)). This vary sum of area is also being kept equal for sub groups.
These iterations are going till all cells are assigned and constraint-based assigned to rows.
3. Quadratic Placer Algorithm Implementation
The input for the placer is netlist with initial fixed cells and their positions and the connections between placeable cells. Fixed and placeable cells constitute the vertices of a graph.
One more input for the algorithm is the move threshold, which described optimization level and is very important for algorithm runtime. This value is the specification of movement―the maximum value that displacement can have. In some cases, when threshold value is too small, placer can have multiple minor movements leading to quasi-infinite loops, which will bring to huge runtime.
Basic syntax of input netlist is shown in Figure 3.
After netlist is read, netlist handler is translating syntax to the graph-based connection.
At the beginning fixed cells are placed at their location and all movable cells are located in the start point of calculation system. Basic view of placement after netlist is read, can be shown in Figure 4.
Figure 4 is missing connections between all cells just to be clean. They will be shown later.
After Netlist is read and initial placement is done for fixed cells, algorithm is looping through all cells moving one cell at a time. First iterations are creating very rough estimation of cell placement, because in placement there are cells on (0, 0) position, and they are excluded from calculations.
To ensure near-optimal placement at the beginning stage of placement, algorithm is not considering cells which are placed at (0, 0) position. This approach is also minimizing runtime with a smaller number of needed calculations.
For algorithm run speed increasing and adding level of optimization algorithm is assigning initial values for cell group mass center. Cell groups are selected based on connections’ count. After initial placement is done, mass center coordinates are updated.
For each cell group algorithm is first placing cells in row and starting optimization by dividing placement area in that way, that count of connections is remaining similar for each group. This way algorithm is keeping area of cell and routes similar for each group (approximated that all cells have same size).
Visualization of first few steps is shown in Figures 5(a)-(d).
• ast iteration is when all placeable cells are placed (Figure 6 Step N). Main point is that every time when any cell is being placed, it is becoming “quasi-fixed” for next iteration’s cell, so next cell which relates to that cell will have one more fixed connection and more accurate mass center. In other words, Placer considers only sells which have connection with fixed or quasi-fixed cells and ignores the connectivity of the standard cell which is leaded from (0, 0) coordinate.
• ater, next iterations are assuming all other cells are placed, and moving one cell to meet minimum wire length.
![]()
Figure 4. Placement after first iteration.
![]()
Figure 5. Visualization of first few steps of placement.
Placement is done, when for one iteration all cells are not being moved more than the threshold value. The threshold value implementation brings reduction of run time in the last finalizing part of the global placement. In this time, we have well placed and optimized placement, with optimal wire length estimation.
Algorithm block diagram is shown in Figure 6.
4. Conclusions
In this paper, standard cell global placement algorithm is demonstrated. The approach is simple in implementation. Imbanded standard cell connectivity quasi-decreasing method brings algorithm implementation runtime degree to the level of existing algorithms ( [1] [2] and [3] ). For example, for logic which contains 5K standard cells, algorithm implementation takes 83 second․