布局优化算法模拟退火课件

《布局优化算法模拟退火课件》由会员分享，可在线阅读，更多相关《布局优化算法模拟退火课件（27页珍藏版）》请在装配图网上搜索。

1、模拟集成电路版图自动布局布线技术2010年6月26日版图基本数据结构版图基本数据结构链表结构（Linked List）占用空间小，适合存放静态数据不显式表达空间区域，查找较慢四叉树（Quad Tree）分区管理，查找时间快，适合实图形的查询和编辑不适合推移、压缩等针对空区域的操作角钩链（Corner Stitching）适合推移、压缩和通道生成等操作版图基本数据结构版图基本数据结构自动布局规划问题自动布局规划问题将若干电路模块放置在电路的适当位置上，并满足一定的目标函数和限制条件。目标函数主要包括：芯片面积宽长比线网长度布线拥挤度（Congestion）目标函数可进行归一化加权处理布局中的线长

2、估计布局中的线长估计边界框（Bounding-Box）包含线网内所有引脚（Pin）的最小矩形计算简单快速，但误差较大Steiner最小树（SMT）线长最小，估计精确，但生成复杂，计算量大单树干Steiner树树干位置是所有引脚的X（或者Y）坐标的平均值，然后从所有引脚向树干做垂线兼顾精度和计算量布局中的布线拥挤度问题布局中的布线拥挤度问题布局限制条件布局限制条件限制条件主要有：相邻（Adjacency）对称（Symmetry）边界条件（Boundary）匹配（Matching）更复杂的布局问题预设障碍布局多边形模块布局软模块布局器件匹配（器件匹配（Matching）CMOS器件的random

3、mismatch计算公式：决定匹配质量的因素器件的尺寸两个器件之间的距离周围环境的相似程度均匀分布的位置匹配模式（匹配模式（Interdigitate）匹配模式（匹配模式（Common-Centroid）布局问题实例（部分）布局问题实例（部分）(a)no constraints(c)adjacent blocks(b)boundary blocks(d)L/T shape blocks布局拓扑表示应考虑的因素布局拓扑表示应考虑的因素完备性对每个布局方案都有相应的拓扑表示存在，确保搜索时不会漏掉最优解有效性每个布局方案的拓扑表示应尽量少，避免浪费时间试探多个等价的拓扑结构独立性拓扑表示应独立于模

4、块的尺寸高效性从拓扑表示到布局方案的转换效率高简洁性拓扑表示应尽量占用较少的存储空间布局方案的拓扑表示方法布局方案的拓扑表示方法Slicing结构数据表示方便计算复杂度低解决问题有局限性Non-Slicing结构布局方案表示完整处理特殊问题方便数据结构复杂Slicing结构结构可以用二叉树和波兰表达式表示下图的波兰表达式为：FE+BA+C*+GH*D+*由+、*符号可以得到模块间的拓扑关系，+表示上下，*表示左右Non-Slicing结构结构序列对（Sequence Pair）模型由两组序列表+（左上至右下）和-（左下至右上）确定布局方案搜索空间O(n!2)，转换效率O(n2)Non-Slic

5、ing结构结构O-Tree模型只能表示LB-compact的布局精确的布图规划拓扑结构依赖于模块的形状搜索空间O(n!22n-2/n1.5)，转换效率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/n1.5)，转换效率O(n)Non-

6、Slicing结构结构S=S=（A A，B B，C C）L=L=（0 0，1 1，0 0）T=T=（0 0，0 0，1 1）产生布局方案新解产生布局方案新解以角模块表为例，可以使用的手段包括：交换S列表中任意两个模块的位置旋转S列表中某个模块的方向改变L列表中的某个位置的值（01或者10）改变T列表中的某个位置的值布局优化算法（模拟退火）布局优化算法（模拟退火）Algorithm SIMULATED_ANNEALING begin temp=INIT_TEMP;place=INIT_PLACEMENT;while(temp FINAL_TEMP)do while(inner_loop_crit

7、erion=FALSE)do new_place=PERTURB(place);C=COST(new_place)-COST(place);if(C 0)then place=new_place;else if(RANDOM(0,1)e-C/temp)then place=new_place;temp=SCHEDULE(temp);end;布局优化算法（模拟退火）布局优化算法（模拟退火）来源于冶炼加工中的固体退火原理 可以从局部优化解中解脱出来在有限的时间内只能得到近似最优解求解质量受降温方案（Cooling Schedule）影响版图自动布线版图自动布线实现策略直接区域布线总体布线+详细布线数据结构网格布线无网格布线布线算法迷宫（Maze）算法线探索（Line-Search）算法迷宫算法线探索算法布线中的限制条件布线中的限制条件线网对称线网匹配若干条线网的长度相等满足时序（Timing）要求线网保护（Shielding）与被保护线网平行走线屏蔽外来信号对关键线网的干扰其他布线问题其他布线问题多端线网布线求解多端线网的Steiner树问题电子迁移（Electromigration）问题，线网中每段金属的宽度由通过的具体电流值决定多层布线指定每层的走线方向采用三维网格，并对网格填数方向加权布线顺序和拆线重布并行布线Q&A