FDPlacement

Force-directed placement

Force-directed placement is used to place center of standard cell clusters onto the center of the grid cells.

Information provided by Google

The Methods section of the Nature paper provides the following information.

• “(1) We group millions of standard cells into a few thousand clusters using hMETIS, a partitioning technique based on the minimum cut objective. Once all macros are placed, we use an FD method to place the standard cell clusters. Doing so enables us to generate an approximate but fast standard cell placement that facilitates policy network optimization.”

• “We discretize the grid to a few thousand grid cells and place the centre of macros and standard cell clusters onto the centre of the grid cells.”

• “Placement of standard cells. To place standard cell clusters, we use an approach similar to classic FD methods. We represent the netlist as a system of springs that apply force to each node, according to the weight×distance formula, causing tightly connected nodes to be attracted to one another. We also introduce a repulsive force between overlapping nodes to reduce placement density. After applying all forces, we move nodes in the direction of their force vector. To reduce oscillations, we set a maximum distance for each move.”

Our implementation

Our force-directed placer takes a clustered netlist as input and generates the locations for standard-cell clusters. During the force-directed placement, all the hard macros and IO ports are fixed. Only the standard-cell clusters can be moved but the standard-cell clusters are not necessarily placed onto the centers of gridcells. At the beginning, all the standard-cell clusters will be placed at the center of the canvas. [code]

In the force-directed placement, there are two types of forces between nodes: attractive force and repulsive force.

• The attractive force is ONLY applied to the nodes connected by nets. For the two-pin net connecting pin $P1$ of macro $M1$ and $P2$ of macro $M2$, the attractive force applied to $M1$ and $M2$ is calculated as $f_x = k_a * abs(P1.x - P2.x)$ and $f_y = k_a * abs(P1.y - P2.y)$, where $k_a$ is the attractive factor. If one of pins is an IO port, $k_a$ is the attractive factor times io factor. The attractive force is along the straight line joining $P1$ and $P2$. All the multi-pin nets are decomposied into two-pin nets using the start model. [code]
• The repulsive force is ONLY applied to the nodes overlapped with each other. If two macros are not overlapped, there is no repulsive force between them. For the two macros $M1$ and $M2$ overlapped with each other, the repulsive force applied to $M1$ and $M2$ is calculated as $f_x = F * abs(M1.x - M2.x) / distance(M1, M2)$ and $f_y = F * abs(M1.y - M2.y) / distance(M1, M2)$, where $F$ is the maximum move distance specified by the users. If $distance(M1, M2) = 0.0$, then $f_x = F$ and $f_y = F$. The repulsive force is along the straight line joining $M1$ and $M2$. For the cases where multiple macros are overlapped together, we calculate the repulsive forces between each pair of macros in sequence. [code]

After calculating all the attractive forces and repulsive forces, all the forces are normalized as following:

• f_x = f_x / f_x_max * max_move_distance
• f_y = f_y / f_y_max * max_move_distance

Here f_x_max (f_y_max) is the absolute value of f_x (f_y) which has the maximum absolute value. max_move_distance is the maximum move distance specified by users. [code]

After normalization, the standard-cell clusters are moved based on the forces exerted on them. The move which will push the standard-cell clusters outside of canvas will be canceled.

How to run our implementation

We provide implementations in both python and c++.

To run the FD placer implemented in python, you need to install all the dependencies of Circuit Training. You can set the testcase and related parameters in FD.py. Then you can our FD placer as following:

python FD.py

To run the FD placer implemented in c++, you need to compile c++ codes as following:

mkdir build
cd build
cmake ..

You can set the related parameters in main.cpp before you compile the codes. Then you can run FD placer as following:

./build/fd_placer ariane133/ariane.pb.txt ariane133/ariane.plc

Experimental results

We have tested our codes on the Ariane133 (NanGate45). The experimental results are presented below. The results from our python implementation and our c++ implementation are a little different. This is due to the precision loss while converting from python codes to C++ codes.

Figure 1. results for Ariane133 (NanGate45).