VLSI布局结构表示及角模块布局法

《VLSI布局结构表示及角模块布局法》由会员分享，可在线阅读，更多相关《VLSI布局结构表示及角模块布局法（57页珍藏版）》请在金锄头文库上搜索。

1、VLSI布局结构表示及基于热约束的角模块布局法,VLSI 布局结构表示研究进展 徐 宁 洪先龙 董社勤 (清华大学计算机科学与技术系 北京 100084),热约束的BBL 布局算法研究,徐 宁 洪先龙 陈 松 董社勤 ( 清华大学计算机科学与技术系 北京 100084),一、VLSI 布局结构表示研究进展 二、角模块布局法 三、 热约束的BBL布局算法研究,目 录,一、VLSI 布局结构表示研究进展 二、角模块布局法 三、 热约束的BBL布局算法研究,目 录,一、VLSI 布局结构,在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中,布局结果的好坏直接影响整个布图设计。,布图设计过

2、程包括划分、布局、布线、优化等。,A,B,C,例1,FPGA,电路,模块划分,A1,B2,C2,B1,C1,A2,FPGA,模块划分,A2,B2,C2,A1,B1,C1,FPGA,布局,A2,B2,C2,A1,B1,C1,FPGA,布局面积,A2,B2,C2,A1,B1,C1,FPGA,问题：,怎样描述这个布局的结果？ 即：用怎样的数据结构和算法来记录和 描述该种布局的结果，布局速度比较快， 布局过程耗费的存储空间比较小。,布局的问题和目标,A2,B2,C2,A1,B1,C1,FPGA,问题：,用怎样的数据结构和算法来记录和 描述该种布局的结果？ 数组，矩阵，二叉树， B*树 ，字符串,布局的

3、表示,A2,B2,C2,A1,B1,C1,FPGA,A2,B2,C2,A1,B1,C1,使芯片中所占的面积最小,模块间的连线最短,布局后的优化：,布局的优化,BBL 布局的过程就是将一组模块或单元安置在芯片合适的位置上，使芯片的面积最小,、模块间的连线最短并容易布通。,BBL ：Building Block Layout,BBL块布局法,BBL 布局特点： 一个由模块或单元组成的集合A = M1 , M2 , , Mm ,其中每个模块是有固定边长的矩形或其他形状的硬模块,或是面积固定而长宽比可以变动的矩形软模块。,布局结构,BBL 布局结构通常有两种:一种是可二划分的结构( Slicing);

4、 另一种是不可二划分的结构(Non-Slicing)。,Slicing,Non-Slicing,Slicing 结构中，通过递归地使用垂直或水平划分线,把芯片矩形划分为两个子部分,依此类推，直到每个子区域中只包含一个模块,如图1 a 所示。,Slicing结构,Non-Slicing 结构包括所有可能出现的布局结构,是一种更为一般的布局结构,如图1 b 所示。,Non-Slicing,Non-Slicing 结构中， 不能递归地使用垂直 或水平划分线得到对 应的布局,Non-Slicing结构,布局表示,布局表示就是用字母或数字代表各模块,并将其用一定的数据组织形式(如序列、树、图等) 组织起

5、来从而表达模块之间的几何位置关系。,布局表示,对应着一个模块布局的序列、树或图称为编码。从编码到模块布局的映射称为解码。 所有可能的编码形式称为这个布局表示法的组合空间或解空间。,布局表示,许多新的布局表示法: 如1999 年的O-tree 和SG ，2000 年的B-tree ,CBL 和Q-sequence ; 2001 年的TCG 和Twin Binary Tree ;2002 年的TCG-S,一、VLSI 布局结构表示研究进展 二、角模块布局法 三、 热约束的BBL布局算法研究,目 录,角模块序列 布局法,2000 年洪先龙等首先提出了Mosaic 布局结构,以及可以用于解决Mosai

