%0 Journal Article
%T 一种多层绕障直角斯坦纳最小树启发式算法
%A 叶东毅
%A 张浩
%A 郭文忠
%J 中山大学学报（自然科学版）
%D 2016
%X 摘要 直角斯坦纳树问题是大规模集成电路物理设计中重要的基本模型.现代集成电路设计需要同时考虑障碍和多层布线等约束条件.通过构造布线图，提出一种多层绕障直角斯坦纳最小树启发式算法.为了避开障碍和连通各布线层之间的引脚，本文引入了三种候选通孔位置.在同一布线层内，通过扩展满直角斯坦纳树网格来构造单层布线图，再使用候选通孔互联成多层布线图.在多层布线图中，引入候选斯坦纳点来构造斯坦纳树，并以标记的引导点执行局部搜索策略来提高求解质量.实验结果表明，本文算法能够有效求解多层绕障直角斯坦纳最小树问题.本文算法所得总布线权重与最新的两种算法相比，改进率可达2.34%和5.48%
%K 大规模集成电路
%K 多层布线
%K 布线图
%K 斯坦纳树
%U http://xwxt.sict.ac.cn/CN/abstract/abstract3547.shtml