Algorithm Parallelization of on-Die Power/Ground Network Solving Based on GPU Parallel Computing

In order to study fast and accurate algorithms for power/ground network(P/G network)analyses,based on the locality effect of structure P/G networks,this work rethinks the efficiency and parallelism of successive over relaxation(SOR) algorithm and alternating direction implicit(ADI)algorithm.And then it proposes the optimized GPU-friendly parallel algorithms:G_RBSOR and G_ADI.The algorithms both use the regular data structure to facilitate GPU parallel data reading/writing.And they both use the merging reduction technique for GPU parallel computing to fast calculate the iteration-ending flags,too.Furthermore,in order to avoid the data collision in GPU parallel calculating,G_RBSOR uses the checkerboard strategy to classify all P/G network nodes into red and black groups and then,relax red nodes and black nodes step-by-step.Experimental results show that without any precision penalty,G_RBSOR and G_ADI algorithms can achieve more than 50 X speedup over their serial CPU counterparts.In comparison with the efficient serial algorithm ICCG,both can also achieve more than 5X speedup.