Parallel Sparse Left-Looking Algorithm

In this chapter, we will propose parallelization methodologies for the G-P sparse left-looking algorithm. Parallelizing sparse left-looking LU factorization faces three major challenges: the high sparsity of circuit matrices, the irregular structure of the symbolic pattern , and the strong data dependence during sparse LU factorization. To overcome these challenges, we propose an innovative framework to realize parallel sparse LU factorization. The framework is based on a detailed task-level data dependence analysis and composed of two different scheduling modes to fit different data dependences: a cluster mode suitable for independent tasks and a pipeline mode that explores parallelism between dependent tasks. Under the proposed scheduling framework, we will implement several different parallel algorithms for parallel full factorization and parallel re-factorization . In addition to the fundamental theories, we will also present some critical implementation details in this chapter.