基于遗传算法与模拟退火的VLSI布局算法

论文摘要

随着超大规模集成电路(VLSI)复杂度的急剧增加,人们对其中的模块布局问题提出了更高的要求。但是人工的进行物理设计已经远远的不能满足该问题的要求,因此自动布局方法在计算机辅助设计(CAD)中的地位显的更加重要。VLSI模块布局问题是一个NP完全问题,一般采用启发式算法解决。目前,随着对超大规模集成电路布局算法更加广泛和深入的研究,人们提出了许多较为有效的布局算法,如遗传算法、模拟退火算法等,但是它们的布局质量还不太令人满意,尤其是在VLSI模块布局问题中存在边界约束、预置模块或软模块等限制条件的时候,布局结果的“面积”或者“长宽比”较差。模块布局问题仍然是VLSI设计中最具挑战性的问题之一。本文基于传统的模拟退火和遗传算法,提出了一种新的VLSI模块布局算法。新算法采用序列对(SP)编码方式,该编码方式已被证明可以成功的应用在解决VLSI模块布局问题的算法中。为了验证新算法的有效性,程序采用MCNC的标准数据集[12]和两个随机生成的模块集合作为实验数据。经过多次的测试,实验结果表明本文的算法在布局质量方面有很大的优势。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 问题提出的背景
• 1.2 研究意义与现状
• 1.3 布局问题简述
• 1.4 本文的主要内容与结构
• 第二章 超大规模集成电路布局问题概述
• 2.1 布局问题的编码
• 2.1.1 不可二分结构
• 2.1.2 序列对编码方式
• 2.2 布局问题的解码
• 2.2.1 传统的LCS算法
• 2.2.2 改进的LCS算法
• 2.3 特殊条件下的模块布局
• 2.3.1 带有软模块的约束情况
• 2.3.2 带有预置模块的约束情况
• 2.3.3 带有边界约束模块的约束情况
• 第三章 基于模拟退火和遗传算法的布局算法
• 3.1 多目标优化
• 3.1.1 多目标优化的定义
• 3.1.2 多目标优化的难点和解决方法
• 3.2 模拟退火算法
• 3.2.1 模拟退火算法简述
• 3.2.2 模拟退火算法的详细设计
• 3.2.3 模拟退火算法的要点与改进
• 3.3 遗传算法
• 3.3.1 遗传算法的基本概念
• 3.3.2 遗传算法的详细设计
• 3.3.3 遗传算法的改进策略
• 3.4 遗传算法和模拟退火相结合的布局算法
• 3.5 实验结果与分析
• 3.5.1 实验数据
• 3.5.2 实验结果与分析
• 3.5.3 实验总结
• 第四章 总结和展望
• 致谢
• 参考文献
• 研究成果