考虑簇减少的可变长度限制X结构Steiner最小树算法

刘耿耿; 吕星灿; 周茹平; 郑瀚; 傅仰耿

doi:10.12263/DZXB.20260062

您当前的位置：

首页 >

文章列表页 >

考虑簇减少的可变长度限制X结构Steiner最小树算法

学术论文 | 更新时间：2026-06-17

- 考虑簇减少的可变长度限制X结构Steiner最小树算法
- Variable Length-Restricted X-Architecture Steiner Minimum Tree Algorithm Considering Cluster Reduction
- 电子学报 2026年54卷第4期页码：1682-1699
- 作者机构：
  
  1.福州大学计算机与大数据学院，福建福州 350116
  2.大数据智能教育部工程研究中心，福建福州 350116
  3.福建省网络计算与智能信息处理重点实验室，福建福州 350116
- 作者简介：
  
  刘耿耿男，1988年生，福建南安人。博士，现为福州大学计算机与大数据学院教授。中国计算机学会（CCF）杰出会员。主要研究方向为EDA算法。E-mail: liugenggeng@fzu.edu.cn
  吕星灿男，2002年生，浙江永康人。现为福州大学计算机与大数据学院硕士研究生。主要研究方向为超大规模集成电路布线。E-mail: 13003842518@163.com
  周茹平女，1998年生，福建宁德人。现为福州大学计算机与大数据学院博士研究生。主要研究方向为集成电路设计自动化。E-mail: zrp08200331@163.com
  郑瀚男，2001年生，福建福州人。现为福州大学计算机与大数据学院硕士研究生。主要研究方向为超大规模集成电路布线。E-mail: hanzheng.cn@outlook.com
  傅仰耿男，1981年生，福建南安人。博士，现为福州大学计算机与大数据学院教授。中国计算机学会（CCF）杰出会员。主要研究方向为数据挖掘与机器学习、智能决策支持系统。E-mail: fu@fzu.edu.cn
- 基金信息：
  
  国家自然科学基金(62372109);福建省杰出青年科学基金(2023J06017)
- DOI：10.12263/DZXB.20260062
  中图分类号： TP301;
- 收稿：2026-03-05，
  
  录用：2026-04-08，
  
  纸质出版：2026-04-25
- 稿件说明：
移动端阅览
刘耿耿, 吕星灿, 周茹平, 等. 考虑簇减少的可变长度限制X结构Steiner最小树算法[J]. 电子学报, 2026, 54(04): 1682-1699.

LIU Genggeng, LÜ Xingcan, ZHOU Ruping, et al. Variable Length-Restricted X-Architecture Steiner Minimum Tree Algorithm Considering Cluster Reduction[J]. Acta Electronica Sinica, 2026, 54(04): 1682-1699.
刘耿耿, 吕星灿, 周茹平, 等. 考虑簇减少的可变长度限制X结构Steiner最小树算法[J]. 电子学报, 2026, 54(04): 1682-1699. DOI：10.12263/DZXB.20260062

LIU Genggeng, LÜ Xingcan, ZHOU Ruping, et al. Variable Length-Restricted X-Architecture Steiner Minimum Tree Algorithm Considering Cluster Reduction[J]. Acta Electronica Sinica, 2026, 54(04): 1682-1699. DOI：10.12263/DZXB.20260062

摘要

