文档介绍：模拟集成电路版图自动布局布线技术
2010年6月26日
版图基本数据结构
链表结构（Linked List）
占用空间小，适合存放静态数据
不显式表达空间区域，查找较慢
四叉树（Quad Tree）
分区管理，查找时间快，适合实模拟集成电路版图自动布局布线技术
2010年6月26日
版图基本数据结构
链表结构（Linked List）
占用空间小，适合存放静态数据
不显式表达空间区域，查找较慢
四叉树（Quad Tree）
分区管理，查找时间快，适合实图形的查询和编辑
不适合推移、压缩等针对空区域的操作
角钩链（Corner Stitching）
适合推移、压缩和通道生成等操作
版图基本数据结构
自动布局规划问题
将若干电路模块放置在电路的适当位置上，并满足一定的目标函数和限制条件。
目标函数主要包括：
芯片面积
宽长比
线网长度
布线拥挤度（Congestion）
目标函数可进行归一化加权处理
布局中的线长估计
边界框（Bounding-Box）
包含线网内所有引脚（Pin）的最小矩形
计算简单快速，但误差较大
Steiner最小树（SMT）
线长最小，估计精确，但生成复杂，计算量大
单树干Steiner树
树干位置是所有引脚的X（或者Y）坐标的平均值，然后从所有引脚向树干做垂线
兼顾精度和计算量
布局中的布线拥挤度问题
布局限制条件
限制条件主要有：
相邻（Adjacency）
对称（Symmetry）
边界条件（Boundary）
匹配（Matching）
更复杂的布局问题
预设障碍布局
多边形模块布局
软模块布局
器件匹配（Matching）
CMOS器件的random mismatch计算公式：
决定匹配质量的因素
器件的尺寸
两个器件之间的距离
周围环境的相似程度
均匀分布的位置
匹配模式（Interdigitate）
匹配模式（Common-Centroid）
布局问题实例（部分）
(a) no constraints
(c) adjacent blocks
(b) boundary blocks
(d) L/T shape blocks
布局拓扑表示应考虑的因素
完备性–对每个布局方案都有相应的拓扑表示存在，确保搜索时不会漏掉最优解
有效性–每个布局方案的拓扑表示应尽量少，避免浪费时间试探多个等价的拓扑结构
独立性–拓扑表示应独立于模块的尺寸
高效性–从拓扑表示到布局方案的转换效率高
简洁性–拓扑表示应尽量占用较少的存储空间
布局方案的拓扑表示方法
Slicing结构
数据表示方便
计算复杂度低
解决问题有局限性
Non-Slicing结构
布局方案表示完整
处理特殊问题方便
数据结构复杂
Slicing结构
可以用二叉树和波兰表达式表示
下图的波兰表达式为：FE+BA+C*+GH*D+*
由+、*符号可以得到模块间的拓扑关系，+表示上下，*表示左右
Non-Slicing结构
序列对（Sequence Pair）模型
由两组序列表+（左上至右下）和-（左下至右上）确定布局方案
搜索空间O(n!2) ，转换效率O(n2)
Non-Slicing结构
O-Tree模型
只能表示LB-compact的布局
精确的布图规划拓扑结构依赖于模块的形状
搜索空间O(n!22n-2/) ，转换效率O(n)
Non-Slicing结构
角模块表（Corner Block List）模型
由三个数据表构成
S：名字列表，记录模块名字和几何信息
L：方向列表，以0/1表示相对前一个模块，当前模块的相对位置，0表示在上方，左边对齐；1表示在右方，底边对齐。
T：修正列表，改变L List中所相对的模块，以数字（不小于0）表示当前模块位置的修正次数。L值为0时，向左修正；L值为1时，向下修正。
搜索空间O(n!23n-3/) ，转换效率O(n)
Non-Slicing结构
S =（A，B，C）
L =（0，1，0）
T =（0，0，1）
产生布局方案新解
以角模块表为例，可以使用的手段包括：
交换S列表中任意两个模块的位置
旋转S列表中某个模块的方向
改变L列表中的某个位置的值（0→1或者1→0）
改变T列表中的某个位置的值
布局优化算法（模拟退火）
Algorithm SIMULATED_ANNEALING
begin
temp = INIT_TEMP;
place = INIT_PLACEMENT;
while (temp > FINAL_TEMP) do
while (inner_loop_criterion = FALSE) do
n