Title :
An adaptive LU factorization algorithm for parallel circuit simulation
Author :
Chen, Xiaoming ; Wang, Yu ; Yang, Huazhong
Author_Institution :
Dept. of Electron. Eng., Tsinghua Univ., Beijing, China
fDate :
Jan. 30 2012-Feb. 2 2012
Abstract :
Sparse matrix solver has become the bottleneck in SPICE simulator. It is difficult to parallelize the solver because of the high data-dependency during the numerical LU factorization. This paper proposes a parallel LU factorization (with partial pivoting) algorithm on shared-memory computers with multi-core CPUs, to accelerate circuit simulation. Since not every matrix is suitable for parallel algorithm, a predictive method is proposed to decide whether a matrix should use parallel or sequential algorithm. The experimental results on 35 circuit matrices reveal that the developed algorithm achieves speedups of 2.11×~8.38× (on geometric-average), compared with KLU, with 1~8 threads, on the matrices which are suitable for parallel algorithm. Our solver can be downloaded from http://nicslu.weebly.com.
Keywords :
SPICE; circuit simulation; matrix decomposition; multiprocessing systems; parallel algorithms; shared memory systems; SPICE simulator; adaptive LU factorization algorithm; circuit matrices; multicore CPU; parallel LU factorization algorithm; parallel algorithm; parallel circuit simulation; predictive method; sequential algorithm; shared memory computer; simulation program with integrated circuit emphasis; Application specific integrated circuits; Benchmark testing; Circuit simulation; Parallel algorithms; Pipelines; Prediction algorithms;
Conference_Titel :
Design Automation Conference (ASP-DAC), 2012 17th Asia and South Pacific
Conference_Location :
Sydney, NSW
Print_ISBN :
978-1-4673-0770-3
DOI :
10.1109/ASPDAC.2012.6164974