多动态电压（Multiple Dynamic Supply Voltage，MDSV）设计模式通过在芯片中划分不同电压域，使各模块在满足性能与时序要求的前提下采用差异化供电，从而降低整体功耗并提升能效。然而，现有的Steiner最小树（Steiner Minimum Tree，SMT）问题相关工作尚未考虑到MDSV设计模式带来的新约束条件与新优化目标，难以满足MDSV设计模式下的可变长度约束，同时也未考虑引入电压转换器（Level Shifter，LS）带来的额外开销。为此，本文提出了一种考虑簇减少的可变长度限制X结构SMT算法（Variable Length-Restricted X-architecture Steiner Minimum Tree algorithm considering Cluster Reduction， VLRXSMT-CR）。首先，为有效求解MDSV设计模式下SMT这一离散化多目标优化问题，提出了离散化的正向学习算子和变异算子，并引入竞争选择机制与基于拥塞度的外部存档更新机制，实现了LS数量和线长的多目标优化。其次，为避免算法过早陷入局部最优并增强迭代后期的局部搜索能力，以进一步提升解的质量，提出了多样化麻雀比例调整策略。再次，为提高算法更新阶段学习对象的多样性，将分层学习机制引入离散麻雀搜索算法（Sparrow Search Algorithm，SSA）更新过程中。最后，为满足MDSV设计约束并进一步优化布线结构，引入了调整与混合精炼策略，对候选解中违反约束条件的布线边进行调整，同时对候选解中的非最优局部拓扑结构进行优化。与现有方法相比，本文提出的算法在线长指标上取得一定优化的同时，在MDSV设计模式下的关键性能指标（LS）使用数量方面取得了38.60%~51.91%的大幅优化。

Abstract

The multiple dynamic supply voltage (MDSV) design paradigm partitions a chip into multiple voltage domains

enabling modules to operate with differentiated supply voltages while meeting performance and timing requirements

thereby reducing overall power consumption and improving energy efficiency. However

existing studies on the Steiner minimum tree (SMT) problem have not yet taken into account the new constraints and optimization objectives introduced by the MDSV design paradigm. Consequently

these methods are unable to effectively handle variable length restriction under the MDSV environment and fail to account for the additional overhead introduced by level shifters (LSs). To address these issues

this paper proposes a variable length-restricted X-architecture SMT algorithm considering cluster reduction (VLRXSMT-CR). First

in order to effectively solve the discrete multi-objective optimization problem of the SMT under the MDSV design paradigm

discrete forward learning operators and mutation operators are proposed. In addition

a competitive selection mechanism and a congestion-based external archive update mechanism are introduced to achieve multi-objective optimization of the number of LSs and routing wirelength. Second

to avoid premature convergence of the algorithm to local optima and to enhance local search capability in the later stages of iteration

thereby further improving solution quality

a diversified sparrow proportion adjustment strategy is proposed. Then

to improve the diversity of learning targets during the algorithm update stage

a hierarchical learning mechanism is introduced into the update process of the discrete sparrow search algorithm (SSA). Finally

in order to satisfy MDSV design constraints and further optimize routing structures

adjustment and hybrid refinement strategies are introduced to adjust routing edges that violate constraint conditions in candidate solutions

while optimizing non-optimal local topological structures in candidate solutions. Compared with existing methods

the proposed algorithm achieves certain improvements in routing wirelength

while obtaining a significant improvement of 38.60% to 51.91% in the number of LSs

which is a key performance metric under the MDSV design paradigm.

关键词

Keywords

references

Zheng Huajian , Ye Zhuohang , Liu Baiquan , et al . Dual-gate metal-oxide-semiconductor transistors: Nanoscale channel length scaling and performance optimization [J ] . Electronics , 2025 , 14 ( 7 ): 1257 . DOI: 10.3390/electronics14071257 http://dx.doi.org/10.3390/electronics14071257

Razif R A M , Maharum S M M , Hasani A H , et al . Mitigation techniques for crosstalk in ICs [J ] . IOP Conference Series: Materials Science and Engineering , 2019 , 701 ( 1 ): 012037 . DOI: 10.1088/1757-899x/701/1/012037 http://dx.doi.org/10.1088/1757-899x/701/1/012037

Chauhan P , Gupta S . Challenges and future perspectives of low-power VLSI circuits: A study [M ] // Modern Electronics Devices and Communication Systems . Singapore : Springer Nature Singapore , 2023 : 561 - 569 . DOI: 10.1007/978-981-19-6383-4_46 http://dx.doi.org/10.1007/978-981-19-6383-4_46

