Multilevel-based Graph Partitioning And Its Application In VLSI Design

Over the years, partitioning has emerged as one of the most effective tools for managing VLSI design complexity. In this dissertation, we study the weighted undirected graph partitioning problem based on the multilevel paradigm and its application in VLSI design. Furthermore, we propose and implement multilevel circuit partitioner (MCP). The achievements of the dissertation are as follows:1. During the coarsening phase, we propose the core-sorted heavy-edge matching (CSHEM) algorithm and give its details based on the compressed storage format of graph. The CSHEM algorithm not only improves previous matching schemes which are based on local information of vertex, using the global information of the finest graph core to develop its guidance role, but overcomes the defect that we can only choose the random matching (RM) algorithm as a guide matching algorithm in the multilevel paradigm. We also present an effective matching-based coarsening scheme that uses the CSHEM algorithm on the finest graph and the Sorted Heavy-Edge Matching (SHEM) algorithm on the coarser graphs. The scheme plays a guidance role of the core so as to make the coarser graph in accord with the core-consistent principle. Our experimental evaluations on ISPD98 circuit benchmark show the scheme produces encouraging performance improvement compared with those produced by the combination scheme of RM and SHEM of MeTiS that is a state-of-the-art partitioner in the literature.2. During the initial partitioning phase, we propose the algorithm for spectral partitioning with weighted undirected graph (SPWUG) and give the second smallest eigenvector (called the Fiedler vector) calculation of Laplacian matrix using the Lanczos iteration method. The components of the Fiedler vector are weights on the corresponding vertices of graph such that differences of the components provide information about the distances between the vertices. According to the distances, the SPWUG algorithm computes the initial partition of the coarsest graph by extending the Laplacian spectral graph theory from the unweighted undirected graph into the weighted undirected graph. Our experimental evaluations on ISPD98 show the SPWUG algorithm produces the further performance improvement coupled with the combination scheme of CSHEM and SHEM. Meanwhile, the experiments show that the approximate global minimum partition of the coarsest graph may be the local minimum partition of the finest graph and we need to strengthen the global search ability of refinement algorithm in the refinement phase.3. During the refinement phase, we propose the multi-level tabu search refinement algorithm and the multi-level swarm intelligence refinement algorithm. These algorithms try to find the better partition of the finest graph by introducing respective intelligent optimization techniques which allow movements towards solutions worse than the current one in order to escape from local minima. Our experimental evaluations on ISPD98 show that these algorithms produce the further performance improvement coupled with the CSHEM and SPWUG algorithm. Meanwhile, the experiments show that the multi-level swarm intelligence refinement algorithm is better than the multilevel tabu search refinement algorithm, especially in view of the probability that the approximate global minimum partition of the coarser graph may be the local minimum partition of the finer graph. Furthermore, the experiments show that the multi-level ant colony optimization refinement algorithm achieves more performance improvement than the multi-level particle swarm optimization refinement algorithm, using the gain of vertex more effectively.4. Finally, we apply the weighted undirected graph partitioning based on the multilevel paradigm in VLSI design. A system for circuit partitioning is proposed and implemented, named MCP. The MCP's framework, flow, composition modules as well as their realization difficulties are described in this dissertation. The MCP system can be used to divide the VLSI into clusters with equal size such that the inter-cluster connections are minimized. The MCP system outputs the clusters described by the Verilog language which can be used in the subsequent process of software/hardware Co-Emulation system.