A practical scheduling algorithm for parallel LU factorization in circuit simulation

A static task clustering scheduling algorithm is proposed for the parallel LU factorization of a sparse linear system on a shared-memory parallel computer. Assuming a column-based medium-grained task model, the parallel LU factorization process is accomplished using a nested bordered block diagonal node reordering technique. In order to minimize the overhead due to task synchronization on a shared-memory parallel machine, it is proposed to regroup tasks into task clusters in which tasks have to be executed sequentially. Both theoretical analysis and actual implementation using benchmark circuits indicate significant speedup compared with the conventional critical path scheduling algorithm