Row-Based Analysis of Structure Power/Ground Grids with General Purpose GPU

As mega-scale power/ground (P/G) grids came into being, the IR drop analysis is of the daunting computational complexity. By taking the topological advantage of the structure P/G grids, this work uses the row-based analysis method to transform the mesh-circuit analysis into many parallel triangle-diagonal row-circuit analyses of far smaller complexity. Then, the Graphics Process Unit (GPU) is employed to fast solve these row circuits in the parallel style. And this work further employs the LU decomposition of the triple-diagonal matrix to increase the efficiency of our method. Experimental results show that our method out-performs the traditional methods implemented on CPU. For mega-scale P/G grids of 1-4 million nodes, our GPU-implemented method is 9-12 times faster than its CPU counterpart and 2-3 times faster than its OpenMP counterpart.