An Efficient Circuit Partitioning Using Iterative Improvement Technique = 반복개선기법을 이용한 효율적인 회로분할

다국어 초록 (Multilingual Abstract)

In this paper, we present a fast and efficient iterative improvement partitioning technique for VLSI circuits and hybrid bucket structures on its implementation. Due to their time efficiency, IIP algorithms are widely used in VLSI circuit partition. As the performance of these algorithms depends on choices of moving cells, various methods have been proposed. In particular, the cluster-removal algorithm by Dutt significantly improved partition quality. We indicate the weakness of previous algorithms using a uniform method for the choice of cells during improvement. To solve this problem, we propose a new IIP technique that selects the method for choice of cells according to improvement status and presents hybrid bucket structures for easy implementation. The time complexity of the proposed algorithm it the same as the FM method, and the experimental results on ACM/SIGDA benchmark circuits show improvement up to 33-44％, 45-50％ and 10-12％ in cutsize over FM, LA-3 and CLIP respectively.