A FAST CLUSTERING-BASED MIN-CUT PLACEMENT ALGORITHM WITH SIMULATED-ANNEALING PERFORMANCE

Placement is an important constrained optimization problem in the desi gn of very large scale (VLSI) integrated circuits [1-4]. Simulated ann ealing [5] and min-cut placement [6] are two of the most successful ap proaches to the placement problem, Min-cut methods yield less congeste d and more routable placements at the expense of more wire-length, whi le simulated annealing methods tend to optimize more the total wire-le ngth with little emphasis on the minimization of congestion, It is als o well known that min-cut algorithms are substantially faster than sim ulated-annealing-based methods. In this paper, a fast min-cut algorith m (ROW-PLACE) for row-based placement is presented and is empirically shown to achieve simulated-annealing-quality wire-length on a number o f benchmark circuits. In comparison with Timberwolf 6 [7], ROW-PLACE i s at least 12 times faster in its normal mode and is at least 25 times faster in its faster mode. The good results of ROW-PLACE are achieved using a very effective clustering-based partitioning algorithm in com bination with constructive methods that reduce the wire-length of nets involved in terminal propagation.