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

    A Partitioning Method for Three-dimensional Integrated Circuits Based on Variable Neighborhood Search Algorithm

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

       

      Abstract: In order to minimize the number of through-silicon vias (TSVs) between different layers in the physical design of three-dimensional integrated circuits (3D ICs) and reduce the cost of chip manufacturing, a 3D IC partitioning method based on the variable neighborhood search (VNS) algorithm is proposed. Firstly, the minimum secant algorithm is utilized to partition a two-dimensional circuit into multiple partitions, where the number of partitions matches the required number of layers. Then, the linear sorting algorithm is used to stack-sort the partitions to determine the optimal layer-placement order with the minimum number of long connections. Finally, an improved VNS algorithm is applied to move the cells between layers, incorporating a force-oriented mechanism to reduce the search space of neighborhoods, which further reduces the number of TSVs. Benchmark tests using internationally recognized datasets are conducted and the proposed method is compared with the currently best-performing FSA method. Experimental results show that the proposed 3D IC partitioning algorithm achieves the best average total number of TSV, with a reduction in computation time by an average of 94% compared to the FSA method. The proposed algorithm effectively addresses the 3D IC partitioning problem and demonstrates remarkable practical value.

       

    /

    返回文章
    返回