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...

Descripción completa

Detalles Bibliográficos
Autores principales: Liu, Genggeng, Yang, Liliang, Xu, Saijuan, Li, Zuoyong, Chen, Yeh-Cheng, Chen, Chi-Hua
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