Varadharajan S K , Nallasamy V . Low power VLSI circuits design strategies and methodologies: A literature review [C ] // 2017 Conference on Emerging Devices and Smart Systems (ICEDSS) . Piscataway : IEEE , 2017 : 245 - 251 . DOI: 10.1109/icedss.2017.8073688 http://dx.doi.org/10.1109/icedss.2017.8073688

Kao C C . Clock skew minimization in multiple dynamic supply voltage with adjustable delay buffers restriction [J ] . Journal of Signal Processing Systems , 2015 , 79 ( 1 ): 99 - 104 . DOI: 10.1007/s11265-014-0888-x http://dx.doi.org/10.1007/s11265-014-0888-x

Gundala S , Basha M M , Vijayakumar S . Level-up/level-down voltage level shifter for nano-scale applications [J ] . Journal of Engineering Science and Technology , 2022 , 17 ( 1 ): 745 - 759 .

Liu Genggeng , Zhu Yuhan , Xu Saijuan , et al . Performance-driven X-architecture routing algorithm for artificial intelligence chip design in smart manufacturing [J ] . ACM Transactions on Management Information Systems , 2022 , 13 ( 4 ): 3519422 . DOI: 10.1145/3519422 http://dx.doi.org/10.1145/3519422

刘耿耿 , 黄逸飞 , 王鑫 , 等 . 基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法 [J ] . 计算机学报 , 2021 , 44 ( 12 ): 2542 - 2559 .

Liu Genggeng , Huang Yifei , Wang Xin , et al . Hybrid discrete particle swarm optimization algorithm for X-architecture Steiner minimal tree construction with Slew constraints [J ] . Chinese Journal of Computers , 2021 , 44 ( 12 ): 2542 - 2559 . (in Chinese)

汤浩 , 刘耿耿 , 郭文忠 , 等 . 考虑布线资源松弛的X结构Steiner最小树算法 [J ] . 模式识别与人工智能 , 2020 , 33 ( 5 ): 401 - 412 . DOI: 10.16451/j.cnki.issn1003-6059.202005003 http://dx.doi.org/10.16451/j.cnki.issn1003-6059.202005003

Tang Hao , Liu Genggeng , Guo Wenzhong , et al . X-architecture Steiner minimum tree algorithm considering routing resource relaxation [J ] . Pattern Recognition and Artificial Intelligence , 2020 , 33 ( 5 ): 401 - 412 . (in Chinese) . DOI: 10.16451/j.cnki.issn1003-6059.202005003 http://dx.doi.org/10.16451/j.cnki.issn1003-6059.202005003

Liu Wenhao , Li Yilang , Chao Kaiyuan . High-quality global routing for multiple dynamic supply voltage designs [C ] // 2011 IEEE/ACM International Conference on Computer-Aided Design . Piscataway : IEEE , 2011 : 263 - 269 . DOI: 10.1109/ICCAD.2011.6105338 http://dx.doi.org/10.1109/ICCAD.2011.6105338

饶凌风 , 耿娜 , 张勇 , 等 . 不确定环境下无人机任务分配的种群交互式粒子群算法 [J ] . 电子学报 , 2025 , 53 ( 8 ): 2678 - 2690 .

Rao Lingfeng , Geng Na , Zhang Yong , et al . Population interactive particle swarm optimization algorithm for UAV task allocation in uncertain environments [J ] . Acta Electronica Sinica , 2025 , 53 ( 8 ): 2678 - 2690 . (in Chinese)

李照希 , 苏震宇 , 田宇浩 , 等 . 基于人工智能算法的单级全差分折叠式共源共栅运算放大器的多目标设计方法 [J ] . 电子学报 , 2025 , 53 ( 6 ): 1784 - 1791 . DOI: 10.12263/DZXB.20250055 http://dx.doi.org/10.12263/DZXB.20250055

Li Zhaoxi , Su Zhenyu , Tian Yuhao , et al . Multi-objective design method for single-stage fully differential folded cascode operational amplifiers based on the artificial intelligence algorithm [J ] . Acta Electronica Sinica , 2025 , 53 ( 6 ): 1784 - 1791 . (in Chinese) . DOI: 10.12263/DZXB.20250055 http://dx.doi.org/10.12263/DZXB.20250055

