Accurate and Fast Cell Spreading Technology for Force Directed Placement

Sifei Wang1,  Qiang Zhou2,  Xu Qian1,  Yici Cai2,  Wenchao Gao1,  Wenjun Zhou1
1School of Mechanical Electronic & Information Engineering, China University of Mining and Technology, 2Dept. of Computer Science & Technology, Tsinghua University


As a key phase of force-directed placement, cell shifting can smooth the overlap linearly which adds additional forces to shift cells to the suitable place based on their respective bins and its current utilization. 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 shifting technique called FACS to cope with these problems and further optimize wire length. It mainly takes the following measures. Firstly, group cells into three steady sets according to their attribute, external connections and last move. Then amend additional forces of different cells respectively. Secondly, add the barrier during the cell shifting, which will limit the maxi-mum step length and avoid breaking the integrity of original placement. This trick can reduce the average wire length by 0.8%. Thirdly, we put magnitude of HPWL change into additional forces function to amend the deviation which caused by quadratic wire length model. After analyzing the experimental results, a better placement whose average wire length can be reduced by 12% will be obtained.