Accurate and fast cell spreading for force directed placement

As a key phase of force-directed placement, cell spreading can smooth the overlap linearly by adding additional forces to shift cells to the suitable place based on the utilization of bins. However, the magnitude and direction of these additional forces is hard to be determined. Unreasonable additional forces will bring great damage to the wire length and run time. In this paper, we present a new fast and accurate cell spreading technique called FACS to cope with these problems and further optimize wire length. It mainly takes the following measures: Firstly, cells are grouped into three steady sets according to their attributes, external connections and last move, and the different strategies of amending force are adopted base on the sets respectively. Secondly, the barrier is added during the cell spreading, which will limit the maximum step length and avoid breaking the integrity of original placement. This makes the average wire length reduced by 0.84%. Thirdly, the magnitude of half perimeter wire length (HPWL) change has also been put into additional forces function to amend the deviation which caused by quadratic wire length model. The experimental results show that the average wire length can be reduced by 12%.