Name
Abstract | ||
|---|---|---|
The minimal block storage Distributed Square Block Packed (DSBP) format for distributed memory computing on symmetric and triangular matrices is presented. Three algorithm variants (Basic, Static, and Dynamic) of the blocked right-looking Cholesky factorization are designed for the DSBP format, implemented, and evaluated. On our target machine, all variants outperform standard full-storage implementations while saving almost half the storage. Communication overhead is shown to be virtually eliminated by the Static and Dynamic variants, both of which take advantage of hardware parallelism to hide communication costs. The Basic variant is shown to yield comparable or slightly better performance than the full-storage ScaLAPACK routine PDPOTRF while clearly outperformed by both Static and Dynamic. Models of execution assuming zero communication costs and overhead are developed. For medium- and larger-sized problems, the Static schedule is near optimal on our target machine based on comparisons with these models and measurements of synchronization overhead. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1499096.1499100 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
distributed square block format,sbp cholesky factorization algorithm,synchronization overhead,packed storage,parallel computing,communication overhead,minimal block storage,positive definite matrices,full-storage scalapack routine pdpotrf,communication cost,dynamic variant,real symmetric matrices,zero communication cost,static schedule,dsbp format,near-optimal scheduling,parallel algorithms,target machine,cholesky factorization,distributed memory,parallel computer,symmetric matrices,parallel algorithm | Scheduling (computing),Matrix (mathematics),Computer science,Theoretical computer science,Cholesky decomposition,Synchronization,Mathematical optimization,Parallel algorithm,Parallel computing,Distributed memory,Algorithm,Block (data storage),ScaLAPACK | Journal |
Volume | Issue | ISSN |
36 | 2 | 0098-3500 |
Citations | PageRank | References |
9 | 0.84 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fred G. Gustavson | 1 | 1185 | 223.40 |
| Lars Karlsson | 2 | 51 | 5.16 |
| Bo Kågström | 3 | 1045 | 189.17 |