Net cluster

摘要

The complexity and size of digital circuits has grown exponentially and today's circuits can contain millions of logic elements. Clustering algorithms have become popular due to their ability to reduce the circuit sizes so that circuit layout can be performed faster and with higher quality. This paper presents a deterministic, net-reduction based clustering algorithm, called Net Cluster. The basic idea of the proposed technique is to put the emphasis of clustering on reducing the number of nets versus the number of cells. The proposed algorithm has proven linear time complexity of O(p), where p is the number of pins in a circuit. To demonstrate the effectiveness of the proposed clustering technique, it has been applied to multilevel partitioning process. The numerical experiments on ISPD98 benchmark suite demonstrate that by applying Net Cluster, the performance of state-of-the-art multilevel partitioners can be further improved.