论文部分内容阅读
电路划分是超大规模集成电路(VLSI)物理设计中的一个重要阶段。k路划分是把电路分成k个部分,划分目标是在保持各部分均衡的前提下,最小化被切割的线网数。本文把原问题转化为一个等价的非线性整数规划问题,并设计一个用于求解该问题的局部搜索算法。在此基础上,提出基于离散动态凸化方法的k路划分算法,并从理论上分析了该算法可以不断改进局部最优解,具有全局搜索能力。实验结果表明,该方法可以有效提高著名的k路划分工具h METIS-Kway的划分质量。
Circuit division is an important phase in the VLSI physical design. k Road Division is divided into k parts of the circuit, the goal is to divide the circuit in the premise of maintaining the balance of all parts, to minimize the number of lines being cut. This paper transforms the original problem into an equivalent non-linear integer programming problem and designs a local search algorithm to solve the problem. On this basis, a k-way partitioning algorithm based on discrete dynamic convexization is proposed, and theoretically analyzed that the algorithm can continuously improve the local optimal solution with global search capability. The experimental results show that the proposed method can effectively improve the partitioning quality of the famous k-way dividing tool h METIS-Kway.