一种含浮动端点的斯坦纳树的构造算法

• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: VLSI 布图 多层布线 斯坦纳树
• 年，卷（期）: 1998,（6）
• 页码范围: 80-86
• 页数: 7页
• 分类号: TP13
• 语种: 中文

摘要

在集成电路的自动布图技术中,在完成布局过程,即各模块(或子电路单元)的拓扑位置确定以后,布线需要完成各电路模块之间的连接.斯坦纳树(STEINERTREE)的构造问题可以应用于总体布线;如果考虑已有单元或连线的障碍,它也可以应用于详细布线.根据已有的研究,构造斯坦纳树的问题,是一个NP完全问题［4］.随着集成电路工艺的发展,人们越来越多地考虑多层布线的问题.该文从多层布线出发,利用在单元或模块内部已有的连线所提供的可用通孔集合作为布线资源,引入浮动端点的概念,提出了一种处理浮动端点的斯坦纳树构造算法AFLOST.该算法能先后生成含浮动端点的最小生成树和含浮动端点的斯坦纳树.根据给定的算法,文中给出了相应的图例来演示构造过程.