A Broad Review on Various VLSI CAD Algorithms for Circuit Partitioning Problems

Circuit partitioning is the first and the most important step in the designing of VLSI circuits. Owing to the rapidly increasing size of the designs, partitioning tools are becoming more important for the future. The partitioning algorithms are of two types, namely, constructive algorithms and iterative algorithms. In constructive algorithms, partition sets are formed with the help of algorithms; whereas, in case of iterative algorithms, new improved partition sets are formed at each iteration stepwith the modified netlist. A variety of heuristic algorithms have been developed to solve the problem of mincut which is NP-complete. With the main objective of minimizing the cutsize, numerous algorithms have been proposed for circuit partition which includes genetic and evolutionary algorithms, probability-based algorithms, clustering algorithms, and nature-based heuristics. The main intention of this paper is to provide a concise review of the VLSI CAD algorithms adopted for designing VLSI circuits. From the numerous partitioning methods available in the literature, a subjective selection has been made.