TAILIEUCHUNG - Parallel Programming: for Multicore and Cluster Systems- P46

Parallel Programming: for Multicore and Cluster Systems- P46: Innovations in hardware architecture, like hyper-threading or multicore processors, mean that parallel computing resources are available for inexpensive desktop computers. In only a few years, many standard software products will be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing, up to now the main application area for parallel computing | Cholesky Factorization for Sparse Matrices 433 express the specific situation of data dependences between columns using the relation parent j 124 118 . For each column j 0 j n we define parent j min i i e Struct L j if Struct L j 0 . parent j is the row index of the first off-diagonal non-zero of column j. If Struct L j 0 then parent j j. The element parent j is the first column i j which depends on j .A column l j l i between them does not depend on j since j Struct Ln and no cmod l j is executed. Moreover we define for 0 i n children i j i parent j i . children i contains all columns j that have their first off-diagonal non-zero in row i. The directed graph G V E has a set of nodes V 0 . n - 1 with one node for each column and a set of edges E where i j e E if i parent j and i j. It can be shown that G is a tree if matrix A is irreducible. A matrix A is called reducible if A can be permuted such that it is block-diagonal. For a reducible matrix the blocks can be factorized independently. In the following we assume an irreducible matrix. Figure shows a matrix and its corresponding elimination tree. In the following we denote the subtree with root j by G j . For sparse Cholesky factorization an important property of the elimination tree G is that the tree specifies the order in which the columns must be evaluated The definition of parent implies that column i must be evaluated before column j if j parent i . Thus all the children of column j must be completely evaluated before the computation of j . Moreover column j does not depend on any column that is not in the subtree G j . Hence columns i and j can be computed in parallel if G i and G j are disjoint subtrees. Especially all leaves of the elimination tree can be computed in parallel and the computation does not need to start with column 0. Thus the sparsity structure determines the parallelism to be exploited. For a given matrix elimination trees of smaller height usually represent a larger .

• Phần cứng
• sửa chữa máy tính
• sổ tay phần cứng
• MainBoard
• thiết bị máy tính
• thiết bị mạng
• lắp ráp máy tính
• Phần cứng máy tính
• lỗi máy tính
• hệ thống mạch máy tính
• điện máy tính
• Tài liệu máy tính