X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution

Genggeng Liu

doi:10.7717/peerj-cs.473

Return

X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution

2021-04-13

DOI：10.7717/peerj-cs.473

Original

Save

View PDF

Abstract

En 中文

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.

Keywords:

Discrete differential evolution

Steiner minimal tree

Non-Manhattan architecture

Global routing

Multi-strategy optimization

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.