基于离散动态凸化方法的VLSI电路k路划分

摘要：

电路划分是超大规模集成电路(VLSI)物理设计中的一个重要阶段。k 路划分是把电路分成k 个部分，划分目标是在保持各部分均衡的前提下，最小化被切割的线网数。本文把原问题转化为一个等价的非线性整数规划问题，并设计一个用于求解该问题的局部搜索算法。在此基础上，提出基于离散动态凸化方法的k 路划分算法，并从理论上分析了该算法可以不断改进局部最优解，具有全局搜索能力。实验结果表明，该方法可以有效提高著名的k 路划分工具hMETIS-Kway的划分质量。

关键词：电路划分、k 路划分、离散动态凸化算法

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金No.61170308，No.61070020；教育部高校博士点专项科研基金No.20093514110004。

在线出版日期：2014-01-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共17页

页码：48-64