Cheng Lianyu , Ling Guang , Liu Feng , et al . Application of uniform experimental design theory to multi-strategy improved sparrow search algorithm for UAV path planning [J ] . Expert Systems with Applications , 2024 , 255 : 124849 . DOI: 10.1016/j.eswa.2024.124849 http://dx.doi.org/10.1016/j.eswa.2024.124849

Xue Jiankai , Shen Bo . A novel swarm intelligence optimization approach: Sparrow search algorithm [J ] . Systems Science & Control Engineering , 2020 , 8 ( 1 ): 22 - 34 . DOI: 10.1080/21642583.2019.1708830 http://dx.doi.org/10.1080/21642583.2019.1708830

Lei Lei , Shao Suola , Liang Lixia . An evolutionary deep learning model based on EWKM, random forest algorithm, SSA and BiLSTM for building energy consumption prediction [J ] . Energy , 2024 , 288 : 129795 . DOI: 10.1016/j.energy.2023.129795 http://dx.doi.org/10.1016/j.energy.2023.129795

Chang Chun , Pan Yaliang , Wang Shaojin , et al . Fast EIS acquisition method based on SSA-DNN prediction model [J ] . Energy , 2024 , 288 : 129768 . DOI: 10.1016/j.energy.2023.129768 http://dx.doi.org/10.1016/j.energy.2023.129768

王毅 , 郑宏志 , 黄欣 , 等 . 基于多阶段调度框架的麻雀搜索优化算法 [J ] . 电子学报 , 2024 , 52 ( 9 ): 3086 - 3096 .

Wang Yi , Zheng Hongzhi , Huang Xin , et al . Sparrow search optimization algorithm based on multi-stage scheduling framework [J ] . Acta Electronica Sinica , 2024 , 52 ( 9 ): 3086 - 3096 . (in Chinese)

Chu C , Wong Y C . FLUTE: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2008 , 27 ( 1 ): 70 - 83 . DOI: 10.1109/TCAD.2007.907068 http://dx.doi.org/10.1109/TCAD.2007.907068

