Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search
In this paper, a circuit-partitioning method is proposed based on partition connectivity clustering and tabu search. It includes four phases: coarsening, initial partitioning, uncoarsening, and refinement. In the initial partitioning phase, the concept of partition connectivity is introduced to opti...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-02-01
|
| Series: | Technologies |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7080/13/2/81 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In this paper, a circuit-partitioning method is proposed based on partition connectivity clustering and tabu search. It includes four phases: coarsening, initial partitioning, uncoarsening, and refinement. In the initial partitioning phase, the concept of partition connectivity is introduced to optimize the vertex-clustering process, which clusters vertices with high connectivity in advance to provide an optimal initial solution. In the refinement phase, an improved tabu search algorithm is proposed, which combines two flexible neighborhood search rules and a candidate solution-selection strategy based on vertex-exchange frequency to further optimize load balancing. Additionally, a random perturbation method is suggested to increase the diversity of the search space and improve both the depth and breadth of global search. The experimental results based on the ISCAS-89 and ISCAS-85 benchmark circuits show that the average cut size of the proposed circuit-partitioning method is 0.91 times that of METIS and 0.86 times that of the KL algorithm, with better performance for medium- and small-scale circuits. |
|---|---|
| ISSN: | 2227-7080 |