基于Single—Sequence表示法的BUS总线约束布局优化

摘要：基于Single-Sequence表示法和模拟退火算法框架，通过检验single-sequence编码的直接升序和直接降序判断BUS总线布局中水平和垂直约束的可行性。在MCNC benchmark上的实验结果验证了算法的有效性.。

关键词：Single-Sequence表示法；BUS布局约束；直接升序；直接降序

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）33-0225-02

随着微电子技术不断发展，越来越多的元器件被集成到一块芯片上，同时需要多层金属实现器件间的连接（通常包括几条BUS总线）以完成既定功能。随着电路复杂度和集成度急剧增加，BUS布线成为一项艰巨任务，尤其是在网络和数据处理芯片上。为使BUS总线连接更加方便高效，应在布图规划的早期阶段就考虑BUS总线的布局及其优化。文中应用Single Sequence（以下简称SS）表示法来讨论BUS总线布局问题。

1 Single-Sequence表示法

Single-Sequence表示法用1～n的自然数排列表示平面上n个模块的布图规划（布局）的拓扑结构。每个SS编码所包含的ABLR关系（上、下、左、右）由每个表示模块或区域的自然数在SS中的相对大小和位置确定[1-6]：

SS中的ABLR关系：假设在SS编码中两个自然数x和y保持这种位置关系。当且仅当xy时，x所代表的模块或区域在y所代表的模块（或区域）的下边。

SS编码是平面上n个物体之间ABLR位置关系的产生器。考虑平面上n个物体，一个SS编码定义了平面上n个物体之间n（n-1）/2个ABLR关系[1-3]。SS编码的标识和获得过程如图1所示，图中SS编码为41352。

2 BUS总线约束布图规划（布局）

2.1 BUS约束布图规划问题定义

假设布线区域为多层金属层，BUS总线以水平或垂直方向分布在两层。单条BUS总线可表示为ui={b1，…，bk}，k=︱ui︱，。每个模塊bi的左下角坐标为（xi，yi），其宽度和高度分别为wi和hi。BUS线驱动布图规划（布局）可如下定义[7-10]：

给定n个长方形模块集B={bi︱i=1…，n}和m条BUS总线集U={ui︱i=1…，m}，每条BUS线宽度为ti并穿过模块集Bi（Bi[?]B，︱Bi︱=ki）。确定每个模块和BUS线在布局平面上的位置，使得任意两个模块及BUS总线（水平或垂直）不重叠，每条BUS线ui穿越所包含的所有模块ki。同时，包围所有模块的外框矩形（芯片面积）和BUS线占用面积最小化（如图2所示）。

命题1 水平BUS线布局约束条件

水平BUS总线uk={b1，…，bk}满足布局条件当且仅当ymax-ymin[≥]tk， ymax=min{yi+hi︱i=1…，k}， ymin=max{yi︱i=1…，k}。

命题2 垂直BUS线布局约束条件

垂直BUS总线uk={b1，…，bk}满足布局条件当且仅当xmax-xmin[≥]tk， xmax=min{xi+wi︱i=1…，k}， ymin=max{xi︱i=1…，k}。

图3（a）中，两条BUS线u（A，G）和v（D，E，F）分别穿过各自给定的连线模块。但在图3（b）中，BUS线u（A，G）未完全连接模块A（不满足命题1中条件）；v（D，E，F）不能实现相应模块连接。

2.2 BUS约束布图规划（布局）文献概述

文献中，一些学者讨论过布图规划（布局）中的模块间位置约束问题，但这些方法多基于单个模块的位置调整。Xiang等在文献[7]中讨论过模块间上、下、左、右的相邻放置，但使用sequence-pair表示法，编码变形复杂，计算复杂度较高。Tang等在文献[8]中给出了一种模块位置对齐且相邻的方法，但在BUS总线约束中并不强制要求模块间相邻。Rafiq等在文献[10]中给出了一种基于BUS总线的布图规划方法，但给出的BUS总线只包括两个模块极其繁杂连线。

3 基于SS编码的BUS约束布图规划

