An Optimum Placement Search Algorithm Based on Extended Corner Block List

A non-slicing approach, Corner Block List (CBL), has been presented recently.Since CBL only can represent floorplans without empty rooms, thealgorithm based on CBL cannot get the optimum placement. In this paper,an extended corner block list, ECBLla, is proposed. It canrepresent non-slicing floorplan including empty rooms. Based on theoptimum solution theorem of BSG (bounded-sliceline grid), it is provedthat the solution space of ECBLn, where n is the number ofblocks, contains the optimum block placement with the minimum area. Aplacement algorithm based on ECBLla, whose solution space can becontrolled by setting la, the extending ratio, is completed. Whenla is set as n, the algorithm based on ECBLn is theoptimum placement search algorithm. Experiments show that lahas a reasonable constant range for building block layout problem, sothe algorithm can translate an ECBLla representation to itscorresponding placement in O(n) time. Experimental results on MCNCbenchmarks show promising performance with 7% improvement in wirelength and 2% decrease in dead space over algorithms based on CBL.Meanwhile, compared with other algorithms, the proposed algorithm canget better results with less runtime.