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

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×10⁷ unknowns,for which other methods are not feasible,and it has O(n log n) time complexity and O(n) space complexity,where n is the total unknown number.