Cargando…
X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution
Global routing is an important link in very large scale integration (VLSI) design. As the best model of global routing, X-architecture Steiner minimal tree (XSMT) has a good performance in wire length optimization. XSMT belongs to non-Manhattan structural model, and its construction process cannot b...
Autores principales: | , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
PeerJ Inc.
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8053017/ https://www.ncbi.nlm.nih.gov/pubmed/33954247 http://dx.doi.org/10.7717/peerj-cs.473 |
_version_ | 1783680034103361536 |
---|---|
author | Liu, Genggeng Yang, Liliang Xu, Saijuan Li, Zuoyong Chen, Yeh-Cheng Chen, Chi-Hua |
author_facet | Liu, Genggeng Yang, Liliang Xu, Saijuan Li, Zuoyong Chen, Yeh-Cheng Chen, Chi-Hua |
author_sort | Liu, Genggeng |
collection | PubMed |
description | Global routing is an important link in very large scale integration (VLSI) design. As the best model of global routing, X-architecture Steiner minimal tree (XSMT) has a good performance in wire length optimization. XSMT belongs to non-Manhattan structural model, and its construction process cannot be completed in polynomial time, so the generation of XSMT is an NP hard problem. In this paper, an X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution (XSMT-MoDDE) is proposed. Firstly, an effective encoding strategy, a fitness function of XSMT, and an initialization strategy of population are proposed to record the structure of XSMT, evaluate the cost of XSMT and obtain better initial particles, respectively. Secondly, elite selection and cloning strategy, multiple mutation strategies, and adaptive learning factor strategy are presented to improve the search process of discrete differential evolution algorithm. Thirdly, an effective refining strategy is proposed to further improve the quality of the final Steiner tree. Finally, the results of the comparative experiments prove that XSMT-MoDDE can get the shortest wire length so far, and achieve a better optimization degree in the larger-scale problem. |
format | Online Article Text |
id | pubmed-8053017 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | PeerJ Inc. |
record_format | MEDLINE/PubMed |
spelling | pubmed-80530172021-05-04 X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution Liu, Genggeng Yang, Liliang Xu, Saijuan Li, Zuoyong Chen, Yeh-Cheng Chen, Chi-Hua PeerJ Comput Sci Algorithms and Analysis of Algorithms Global routing is an important link in very large scale integration (VLSI) design. As the best model of global routing, X-architecture Steiner minimal tree (XSMT) has a good performance in wire length optimization. XSMT belongs to non-Manhattan structural model, and its construction process cannot be completed in polynomial time, so the generation of XSMT is an NP hard problem. In this paper, an X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution (XSMT-MoDDE) is proposed. Firstly, an effective encoding strategy, a fitness function of XSMT, and an initialization strategy of population are proposed to record the structure of XSMT, evaluate the cost of XSMT and obtain better initial particles, respectively. Secondly, elite selection and cloning strategy, multiple mutation strategies, and adaptive learning factor strategy are presented to improve the search process of discrete differential evolution algorithm. Thirdly, an effective refining strategy is proposed to further improve the quality of the final Steiner tree. Finally, the results of the comparative experiments prove that XSMT-MoDDE can get the shortest wire length so far, and achieve a better optimization degree in the larger-scale problem. PeerJ Inc. 2021-04-13 /pmc/articles/PMC8053017/ /pubmed/33954247 http://dx.doi.org/10.7717/peerj-cs.473 Text en © 2021 Liu et al. https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ Computer Science) and either DOI or URL of the article must be cited. |
spellingShingle | Algorithms and Analysis of Algorithms Liu, Genggeng Yang, Liliang Xu, Saijuan Li, Zuoyong Chen, Yeh-Cheng Chen, Chi-Hua X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
title | X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
title_full | X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
title_fullStr | X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
title_full_unstemmed | X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
title_short | X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
title_sort | x-architecture steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution |
topic | Algorithms and Analysis of Algorithms |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8053017/ https://www.ncbi.nlm.nih.gov/pubmed/33954247 http://dx.doi.org/10.7717/peerj-cs.473 |
work_keys_str_mv | AT liugenggeng xarchitecturesteinerminimaltreealgorithmbasedonmultistrategyoptimizationdiscretedifferentialevolution AT yangliliang xarchitecturesteinerminimaltreealgorithmbasedonmultistrategyoptimizationdiscretedifferentialevolution AT xusaijuan xarchitecturesteinerminimaltreealgorithmbasedonmultistrategyoptimizationdiscretedifferentialevolution AT lizuoyong xarchitecturesteinerminimaltreealgorithmbasedonmultistrategyoptimizationdiscretedifferentialevolution AT chenyehcheng xarchitecturesteinerminimaltreealgorithmbasedonmultistrategyoptimizationdiscretedifferentialevolution AT chenchihua xarchitecturesteinerminimaltreealgorithmbasedonmultistrategyoptimizationdiscretedifferentialevolution |