Gate-Level Circuit Partitioning Algorithm Based on Clustering and an Improved Genetic Algorithm

Abstract

Gate-level circuit partitioning is an important development trend for improving the efficiency of simulation in EDA software. In this paper, a gate-level circuit partitioning algorithm, based on clustering and an improved genetic algorithm, is proposed for the gate-level simulation task. First, a clustering algorithm based on betweenness centrality is proposed to quickly identify clusters in the original circuit and achieve the circuit coarse. Next, a constraint-based genetic algorithm is proposed which provides absolute and probabilistic genetic strategies for clustered circuits and other circuits, respectively. This new genetic strategy guarantees the integrity of clusters and is effective for realizing the fine partitioning of gate-level circuits. The experimental results using 12 ISCAS ‘89 and ISCAS ‘85 benchmark circuits show that the proposed algorithm is 5% better than Metis, 80% better than KL, and 61% better than traditional genetic algorithms for finding the minimum number of connections between subsets.

Keywords

• circuit partitioning
• clustering algorithm
• genetic algorithm
• betweenness centrality