定义1 直接升序 给定包含n个模块的任一SS编码{ s1s2…si..sj…sn︱si∈N}，从任意位置上的数字si出发（记为p1），向右（向后）扫描，大于p1且离其最近的数字记为p2，重复此过程直到编码右端，得到的序列称为该数字（位置）的直接升序，记为{p1p2…pk︱pk∈SS，pi

定义2 直接降序 给定包含n个模块的任一SS编码{ s1s2…si..sj…sn︱si∈N}，从任意位置上的数字si出发（记为q1），向右（向后）扫描，小于q1且离其最近的数字记为q2，重复此过程直到编码右端，得到的序列称为该数字（位置）的直接降序，记为{q1q2…qk︱qk∈SS，qi>qi+1}。SS编码中模数最大直接降序称为该编码的最大降序。

例：图1（b）的编码为41352，其最大升序为135，最大降序为432。

命题3 当SS编码的任一直接升序的模大于某一水平BUS总线约束的模，将水平BUS总线约束包含的模块放置到该直接升序代表的模块位置处，可得到一个可行解。

证明：因为SS编码表示数字代表的矩形区域上下左右的位置关系，任一直接升序中数字代表的位置左右直接相邻；如果不直接相邻，可通过滑动模块（区域）右上角的T型连接的边使其直接相连[1，3]。

命题4 当SS编码的任一直接降序的模大于某一垂直BUS总线约束的模，将垂直BUS总线约束包含的模块放置到该直接降序代表的模块位置处，可得到一个可行解。

证明：同命题3。

4 算法描述

算法总体框架为退火。需要注意的是，一个SS编码仅给出了数字代表的区域（模块）的位置关系，还需将模块分配到区域里，压缩后得到最终的布局。

5 实验结果

参考文献：

[1] Kajitani Y. The single-sequence that unifies placement and floorplanning [C]. Presession meeting of ASP-DAC，Asian Semi-conductor University Cooperations， Jan.2003， PP： 368-371.

[2] 李康， 虞厥邦，于永斌. Single-Sequence的边界约束条件[J]. 电子科技大学学报， 2008，37（1）： 70-73.

[3] K Li， J Yu， J Li. VLSI Floorplanning with Boundary Constraints Based on Single-Sequence Representation[J]. Ieice Trans on Fundamentals， 2009， 92（9）： 2369-2375.

[4] 李康.VLSI物理设计中布局及有约束的布局优化[D]. 成都：电子科技大学，2010.

[5] 李坤龙.布图规划约束对VLSI设计性能的影响[D].青岛：青岛理工大学，2016.

[6] 徐敏.基于Single-Sequence的布圖规划改进算法及实现[D].南京：南京邮电大学，2010.

[7] H. Xiang， X. Tang， D. Wong， Bus-driven floorplanning. Proceedings of IEEE International Conference on Computer-Aided Design， 2003：66-73.

[8] E.F. Young， C.C. Chu， M.L. Ho， A unified method to handle different kinds of placement constraints in floorplan design. Proceedings of the Seventh Asia and South Pacific Design Automation Conference and 15th International Conference on VLSI Design， 2002： 661–667.

[9] X. Tang， D. F. Wong. Floorplanning with alignment and performance constraints[J]. ACM DAC， 2002， pp：848-853.

[10] Rafiq. F， C. Jeske， M Yang. BUS based integrated floorplanning. IEEE International Symposium on Circuits & Systems， 2002，l2（2）： 875-878.

[11] 李煜，张徐亮，虞厥邦. 基于O-TREE树表示的总线约束在VLSI/PCB布局中的应用[J].成都信息工程学院学报，2005，（20）：291-296.

[12] Xiaoping Tang， D. F. Wong. Floorplanning with alignment and performance constraints[J]. ACM DAC， 2002：848-853.

[13] H. Murata， K. Fujiyoshi， S. Nakatake， Y. Kajitani. VLSI module placement based on rectangle packing by the sequence pair[J]. IEEE Trans on CAD， 1996， 15（12）：1518-1524.

【通联编辑：张薇】