Stochastic and hybrid linear equation solvers and their applications in VLSI design automation.

摘要

This thesis presents two new linear equation solvers, and investigates their applications in VLSI design automation. Both solvers are derived in the context of a special class of large-scale sparse left-hand-side matrices that are commonly encountered in engineering applications, and techniques are presented that can potentially extend the theory to more general cases.;The first is a stochastic solver that performs the computation by establishing the equivalence between linear equations and random walks. It has a desirable locality feature: a single unknown variable can be evaluated without solving the entire system. For complete solutions, it is competitive in applications with moderate accuracy requirement.;The second is a hybrid solver: it combines the random walk technique and traditional iterative approaches. Given a set of linear equations, if the left-hand-side matrix satisfies certain conditions, it is proven that an incomplete triangular factorization can be obtained from random walks, and these factors can be used as a preconditioner in a traditional iterative linear equation solver to accelerate its convergence. In other words, the proposed hybrid solver is a stochastically preconditioned iterative solver. It is argued that our factor matrices have better quality, i.e., better accuracy-size tradeoffs, than preconditioners produced by existing incomplete factorization methods. Therefore the hybrid solver requires less computation than traditional preconditioned iterative solvers to solve a set of linear equations with the same error tolerance, and the advantage increases for larger and denser sets of linear equations.;The application of these solvers on several problems in VLSI design is illustrated in this thesis, namely, power grid analysis, chip-level electrostatic discharge simulation, and quadratic placement. We not only demonstrate the efficiency of direct usage of the solvers, but also devise a set of application-specific techniques that are often based on indirect usage of the stochastic solver, due to the fact that the localized computation process of random walks carries meaningful information in various scenarios.