Design of a Multicore Sparse Cholesky Factorization Using DAGs
Design of a Multicore Sparse Cholesky Factorization Using DAGs
复制标题
DOI：
10.1137/090757216
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
Jonathan D. Hogg;J. Reid;J. Scott
中科院分区：
文献类型：
--
作者：
Jonathan D. Hogg;J. Reid;J. Scott
多功能机器的快速出现导致需要设计有效的这些体系结构的新算法。在这里，我们考虑通过cholesky分解稀疏的对称阳性线性系统的解决方案。我们是由于密集情况下的计算成功分配的动机，并使用块上的任务，并使用任务管理器利用这些任务之间可用的所有并行性，这些任务之间的依赖关系可以用有向的无循环图（DAG）表示。我们的稀疏算法是在组装树上构建的，并将每个节点的作品细分为Cholesky因子块上的任务。这些任务之间的依赖项可能再次由DAG表示。为了限制内存需求，块是直接更新而不是通过生成的元素矩阵更新。我们的算法是在新的高效和便携式求解器HSL_MA87中实现的。它用Fortran 95加OpenMP编写，可作为软件库HSL的一部分。使用由一系列应用产生的问题，我们提出了支持我们的设计选择的实验结果，并证明HSL_MA87在我们的8核测试机上获得了良好的串行和并行时间。比较与现有现代求解器进行比较，并表明HSL_MA87的性能很好，尤其是在很大的问题的情况下。
The rapid emergence of multicore machines has led to the need to design new algorithms that are efficient on these architectures. Here, we consider the solution of sparse symmetric positive-definite linear systems by Cholesky factorization. We were motivated by the successful division of the computation in the dense case into tasks on blocks and use of a task manager to exploit all the parallelism that is available between these tasks, whose dependencies may be represented by a directed acyclic graph (DAG). Our sparse algorithm is built on the assembly tree and subdivides the work at each node into tasks on blocks of the Cholesky factor. The dependencies between these tasks may again be represented by a DAG. To limit memory requirements, blocks are updated directly rather than through generated-element matrices. Our algorithm is implemented within a new efficient and portable solver HSL_MA87. It is written in Fortran 95 plus OpenMP and is available as part of the software library HSL. Using problems arising from a range of applications, we present experimental results that support our design choices and demonstrate that HSL_MA87 obtains good serial and parallel times on our 8-core test machines. Comparisons are made with existing modern solvers and show that HSL_MA87 performs well, particularly in the case of very large problems.