超大规模集成电路布线中的图论问题研究
| 摘要 | 第5-6页 |
| Abstract | 第6页 |
| 引言 | 第12-15页 |
| 1 绪论 | 第15-25页 |
| 1.1 VLSI历史进展 | 第15页 |
| 1.2 VLSI设计流程 | 第15-20页 |
| 1.3 物理设计 | 第20-22页 |
| 1.4 物理设计优化 | 第22-23页 |
| 1.5 本论文内容简介 | 第23-25页 |
| 2 详细布线算法分析 | 第25-32页 |
| 2.1 引言 | 第25-26页 |
| 2.2 通道布线问题描述 | 第26-32页 |
| 2.2.1 物理设计问题的数学描述 | 第26-27页 |
| 2.2.2 电路划分问题 | 第27-29页 |
| 2.2.3 VLSI布线的数学表示 | 第29-32页 |
| 3 给定水平约束图为路的通道布线 | 第32-44页 |
| 3.1 引言 | 第32页 |
| 3.2 详细布线问题描述 | 第32-35页 |
| 3.2.1 物理设计问题的图论描述 | 第32-33页 |
| 3.2.2 详细布线问题的图论描述 | 第33-35页 |
| 3.3 详细布线算法分析 | 第35-38页 |
| 3.3.1 单行布线算法分析 | 第35-36页 |
| 3.3.2 通道布线 | 第36-38页 |
| 3.4 水平约束图为路的通道布线 | 第38-44页 |
| 3.4.1 算法设计 | 第39-42页 |
| 3.4.2 算法复杂性分析 | 第42页 |
| 3.4.3 算法结果比较 | 第42-44页 |
| 4 给定水平约束图为星图的通道布线 | 第44-50页 |
| 4.1 通道布线介绍 | 第44-46页 |
| 4.2 通道布线面临的挑战 | 第46-47页 |
| 4.3 给定水平约束图为星图的布线结构分析 | 第47-50页 |
| 4.3.1 算法设计 | 第47-48页 |
| 4.3.2 运行时间分析 | 第48-49页 |
| 4.3.3 上界 | 第49-50页 |
| 结论 | 第50-51页 |
| 参考文献 | 第51-55页 |
| 致谢 | 第55-56页 |
| 作者简介及读研期间主要科研成果 | 第56页 |
