An efficient sparse LU factorization algorithm on popular shared memory multiprocessors is presented. Interprocess communication is critically important on these architectures- the algorithm introduces O(n) synchronization events only. No global barrier is
Parallel Sparse Factorization with Left-Right Looking Strategy 1: 2: Scheduler= initialized with leaves of the elimination tree 3: P=1,#proc 4: (Scheduler not empty) 5: lock I 6: Scheduler Scheduler J 7:= panel J is computed by process P= 8: unlock I 9: panel K in with AK;J 0 10:= outer factorization, dependent on other processes= 11: lock II 12: identify all computed descendants K of panel J 13:= left looking, row traversal= 14: unlock II 15: A;J A;J A;K AK;J 16: AJ; AJ; AJ;K AK; 17: 18:= inner factorization, independent of other processes= 19: AJ;J LJ;J UJ;J?1 20: A;J A;J UJ;J
3
Q?
for
f
g
while
?
nf g
while 9
Q
6=
end while =:= 1= L?J J
==
??
21: 22: 22: 23: 24: 25: 26:
end while end for Fig. 1. Parallel left-right looking sparse supernode block LU factorization
AJ; AJ;; lock II mark parents K of panel J for pipelining of the outer factorization= right looking, column traversal= unlock II
The rst interprocess communication results from the assignment of panel J to a process| multiple execution has to be prevented by mutual exclusion. Now the process is able to compute the outer and inner factorization of panel J. In contrast to the inner factorization, which is completely independent from other processes, the outer factorization needs to be synchronized. Computing the outer factorization with a left-looking approach in line 9 (Figure 2), the process enters a second critical section and removes all panel children of panel J that are already factorized from a queue Q. With respect to the completely factored panels the computation is independent and the outer factorization can be performed. After having nished all the external updates of panel J, the process executes the inner factorization. The factorization of panel J terminates with a third critical section. Within this critical section all parents of panel J are informed that panel J is factorized (Figure
3: column traversal of the factor L). This is called rightlooking, since the process computes the information for all panel K with K J. No global barrier is used within this algorithm, and the execution of di erent processes is completely asynchronous. Since a left-right looking strategy is being introduced, three critical sections have to be handled. In total, the number of interprocess communications is roughly 3np (np the number of panels).
Highly scalable parallel... 暂无评价 27页 免费 Highly scalable parallel..... Sparse LU factorization with partial pivoting, Message passing performance, ...
S+ Efficient 2D sparse LU factorization on parallel machines Abstract. Static symbolic factorization coupled with supernode partitioning and asynchronous ...
Cholesky Factorization and Sparse Approxi_专业资料。... but its scalable parallel implementation poses ...We start with a good ?ll-reducing strategy such...
parallel sparse LU factorization with partial pivoting on distributed memory ...In the literature 2-D mapping has been shown more scalable than 1-D for...
Highly scalable parallel... 暂无评价 27页 免费 Highly scalable parallel..... Comparing Nested Dissection Orderings for Parallel Sparse Matrix Factorization ...
Highly scalable parallel algorithms for sparse matrix factorization In this paper, we describe a scalable parallel algorithm for sparse matrix factorization, ...
PSPASES An efficient and scalable parallel sparse direct solver Many problems... with the highest performance (51 GFLOPS for Cholesky factorization) ever ...
PSPASES A scalable parallel direct solver for sparse symmetric positive ... symbolic factorization, Cholesky factorization, and triangular systems solution....
PSPASES Scalable Parallel Direct Solver Library for Sparse Symmetric Positive ... symbolic factorization, Cholesky factorization, and triangular systems solution....
On Sparse Matrix Reorder... 暂无评价 8页 免费 Highly scalable parallel.....Keywords: basis pursuit, dictionary learning, matrix factorization, online ...
热门文档