改进的O-TREE表示法在求解带总线约束的VLSI电路BBL布局问题中的应用

论文摘要

随着系统芯片（SOC）设计方法和知识产权（IP）模块技术在集成电路设计中的不断发展和应用,布图规划（Floorplanning）和布局日渐成为超大规模集成（VLSI）电路与系统物理设计的关键环节。布图规划的主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及模块的引线端位置,使得芯片的面积以及模块之间的互连线总长最小。由于布图规划设计是芯片物理设计的第一个步骤,其结果将影响芯片的最终性能。人们一直在寻求有效的优化算法以应用于布局问题,通过正确的策略我们可以很好地解决布局问题,同时减少算法的复杂度,缩短整个实现的时间。本文正是在这样的背景下,基于四川省科技厅基金项目,面对VLSI 电路物理设计中的关键环节,针对BBL 模式下的带约束布局问题,展开了一些研究工作。本文主要研究如何来求解在超大规模集成电路布局中,具有预定义坐标结群约束模块的布局问题（简称PCA 问题）,研究途径是采用O-TREE 的编码表示方法和模拟退火的算法。目前,存在一些成功的算法来解决PCA 问题。然而,它们的算法有些很复杂,有些很耗时。在这篇文章里,我们提了一种新的布局算法来解决这个问题,该算法是基于O-Tree 结构,旨在减少总的运行时间且简便。通过对MCNC 的基准例子ami33 和ami49 上的仿真实验表明:与参考文献[32]中提出方法所得的结果相比,我们的新算法是可行的并且很有效。它不仅使芯片面积利用率得到改善,而且节约了一半以上的设计计算时间开销。本文还考虑到算法是否受模块规模大小的影响,为此我们进行了电路模块扩张的实验验证。针对ami33 基准例,实验模块被扩展到了65 个,实验结果表明我们的算法是很有效、鲁棒的,并且运行很快。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 IC 及EDA 技术的发展概况
• 1.1.1 前言
• 1.1.2 EDA 技术的发展
• 1.1.3 ESDA 技术的基本特征
• 1.2 超大规模集成电路（VLSI）设计流程
• 1.3 物理设计过程
• 1.4 VLSI 物理设计的布图模式
• 1.5 VLSI 布局布线的研究现状和发展态势
• 1.6 本论文完成的工作和内容的组织
• 第二章 VLSI 物理设计的算法介绍
• 2.1 图论算法
• 2.1.1 图搜索算法
• 2.1.2 最短路径
• 2.1.3 最小生成树
• 2.1.4 斯坦纳（Steiner）树算法
• 2.2 计算智能优化算法
• 2.2.1 模拟退火（SA）
• 2.2.2 遗传算法（GA）
• 2.2.3 神经网络算法（NNA）
• 2.2.4 人工蚁群算法（ACS）
• 2.2.5 禁忌搜索算法（TS）
• 2.3 计算智能算法在集成电路布局中的应用
• 2.3.1 初始布局
• 2.3.2 迭代改善布局
• 2.3.3 布局的目标函数
• 2.4 小结
• 第三章 VLSI 布局表示方法的评述
• 3.1 引言
• 3.2 Non-slicing 布局表示方法研究进展
• 3.2.1 序列对SP（Sequence Pair）
• 3.2.2 传递闭包图TCG（Transitive Closure Graph）
• 3.2.3 变形网格BSG（Bounded Sliceline grid）
• 3.2.4 O-Tree 表示法和B*-Tree 表示法
• 3.2.5 角模块CBL（Corner-Block-List）及其它Mosaic 布局表示法
• 3.2.6 TBT（Twin Binary Tree）布局表示法
• 3.2.7 S-Sequence（Segment-State Sequence）布局表示法
• 3.2.8 三维（3D）的布局表示法
• 3.3 布局表示方法的总结
• 第四章 改进的O-TREE 在有约束的VLSI 布局中的应用
• 4.1 引言
• 4.1.1 三种总线的逻辑结构图及描述
• 4.1.2 三种总线的分析和对比
• 4.1.3 小结
• 4.2 有PCA 约束的布局问题描述
• 4.3 改进O-Tree 编码表示方法
• 4.3.1 O-Tree 表示法
• 4.3.2 约束图（Constraint Graph）和容许布局（Admissible Placement）
• 4.3.3 O-Tree 布局
• 4.3.4 改进的O-Tree 表示
• 4.4 算法描述
• 4.4.1 目标函数
• 4.4.2 算法的设计和伪码描述
• 4.4.3 应用模拟退火算法迭代改善布局结果
• 4.5 结论
• 第五章 总结与展望
• 5.1 总结
• 5.2 进一步的工作与展望
• 参考文献
• 致谢
• 个人简历及在学期间发表的学术论文和工业实践情况