An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair(Place and Routing)(<Special Section>VLSI Design and CAD Algorithms)

概要

論文の詳細を見る
In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n^2) time (conventional method needs O(n^3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n^2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n^2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.
社団法人電子情報通信学会の論文
2003-12-01