基于冲突移除的冗余孔的插入

论文摘要

由于集成电路的规模越来越小,通孔的失误率也就越来越高。双通孔的插入能够提高芯片的成品率和可靠度,减少由于通孔的故障而造成的电路板的成品率下降,所以这种方法是一个有效的和值得推荐的方法。论文中提出了一种用遗传算法来进行优化的双通孔插入方法,这种方法也可以应用于无网格布局的结构。首先建立一个用于表示通孔和冗余通孔之间的候选关系的无向图,这个无向图也能用于表示违反了设计规则的冗余孔之间的冲突关系。在这个无向图中,如果任何冗余孔之间都不存在着冲突关系,那么这个无向图就是一个二分图,如果是这种情况,冗余孔的插入问题就能通过最大二分匹配算法得以优化解决。否则,为了减小问题的规模,我么要对无向图进行预处理,如果冲突图中的连同分量是一个最大团并且这个连同分量的顶点代表冗余孔,它的边代表了两个冗余孔之间由于违反了设计规则而造成了冲突,我们就把这种连同分量合并成一个顶点(一个冗余孔)。最后,提出一种通过遗传算法来优化冗余孔的移除的方法,从而得到一个没有冲突的二分图,通过最大二分匹配算法来实现双通孔的插入。实验结果表明了这种方法对于实现双通孔的插入是很有效的。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 在布线过程中的双通孔的插入
• 1.2.2 布线后双通孔的插入
• 1.3 本文的贡献
• 1.4 论文结构
• 2 系统开发的相关工具
• 2.1 Linux系统
• 2.1.1 Linux系统的起源
• 2.1.2 Linux系统的特点
• 2.2 C++语言
• 2.2.1 C++和面向对象编程
• 2.2.2 C与C++
• 3 系统开发的相关算法
• 3.1 通孔的简介
• 3.2 无网格布局模型
• 3.3 基本算法
• 3.3.1 算法简介
• 3.3.2 最大流
• 3.3.3 最大二分匹配算法
• 3.3.4 原始算法
• 3.3.5 Hopcroft-Karp算法
• 3.3.6 遗传算法
• 4 冗余孔插入问题的建立
• 4.1 基本理论
• 4.2 问题的建立
• 5 无网格结构的双通孔插入算法
• 5.1 建立候选冗余通孔
• 5.2 图的规划
• 5.2.1 图的建立
• 5.2.2 预处理过程
• 5.3 无网格结构的双通孔的插入
• 5.3.1 基于网格结构的双通孔的插入
• 5.3.2 无网格结构的双通孔插入算法
• 5.4 算法的工作流程
• 6 实验结果
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