Lin S E D , Kim D H . Construction of all rectilinear Steiner minimum trees on the Hanan grid and its applications to VLSI design [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2020 , 39 ( 6 ): 1165 - 1176 . DOI: 10.1109/tcad.2019.2917896 http://dx.doi.org/10.1109/tcad.2019.2917896

Guo Zizheng , Gu Feng , Lin Yibo . GPU-accelerated rectilinear Steiner tree generation [C ] // The 41st IEEE/ACM International Conference on Computer-Aided Design . New York : ACM , 2022 : 3549434 . DOI: 10.1145/3508352.3549434 http://dx.doi.org/10.1145/3508352.3549434

Kahng A B , Nerem R R , Wang Yusu , et al . NN-Steiner: A mixed neural-algorithmic approach for the rectilinear Steiner minimum tree problem [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2024 , 38 ( 12 ): 13022 - 13030 . DOI: 10.1609/aaai.v38i12.29200 http://dx.doi.org/10.1609/aaai.v38i12.29200

Lin Zhenkun , Liu Genggeng , Huang Xing , et al . A unified deep reinforcement learning approach for constructing rectilinear and octilinear Steiner minimum tree [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2025 , 44 ( 7 ): 2711 - 2724 . DOI: 10.1109/tcad.2024.3523429 http://dx.doi.org/10.1109/tcad.2024.3523429

Liu Genggeng , Chen Xiaohua , Zhou Ruping , et al . Social learning discrete Particle Swarm Optimization based two-stage X-routing for IC design under Intelligent Edge Computing architecture [J ] . Applied Soft Computing , 2021 , 104 : 107215 . DOI: 10.1016/j.asoc.2021.107215 http://dx.doi.org/10.1016/j.asoc.2021.107215

Guo Wenzhong , Huang Xing . PORA: A Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design [J ] . Applied Mathematical Modelling , 2020 , 78 : 268 - 286 . DOI: 10.1016/j.apm.2019.10.027 http://dx.doi.org/10.1016/j.apm.2019.10.027

Kundu S , Roy S , Mukherjee S . An efficient obstacle-avoiding rectilinear Steiner tree construction method using PB-SAT [J ] . IETE Journal of Research , 2023 , 69 ( 6 ): 3346 - 3356 . DOI: 10.1080/03772063.2021.1967790 http://dx.doi.org/10.1080/03772063.2021.1967790

Lin Zhenkun , Zhu Yuhan , Huang Xing , et al . Obstacle-avoiding rectilinear Steiner minimal tree algorithm based on deep reinforcement learning [C ] // 2023 International Conference on Artificial Intelligence of Things and Systems . Piscataway : IEEE , 2023 : 149 - 156 . DOI: 10.1109/aiotsys58602.2023.00044 http://dx.doi.org/10.1109/aiotsys58602.2023.00044

Zhang Tiancheng , Lyu Zhipeng , Ding Junwen . Guiding solution based local search for obstacle-avoiding rectilinear Steiner minimal tree problem [J ] . IEEE Transactions on Emerging Topics in Computational Intelligence , 2024 , 8 ( 1 ): 440 - 453 . DOI: 10.1109/tetci.2023.3306241 http://dx.doi.org/10.1109/tetci.2023.3306241

Huang Xing , Liu Genggeng , Guo Wenzhong , et al . Obstacle-avoiding algorithm in X-architecture based on discrete particle swarm optimization for VLSI design [J ] . ACM Transactions on Design Automation of Electronic Systems , 2015 , 20 ( 2 ): 2699862 . DOI: 10.1145/2699862 http://dx.doi.org/10.1145/2699862

Held S , Spirkl S T . A fast algorithm for rectilinear Steiner trees with length restrictions on obstacles [C ] // 2014 International Symposium on Physical Design . New York : ACM , 2014 : 37 - 44 .

Qin Yuancheng , Yao Yingbiao , Feng Wei , et al . Dynamic voltage scaling based energy-minimized partial task offloading in fog networks [J ] . Wireless Networks , 2022 , 28 ( 8 ): 3337 - 3347 . DOI: 10.1007/s11276-022-03052-3 http://dx.doi.org/10.1007/s11276-022-03052-3

Wu T H , Davoodi A , Linderoth J T . Power-driven global routing for multisupply voltage domains [J ] . VLSI Design , 2013 , 2013 ( 1 ): 905493 . DOI: 10.1155/2013/905493 http://dx.doi.org/10.1155/2013/905493

Khan Q A , Wadhwa S K , Misri K . A single supply level shifter for multi-voltage systems [C ] // The 19th International Conference on VLSI Design Held Jointly with 5th International Conference on Embedded Systems Design . Piscataway : IEEE , 2006 : 24 . DOI: 10.1109/VLSID.2006.24 http://dx.doi.org/10.1109/VLSID.2006.24

Zhang Hao , Ye Dongyi , Guo Wenzhong . A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles [J ] . Integration , 2016 , 55 : 162 - 175 . DOI: 10.1016/j.vlsi.2016.06.001 http://dx.doi.org/10.1016/j.vlsi.2016.06.001

Zhu Yuhan , Liu Genggeng , Lu Ren , et al . Timing-driven obstacle-avoiding X-architecture Steiner minimum tree algorithm with slack constraints [J ] . IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2024 , 54 ( 5 ): 2927 - 2940 . DOI: 10.1109/tsmc.2024.3353534 http://dx.doi.org/10.1109/tsmc.2024.3353534

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向多目标车辆路径规划问题的进化多任务算法

带特征选择的综合因果多目标反事实解释方法

基于多目标并行混沌优化的分布式驱动电动汽车横摆稳定性研究

带时间窗的无线可充电传感器网络多目标路径规划算法

基于时空维度分解与异构解码的轻量化轨迹预测模型