多动态电压设计下低功耗总体布线算法研究

Global routing is one of the most important steps in very large scale integration (VLSI) physical design. The introduction of multiple dynamic supply voltage (MDSV) designs can improve the power index of the chip in physical design. The proposed MDSV designs make the global routing problem be more complex. Besides, the recent research working on MDSV designs had only focused on the placement phase and clock tree construction, however, which still lack an effective and complete global routing algorithm for MDSV designs. For this reason, we will study the construction of an efficient VLSI low-power global router for MDSV designs: (1) According to the characteristics of multiple dynamic supply voltage designs provided by the industry, the coverage table and the related constraints are presented and then we formulate the new global routing model under MDSV designs;(2) We define an adjacency matrix among the different power domains to record the new distance relations between every two adjacent power domains, introduce a pretreatment strategy, and finally design the particle swarm optimization (PSO) algorithm for the power domain driven Steiner minimal tree construction; (3) Further considering the reduction of the level shifters, we view it as the reduction of the clusters and then design a multi-objective algorithm based on PSO for the power domain driven Steiner minimal tree construction with the reduction of the clusters; (4) Based on the integer linear programming (ILP) formulation, we design a partition strategy to reduce the complexity of ILP and then construct the VLSI low-power global router for MDSV designs.

总体布线是物理设计中极为重要的一个环节。多动态电压设计模式带来物理设计阶段功耗指标的优化，该设计模式的引入使得总体布线问题更为复杂，且目前相关工作只围绕布局、时钟树构造等阶段展开，缺乏一个多动态电压设计模式下有效完整的总体布线方案。为此，本课题研究在多动态电压设计模式下低功耗总体布线器的构建：（1）根据业界提供的多动态电压设计模式特点，引入涵盖表及相关约束条件，构建该设计模式下的总体布线问题模型；（2）定义不同电源定域的邻接矩阵，用以记录两两之间的新型距离，引入预处理策略，构建求解电源定域驱动Steiner最小树问题的粒子群优化方法；（3）进一步考虑电压转换器个数减少问题，将其转换为簇减少问题，构建求解考虑簇减少的电源定域驱动Steiner最小树问题的多目标粒子群优化方法；（4）基于整数线性规划模型，并引入划分策略以减少模型复杂度，构建多动态电压设计下低功耗总体布线器。

总体布线是超大规模集成电路物理设计中极为重要的一个环节。多动态电压设计（Multiple Dynamic Supply Voltage，MDSV）模式带来物理设计阶段功耗指标的优化，该设计模式的引入使得总体布线问题更为复杂，且目前相关工作只围绕布局、时钟树构造等阶段展开，缺乏一个MDSV设计模式下有效完整的总体布线方案。为此，本项目研究在MDSV设计模式下低功耗总体布线器的构建。以低功耗为总体布线算法的优化目标，选取优化线长策略以优化芯片的功耗，同时将多动态电压模型转换为障碍物内可走线长度限制模型，对MDSV设计模型下超大规模集成电路（Very Large Scale Integration，VLSI）总体布线相关问题展开一系列研究工作：包括构建了X结构Steiner最小树、长度限制的绕障直角Steiner树、单层芯片下绕障X结构Steiner最小树、多层芯片下绕障X结构Steiner最小树、多层芯片下绕障直角Steiner树、高性能X结构多层总体布线器、可布线性驱动的轨道调度方式等。同时将本项目构建的离散PSO等系列进化算法及其高效的启发式策略扩展并应用于其他大规模组合优化问题中，也取得一系列不错的研究成果。项目执行过程中，完成学术论文22篇，发表\录用期刊论文12篇，其中SCI收录3篇，申请国家发明专利8项，其中授权4项，培养研究生6名，其中已毕业博士1名。