应用于三维集成电路解析式布局的层分配算法

摘要：层分配是解析式三维集成电路布局算法中的关键一步。解析式布局需要通过层分配将连续的三维空间中的单元划分到二维的芯片层上，这个过程会破坏之前三维空间中得到的连续解。为了实现从优化的三维布局到合法的多层二维结构的平滑过渡，提出一种使用最小代价流的层分配方法，尽可能地继承三维优化结果，保护解空间。将此层分配算法嵌入到多层次的解析式三维集成电路布局算法中，以总线长和穿透硅通孔数目的加权总和为目标，面积密度为约束条件，对比当前其他三维布局算法，该算法得到较好的线长结果、穿透硅通孔数量和运行时间。

关键词：层分配；解析式布局算法；三维集成电路；穿透硅通孔；最小代价流

三维电路的出现，不仅能够在很大程度上解决由于电路规模的急剧增长带来的互连性能优化问题，而且提供给设计者一种新的芯片设计模式。因此，具有三维结构的芯片设计、实现与制造在近年来得到了学术界和工业界的极大关注，成为当前集成电路研究一个新的热点。

与传统的二维电路相比，三维电路具有特殊结构，其布局设计需要新的算法实现。现有的三维布局算法包括堆叠布局、力驱动布局、基于划分的布局、二次规划布局和解析式布局。

文献[2]提出一种堆叠布局方法。它首先建立一个三维空间；然后把二维布局的结果通过堆叠方法形成三维的层结构。这种方法对单元重新分配层，提高了布局质量，但是运行时间比较长，比较复杂。

力驱动的三维布局方法[3]把立体空间离散成元素，或化成网格，然后计算力的方向得到单元位置。最后把单元在垂直方向上排序，就近分配到层上。因为坐标在垂直方向上是连续的，层分配过程需要取整，这样会产生错误。

基于划分的方法[4]以总的线长结合温度、穿透硅通孔（ThroughSiliconVia，TSV）数量和热效应为最小割的目标将单元迭代划分到立体空间的特定区域中，然后整体或局部移动互换单元进行优化调整。即使在没有I/O的情况下，它也可以快速有效地达到目标。但是同二维情况下问题一样，此方法容易陷入局部最小解，得到的布局结果的质量没法与解析的方法相比。

基于二次规划的方法[5]进行三维布局是用拉格朗日松弛法求解目标函数：二次线长和离散余弦变换的密度矩阵。但它使用二次线长模拟半周长会引起一些误差，同时它不能整体进行优化。

解析式布局方法[6]基于线长模型，同时考虑TSV的位置、大小和数量。但是它没有对层分配进行说明。文献[7]松弛离散的层分配使单元在垂直方向上的移动是连续的。它的基本思想是用一个夹层密度函数，消除位于两层之间的单元。

层分配将空间内的单元放置到合适的层上，这将直接影响TSV的数量。TSV一般都占有较大的面积，在三维集成电路布局中应该考虑TSV。这样就使层分配过程在整个三维布局算法中变得非常重要。现在大多的三维布局算法都没有合适的层分配算法或是没有具体说明。所以，本文提出并且详细阐述一种新的层分配算法，然后将新的层分配算法加入到三维集成电路解析式布局算法流程中。本文主要贡献如下：

1）提出一种新的使用最小代价流的层分配算法。在实现三维空间极大扩散后在垂直方向上进行合法化。算法将TSV的数量作为代价函数，每一层面积阈值作为限制条件，然后用最小的代价值将单元分配到合适的层上。它可以保护三维空间优化的线长并且减少解空间的损失。

2）提出一种三维集成电路解析式布局算法，最终得到合法化的三维空间分布状况。算法分为三部分：三维空间扩散、层分配和二维整体优化。工作的目标是先开发一个高质量的简单的三维集成电路布局算法，这样就可以将其作为一个基础引擎来考虑三维集成电路中其他的限制和目标。

3）实验观察到多层次模式可以有效地控制TSV数目，以此来减少TSV数量，并且加速层分配过程。

4）密度立方用来建立三维集成电路布局模型，而不用单元的面积来评估布局密度。

5）在层分配之后，采用整体二维优化方法，用二维线长和各层重叠建模来进一步优化线长。