基于图论的单元上通道布线算法研究

摘要

当前集成电路产业向深亚微米工艺不断推进，正力图突破45nm甚至15nm大关。现有EDA工具难以应付复杂度呈指数增长的诸多VLSI电路设计难题，也缺乏对深亚微米工艺下一系列新问题的考虑。另一方面，在计算智能领域，各种优化技术日新月异，为解决非NP和NP复杂度的大规模、超大规模问题展示了广阔的前景。在我国21世纪初的“十五计划”里，明确地把软件产业和集成电路产业作为中国高科技的两大重点发展方向。本文正是在这样的背景下，研究通道布线和单元上通道布线在深亚微米工艺下VLSI生产工序中关键环节——物理设计中的应用。 随着VLSI电路的工艺向深亚微米的推进，由于问题规模的急剧增大，电路物理设计中的布线问题(无论是非NP问题、NP完全问题和NP困难问题)，都迫切需要更有效的优化算法解决方案。 同时，由于近年来IC工艺的发展，使得其速度越来越高。由此可见，由IC芯片构成的电子系统是朝着大规模、小体积、高速度的方向飞速发展的，而且发展速度越来越快。如何在缩小电子系统体积的同时，保持并提高系统的速度与性能成为摆在设计者面前的一个重要课题。所以研究在深亚微米工艺下性能驱动的VLSI电路的EDA工具中的应用，无疑是十分具有重要的战略意义。 本文的贡献在于： 1.较深入的研究了基于图论的通道布线算法，并将该算法推广应用于单元上(OTC)通道布线中，对于单元上布线区域的特殊性，定义了新的线网约束关系，找到了新的解决算法。 2.提出减少信号反射的OTC通道布线算法，该算法将菊链法布线技术用于VLSI性能驱动的布线问题，该算法可以有效地减少信号反射，提高信号质量。 上述算法均在PC机上编程实现，并应用于一些经典的Benchmark布线例子，实验结果是令人满意的。

目录

文摘

英文文摘

独创性声明及关于论文使用授权的说明

第一章绪论

第二章VLSI电路物理设计的算法介绍

第三章布线问题的研究现状及求解的各种算法

第四章基于图论的单元上(OTC)通道布线算法

第五章减少信号反射的OTC通道布线算法

第六章总结和展望

致谢

参考文献

个人简历及在学期间发表的学术论文