论文部分内容阅读
当今信息时代，作为电子信息技术发展的核心和基础，集成电路得到了迅猛的发展，这除了由于半导体工艺技术、设备、原材料等方面的不断改进之外，计算机辅助设计技术的采用也是一个重要原因。然而，随着半导体制造工艺的特征尺寸越来越小，芯片的集成度越来越大，电路的工作频率越来越高，布图工艺越来越复杂，这些发展都对集成电路计算机辅助设计技术提出了新的要求。布局作为集成电路版图设计中一个基本而且非常重要的环节，也面临着严峻的挑战，在大规模(上百万门的单元需要布局)和复杂的设计约束(时延、噪声、功耗、拥挤度等)条件下，如何获得高质量的布局结果同时花费较少的布局时间非常关键。本文正是围绕这些问题展开计算机辅助设计领域内的超大规模集成电路布局算法研究工作的，通过改进现有的方法以及提出新的布局算法，尝试更好地解决当前和未来集成电路设计中的一些问题。
首先介绍了本文的研究对象——标准单元设计模式和基本的布局理论，然后对传统的以线网总长为优化目标的基本布局算法进行了分类分析。在此基础上，提出了一个基于改进等分节点法的启发式迭代优化布局算法，该算法对原有的等分节点法进行了改进，使得单元的目标位置在更广的范围内得到搜寻，从而提高了迭代法的优化质量，而且通过使用启发式策略使迭代优化跳出局部最优，设定合理的局部寻优次数来有效地终止布局优化，并采用记忆装置记录最优布局结果，使整个优化布局过程在没有花费过多时间的情况下，得到了较充分的迭代优化。实验表明，与接近全局最优的()Wolf7.0布局算法相比，该算法能够获得更好的布局质量。
针对超大规模集成电路线长优化布局中布局质量和花费时间的严峻挑战，讨论了面向高复杂度、大规模问题的有效解决策略——分级设计方法，分析了基于分级设计的各种超大规模集成电路线长优化布局算法。在此基础上，提出了一个基于划分的迭代优化布局算法，该算法采用分级设计将大规模的布局问题分拆，借鉴好的递归划分方法将电路分解，采用和改进结群、终端传递等技术提高了划分质量，并且结合本文提出的启发式迭代优化方法在划分所得的各个子电路内进行并行布局优化，在保证布局质量的同时提高了布局速度。实验表明，与当前流行的FengShui布局工具相比，该算法在花费稍长一点的时间内获得了更好的布局质量。
时序约束作为保证电路正常工作性能的一个重要因素，本文讨论了以路径时延为优化目标的布局算法。首先介绍了有关时序问题的基本知识，分析了互连线时延的估算模型，并对当前的各种时延驱动布局算法进行了分类分析。在此基础上，提出了一个时延驱动布局算法，该算法基于对电路时延图的拓扑结构分析，将优化路径时延的问题转换成优化路径上单元位置的问题，通过建立优化单元位置的队列链表，采用一种新的等分节点法寻找路径上单元的目标位置，使得关键路径的时延得到了有效地减小，路径时延的分布更加合理。在优化路径时延的同时还结合了优化线长的布局算法，在获得好的路径时延优化效果的同时，能够尽量保留原有已取得的好的线长优化效果，使两种布局优化目标能够有机地结合。
在深亚微米及更先进的工艺条件下，芯片的设计密度问题变得严峻起来，它会导致对布线资源需求的大幅度增加，当芯片某些区域内的布线资源无法满足实际的走线需要时，就会迫使线网绕道而行从而恶化设计性能，甚至无法实现100﹪布通率，造成布线拥挤，因此本文对以布线密度为优化目标的拥挤度驱动布局算法进行了研究。首先介绍了布局阶段使用的布线密度分析方法和常见的布线密度估计模型，在对现有的各种拥挤度驱动布局算法分析的基础上，提出了一个用于布局后处理的拥挤度驱动布局算法，该算法对原有的线网边框布线估计模型进行了改进，在保留估算速度快，易于编程实现等优点的同时，提高了分析布线密度的精度；在优化布线拥挤度时，提出以线网为中心，通过逐步扩大或者缩小布线拥挤区域内线网边框尺寸的方法，最终达到降低布线拥挤度的目的。实验结果显示，电路的布线溢出总量和布线溢出峰值都明显减小，电路的布线拥挤情况得到了明显的缓解。
最后，将本文布局算法的研究成果进行了软件实现，开发了具有自主知识产权的布局自动设计工具。论文首先介绍了布局程序系统的结构框架，然后针对系统中各个软件模块分别进行了解释和说明，并给出了用户界面和实际电路布局结果的显示。该布局工具既可以与工业界其它布图工具进行无障碍衔接，实现混合运用，也可以用于学术研究，具有很好的可扩展性。