一种多层绕障直角斯坦纳最小树启发式算法  

Effective Heuristic for the Multilayer Obstacle-avoiding Rectilinear Steiner Minimal Tree

作　　者：张浩[1,2] 叶东毅[1,2] 郭文忠[1,2] 

机构地区：[1]福州大学数学与计算机科学学院,福州350116 [2]福建省网络计算与智能信息处理重点实验室,福州350116

出　　处：《小型微型计算机系统》2016年第8期1760-1764,共5页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2011CB808000)资助;国家自然科学基金项目(11271002;11501114)资助;福建省自然科学基金项目(2016J01754)资助;福建省省教育厅中青年教师教育科研项目(JA15069)资助

摘　　要：直角斯坦纳树问题是大规模集成电路物理设计中重要的基本模型.现代集成电路设计需要同时考虑障碍和多层布线等约束条件.通过构造布线图,提出一种多层绕障直角斯坦纳最小树启发式算法.为了避开障碍和连通各布线层之间的引脚,本文引入了三种候选通孔位置.在同一布线层内,通过扩展满直角斯坦纳树网格来构造单层布线图,再使用候选通孔互联成多层布线图.在多层布线图中,引入候选斯坦纳点来构造斯坦纳树,并以标记的引导点执行局部搜索策略来提高求解质量.实验结果表明,本文算法能够有效求解多层绕障直角斯坦纳最小树问题.本文算法所得总布线权重与最新的两种算法相比,改进率可达2.34%和5.48%.The rectilinear Steiner minimal tree problem is a fundamental problem in very large-scale integrated circuit physical design. Modem integrated circuit design often contains several routing layers and a lot of routing blockages. By building a routing graph, we propose a heuristic for the multilayer obstacle-avoiding rectilinear Steiner minimal tree problem. Three types of candidate via positions which are used for avoiding the obstacles and interconnecting the adjacent circuit layers are selected. The routing graph of a single layer is built by connecting the pins and candidate via positions with the extended rectilinear full Steiner trees grid. A routing graph of the multilayer obstacle-avoiding rectilinear Steiner minimaltree problem is built by connecting the routing graphs of adjacent layers with candidate vias. We use the Steiner pointcandidates to construct a good initial Steiner tree. The marked guide pointsare consideredinsertable key nodes; they are used in a key-node insertionlocal search to improve the quality of the initial feasiblesolution. Experimental results show that the proposed heuristic is effective. Compared with two state-of-the-art algorithms, our methods improve the solution quality in terms of weight of the Steiner tree by about 2.34% and 5.48% ,respectively.

关 键 词：大规模集成电路 多层布线 布线图 斯坦纳树 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]