HALO: an efficient global placement strategy for standard cells

An efficient global cell (module) placement strategy called hierarchical alternating linear ordering (HALO) which generates a global 2D placement of circuit modules by hierarchical application of linear ordering in alternating direction is described. It is explained why HALO should perform better than other typical, somewhat successful, analytical approaches such as min-cut, force-directed relaxation (FDR), or their variations. HALO is implemented in a program for standard cell placement. The remaining procedures in the standard cell placement, i.e. row assignment, feedthrough cell assignment, and intrarow assignment, are explained. Experimental results are given and discussed. The results on two benchmark circuits consisting of 752 and 2907 cells show a decrease of the half-perimeter routing lengths by 7% and 24%, respectively, compared to other available results. Total CPU time including the following detailed placement is less than half of that reported in previously published work