二维矩形Packing问题和大规模集成电路布图规划问题的算法研究

摘要

NP难问题是一大类问题，其解空间随着数据规模的增加呈指数型增长，不存在多项式时间复杂度的精确求解算法，除非P=NP。设计可在有效时间内给出NP难问题的高质量解的启发式算法或近似算法，是现代计算机科学界的一个核心问题。二维矩形Packing问题是一种典型的NP难问题，对它的启发式算法的研究，可以为其它NP难问题的求解提供参考，有深刻的理论意义。作为二维矩形Packing问题在工业应用中的一个扩展问题，布图规划是大规模集成电路设计中的一个核心步骤，其算法研究将有力推动集成电路产业的发展。
　　本文有机地结合了二维矩形Packing问题的研究和布图规划问题的研究，对三类二维矩形Packing问题和两类布图规划问题，设计了高效率的启发式求解算法。主要工作包括：
　　（1）对于二维矩形Packing中的背包问题和面积最小化问题，分别设计了最小损害度算法（LIF）和动态规约算法（DRA）。对于背包问题，提出了衡量矩形块放置动作对后续矩形块放置影响程度的标准——损害度，并基于此标准设计了贪心构造算法LIF，迭代执行损害度最小的矩形块放置动作以构造布图。不同于背包问题，面积最小化问题要求在面积最小的矩形框内放入所有矩形块。通过动态地构造一组矩形框，DRA将求解一个面积最小化问题转化为求解一组背包问题，并用LIF计算对应的背包问题。使用了15个面积最小化问题的代表性算例对DRA进行了测试，DRA改进了8个算例的当前最优解，另有3个算例与当前最优解持平。
　　（2）对于二维软矩形Packing问题和固定边界的软模块布图规划问题，分别设计了迭代糅合Packing算法（IMP）和基于迭代糅合的层次划分算法（IMP-HP）。IMP是用以处理矩形框上无闲置空间的问题的原创算法。首先，类似于哈弗曼树的构造过程，IMP迭代地将面积最小的两个矩形块糅合成组合矩形块，直至所有矩形块均被糅合在一起。之后，递归地根据每个组合矩形块的位置和形状，确定两个子矩形块的位置和形状。证明了IMP可得可行布图（所有矩形块均被合法放置的布图）的一组充分条件，相比于同类算法Zero-Dead-Space（ZDS）可得可行布图的充分条件，该组充分条件更加宽松。基于提出的闲置空间动态分配策略，进一步扩展了IMP，使其可处理矩形框上有闲置空间的问题。IMP-HP采用了层次划分的算法框架，首先利用超图分割算法hMetis层次地将原问题划分成一组子问题，然后用IMP计算子问题得到原问题的布图。将电路板高宽比为1的18个IBM-HB算例中的硬模块松弛为软模块，得到18个IBM-SHB算例，并与两个代表性算法PATOMA和DeFer进行了比较。实验结果表明，IMP-HP的平均连线长度优于PATOMA和DeFer，分别减小了4.1％和4.0%，并在其中10个算例上找到了更好的解。
　　（3）对于固定边界的混合模块布图规划问题，设计了基于拟牛顿法的布图规划算法（QNF）。QNF包含三个子算法：粗略放置算法、局部优化算法和精细放置算法。粗略放置算法利用hMetis递归地划分问题，直至所有子问题都只包含一个模块，然后将模块放置到相应的子电路板上，其目标是得到一个模块均匀放置、连线长度较短的布图，但模块间允许有重叠。局部优化算法设计了弹性势能函数，以评估布图中模块间重叠的面积和模块超出电路板的幅度，并用拟牛顿法L-BFGS-B优化弹性势能函数，其目标是通过局部微调模块的位置和形状，设法将粗略放置算法所得布图转化为合法布图。若以上合法化失败，则调用提出的精细放置算法重新生成模块放置更加均匀的布图，并用局部优化算法将其合法化。精细放置算法先将尺寸超大的模块无重叠地固定在电路板上，然后将未固定模块均匀放置到电路板的剩余空间上。使用了54个IBM-HB算例对算法进行了测试，QNF可合法求解51个算例，改进了35个算例的当前最优解。与两个目前性能最好的算法DeFer和F-FM相比，QNF分别将平均连线长度减小了6.3%和2.3%。
　　所设计的二维矩形Packing问题求解算法和布图规划问题求解算法的性能均已达到或超过了目前业界的最高水平，其中布图规划算法同时已达到实际工业应用标准。

目录

第一个书签之前

摘要

Abstract