2012 · 11 citations · 19 references
ComputingComputer EngineeringComputer ScienceParallel AlgorithmsParallel ComputingScientific ComputingGraphics Processing Unit ArchitectureGraphics Processing UnitsParallel ArchitecturesParallel ComputationParallel Computer ArchitectureParallel Numerical MethodsMatrix FormulationParallel Computing ArchitecturesParallel PreconditioningParallel Processing ArchitecturesPreconditioningPreconditioning Techniques
Efficient analysis of massive on-chip power delivery networks is among the most challenging problems facing the EDA industry today. In this paper, we present a new preconditioned iterative method for fast DC and transient simulation of large-scale power grids found in contemporary nanometer-scale ICs. The emphasis is placed on the preconditioner which reduces the number of iterations by a factor of 5X for a 2.6M-node industrial design and by 72.6X for a 6.2M-node synthetic benchmark, compared with incomplete factorization preconditioners. Moreover, owing to the preconditioner's special structure that allows utilizing a Fast Transform solver, the preconditioning system can be solved in a near-optimal number of operations, while it is extremely amenable to parallel computation on massively parallel architectures like graphics processing units (GPUs). Experimental results demonstrate that our method achieves a speed-up of 214.3X and 138.7X for a 2.6M-node industrial design, and a speed-up of 1610.5X and 438X for a 3.1M-node synthetic design, over state-of-the-art direct and iterative solvers respectively when GPUs are utilized. At the same time, its matrix-less formulation allows for reducing the memory footprint by up to 33% compared to the memory requirements of the best available iterative solver.
19
Yanqing Chen, Timothy A. Davis, William W. Hager et al. · ACM Transactions on Mathematical Software · 2008 · 751 citations
Fast tridiagonal solvers on the GPU
Yao Zhang, Jonathan Cohen, John D. Owens · 2010 · 212 citations · Full text