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

    Three-dimensional Integrated Circuit Partitioning Method Based on Variable Neighborhood Search Algorithm

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

       

      Abstract: In order to minimize the number of through-silicon via (TSV) between different layers in the physical design of three-dimensional integrated circuit (3D IC) and reduce the cost of chip manufacture, a 3D IC partitioning method based on the variable neighborhood search algorithm (VNS) is proposed. Firstly, the approach by utilizing a minimum secant algorithm to partition the two-dimensional circuit into multiple partitions, where the number of partitions matches the required layers. Then, a linear sorting algorithm is used to stack-sort the partitions to find the layer-placement order with the minimum number of long connections. Finally, an improved VNS is applied to move the cells between layers, and a force-oriented mechanism is introduced to reduce the search space of neighborhoods, which further reduces the number of TSV. By testing and analyzing our algorithm on internationally common benchmarks and comparing the results with the best-performing FSA methods available. The experimental results show that the proposed 3D IC partitioning algorithm achieves the best average total number of TSV, with a reduction in solving time by 94% on average compared to the FSA. The algorithm presented in this paper effectively addresses the 3D IC partitioning problem and demonstrates remarkable practical value.

       

    /

    返回文章
    返回