Multigranular parallel algorithms for solving linear equations in VLSI circuit simulation

Algorithms for parallel execution of forward elimination to solve linear equations arising from very large scale integrated circuit simulation are discussed. Here, a multigranular method is introduced, exploiting different levels of potential parallelism. According to these levels, the new method contains four phases, which are dynamically linked. Therefore, the use of an architecture with shared memory in connection with multithreaded programming enables the parallelization of a serial well-adapted sparse-matrix solver. In order to take system-specific properties into account, an adaptive partitioning is proposed. For this, the partition size is enlarged step by step as long as the measured execution time decreases. Applying this method to industrial examples an efficiency of processor usage of nearly 90%, with up to 12 processors, is reached for relevant circuits.