BBL布局结构及算法研究

摘要

作为电子信息产业发展的核心和基础，集成电路技术正迅速向着更高集成度，超小型化，高性能、高可靠性的方向发展。随着系统芯片(SOC)设计方法和知识产权(IP)模块技术在集成电路设计中的不断发展和应用，布图规划和布局日渐成为超大规模集成(VLSI)电路与系统物理设计的关键环节。布图规划和布局的主要目标是在满足用户约束条件的前提下确定芯片上模块的最佳形状、位置以及模块的引线端位置，使得芯片的面积以及模块之间的互连线总长最小。由于布图规划和布局是芯片物理设计的第一个重要步骤，其结果将影响芯片的最终性能。 在VLSI设计流程中，物理设计是既关键又复杂的一步，而布局又是物理设计中最重要的一步，布局的诸多问题都是NP完全问题，需要启发式算法来求解。随着VLSI集成度的迅猛提高，寻求有效的优化算法应用于布局问题，以提高布局质量和速度已成为当务之急；同时如何高效地表示布局结构，从而提高布局质量成为物理设计中的一个国际研究热点。本文正是在这样的背景下，对VLSI物理设计中的关键环节——布局，展开了一些研究工作。 本文概括地介绍了布局结构表示研究的进展。针对不可二划分的BBL布局问题，近年来国内外涌现出如：CBL、BSG、SP、O-tree等优秀的布局结构表示方法，但它们在解空间的大小、编码的费用、编码与布局之间的转换时间等方面各有差异。 本文提出了一种求解VLSI布局问题的启发式算法。该算法通过设计模块的优先顺序进行合理的布局，再辅助于边界矩形来减少边界浪费，对于模块布局放置的多个可能位置进行比较，并将其放置在优先度最高的适当区域。同时本文阐述了一种布局表示方法，在这种表示方法中尽量先用更受限制的资源，而尽量后用“一般”的资源，一般有更多机会满足匹配来解决问题。

目录

文摘

英文文摘

论文说明：图目录，表目录

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

第一章绪论

1.1 VLSI(超大规模集成电路)设计流程

1.2物理设计过程

1.3 VLSI的布图模式

1.3.1全定制模式

1.3.2半定制设计模式

1.4本论文完成的工作和内容组织

第二章VLSI布局中的基本问题

2.1布局问题定义

2.2布局问题的求解特性及原则

2.2.1布局问题的求解特性

2.2.2布局问题求解的原则

2.3初始布局

2.3.1布局单元的安置

2.3.2布局单元的选择

2.3.3小结

2.4迭代改善布局

2.4.1改善布局的目标函数

2.4.2基于对交换的迭代改善

2.4.3基于数学规划方法的的迭代改善

2.4.4 BBL模式下的布局改善

2.4.5小结

2.5总结

第三章VLSI布局问题的启发式算法

3.1布局对象

3.1.1布局空间

3.1.2布局物体

3.2布局约束

3.2.1目标约束

3.2.2模式约束

3.2.3几何约束

3.2.4位置约束

3.3布局问题的启发式算法规则

3.3.1可行域

3.3.2布局策略

3.3.3布局算法的定序规则

3.3.4布局算法的定位规则

3.4总结

第四章BBL的布局表示方法的评述

4.1变形网格(Bounded-Sliceline Grid，简称BSG)表示法

4.1.1变形网格结构描述

4.1.2 BSG表示法特点

4.2序列对(Sequence Pair，简称SP)表示法

4.2.1有序列对的基本定理

4.2.2序列对表示法布局

4.2.3序列对表示法特点

4.3传递闭包图(Transitive Closure Graph，TCG)表示法

4.3.1 TCG表示法

4.3.2 TCG表示法特点

4.4角模块序列(Corner Block List，CBL)表示法

4.4.1角模块序列CBL

4.4.2角模块序列表示法特点

4.4.3扩展角模块序列ECBL(Extended Corncr Block Lists)

4.5角序(Corner Sequence)表示法

4.5.1基本概念

4.5.2角序表示法

4.5.3角序表示法特点

4.6 O-tree表示法

4.6.1约束图(Constraint Graph)和容许布局(Admissible Placement)

4.6.2 O-tree表示法

4.6.3 O-tree布局

4.6.4 O-tree表示法特点

4.7 B*-tree表示法

4.7.1 B*-tree表示法

4.7.2 B*-tree表示法特点

4.8总结

第五章一种改进的VLSI布局算法

5.1引言

5.2基于BBL布局的启发式算法

5.2.1最优性原理

5.2.2基于目标的布局启发式算法

5.3相关问题描述

5.4具体算法描述分析

5.4.1布局安置的位置

5.4.2布局结构表示

5.4.3算法详细步骤

5.5实验结果

5.5.1测试1

5.5.2测试2

5.6结论

第六章总结与展望

6.1总结

6.2进一步的工作与展望

致谢

参考文献

个人简历及攻读硕士学位期间的研究成果