一种分块并行Cholesky分解动态调度算法

A dynamic scheduling algorithm for block parallel Cholesky factorization

为解决分块并行Cholesky分解过程中各处理器间的负载平衡问题,分析了算法的下三角矩阵特性以及各轮循环和循环内部各步骤基本计算任务之间存在的依赖关系,以各步骤的矩阵块基本计算任务为顶点,任务间的依赖关系为有向边,构造有向无环图,并根据有向无环图的性质建立二级队列,然后利用该队列对就绪任务进行排队,实现任务的动态调度.研究结果表明:在矩阵块数不是非常大的情况下,该算法在时间性能上比传统的分块并行Cholesky分解算法具有明显的优势.

To solve the load balancing problem on block parallel Cholesky factorization algorithm running on system with multiple processors, this paper analyzed the lower triangular feature of the algorithm and dependencies of the basic computing tasks in every loop and among the loops and built a directed acyclic graph by taking the basic computing tasks for matrix block at every step as vertices and dependencies of the tasks as directed edges. According to this directed acyclic graph, a two-level queue was created to queue the ready tasks and implemented dynamic scheduling strategy. Experiment results show that the presented algorithm is evidently superior to the traditional parallel Cholesky block factorization when the numbers of block is not very large.