芯片布局问题的求解算法研究

管瑶

摘要：本文基于布局问题及其特点，提出了以先初始布局再改善布局的解决布局问题的基本思想。对于初始布局，提出了中心生长法和模拟拼图法两种算法。对于改善布局提出二类基于迭代改善的算法。

关键词：布图规划；中心生长法；模拟拼图法

中图分类号：TN401 文献标识码：A 文章编号：1007-9416（2018）09-0098-01

1 初始布局

对于布局问题而言，如果参与布局的所有模块的尺寸都相同，凭直觉就可以容易地得到最优的布局。例如，对于49个尺寸相同的模块来说，很容易就知道，如果按照7×7的方式来码放就可以得到最佳布局。从这一想法出发，初始布局应为近似2*2，3*3，4*4等中心对称图形为佳。所以我们想到第一种初始布局安置策略，中心生长法。

中心生长法。首先将所有单元按COST排序。凭直觉，我们知道拥有连接点越多的单元，应安置在越中心的位置，所以我们这里的COST可以为单元上有连接点的个数。然后将接点个数排序第一位的单元布置到在芯片的中心位置。以这些单元为中心，从未安置的单元中按照排序集中选择单元，围绕核心选择合适的位置进行布置。使用类似的原理，向芯片四周扩展，直至把整个芯片都布局完成[1]。

我们在实验该算法时，发现采用中心生长法构造初始布局时，我们并未考虑芯片与其它芯片间的要求，只是盲目的进行安置。例如一个案例：有4个正方形单元，边长为2。若采用中心生长法，我们能得到的最好布局连线长度为2，实际上最优布局连线长度为0。

因此，中心生长法在安置过程中，并没有考虑待安置单元与已安置单元的关系，每次安置都是机械与盲目的。而且很多的最优解并不是像直觉那样为近似2*2，3*3，4*4等中心对称图[2]。介此，我们又提出了如下想法：模拟拼图法。

2 模拟拼图法

我们都玩过拼图游戏，在整个研究过程中，集成电路布局问题感觉就象硅片上的拼图游戏一样，拼出最完美的那副图。回忆一下在玩拼图游戏时，我们人是怎么做的。我们首先随机选择一块图形碎片为基础，然后在剩下众多碎片中选取与该碎片图形相吻合的拼接在一起成为新的基础群，接着继续在剩下碎片中选取与基础图形相吻合的拼接在一起成为新的基础群，如此反复，直到难以找到相吻合的碎片为止。这时，我们会重新在剩下碎片中选取一个作为基础，按如上方法拼成基础群。当我们把所有碎片拼成基础群后，我们再把基础群拼在一起，成为完美的图片。在安置时，模拟拼图法充分考虑到了待安置单位與已安置单元的关系，并且采用结群的方式[3]。

3 改善布局

改善布局是整个布局过程中十分重要的一个环节，其迭代思想是，选中一种特定的布局方式，按照一定的办法来改变其位置和单元，通过对比改变前后的布局效率来决定是否要采用新的布局方式。如果改变后的布局方式更为优秀，则更新布局算法。采用这个办法一直迭代，知道无法找到更优的算法为止[4-5]。

3.1 成对交换法

成对交换法是一种最简单的交换策略。每次选定一个单元，依次与其他的单元进行交换，看交换以后的布局是否更优秀。若交换以后，这两个单元相关的布线总长有减少，则采用新的布局方式。整个交换枚举次数为n（n-1）/2，与单元i相关的布局总线长度可用下式表示：

公式（5）即可作为力矢量力矢量成对交换松弛法的目标函数。其算法步骤如下：

（1）根据公式（5）计算每个模块i的（xi，yi），即每个模块0张力的位置；（2）选择满足如下条件的一对单元i，j：模块i的0张力位置（xi，yi）刚好在模块j处或在j附近，模块j的0张力位置（xi，yi）刚好在模块i处或在i附近，交换模块i和模块j的位置；（3）计算总张力和，如比原布局小，则接受新的布局，否则保持原布局；（4）反复执行上述3个步骤，直到使总张力之和不能再减小为止。

参考文献

[1]董社勤，洪先龙.基于矩形宏模块的片上系统布图规划算法[J].清华大学学报（自然科学版），2003，（4）：484-486.

[2]董社勤，洪先龙，黄钢，顾均.基于新约束图模型的布图规划和布局算法[J].软件学报，2001，（11）：1586-1594.

[3]洪先龙，严晓浪，乔长阁.超大规模集成电路布图理论与算法[M].科学出版社，1998.

[4]薄建国，俞明永，尹锦柏，等.具有多目标形状选择的布局方法[J].电子学报，1992，（2）：1-9.

[5]俞明永，薄建国，洪先龙，等.一种有效地综合两种分级设计方法的BBL布局算法[J].Journal of Semiconductors，1990，（8）：609-614.