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

VLSI布局结构表示及基于热约束的角模块布局法,VLSI 布局结构表示研究进展徐宁洪先龙董社勤(清华大学计算机科学与技术系北京100084),热约束的BBL 布局算法研究,徐 宁 洪先龙 陈 松 董社勤(清华大学计算机科学与技术系 北京 100084),一、VLSI 布局结构表示研究进展 二、角模块布局法 三、热约束的BBL布局算法研究,目 录,一、VLSI 布局结构表示研究进展 二、角模块布局法 三、热约束的BBL布局算法研究,目 录,一、VLSI 布局结构,在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中,布局结果的好坏直接影响整个布图设计。,布图设计过程包括划分、布局、布线、优化等。,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*树，字符串,布局的表示,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);另一种是不可二划分的结构(Non-Slicing)。,Slicing,Non-Slicing,Slicing 结构中，通过递归地使用垂直或水平划分线,把芯片矩形划分为两个子部分,依此类推，直到每个子区域中只包含一个模块,如图1 a 所示。,Slicing结构,Non-Slicing 结构包括所有可能出现的布局结构,是一种更为一般的布局结构,如图1 b 所示。,Non-Slicing,Non-Slicing 结构中，不能递归地使用垂直或水平划分线得到对应的布局,Non-Slicing结构,布局表示,布局表示就是用字母或数字代表各模块,并将其用一定的数据组织形式(如序列、树、图等)组织起来从而表达模块之间的几何位置关系。,布局表示,对应着一个模块布局的序列、树或图称为编码。从编码到模块布局的映射称为解码。所有可能的编码形式称为这个布局表示法的组合空间或解空间。,布局表示,许多新的布局表示法:如1999 年的O-tree 和SG，2000 年的B-tree,CBL 和Q-sequence;2001 年的TCG 和Twin Binary Tree;2002 年的TCG-S,一、VLSI 布局结构表示研究进展 二、角模块布局法 三、热约束的BBL布局算法研究,目 录,角模块序列 布局法,2000 年洪先龙等首先提出了Mosaic 布局结构,以及可以用于解决Mosaic 布局问题的角模块序列(Corner Block List,CBL)表示法。,如果某模块位于一个布局的最右上角区域,则称该模块为该布局的角模块。,角模块的编码,具体过程如下:删除当前布图规划中的角模块,在S序列中记录模块名称;在L 序列中记录模块类型,水平记1、垂直记0;在T 序列中记录删除时有多少个T-连接随着划分线被拉动。,通过对一个包含n 个模块的MOSAIC 布图规划进行n 次模块删除操作,可以得到三个序列(S,L,T),这三个序列组成的结构被称为角模块结构编码。,在记录序列T 时,每次记录的是一个二进制的子串,该子串包含1 的数目是被拉动的牵连T-连接的数目,子串的末尾以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 型逆时针旋转180得到,则称该T-连接的方向为水平方向。,逆时针1800,对于一个布局,可以通过不断地删除其角模块 得到它的CBL编码;反之,根据其CBL 编码 可以得到其布局。,角模块编码,下面看看删除角模块的过程：,删除水平角模块的过程如下:将该角模块的左边向右移动,以该边为贯穿划分线的T-连接也随之向右移动,直至该边与芯片的右边界重合,该角模块就被推出了。,删除水平角模块,删除b,如果角模块为水平方向,移动它的左边界到芯片的右边框删除该角模块,并拖动其左边界的牵连T-连接到右边框;,删除水平角模块,删除b后,删除垂直角模块的过程如下:将该角模块的 下 边向 上 移动,以该边为贯穿划分线的T-连接也随之向 上 移动,直至该边与芯片的 上 边界重合,该角模块就被推出了。,删除垂直角模块,如果角模块为垂直方向,移动它的下边界到芯片的上边框删除该角模块,并拖动其下边界的牵连T-连接到上边框。,删除垂直角模块,后,插入一个水平角模块的过程如下:将芯片右边界上覆盖指定牵连数目T-连接的划分线向左推动,以该划分线作为贯穿划分线的T-连接随之移动,这样就得到一个新的room,将角模块分配到该room 就完成了插入。,插入水平角模块,插入角模块是删除角模块的逆操作,插入水平角模块b,插入一个垂直角模块的过程如下:将芯片上边界上覆盖指定数目T-连接的划分线向 下 推动,以该划分线作为贯穿划分线的T-连接随之移动,这样就得到一个新的room，将新角模块分配到该room，就完成了插入。,插入垂直角模块,垂直,角模块的编码,三个序列(S,L,T)组成的编码被称为角模块编码。,具体过程如下:删除当前布图规划中的角模块,在S序列中记录模块名称;在L 序列中记录模块类型,水平记0、垂直记1;在T 序列中记录删除时有多少个T-连接随着划分线被拉动。,实例：,B 4=bL 4=1T 4=0,B 3=aL 3=0T 3=10,B 2=dL 2=1T 2=0,B 1=c,(S,L,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=cL 5=0T 5=10,B 4=bL 4=1T 4=10,B 3=eL 3=1T 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=aL 2=0T 2=0,角模块的解码,通过三个序列(S,L,T),根据三个序列不断的进行插入操作，就会得到角模块布局图。例,B 5=cL 5=0T 5=1 0,B 4=bL 4=1T 4=1 0,B 3=eL 3=1T 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=aL 2=0T 2=0,d,一、VLSI 布局结构表示研究进展 二、角模块布局法 三、热约束的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,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)这个成本公式中，取面积和热偏差的和较少的方案为最优方案，这时可能出现，面积不是最优，但热偏差最佳的方案。例如：两辆新汽车，分别售价5万和8万，哪辆车的综合性能更优？售价成本+耗油成本 综合考虑,结 论,建立对应的热模型,不仅考虑模块本身的温度,而且考虑芯片上其他模块对它的热贡献,用叠加原理求出芯片上每一模块的温度。,从实验结果中可以看到,基于热约束的布局结果,模块的平均温度和最高温度分别改善11%和35%。,Question and Answer,思考：BBL布图方法的改进,目前可以有非矩形的模块，如L型、T型的形状。,问题的表示方法、布图规划、布局、布线算法的研究也在不断进行。,考虑延迟、功耗、噪声串扰等约束以及将布局与布线同时考虑的算法等。,采用分级设计策略可有效地降低复杂性 以布局为列，若原来复杂性为S=O(n2)，分级后先对模块内进行布局，然后对整个芯片进行布局，则总的复杂性会降低。,采用除 BBL布局外的方法进行布局，并同时考虑热均匀分布成本因素，对芯片性能的影响。例如：3维FPGA中布局方法和热热均匀分布的联合考虑。,基于阶梯网格结构的布局算法,考虑面积、线长和宽高比目标的BBL布局算法,带有软模块的布图规划算法,不同宽长比目标下的布图规划效果图,带预置模块和多边形区域上的布图规划,含多边形模块的布局,同时进行布局和总体布线算法,Thank You,