SCRS并行算法的全局通信策略
|
摘要
基于Gu等人提出的全局通信策略,改进平滑共轭残量平方法 (SCRS),提出了改进的适合于分布式并行计算环境的SCRS算法(ISCRS).通过改变算法的计算顺序,使得ISCRS算法相对于SCRS算法将3个全局同步点减少为1个.每次迭代的所有的内积是独立的,且内积所需的通信时间能和计算有效重叠.理论分析和数值实验指出ISCRS比SCRS有更好的并行性和可扩展性.
Based on the ideas of the global communication strategy by Gu et al,and improved smoothed conjugate residual squared( SCRS) method,an improved smoothed conjugate residual squared( ISCRS) method is presented,which is designed for distributed parallel environments.The ISCRS method reduces three global synchronization points to one by changing the computational sequence in the SCRS method. All inner products per iteration are independent and communication time required for inner product can be overlapped with useful computation. Theoretical analysis and numerical experiments show that the ISCRS method has better parallelism and scalability than the SCRS method.
Based on the ideas of the global communication strategy by Gu et al,and improved smoothed conjugate residual squared( SCRS) method,an improved smoothed conjugate residual squared( ISCRS) method is presented,which is designed for distributed parallel environments.The ISCRS method reduces three global synchronization points to one by changing the computational sequence in the SCRS method. All inner products per iteration are independent and communication time required for inner product can be overlapped with useful computation. Theoretical analysis and numerical experiments show that the ISCRS method has better parallelism and scalability than the SCRS method.
引文
[1]SAAD Y.Iterative methods for sparse linear systems[M].Boston:PWS Publishing Company,1996.
[2]SOGABE T,SUGIHARA M,ZHANG S L.An extension of the conjugate residual method to nonsymmetric linear systems[J].J Comp Appl Math,2009,226(1):103-113.
[3]SOGABE T,ZHANG S L.Extended conjugate residual methods for solving nonsymmetric liner systems[M].Beijing:Science Press,2003.
[4]SOGABE T,FUJINO S,ZHANG S L.A product-type krylov subspace method based on conjugate residual method for nonsymmetric coefficient matrices[J].Transaction of IPSJ,2007,48:11-21.
[5]SCHONAUER W.Scientific computing on vector computers[M].New York:Elsevier Science Pub Co Inc,NY,1987.
[6]WEISS R.Convergence behavior of generalized conjugate gradient methods[M]∥Lecture Notes in Mathematics.Berlin:Springer,1990:137-153.
[7]ZHAO J,ZHANG J H.A smoothed conjugate residual squared algorithm for solving nonsymmetric linear systems[C]∥Second International Conference on Information and Computing Science,2009:364-367.
[8]GU T X,ZUO X Y,ZHANG L T.An improved bi-conjugate residual algorithm suitable for distributed parallel computing[J].Appl Math Comput,2007,186(2):1243-1253.
[2]SOGABE T,SUGIHARA M,ZHANG S L.An extension of the conjugate residual method to nonsymmetric linear systems[J].J Comp Appl Math,2009,226(1):103-113.
[3]SOGABE T,ZHANG S L.Extended conjugate residual methods for solving nonsymmetric liner systems[M].Beijing:Science Press,2003.
[4]SOGABE T,FUJINO S,ZHANG S L.A product-type krylov subspace method based on conjugate residual method for nonsymmetric coefficient matrices[J].Transaction of IPSJ,2007,48:11-21.
[5]SCHONAUER W.Scientific computing on vector computers[M].New York:Elsevier Science Pub Co Inc,NY,1987.
[6]WEISS R.Convergence behavior of generalized conjugate gradient methods[M]∥Lecture Notes in Mathematics.Berlin:Springer,1990:137-153.
[7]ZHAO J,ZHANG J H.A smoothed conjugate residual squared algorithm for solving nonsymmetric linear systems[C]∥Second International Conference on Information and Computing Science,2009:364-367.
[8]GU T X,ZUO X Y,ZHANG L T.An improved bi-conjugate residual algorithm suitable for distributed parallel computing[J].Appl Math Comput,2007,186(2):1243-1253.