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 = 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 , 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 = 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 布局结构表示研究进展 二、角模块布局法 三、 热约束的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型的形状。,问题的表示方法、布图规划、布局、布线算法的研究也在不断进行。,考虑延迟、功耗、噪声串扰等约束以及将布局与布线同时考虑的算法等。,采用分级设计策略可有效地降低复杂性 以布局为列，若原