论文部分内容阅读
A non-slicing approach, Corner Block List (CBL), has been presented recently.Since CBL only can represent floorplans without empty rooms, the algorithm based on CBLcannot get the optimum placement. In this paper, an extended corner block list, ECBLλ, isproposed. It can represent non-slicing floorplan including empty rooms. Based on the optimumsolution theorem of BSG (bounded-sliceline grid), it is proved that the solution space of ECBLn,where n is the number of blocks, contains the optimum block placement with the minimum area.A placement algorithm based on ECBLλ, whose solution space can be controlled by setting λ,the extending ratio, is completed. When λ is set as n, the algorithm based on ECBLn is theoptimum placement search algorithm. Experiments show that λ has a reasonable constant rangefor building block layout problem, so the algorithm can translate an ECBLλ representation toits corresponding placement in O(n) time. Experimental results on MCNC benchmarks showpromising performance with 7% improvement in wire length and 2% decrease in dead space overalgorithms based on CBL. Meanwhile, compared with other algorithms, the proposed algorithmcan get better results with less runtime.