The essence of netlist partitioning is to divide a given netlist into sub-netlists such that the number of connections between them is minimized. The netlist partitioning problem occurs in many fields such as cell placement in physical CAD, FGPA partitioning, parallel computation, and any top down hierarchical(divide and conquer) approach. Since early decision in any top down hierarchical approach gives much impact on overall performance and current VLSI designs become more interconnect-dominated, netlist partitioning plays an important role.
During the past two decades, there have been many researches on this subject. In the previous literature, it is reported that clustering methods improve the performance of partitioning algorithms due to the following two reasons: First, clustering reduces solution space, so the probability to find good partitioning solution is increased. Second, clustering increases cell degree and this helps iterative partitioner to find a better solution. Recently, many researches on clustering method show that clustering is almost essential in improving the performance of iterative partitioning algorithms.
In this thesis, a new clustering algorithm is proposed. The proposed clustering algorithm finds clusters based on the following observation: if a group of cells is assigned to the same partition in numerous local optimum solutions, it is desirable to merge the cells into a cluster. The proposed clustering algorithm finds such a group of cells from randomly generated local optimum solutions and merges it into a cluster. Based on the proposed clustering algorithm, a hierarchical bipartitioning algorithm (MBP) is proposed. For MCNC benchmark netlists, MBP improves the total average cut size by 9% and the total best cut size by 3% ~ 4%, compared with the previous state-of-the-art partitioners.
회로분할 문제는 주어진 회로를 상호 연결이 최소가 되도록 k개의 작은 회로들로 분할하는 것 이다. 회로분할 문제는 cell 배치, FPGA 분할, 병렬 연산과 같은 여러 분야에서 발생한다. 또한 최근 다루어야 할 회로의 크기가 급속히 증가하여 여러 CAD 분야에서 회로를 작은 크기의 회로들로 분할한 후 분할된 각각의 회로에서 답을 구하는 top down 접근 방식(divide and conquer approach)이 널리 쓰이고 있고, 이러한 방식에서는 회로 분할 결과가 최종 결과에 큰 영향을 미치게 된다.
회로분할에 관한 기존의 연구결과 들을 통해서 클러스터링 방법은 회로분할 알고리즘의 성능을 크게 향상시킬 수 있음이 알려지게 되었고, 효과적인 클러스터링 알고리즘의 개발이 요구되어지고 있다.
본 논문에서는 새로운 클러스터링 알고리즘과, 이를 이용한 계층적 회로 분할 알고리즘인 MBP를 제안하였다. 제안된 클러스터링 알고리즘은 클러스터들을 찾기 위해 회로분할 문제의 local optimum solution space의 특성을 이용하였다. 제안된 클러스터링 방법은 상호 연결이 많은 cell group들은 대부분의 local optimum solution들에서 같이 움직이는 경향이 있다는 고찰을 바탕으로 하고있다. 이런 cell group들을 찾기 위해서, 몇 개의 local optimum solution들을 임의로 찾은 후 그들 가운데서 항상 같이 움직이는 cell group들을 찾는 방법을 사용하였고 실험을 통해서 약 20개의 local optimum solution들을 이용하면, 이러한 cell group을 찾을 수 있다는 것을 증명하였다. MBP는 제안된 클러스터링 방법을 주어진 회로에 반복적으로 적용하여 회로를 원하는 수준까지 단계적으로 단순화 시키는 과정(coarsening phase)과 가장 단순화된 회로의 회로분할 결과를 바로 이전 단계의 회로에 투사하고, 투사된 결과를 향상시켜가는 과정을 반복하여 원래의 회로에 대한 결과를 얻는 과정(uncoarsening phase)을 통해 주어진 회로를 분할한다.
MBP의 성능을 측정하기 위해 MCNC 실험 회로들(benchmark netlist)에 대한 실험결과를 구하였다. MBP는 최근에 발표된 알고리즘들에 비해 최소 상호 연결 선 수(best cut size)에 대해서는 약 3%, 평균 연결 선 수(average cut size)에 대해서는 9% 향상된 결과를 보였다.