基于两重快速傅里叶变换的三维芯片热仿真

Thermal Simulation of 3D IC Based on the Double-Nested Fast Fourier Transformation

为了解决三维芯片设计中的发热问题,针对三维芯片物理模型提出一种快速、准确的热仿真方法.该方法基于三维有限差分法,利用嵌套的两重快速傅里叶变换对有限差分方程进行求解,从而得到芯片温度分布;通过矩阵的特征值分解与快速傅里叶变换,使得只需求解一系列小规模的三对角线性方程组,即可在不损失精度的前提下有效地提升计算速度.数值实验结果表明,文中方法比稀疏矩阵直接求解算法快几十倍,并且由于占用内存少,能有效地求解变量数多达6×107的三维芯片热仿真问题;该方法具有O(nlogn)的时间复杂度与O(n)的空间复杂度,其中n为离散变量数.

In this paper, a fast method is proposed for the thermal simulation of 3D chip, which is based on the finite difference method （FDM） and the fast Fourier transformation （FFT） algorithm. Utilizing a double-nested FFT, the solution of a large-scale FDM linear equation is converted to the solution of some small-scale tri-diagonal linear system. This largely speeds up the total computation, without loss of accuracy. The numerical results validated the accuracy and efficiency of proposed methods. And, the comparison with the sparse linear equation solver demonstrates above several tens times speedup. The proposed method is also able to tackle a very large problem with 6 ;K 107 unknowns, for which other methods are not feasible, and it has O（n logn） time complexity and O（n） space complexity, where n is the total unknown number.