A concurrent approach to clustering algorithm with applications to VLSI domain

Circuit partitioning plays an important role in physical design automation of very large scale integration (VLSI) chips. In this brief we present a new connectivity based top down as well as bottom up approach to clustering algorithm for VLSI circuit partitioning. The proposed clustering algorithm partitions the circuit by focusing on highly interconnected cell groups. This clustering algorithm leads to a parallel implementation in which multiple processors are used to identify clusters simultaneously. The process starts with forming clusters by grouping the cells that are tightly connected and as well as the cells that are loosely connected. Considering both types of groups has the advantage that clusters formed from this technique will be highly connected and compact too. Therefore the proposed clustering method can reduce the size and also speed-up the large-scale partitioning problem without loosing partitioning solution qualities. The performance of the proposed clustering algorithm is evaluated on a standard set of partitioning benchmark-ISPD98 benchmark suite.