用于VLSI布局的计算智能方法研究

作为电子信息产业发展的核心和基础，集成电路技术正迅速地向着更高集成度、超小型化、高性能、高可靠性的方向发展，在VLSI设计流程中，物理设计是既关键又复杂的一步，而布局又是物理设计中最重要的一步，布局的诸多问题都是NP完全问题，需要启发式算法来求解。随着VLSI集成度的迅猛提高，寻求有效的优化算法应用于布局问题，以提高布局质量和速度已成为当务之急。 本文主要研究用于解决VLSI布局问题的计算智能方法，在总结概括了当前主要的布局优化算法的基础上，引入了禁忌搜索算法和模糊禁忌搜索算法，并用于求解VLSI布局问题。 禁忌搜索算法是一种可广泛用于各种优化问题的思想框架。许多文献也都证明它在时间和性能上扰于其他一些算法，在诸多组合优化领域中显示出了强大的寻优能力，并以其较高的求解质量和效率得到人们越来越多的青睐。本文将其引入，用以解决VLSI门阵列布局问题，与遗传算法比较，在求解质量和速度上都取得了优于遗传算法的结果。 然而，禁忌搜索算法的求解性能严重地依赖于算法的一些参数，它们又大都在算法运行中起着指导算法前进的作用。这些参数都是凭经验选取的，而且这些参数在算法运行过程中始终保持不变，这样的策略在很多情况下都不是很有效。因此，我们发展了一种新的算法——模糊禁忌搜索，它引入一个模糊系统来控制禁忌搜索算法的参数取值。在针对VLSI门阵列布局问题的应用中，用当前解的优劣程度和非优化迭代的次数来控制邻域的产生，计算机仿真结果表明该算法具有很好的寻优性能。