6、c 布局问题的角模块序列(Corner Block List ,CBL) 表示法。,如果某模块位于一个布局的最右上角区域,则称该模块为该布局的角模块。,角模块的编码,具体过程如下: 删除当前布图规划中的角模块, 在S序列中记录模块名称; 在L 序列中记录模块类型,水平记1、垂直记0; 在T 序列中记录删除时有多少个T-连接随着划分线被拉动。,通过对一个包含n 个模块的MOSAIC 布图规划进行n 次模块删除操作, 可以得到三个序列( S ,L , T ) , 这三个序列组成的结构被称为角模块结构编码。,在记录序列T 时, 每次记录的是一个二进制的子串, 该子串包含1 的数目是被拉动的牵连T-连

7、接的数目, 子串的末尾以0 结束。,CBL 是一个三元组( S , L , T) ,其中, S： 是m 个模块构成的序列 L： 是S中所对应的模块的T-连接方向,牵连T-连接的数目是模块删除时受牵连的其它模块中包含的T-连接的数目,通常等于受到压缩或者拉升的模块总数目减1。,T-连接,T-连接由该布局的某个模块的左边和下边所在的连线组成，也就是矩形的左下角所对应的T型。,T-连接,T-连接有几种类型。,水平T连接,垂直T连接,不是T连接,垂直方向的 T-连接,如果该T-连接可以由T 型逆时针旋转90得到则称该T-连接的方向为垂直方向;,逆时针900,水平方向的 T-连接,如果该T-连接可以由T

8、 型逆时针旋转180得到,则称该T-连接的方向为水平方向。,逆时针1800,对于一个布局,可以通过不断地删除其角模块 得到它的CBL编码 ;反之,根据其CBL 编码 可以得到其布局。,角模块编码,下面看看删除角模块的过程：,删除水平角模块的过程如下: 将该角模块的左边向右移动, 以该边为贯穿划分线的T-连接也随之向右移动, 直至该边与芯片的右边界重合, 该角模块就被推出了。,删除水平角模块,删除b,如果角模块为水平方向, 移动它的左边界到芯片的右边框删除该角模块, 并拖动其左边界的牵连T-连接到右边框;,删除水平角模块,删除b后,删除垂直角模块的过程如下: 将该角模块的 下 边向 上 移动,

9、以该边为贯穿划分线的T-连接也随之向 上 移动, 直至该边与芯片的 上 边界重合, 该角模块就被推出了。,删除垂直角模块,如果角模块为垂直方向, 移动它的下边界到芯片的上边框删除该角模块, 并拖动其下边界的牵连T-连接到上边框。,删除垂直角模块,后,插入一个水平角模块的过程如下: 将芯片右边界上覆盖指定牵连数目T-连接的划分线向左推动, 以该划分线作为贯穿划分线的T-连接随之移动, 这样就得到一个新的room, 将角模块分配到该room 就完成了插入。,插入水平角模块,插入角模块是删除角模块的逆操作,插入水平角模块b,插入一个垂直角模块的过程如下: 将芯片上边界上覆盖指定数目T-连接的划分线向

10、 下 推动, 以该划分线作为贯穿划分线的T-连接随之移动, 这样就得到一个新的room， 将新角模块分配到该room， 就完成了插入。,插入垂直角模块,垂直,角模块的编码,三个序列( S ,L , T ) 组成的编码被称为角模块编码。,具体过程如下: 删除当前布图规划中的角模块, 在S序列中记录模块名称; 在L 序列中记录模块类型,水平记0、垂直记1; 在T 序列中记录删除时有多少个T-连接随着划分线被拉动。,实例：,B 4 = b L 4 = 1 T 4 = 0,B 3 = a L 3 =0 T 3 = 10,B 2 = d L 2 = 1 T 2 = 0,B 1 = c,(S , L ,

11、T ) S = c d a b L = 1 0 1 T = 0 1 0 0,编码,当将所有子串连接起来时, 按照得到子串的相反顺序连接, 而子串本身顺序不变。,下图所示的布局对应的角模块编码为 S :daebc; L : 0110; T : 001010， 反过来，由这个编码也可以绘制出与之对应的布局。,编码 S :daebc; L : 0110; T : 001010 ,布局,实例,B 5= c L 5 = 0 T 5= 10,B 4= b L 4= 1 T 4 = 10,B 3 = e L 3 = 1 T 3 = 0,B 1 = d,(S , L , T ) S = d a e b c L

