非曼哈顿结构通道布线算法研究

论文摘要

本文论述了VLSI 物理设计中两种基于非曼哈顿结构的通道布线优化算法研究和实验结果及分析。文中分析了在当前集成电路产业向深亚微米工艺推进,集成度和电路复杂度不断提高,工艺日益进步的条件下,采用非曼哈顿模型进行布线时,可以明显减小芯片面积,缩短布线长度,减小串扰等方面的必要性和可行性,重点研究了以下两个算法: 1、在分析了基于冒泡排序的非曼哈顿结构通道布线中,由排序结果到布线段的映射特点的基础上,提出了二分改进优化算法,通过允许在同一排序步骤中采用不同的交换方向,进一步减小了通道高度（轨道数）,减小了总线长。2、提出了一种采用MD（曼哈顿-对角线）模型的非曼哈顿结构通道布线贪婪算法。算法“贪婪”的使用最少的布线轨道,并且通过启发式拓扑排序最小化轨道数和线长,该算法同时适用于规则与不规则通道,还可以不经修改的用于L 型通道布线。上述算法均在PC 机上编程实现,并应用于一些经典的Benchmark 布线例子,实验结果是令人满意的。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 发展 EDA 的战略意义
• 1.1.1 超大规模集成电路（VLSI）是人类社会进入信息时代的重要硬件基础
• 1.1.2 EDA 技术和制造工艺支撑着VLSI 的发展
• 1.1.3 物理设计是超大规模集成电路 EDA 中重要的一环
• 1.1.4 通道布线是 VLSI 物理设计中重要和基本的一环
• 1.1.5 EDA 发展的迫切需要
• 1.2 物理设计的定义、流程及主要模式和基本问题
• 1.2.1 VLSI 电路设计流程
• 1.2.2 物理设计的定义
• 1.2.3 物理设计的流程
• 1.2.4 目前物理设计的主要模式
• 1.2.4 目前物理设计的基本问题
• 1.4 深亚微米工艺与 EDA 技术的发展趋势
• 1.4.1 布局布线仍然是 VLSI 设计自动化中的重要问题
• 1.4.2 非曼哈顿结构的迅速发展
• 1.5 论文完成的工作和内容安排
• 第二章 VLSI 布图算法及通道布线算法介绍
• 2.1 VLSI 布图算法
• 2.1.1 图论算法
• 2.2.2 计算几何算法
• 2.2.3 基于运筹学的算法
• 2.2.4 计算智能优化算法
• 2.2 通道布线算法介绍
• 2.2.1 通道布线的基本概念
• 2.2.2 通道布线中的λ-geometry 理论
• 2.2.4 通道布线的算法
• 第三章 基于冒泡排序的非曼哈顿通道布线的二分改进优化算法
• 3.1 基于冒泡排序的非曼哈顿通道布线算法介绍
• 3.1.1 理论基础
• 3.1.2 基于冒泡排序的非曼哈顿通道布线算法
• 3.2 冒泡排序法的优化
• 3.3 基于冒泡排序的非曼哈顿通道布线的二分改进优化算法
• 3.3.1 预定义
• 3.3.2 优化的冒泡排序算法
• 3.3.3 优化冒泡排序算法应用于通道布线的二分改进算法
• 3.3.4 算法的时间与空间复杂度
• 3.4 二分改进优化算法布线的的实现
• 3.4.1 二分改进优化算法的实现
• 3.4.1 基于冒泡排序的通道布线实用性讨论
• 3.5 本章小结
• 第四章 非曼哈顿结构不规则通道布线的贪婪算法
• 4.1 引言
• 4.2 预备知识
• 4.2.1 通道定义
• 4.2.2 曼哈顿-对角线（Manhattan-Diagonal,MD）模型
• 4.2.3 通道高度问题
• 4.2.4 布线顺序与拓扑排序（Topologic Sort）
• 4.3 基于曼哈顿-对角线模型的通道布线贪婪算法
• 4.3.1 贪婪算法
• 4.3.2 基于启发式拓扑排序的通孔、线长最小化算法
• 4.3.3 不规则通道布线
• 4.3.4 算法的时间与空间复杂度
• 4.4 实验结果与比较
• 4.5 用不规则通道布线解决 L 型通道布线问题
• 4.4.1 L 型通道与开关盒的必要性
• 4.3.1 L 型通道的不规则通道布线
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 个人简历及在学期间发表的学术论文情况