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

摘要

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

目录

文摘

英文文摘

独创性声明及关于论文使用授权的说明

第一章引言

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)和容许布局(AdmissiblePlacement)

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进一步的工作与展望

参考文献

致谢

个人简历及在学期间发表的学术论文和工业实践情况