본 논문에서는 대규모 집적회로 설계에 있어 효율적이고 안정된 분할을 위한 새로운 다단 분할 방법을 제안한다. 대규모 회로의 설계에 반복적인 분할 개선 방법을 적용함에 있어 성능의 한계를 극복하기 위해 제안된 다단 분할 방법은 분할 계층구조의 형성 방식에 의해 그 성능이 결정되었다. 기존에 제안된 대부분의 다단 분할 방법은 계층구조를 형성하는 과정에서 실험에 의한 인위적인 제한 조건을 설정하여 분할 결과의 안정성이 저하되는 문제가 있었다. 이러한 안정성의 결여는 반복 수행시의 분할 결과 편차가 매우 커지는 상황을 초래한다. 본 논문에서는 이러한 인위적인 제한 조건의 설정을 최소화하고 계층구조 형성 과정에서 현재 회로 연결 상태를 고려하여 자율적인 제한조건에 의해 클러스터링을 수행하는 새로운 계층구조 형성 방식을 제안한다. 제안된 방법에 의해 형성된 분할 계층구조는 HYIP11의 하이브리드 버켓을 이용한 분할 개선방법을 반복적으로 적용하여 분할 결과를 얻는다. 본 다단 분할 방법은 ACM/SIGDA에서 제공한 벤치마크회로를 대상으로 실험한 결과 기존 분할 방식[3] [4] [5] [8] [9]에 비해 약 10-40% 가량의 최소 cutsize 감소 효과가 있었고 기존의 다단 분할 방법 중에 가장 효율적인 방법으로 평가되는 ML[10]에 비해 제안된 방법이 최소 cutsize에 있어서는 약 5%, 평균 outsize에 있어서는 평균 20%이상의 성능 향상을 가져 왔다. 더욱이 제안된 방법을 10회 수행한 결과가 ML 방법을 100회 수행한 결과 보다 앞서는 성능을 보였다.
This paper presents a new efficient and stable multilevel partitioning algorithm for VLSI circuit design. The performance of multilevel partitioning algorithms that are proposed to enhance the performance of previous iterative-improvement partitioning algorithms for large scale circuits, depend on choice of construction methods for partition hierarchy. As the most of previous multilevel partitioning algorithms forces experimental constraints on the process of hierarchy construction, the stability of their performances goes down. The lack of stability causes the large variation of partition results during multiple runs. In this paper, we minimize the use of experimental constraints and propose a new method for constructing partition hierarchy. The proposed method clusters the cells with the connection status of the circuit. After constructing the partition hierarchy, a partition improvement algorithm, HYIP$^{[11]}$ using hybrid bucket structure, unclusters the hierachy to get partition results. The experimental results on ACM/SIGDA benchmark circuits show improvement up to 10-40% in minimum outsize over the previous algorithm $^{[3] [4] [5] [8] [10]}$. Also our technique outperforms ML$^{[10]}$ represented multilevel partition method by about 5% and 20% for minimum and average custsize, respectively. In addition, the results of our algorithm with 10 runs are better than ML algorithm with 100 runs.
