Parallel Sparse Direct Solver for Integrated Circuit Simulation

In the 1970s, the Electronics Research Laboratory of the University of California, Berkeley developed the Simulation Program with Integrated Circuit Emphasis (SPICE), which is a general-purpose integrated circuit (IC) simulator that can be used to check the integrity of circuit designs and predict circuit behaviors at the transistor level.

Parallel circuit simulation has been a popular research topic for several decades since the invention of SPICE. Researchers have proposed a large amount of parallelization techniques for SPICE-like circuit simulation [1]. In this chapter, we will comprehensively review state-of-the-art studies on parallel circuit simulation techniques. Before that, we would like to briefly introduce classifications of these parallel techniques. Based on different points of view, parallel circuit simulation techniques can also have different classifications. From the implementation platform point of view, parallel circuit simulation techniques can be classified into software techniques and hardware techniques. Hardware techniques include field-programmable gate array (FPGA)- and graphics processing unit (GPU)-based acceleration approaches. For software techniques, from the domain of parallel processing point of view, they can be further classified into direct parallel methods, parallel circuit-domain techniques, and parallel time-domain techniques. From the algorithm level of parallel processing point of view, there are intra-algorithm and inter-algorithm parallel techniques.

In this chapter, we will present the basic flow of our proposed solver NICSLU, as a necessary background of the parallelization techniques.

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.

In the previous two chapters, we have presented the basic flow of our solver and the parallelization methodologies for both numerical full factorization and re-factorization, as well as the factorization method selection strategy.

In this chapter, we will present the experimental results of NICSLU and the comparisons with PARDISO and KLU.

In the previous chapter, we have shown the test results of NICSLU, where the relative speedups vary in a big range for different benchmarks. In order to understand the performance difference and find possible limiting factors of the scalability, further investigations are required. Toward this goal, in this chapter, we will build a performance model to analyze the performance and find bottlenecks of the scalability of NICSLU.

Efficiently parallelizing the sparse direct solver in SPICE-like circuit simulators is a practical problem and also an industrial challenge. The high sparsity and the irregular symbolic pattern of circuit matrices, and the strong data dependence during sparse LU factorization, make the sparse direct solver extremely difficult to parallelize. In this book, we have introduced NICSLU, a parallel sparse direct solver which is specially targeted at circuit simulation applications. We have described algorithmic methods and parallelization techniques that aim to realize a parallel sparse direct solver for SPICE-like circuit simulators. Based on the baseline G-P sparse left-looking algorithm [1], we have presented an innovative parallelization framework and novel parallel algorithms of the sparse direct solver in detail. We have also shown how to improve the performance by simple yet effective numerical techniques. Not only the features of circuit matrices, but also the features of the circuit simulation flow are fully taken into account when developing NICSLU. In particular, we have developed the following innovative techniques in NICSLU.