文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Scalable Parallel Sparse Factorization with Left-Right Looking Strategy on Shared Memory Mu
侵权投诉

Scalable Parallel Sparse Factorization with Left-Right Looking Strategy on Shared Memory Mu

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).

上一页第4页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email