Optimality, scalability, stability study of partitioning, and placement algorithms

This paper studies the optimality, scalability and stability of state-of-the-art partitioning and placement algorithms. We present algorithms to construct two classes of benchmarks, one for partitioning and the other for placement, which have known upper bounds of their optimal solutions, and can match any given net distribution vector. Using these partitioning and placement benchmarks, we studied the optimality of state-of-the-art algorithms by comparing their solutions with the upper bounds of the optimal solutions, and their scalability and stability by varying the sizes and characteristics of the benchmarks. The conclusions from this study are: 1) State-of-the-art, multilevel two way partitioning algorithms scale very well and are able to find solutions very close to the upper bounds of the optimal solutions of our benchmarks. This suggests that existing circuit partitioning techniques are fairly mature. There is not much room for improvement for cutsize minimization for problems of the current sizes. Multiway partitioning algorithms, on the other hand, do not perform that well. Their results can be up to 18 % worse than our estimated upper bounds. 2) The state-of-the-art placement algorithms produce significantly inferior results compared with the estimated optimal solutions. There is still significant room for improvement in circuit placement. 3) Existing placement algorithms are not stable. Their effectiveness varies considerably depending on the characteristics of the benchmarks. New hybrid techniques are probably needed for future generation placement engines that are more scalable and stable