X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution.
X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution.
复制标题
基于多策略优化离散差分进化的X架构Steiner最小树算法
DOI：
10.7717/peerj-cs.473
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Chen CH
中科院分区：
文献类型：
--
作者：
Liu G;Yang L;Xu S;Li Z;Chen YC;Chen CH
全局布线是超大规模集成电路(VLSI)设计的重要环节。作为全局布线的最佳模型，X体系结构的施泰纳最小树(XSMT)在布线长度优化方面具有良好的性能。XSMT属于非曼哈顿结构模型，其构造过程不可能在多项式时间内完成，因此XSMT的生成是一个NP难问题。提出了一种基于多策略优化离散差分进化的X体系结构Steiner最小树算法(XSMT-MONDE)。首先，提出了一种有效的编码策略、一种XSMT的适应度函数和一种种群初始化策略，分别用于记录XSMT的结构、评估XSMT的代价和获得较好的初始粒子。其次，提出了精英选择和克隆策略、多变异策略和自适应学习因子策略来改进离散差分进化算法的搜索过程。第三，提出了一种有效的精化策略，进一步提高了最终的Steiner树的质量。最后，对比实验的结果证明，XSMT-MODE算法可以获得到目前为止最短的导线长度，并且在更大规模的问题中达到了更好的优化程度。
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.