基于SS序列集成电路不规则模块布图算法

SS序列(Single-Sequence)为一串互不重复的自然数序列，参考文献[1]中SS解码规则将 SS序列解码作为相对应的单元分布图，并利用模拟退火算法[2]以一定的概率随机改变单元内模块摆放顺序、旋转度及SS序列，通过SS解码规则得出各单元模块的水平/垂直约束图，利用关键路径算法[3]求出最终芯片的面积。但目前为止SS所解决的只是局限于对矩形硬模块的布图问题，而对于非矩形模块或不规则形状模块的布图尚未有很好的解决方法。随着集成电路技术快速发展，模块将不局限在以矩形形式出现，而是有可能以多种多样的形状更加灵活地出现在集成电路版图上，但若仍以矩形的模式处理，必然会导致芯片面积的利用率不高，出现很多空间闲置的现象，因此寻找出一套简单易行的方法解决不规则模块摆放的问题意义重大。

　　1 模块的划分

　　对于不规则模块的先期处理是将其划分为许多小矩形，从而避免了传统算法将整个不规则模块算为1个大矩形而带来的面积浪费。如图1所示，由2个矩形合并而成，传统分割法将其视为1个矩形整体，再利用SS序列算法将其放入版图，如图1(a)所示，造成了底面积的浪费。SS序列无法区分模块空白区域，而是将其视为一整体放入版图，导致下部空白区域永远无法被其他模块空间占用，带来了较大浪费，随着模块面积增大和不规则模块数量增多，面积浪费现象将更为严重。因此在输入模块数据前就应将模块进行划分，为了程序计算方便，规定为对模块自上而下、以左边为基准进行划分，如图1(b)所示将该不规则模块划分为 A、B两个小矩形输入数据，在SS算法处理过程中将其视为两个连在一起不同的模块，运用区域模块连接算法使其在变换的过程中始终保持紧密的连接在一起，如此则可充分利用下部空余的面积部分。对于有弧形的不规则模块，应以弧形最边缘切线为起点画一矩形将其包围，如图1(c)所示模块。首先以整体模块最左边为基准，即起始点，以上半部弧形右边最顶点为终点，上弧形最顶点为上边作一矩形，将该不规则模块分为上下两部分矩形。对于更为复杂的不规则模块也是如此划分。

　　2 模块区域连接算法

　　在划分模块后，存在许多相互需要连接在一起的小模块，这时必须要建立新的序列来反映这些模块间的相互关系。如图2所示，SS布图算法[4]分别变换SS序列及模块数据序列的排列顺序，将模块数据序列一一对应放入SS序列所生成的单元图中，使得版图不断发生变化。因此加入了模块区域连接序列后，应在变换模块数据序列前先将连接在一起的模块放入SS序列所生成的单元中。算法规则如下：

　　(1)将划分过的小矩形根据输入的顺序编号，将同一不规则模块的小矩形归为一组，不同组间由0相隔，从而生成反映模块间相互连接关系的模块区域连接序列。

　　(2)变换SS序列后，由于模块是自上而下的划分，因此需要找出SS单元图中呈上下连接关系的单元号先放入不规则模块。首先随机选取1个SS序列号A，找出其相邻下方的单元且水平位置最接近A的单元号B，即满足公式Mbl(A)-1=Mas(B)并且Min(|Mbs(A)-Mbs(B)|)的 SS序列号。

　　(3)将模块区域连接序列中对应的模块(划分后的小矩形)放入规则(2)所找出的单元中。

　　(4)根据模块区域连接序列，交换与规则(2)所得的单元号相对应的模块数据序列。

　　(5)生成版图。