适用于求解VLSI布图规划问题的多目标PSO算法研究

论文摘要

集成电路对经济和社会的发展起极大的推动作用，在提升国家综合实力上具有重要战略意义。布图规划是集成电路物理设计的一个重要过程，对芯片的成本，性能等方面起着决定作用，它通常需要满足多个设计目标且一些子问题已经被证明是NP完全或NP难问题。随着集成电路发展至超大规模及甚大规模集成电路，布图规划的难度也在不断加大，单靠传统手工方法来完成已不可能，必须借助电子设计自动化技术。粒子群优化算法是一种简单有效的群智能算法，具有良好的全局寻优能力。本文针对超大规模集成电路布图规划中的BBL布图问题，以粒子群优化为算法框架，围绕问题中的的编码和多目标优化等进行研究和分析，提出一种求解布图规划多目标优化问题的方法。主要研究内容如下：(1)采用智能算法解决布图规划问题首先需确定一种合适的布图表示方式。针对积木块布图模式和粒子群算法，采用了两种常见的布图表示方式，并相应地对粒子的更新方式进行重新定义，构造了两个离散粒子群优化算法，最后通过实验进行测试和分析，挑选较为合适的一种编码进行后继研究。(2)针对传统布图规划方法的不足和缺陷，以布图面积和互连线长为优化目标，在粒子群优化算法的基础上引入Pareto概念及其他多目标优化策略，提出了一种求解布图规划问题的多目标粒子优化算法。(3)协同进化算法比传统的进化算法更具优越性，通过对协同进化论及其多目标算法的研究和分析，在已有的多目标粒子群优化算法中引入协同进化的思想对其进行进一步改进，实验结果表明改进后的算法具有更好的性能。

论文目录

• 中文摘要
• Abstract
• 第一章 引言
• 1.1 课题研究的背景与意义
• 1.2 VLSI 设计流程与物理设计
• 1.3 VLSI 布图模式
• 1.4 课题研究现状
• 1.5 本文的主要工作
• 1.6 本文的组织结构
• 第二章 粒子群优化算法和多目标优化算法
• 2.1 粒子群优化算法概述
• 2.1.1 PSO 算法模型
• 2.1.2 参数分析
• 2.1.3 算法流程
• 2.2 离散 PSO 优化算法
• 2.2.1 离散二进制 PSO
• 2.2.2 基于交换的离散 PSO
• 2.2.3 Pan 等的离散 PSO
• 2.3 多目标算法概述
• 2.3.1 多目标优化问题的数学模型
• 2.3.2 多目标算法研究状况
• 2.3.3 多目标粒子群算法简介
• 2.4 小结
• 第三章 求解布图规划问题的多目标 PSO 算法
• 3.1 引言
• 3.2 问题描述
• 3.2.1 数据结构
• 3.2.2 布图结构
• 3.3 采用整数序列编码的布图规划算法
• 3.3.1 编码与解码
• 3.3.2 离散 PSO
• 3.3.3 目标函数
• 3.3.4 多目标粒子群算法
• 3.3.5 算法步骤
• 3.3.6 实验结果
• 3.4 采用序列对编码的布图规划算法
• 3.4.1 序列对表示法
• 3.4.2 多目标粒子群算法
• 3.4.3 算法步骤
• 3.4.4 实验结果
• 3.5 小结
• 第四章 求解布图规划问题的协同 MOPSO 算法
• 4.1 引言
• 4.2 协同多目标算法概述
• 4.2.1 协同进化论
• 4.2.2 协同进化算法
• 4.2.3 协同多目标进化算法
• 4.4 协同 MOPSO 算法
• 4.4.1 粒子的更新公式
• 4.4.2 子群协作过程
• 4.4.3 算法步骤
• 4.4.4 实验结果分析
• 4.5 小结
• 结论
• 参考文献
• 致谢
• 个人简历
• 在学期间研究成果及发表的学术论文