基于变邻域搜索算法的三维集成电路分区方法

摘要

为了减少三维集成电路(three-dimensional integrated circuit,3D IC)物理设计中不同层之间的硅通孔(throughsilicon via,TSV)数量，降低芯片制造成本，提出一种基于变邻域搜索算法(variable neighborhood search,VNS)的3D IC分区方法。应用最小割线算法将二维电路划分为若干个分区，其中分区数量等于需求层数；利用线性排序算法对分区进行堆叠排序，以找到最少长连接数量的层放置顺序；通过改进的VNS将单元进行层间移动，并引入力导向的机制减小邻域搜索的空间，以进一步减小TSV的数量。通过国际通用的基准实例进行测试分析，并与目前性能最佳的力导向模拟退火算法(force-directed simulated annealing,FSA)方法进行对比。实验结果表明，本文提出的3D IC分区算法与FSA方法相比，均获得最佳的平均TSV总数，并且求解时间平均减少了94%。本文的算法能有效解决3D IC分区问题，具有较好的实用价值。

关键词

三维布局 / 硅通孔 / 分区 / 变邻域搜索算法