非曼哈顿结构下VLSI多层总体布线算法研究

项目名称： 非曼哈顿结构下VLSI多层总体布线算法研究

项目编号： No.11271002

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 陈国龙

作者单位： 福州大学

项目金额： 66万元

中文摘要： 总体布线是物理设计中极为重要的一个环节。非曼哈顿结构带来物理设计诸多性能的提高，该结构的引入和多层工艺的普及，使得总体布线算法更为复杂，且目前研究工作只就某些局部目标展开，缺乏一个该结构下有效完整的多层总体布线方案。为此，本课题研究在非曼哈顿结构下高效的VLSI多层总体布线器的构建：（1）利用X结构Steiner树的几何性质，定义其编解码方式和操作算子，继而构造X结构Steiner最小树；（2）定义不同程度的拥挤区域为权重各异的障碍物，融入惩罚机制，构建X结构绕障Steiner树，并利用分治思想和整数规划模型，构建拥挤线网的重布方法；（3）将缓冲器插入问题转换成求解最小半径最小代价生成树，构造求解该问题的多目标粒子群优化算法，以期优化时延；（4）定义线网顺序的评价函数，分析串扰的计算方法，构造同时优化串扰和通孔数的X结构层分配多目标粒子群优化算法，以还原之前映射到平面上的多层总体布线资源。

中文关键词： 超大规模集成电路；总体布线；非曼哈顿结构；多层布线；组合优化

英文摘要： Global routing is one of the most important steps in physical design. The introduction of non-Manhattan Architecture can improve many performance standards of the chip in physical design, such as wire length, via or channel height. The proposed non-Manhattan Architecture and pervasive multilayer technology make the global routing problem be more complex. Besides, the recent research working on non-Manhattan global routing had only focused on certain local goals, however, which still lack an effective and complete multilayer global routing algorithm in non-Manhattan Architecture. For this reason, we will study the construction of an efficient VLSI multilayer global router in the non-Manhattan Architecture: (1) We take full advantage of the X-based Steiner tree and use the new encoding and decoding schemes for the X-based Steiner tree. Considering the problem with the new encoding, here we design the new operators and then construct X-based Steiner minimum tree; (2) We view varying degrees of congested areas as differ power of obstacles and integrate punishment mechanism into the objective function, and then construct obstacle-avoiding X-based Steiner tree. And on that basis we reroute the congested nets combining Divide and Conquer with Integer Programming model; (3) Buffer insertion problem is converted to the

英文关键词： very large scale integration；global routing；non-manhattan；multilayer routing；combinatorial optimization