12、 = 0 1 1 0 T= 0 0 1 0 1 0,a,d,B 2= a L 2 = 0 T 2 = 0,角模块的解码,通过三个序列( S ,L , T ) , 根据三个序列不断的进行插入操作，就会得到角模块布局图。 例,B 5= c L 5 = 0 T 5= 1 0,B 4= b L 4= 1 T 4 = 1 0,B 3 = e L 3 = 1 T 3 = 0,B 1 = d,(S , L , T ) S = d a e b c L = 0 1 1 0 T = 0 0 1 0 1 0,a,d,B 2= a L 2 = 0 T 2 = 0,d,一、VLSI 布局结构表示研究进展 二、角模块布局

13、法 三、 热约束的BBL布局算法研究 （了解）,A2,B2,C2,A1,B1,C1,FPGA,A2,B2,C2,A1,B1,C1,使芯片中所占的面积最小,模块间的连线最短,优化后的布局：,不考虑热分布时,例2,热模型,考虑热约束的布局,以面积最小和热均匀分布为目标,？,A2,B2,C2,A1,B1,C1,布局后的优化：,不考虑热分布时,考虑热分布按照 什么规律进行考虑？,热模型,考虑热约束的布局,以面积最小和热均匀分布为目标,A2,B2,C2,A1,B1,C1,布局后的优化：,考虑热分布时，,如果将每个模块看作是 一个个火炉,那么： 模块A2除了自身发热外 还有四周的A1,B1, B2,C1,

14、C2在发热，该热量会传递到A2模块上。 热量大小怎样计算？,FPGA,A2,B2,C2,A1,B1,C1,使芯片中所占的面积最小,模块间的连线最短,布局后的优化：,A2,B2,C2,A1,B1,C1,考虑热分布后的优化布局：,热模型,考虑热约束的布局,成本公式,本文将热约束考虑在布局过程中, 以面积最小和热均匀分布为目标, 其目标成本公式为：,Cost(p)=面积成本因素+ 热分布成本因素,例如：Cost(p)=Area(p) * (1+ TP / TCOM *P% ),其中, P 为一种布局, T COM为模块的基准温度,在Cost(p)这个成本公式中，取面积和热偏差的和较少的方案为最优方案

15、，这时可能出现，面积不是最优，但热偏差最佳的方案。 例如：两辆新汽车，分别售价5万和8万，哪辆车的综合性能更优？ 售价成本+耗油成本 综合考虑,结 论,建立对应的热模型, 不仅考虑模块本身的温度, 而且考虑芯片上其他模块对它的热贡献, 用叠加原理求出芯片上每一模块的温度。,从实验结果中可以看到, 基于热约束的布局结果, 模块的平均温度和最高温度分别改善11%和35%。,Question and Answer,思考： BBL布图方法的改进,目前可以有非矩形的模块，如L型、T型的形状。,问题的表示方法、布图规划、布局、布线算法的研究也在不断进行。,考虑延迟、功耗、噪声串扰等约束以及将布局与布线同时考虑的算法等。,采用分级设计策略可有效地降低复杂性 以布局为列，若原来复杂性为S=O(n2)，分级后先对模块内进行布局，然后对整个芯片进行布局，则总的复杂性会降低。,采用除 BBL布局外的方法进行布局，并同时考虑热均匀分布成本因素，对芯片性能的影响。 例如：3维FPGA中布局方法和热热均匀分布的联合考虑。,基于阶梯网格结构的布局算法,考虑面积、线长和宽高比目标的BBL布局算法,带有软模块的布图规划算法,不同宽长比目标下的布图规划效果图,带预置模块和多边形区域上的布图规划,含多边形模块的布局,同时进行布局和总体布线算法,Thank You,