一种基于动态分配模式求解三对角线性方程组的并行算法  

A Parallel Algorithm for Solving Tridiagonal Linear Systems Based on the Pattern of Dynamic Dispatch

作　　者：张选平[1] 高由兵[1] 崔骏[1] 陈喜伦[1] 

机构地区：[1]西安交通大学计算机科学与技术系,陕西西安710049

出　　处：《微电子学与计算机》2008年第5期19-23,共5页Microelectronics & Computer

基　　金：国防"十一五"预研基金项目(102010302);国防"十一五"预研基金项目(402040202)

摘　　要：分析了双向并行分裂DPP算法存在空闲等待、通信阻塞以及冗余计算等方面的不足,并在此基础上提出一种基于动态分配模式求解三对角线性方程组的并行算法.该算法摒弃了DPP算法平均分配方程组的模式和完成向中间通信后必须消除所有下(上)对角元素的方式,而采用基于运算和通信参数的动态分布模式以及仅适量消元的方法,从而在保持通信畅通的前提下,充分利用计算与通信重叠技术,减少处理机空闲等待和冗余计算.最后分析了新算法的理论性能,并在IBMRS60000机群上进行了数值实验.实验结果表明,该算法的效率较DPP算法有较大提高.The deficiencies of DPP algorithm, such as idle time, communication blocking and redundant computation, are analyzed, then a parallel algorithm for solving tridiagonal linear systems on workstation cluseters, which is based on the pattern of dynamic dispatch, is presented. Based on the computation and communication parameters, this algorithm adopts the pattern of dynamicly dispatching equations on each workstation as well as the method of just diminating part of the the subdiagonal （or superdiagonal） dements after communication toward middle direction is finished, instead of the DPP＇s pattern of even dispatch and its method of diminating all. The algorithm makes full use of overlapping between computation and communication to decrease the amount of workstations＇ idle time and unnecessary redundant compuation under the precondition of guaranteeing the clear communication. Finally, the theoretic functions of the new algorithm are analyzed, and numerical experiments are conducted on IBM RS60000 Workstation Clusters. The results show that the ef- ficiency of this algorithm is much higher than that of DPP algorithm.

关 键 词：三对角线性方程组 并行算法 分裂法 机群 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]