The essence of partitioning is to divide a circuit or a system into appropriate number of components. As the system complexity is enormously increased in the past several years, partitioning has become more and more important task. Partitioning divides a system into a number of smaller sub-blocks which are manageable with existing CAD tools and technology.
This thesis describes two partitioning approaches with spectral method which uses the eigenvectors and the eigenvalues of the Laplacian of a graph. The first approach is multi-way scaled cost partitioning based on linear ordering. Recently, one-dimensional linear ordering scheme has received increasing attention. Some partitioning algorithm has shown optimal result for a given linear ordering. Thus netlist partitioning with respect to scaled cost can be transformed to the linear ordering problem. In this thesis, two linear ordering algorithms are proposed. The first algorithm called CBLO improved the quality of linear ordering by clustering. CBLO consists of global ordering and local ordering. The global ordering again consists of cluster formation and inter-cluster ordering. As CBLO has more global partitioning information than previous approaches by clustering, the proposed algorithm produces better result in multi-way partitioning than previous algorithms. The second algorithm called LIME constructs linear ordering by merging two segments into new one until only one segment remains. The final resultant segment corresponds to the linear ordering. In this algorithm, it is important to select two segments to be merged. The proposed cost function selecting two segments can produce optimal(q-1) segments for a given q segments in terms of scaled cost function. LIME also runs extremely fast, because it exploits sparsity of netlist. Compared with the earlier work, LIME is eight times faster in producing linear ordering and yields an average of 17% improvement for the multi-way scaled cost partitioning.
The second approach is two-way vector partitioning based on direction vector. In this approach, a procedure to obtain optimal solution of size-constrained two-way vector partitioning is shown if optimal direction vector is given. While the problem to find the optimal direction vector is NP-complete, we propose an efficient heuristic called PDV to obtain high quality direction vector with iterative approach. As a given netlist is approximated into the graph using clique model and we only use the d(≪n) eigenvectors in practice, there is a chance to improve the solution quality by local optimization. In PDV, Fiduccia-Mattheyses algorithm is employed as a post processing. PDV produced favorable results in several experiments.
회로분할은 디지탈 시스템을 현재의 CAD툴과 기술로 다룰 수 있는 작은 블럭들로 나누는 것이다. 지난 수년간 디지탈 시스템의 복잡도가 현저하게 증가되어 CAD분야에서 회로분할의 중요성은 점점 커지고 있다.
본 논문에서는 스펙트럴 방법을 이용하여 회로를 분할하였다. 이 방법은 고유값과 고유벡터를 이용하여 회로의 각 모듈을 새로운 공간에 벡터로 일대일 사상시키고, 사상된 벡터를 분할하여 그에 대응하는 회로분할을 구하는 것이다.
첫번째 방법론은 선형순서를 이용한 회로분할 방법이다. 주어진 회로의 선형순서에 대해 최적의 회로분할방법이 발표되어 이 방법은 최근 많은 호응을 얻고있다. 본 논문에서는 CBLO와 LIME이라는 두 가지 알고리즘을 제안하였다. CBLO는 사상된 벡터들을 클러스터로 만들고, 그것들의 선형순서를 구한 후 각 클러스터에 있는 벡터들의 선형순서를 구하게 된다. 이방법은 클러스터링을 이용함으로써, 기존 방법보다 더 많은 분할 정보를 갖게되므로 좋은 성능을 나타냈다. LIME은 하나의 세그먼트가 남을 때 까지 두 개의 세그먼트를 새로운 하나의 세그먼트로 병합하는 방법을 계속 적용하며, 최종적으로 남는 하나의 세그먼트가 구하고자 하는 선형순서가 된다. LIME에서는 병합될 두 개의 세그먼트를 선택하는 새로운 비용함수를 제안하였으며 회로의 성긴 특성을 이용하여 빠르면서 좋은 결과를 구할 수 있었다.
두 번째 방법론은 방향 벡터를 이용하여 사상된 벡터를 분할하는 것이다. 최적의 방향 벡터를 알면 최적의 벡터분할을 할 수 있음을 보였으며, 이 문제가 NP-complete이므로 좋은 방향벡터를 찾는 휴리스틱을 제안하였다. 최적의 방향백터 대신 휴리스틱으로 구한 방향벡터를 이용해 사상된 벡터들을 분할한 후, 그에 대응하는 회로분할을 얻었다. 실제 예제를 통해 제안된 회로분할 방법이 기존방법에 비해 우수함을 보였다.
