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

《VLSI布局结构表示及角模块布局法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、、优化等.ABC例1FPGA电路模块划分A1B2C2B1C1A2FPGA模块划分A2B2C2A1B1C1FPGA布局A2B2C2A1B1C1FPGA布局面积A2B2C2A1B1C1FPGA问题：怎样描述这个布局的结果？即：用怎样的数据结构和算法来记录和描述该种布局的结果，布局速度比较快，布局过程耗费的存储空间比较小。布局的问题和目标A2B2C2A1B1C1FPGA问题：用怎样的数据结构和算法来记录和描述该种布局的结果？数组，矩阵，二叉树，B*树，字符串布局的表示A2B2C2A1B1C1FPGAA2B2C2A1B1C1使芯片中所占的面积最小模块间的连线最短布局后

3、的优化：布局的优化BBL布局的过程就是将一组模块或单元安置在芯片合适的位置上，使芯片的面积最小,、模块间的连线最短并容易布通。BBL：BuildingBlockLayoutBBL块布局法BBL布局特点：一个由模块或单元组成的集合A={M1,M2,⋯,Mm},其中每个模块是有固定边长的矩形或其他形状的硬模块,或是面积固定而长宽比可以变动的矩形软模块。布局结构BBL布局结构通常有两种:一种是可二划分的结构(Slicing);另一种是不可二划分的结构(Non-Slicing)。SlicingNon-SlicingSlicing结构中，通过递归地使用垂直或水平划分线,

4、把芯片矩形划分为两个子部分,依此类推，直到每个子区域中只包含一个模块,如图1a所示。Slicing结构Non-Slicing结构包括所有可能出现的布局结构,是一种更为一般的布局结构,如图1b所示。Non-SlicingNon-Slicing结构中，不能递归地使用垂直或水平划分线得到对应的布局Non-Slicing结构布局表示布局表示就是用字母或数字代表各模块,并将其用一定的数据组织形式(如序列、树、图等)组织起来从而表达模块之间的几何位置关系。布局表示对应着一个模块布局的序列、树或图称为编码。从编码到模块布局的映射称为解码。所有可能的编码形式称为这个布局表示法

5、的组合空间或解空间。布局表示许多新的布局表示法:如1999年的O-tree和SG，2000年的B-tree,CBL和Q-sequence;2001年的TCG和TwinBinaryTree;2002年的TCG-S一、VLSI布局结构表示研究进展二、角模块布局法三、热约束的BBL布局算法研究目录角模块序列布局法2000年洪先龙等首先提出了Mosaic布局结构,以及可以用于解决Mosaic布局问题的角模块序列(CornerBlockList,CBL)表示法。如果某模块位于一个布局的最右上角区域,则称该模块为该布局的角模块。角模块的编码具体过程如下:删除当前布图规划中

6、的角模块,在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-连接的数目,通常等于受

7、到压缩或者拉升的模块总数目减1。T-连接T-连接由该布局的某个模块的左边和下边所在的连线组成，也就是矩形的左下角所对应的T型。T-连接T-连接有几种类型。水平T连接垂直T连接不是T连接垂直方向的T-连接如果该T-连接可以由T型逆时针旋转90°得到则称该T-连接的方向为垂直方向;逆时针900水平方向的T-连接如果该T-连接可以由T型逆时针旋转180°得到,则称该T-连接的方向为水平方向。逆时针1800对于一个布局,可以通过不断地删除其角模块得到它的CBL编码;反之,根据其CBL编码可以得到其布局。角模块编码下面看看删除角模块的过程：删除水平角模块的过程如下:将该

8、角模块的左边向右移动,以该边为贯穿划分