APP下载
登录
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)生成版图。
热门文章
