超大规模集成电路划分算法研究

论文摘要

超大规模集成电路布图领域的划分问题是一个NP完全问题,一般采用启发式算法解决。目前,超大规模集成电路划分问题已经得到了广泛而深入的研究,出现了许多较为有效的解决算法。在这些算法当中,组迁移算法以其简单有效得到了最广泛的应用。但是随着电路规模的不断增大,研究人员开始更多的利用多级层次划分策略解决该问题。本文首先对已有的电路划分算法进行了介绍,尤其深入分析了基于多级层次划分策略、运用组迁移算法进行电路划分的思想。在此基础上,提出了一种新的多级层次划分算法。该算法首先从电路连接关系中抽象出超图模型,然后对所得超图模型进行多级层次划分。在层次划分时,采用了多次塌缩优化的策略扩大搜索空间,并在恢复优化时运用了贪婪策略,使得算法在避免局部最优的同时,仍然维持了较低的计算时间。对ISPD98测试数据的仿真实验表明,该算法要比二分法和简单的多块多级层次划分法更为有效。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 超大规模集成电路划分算法的研究现状与动态
• 1.3 论文主要研究内容和结构
• 第二章 超大规模集成电路划分算法概述
• 2.1 VLSI 划分的基本概念和问题描述
• 2.1.1 VLSI 划分问题介绍
• 2.1.2 电路划分问题的一般数学模型
• 2.2 VLSI 划分算法的意义
• 2.3 几种图的划分算法介绍
• 2.3.1 组迁移算法
• 2.3.2 多级层次划分算法
• 2.4 本章小结
• 第三章 一种基于多级划分策略的多块划分算法
• 3.1 算法框架
• 3.2 VLSI 电路划分问题的超图模型表示
• 3.3 基于多级划分策略的多块划分算法
• 3.3.1 粗化塌缩算法
• 3.3.2 初始划分算法
• 3.3.3 基于FM 的全局超图多块均分优化
• 3.4 实验结果及分析
• 3.4.1 仿真实验与测试数据
• 3.4.2 实验结果与分析
• 第四章 总结与展望
• 参考文献
• 致谢
• 研究成果