Research On Partition Algorithms Applied In VLSI Domain

The partitioning problem of VLSI circuits is NP-complete and so many heuristic algorithms have been developed to make near-optima. This problem has been widely and deeply studied and many efficient algorithms are available now. The simple and efficient group-migration algorithms are widely adopted in solving this problem. But with the rapidly increasing scale of VLSI, more researchers have investigated the application of multilevel paradigm in this domain.In this paper, we firstly introduced some efficient algorithms on this problem, especially the very ones based on the multilevel paradigm. Then we present a new algorithm based on that. By this algorithm, we first construct a hypergraph from the circuit. Then the hypergraph is partitioned in multilevel paradigm. To extend the search space, several coarsening phases are adopted. A greedy method is developed and used in the refinement phase to avoid the local-optima with less time. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are better than those produced by the bisection or simple k-way algorithms.