AKEBONO: A novel quick incremental placer

In DSM era, the every stages of realistic design flow must interact with physical aspects of the design. For example, improvements in power timing may require replacing many modules with variants that have different shape and connectivity. In this paper, we present AKEBONO - a very quick incremental placement algorithm for performing Engineering Change Order (ECO). AKEBONO consists of two stages: first is an iterative net-driven standard-cell placement with hierarchical partitioning, second is a legalization to fit rows and to remove overlaps. As a radix-like sort algorithm is applied to AKEBONO, the total time complexity of it is O(n). Experimental results on ISPD04 IBM standard cell benchmark suite [3] show that run time of AKBONO is 30times faster than the state state-of-the-art academic placers Capo 10.5 legalizer with Greedy and RowIroning [4] on average. Though Capo 10.5 legalizer generally increases HPWL by 9.4% while our placer produces an increase of 13.8%, however we will claim that AKEBONO provides evener and practical placement results.