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
2
Olaf Schenk et al.
over a wide range of numerical properties and therefore the parallel sparse direct solver PARDISO has been integrated into complex semiconductor device and process simulation packages 4, 5]. The rapid and widespread acceptance of shared memory multiprocessor architectures, from the desktop to the high-end server, has now created a demand for e cient parallel sparse linear solvers on such shared memory architectures. The synchronization on modern multiprocessor architectures is one form of interprocess communication and can have large impact on program performance. Therefore, in section 2 we describe a method using O(n) synchronization events. The experimental results are presented in Section 3. Section 4 provides a short comparison of iterative and sparse direct methods for several semiconductor device simulation examples on di erent architectures. Section 5 contains a summary of our results.
There are three levels of parallelism that can be exploited by parallel direct methods. The rst one, elimination tree parallelism 8] is generally exploited in all parallel sparse direct packages. In practice, however, a large percentage of the computation occurs at the top levels of the tree and the sequential part of the elimination tree usually limits the e ciency. It is therefore important to consider more levels of parallelism. Another type of parallelism, called node level parallelism, solves in a hybrid approach at the top level of the tree the factorization of each supernode in parallel 9]. However, the size of the supernodes and the numbers of processors determine the e ciency. The third type, pipelining parallelism, instead, is suitable for a larger number of processors. In this case, a processor can start with the external factorization of all supernodes that are already factorized. Although a pipelining approach is di cult to realize in sparse direct solver packages, the pipelining parallelism is essential to achieve higher concurrency. Our parallel formulation of the sparse numerical factorization is based on the general framework described in 2, 10]. It successively computes fractions of supernodes called panels, which are introduced to increase load balancing and pipelining parallelism i
n the sequential part of the elimination tree. The algorithm with reduced synchronization is shown in Figure 1. First, the scheduler is initialized with all leaves of the elimination tree (line 2). Then, a group of p processes is created. Each process asks the scheduler for a new task until all panels have been factorized. The assignment of panel tasks (line 6) is completely dynamic, resulting in a signi cant improvement of load-balancing| if su ciently small tasks can be assigned last. That is the reason for the introduction of the panels. We have found from experimental results that the following strategy results in panel sizes that a large enough for Level 3 BLAS and small enough to exploit load balancing and pipelining parallelism: First, if (1< nproc 4) then each panel contains not more than 96 columns of the factor, if (4< nproc) then the maximum panel size is reduced to 72 columns. The scheduling is dynamic but not completely independent of other processes.
2 Parallel left-right looking strategy and asynchronous computation scheduling.
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 ...
热门文档