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!
|
| _version_ | 1849719445232025600 |
|---|---|
| author | Linzi Yin Hao Hu Changgeng Li |
| author_facet | Linzi Yin Hao Hu Changgeng Li |
| author_sort | Linzi Yin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-9a451d7985054d3d90d8f762becd513a |
| institution | DOAJ |
| issn | 2227-7080 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Technologies |
| spelling | doaj-art-9a451d7985054d3d90d8f762becd513a2025-08-20T03:12:09ZengMDPI AGTechnologies2227-70802025-02-011328110.3390/technologies13020081Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu SearchLinzi Yin0Hao Hu1Changgeng Li2School of Electronic Information, Central South University, Changsha 410012, ChinaSchool of Electronic Information, Central South University, Changsha 410012, ChinaSchool of Electronic Information, Central South University, Changsha 410012, ChinaIn 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.https://www.mdpi.com/2227-7080/13/2/81circuit partitioningtabu searchclustering algorithm |
| spellingShingle | Linzi Yin Hao Hu Changgeng Li Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search Technologies circuit partitioning tabu search clustering algorithm |
| title | Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search |
| title_full | Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search |
| title_fullStr | Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search |
| title_full_unstemmed | Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search |
| title_short | Research on Circuit Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search |
| title_sort | research on circuit partitioning algorithm based on partition connectivity clustering and tabu search |
| topic | circuit partitioning tabu search clustering algorithm |
| url | https://www.mdpi.com/2227-7080/13/2/81 |
| work_keys_str_mv | AT linziyin researchoncircuitpartitioningalgorithmbasedonpartitionconnectivityclusteringandtabusearch AT haohu researchoncircuitpartitioningalgorithmbasedonpartitionconnectivityclusteringandtabusearch AT changgengli researchoncircuitpartitioningalgorithmbasedonpartitionconnectivityclusteringandtabusearch |