测试芯片设计中布线算法的研究与实现

摘要

虽然超大规模集成电路产业在摩尔定律的指引下已经步入纳米时代甚至非常接近摩尔定律的尽头了，但是它仍然在快速发展中。工艺节点的不断减小导致复杂度随之不断攀升，设计规则也越来越复杂，这些前所未有的挑战都需要我们有更高效的测试芯片来保证它们的成品率。目前的测试芯片规模正在迅速扩大，并且随着工艺节点达到16nm甚至更低时，许多新的工艺缺陷随之产生，需求的测试结构的数目越来越多，庞大数目的测试结构的布线问题也就越来越复杂。
　　本文结合当前测试芯片设计技术的不断发展，通过对最近的VLSI芯片布线技术的分析，提出了传统测试芯片布线流程改进后的新的布线新流程，这种新的布线流程中所具有的创新点在于:
　　1)对具体的点对间布线算法进行了新的探索，提出了新的点对间布线算法。通过提出“自由节点”和“节点边界”等新的概念，该算法通过节点边界的扩张来实现自由节点的转移，从而快速地从源节点向目标节点扩散，大大提高了搜索效率。该算法既克服了传统迷宫算法基于遍历网格的复杂度高的缺点，也无需在庞大的网格中搜索障碍构造子图。理论分析和多个实例验证的结果表明，该算法可以很好地解决点对间的布线问题且复杂度较低。
　　2)将测试芯片中原有的单一算法的布线流程调整为多步骤多算法的综合布线流程，把测试芯片布线问题拆分为全局布线和详细布线两个步骤，在每一步中使用模式布线、单调布线和新提出的点对间布线算法等多种技术进行布线，将布线时间缩短到原来的15％-25％，对缩短测试芯片的整体设计周期起到了一定的作用。该布线流程的可靠性和实用性在几家集成电路制造厂商的测试芯片实例中得到了验证。

目录

声明

摘要

第1章 绪论

1．1 集成电路发展概述

1．2 成品率问题

1．3 测试芯片概述

1．4 物理设计

1．4．1 物理设计概述

1．4．2 物理设计中的布线问题

1．5 研究内容

1．6 章节安排

第2章 超大规模集成电路布线算法研究

2．1 超大规模集成电路布线问题描述

2．2 全局布线

2．2．1 全局布线概述

2．2．2 全局布线问题建模

2．2．3 全局布线算法分类

2．3 详细布线

2．4 本章小结

第3章 二端线网的布线新算法研究

3．1 算法提出的背景

3．2 算法的基本概念与定义

3．2．1 自由节点的边界

3．2．2 闭合边、半开放边和开放边

3．2．3 自由节点

3．3 算法的基本思想、实现与分析

3．3．1 算法的基本思想

3．3．2 算法的实现

3．3．3 算法的复杂度分析

3．4 实验结果与分析

3．5 本章小结

第4章 测试芯片设计中的布线算法研究

4．1 测试芯片的布线及遇到的问题

4．2 新的测试芯片布线流程

4．3 测试芯片布线流程中的具体布线算法

4．3．1 模式布线算法

4．3．2 单调布线算法

4．3．3 A*布线算法

4．4 测试芯片布线流程中的几种优化技术

4．4．1 将多端线网拆分成二端线网

4．4．2 拆线重布(Rip-up and Re-route)

4．4．3 局部调整与可调线宽

4．5 实验结果与分析

4．6 本章小结

第5章 结束语

参考文献

致谢