基于GPU的大规模多阶段任务系统可靠性并行计算方法
|
摘要
针对大规模多阶段任务系统(phased-mission system,PMS)的可靠性求解,引入并行计算思想,通过分析传统的一致化方法(uniformization method,UM),基于Nvidia提出的CUDA(compute unified device architecture)架构,实现了基于图形处理器(graphics processing unit,GPU)的UM并行算法(GPU-UM),并采用合并访问和共享内存技术,提高了GPU中数据负载的利用率;PMS中不同阶段参与任务的设备及其数量通常会发生变化,导致阶段间依赖性处理困难。通过对新设备加入、已有设备暂时退出任务或完全退出任务等3种基本情况的分析,提出了阶段间状态映射机制,实际中的阶段变化情况更加复杂,可综合上述3种基本情况进行处理。通过算例对比了GPU-UM、CUDA-UM、传统UM和Krylov子空间等4种算法的计算时间和可靠性结果,分析表明GPU-UM算法的计算耗时优于其他方法,且结果精度也能满足可靠性计算需求;同时,通过对比分析UM算法和Krylov子空间算法与仿真方法的结果误差,表明提出的阶段间映射机制能够正确处理PMS中阶段间的复杂依赖关系。
The parallel computing method is introduced for the mission reliability computation of large phased-mission system(PMS).According to analysis of the traditional uniformization method(UM),a UM parallel algorithm based on graphics processing unit(GPU)is given,which is denoted as GPU-UM.The GPU-UM algorithm is implemented under the compute unified device architecture(CUDA)put forward by Nvidia.The coherence visiting and shared memory techniques have been used to improve the data load utilization ratio on GPU.In addition,the component types and quantities involved in mission may be changed under different phases.The complex phase changes lead to difficulty about handling components dependency.A system states mapping mechanism is proposed by analyzing three basic situations:adding new components,some working components quitting transiently or completely.In practice,changes between two consecutive phases can be processed by coordinating the three situations above as it becomes more complicated.The computation time and reliability under the GPU-UM,the CUDA-UM,the traditional UM and the Krylov subspace algorithms are compared.Results show that the GPU-UM algorithm is the best among them both in computation time and accuracy.Furthermore,the computation errors between the two algorithms(UM and Krylov)and simulation method are analyzed.It shows that the proposed states mapping mechanism can handle the phases dependency in PMS efficiently.
The parallel computing method is introduced for the mission reliability computation of large phased-mission system(PMS).According to analysis of the traditional uniformization method(UM),a UM parallel algorithm based on graphics processing unit(GPU)is given,which is denoted as GPU-UM.The GPU-UM algorithm is implemented under the compute unified device architecture(CUDA)put forward by Nvidia.The coherence visiting and shared memory techniques have been used to improve the data load utilization ratio on GPU.In addition,the component types and quantities involved in mission may be changed under different phases.The complex phase changes lead to difficulty about handling components dependency.A system states mapping mechanism is proposed by analyzing three basic situations:adding new components,some working components quitting transiently or completely.In practice,changes between two consecutive phases can be processed by coordinating the three situations above as it becomes more complicated.The computation time and reliability under the GPU-UM,the CUDA-UM,the traditional UM and the Krylov subspace algorithms are compared.Results show that the GPU-UM algorithm is the best among them both in computation time and accuracy.Furthermore,the computation errors between the two algorithms(UM and Krylov)and simulation method are analyzed.It shows that the proposed states mapping mechanism can handle the phases dependency in PMS efficiently.
引文
[1]WU X Y,WU X Y.Extended object-orient petri net model for mission reliability simulation of repairable PMS with common cause failures[J].Reliability Engineering&System Safety,2015,136:109-119.
[2]刘斌,武小悦.基于多阶段贝叶斯网络的反导系统任务可靠性建模[J].装备指挥技术学院学报,2012,23(1):75-78.LIU B,WU X Y.Mission reliability modeling of missile defense system based on phase mission Bayesian[J].Journal of the Academy of Equipment Command&Technology,2012,23(1):75-78.
[3]狄鹏,黎放,杨晶,等.考虑多阶段任务的舰船任务可靠性分配方法[J].海军工程大学学报,2014,26(3):108-112.DI P,LI F,YANG J,et al.Reliability allocation method of ship multistage mission[J].Journal of Naval University of Engineering,26(3):108-112.
[4]LU J M,WU X Y.A new reliability evaluation method for spaceflight telemetry,tracking and control system[C]∥Proc.of the International Conference on Quality,Reliability,Risk,Maintenance,and Safety Engineering,2013:107-111.
[5]闫华,王魁,刘子林,等.基于Markov方法的多阶段任务系统可靠性分析综述[J].兵器装备工程学报,2016,37(6):92-96.YAN H,WANG K,LIU Z L,et al.Reliability analysis of phased-mission system using Markov approach[J].Journal of Ordnance Equipment Engineering,2016,37(6):92-96.
[6]MOORSEL A P A V,SANDERS W H.Transient solution of Markov models by combining adaptive and standard uniformization[J].IEEE Trans.on Reliability,1997,46(3):430-440.
[7]STEWART W J.Introduction of the numerical solution of Markov chains[M].Princeton,NJ:Princeton University Press,1994.
[8]RAUZY A.An experimental study on iterative methods to compute transient solutions of large Markov models[J].Reliability Engineering&System Safety,2004,86(1):105-115.
[9]WANG D Z,TRIVEDI K S.Reliability analysis of phased-mission system with independent component repairs[J].IEEE Trans.on Reliability,2007,56(3):540-551.
[10]LU J M,WU X Y,LIU Y L,et al.Reliability analysis of largephased-mission systems with repairable components based on success-state sampling[J].Reliability Engineering&System Safety,2015,142:123-133.
[11]梁添.基于GPU的稀疏矩阵运算优化研究[D].武汉:华中科技大学,2012.LIANG T.The research on optimizing sparse matrix computation based on GPU[D].Wuhan:Huazhong University of Science and Technology,2012.
[12]王迎瑞,任江勇,田荣.基于GPU的高性能稀疏矩阵向量乘及CG求解器优化[J].计算机科学,2013,40(3):46-49.WANG Y R,REN J Y,TIAN R.Efficient sparse matrix-vector multiplication and CG solver optimization on GPU[J].Computer Science,2013,40(3):46-49.
[13]柳有权,尹康学,吴恩华.大规模稀疏线性方程组的GMRESGPU快速求解算法[J].计算机辅助设计与图形学学报,2011,23(4):553-560.LIU Y Q,YIN K X,WU E H.Fast GMRES-GPU solver for large scale sparse linear systems[J].Journal of Computer-Aided Design&Computer Graphics,2011,23(4):553-560.
[14]闫华,崔谱龙,苏永东,等.基于CUSPARSE的多阶段任务系统可靠性并行计算方法[J].兵器装备工程学报,2018,39(3):121-125.YAN H,CUI P L,SU Y D,et al.Reliability parallel computing method of phased-mission system using CUSPARSE[J].Journal of Ordnance Equipment Engineering,2018,39(3):121-125.
[15]DUGAN J B.Automated analysis of phased-mission reliability[J].IEEE Trans.on Reliability,1991,40(1):45-52.
[16]ALAM M,AL-SAGGAF U M.Quantitative reliability evaluation of repairable phased-mission systems using Markov approach[J].IEEE Trans.on Reliability,1986,R-35(5):498-503.
[17]SOMANI A K,RITCEY J A,AU S H L.Computationally-efficient phased-mission reliability analysis for systems with variable configurations[J].IEEE Trans.on Reliability,1992,41(4):504-511.
[18]WU X Y,YAN H,LI L R.Numerical method for reliability analysis of phased-mission system using Markov chains[J].Communications in Statistics-Theory and Methods,2012,41(21):3960-3973.
[19]ROSS S M.Introduction to probability models[M].11th ed.Waltham,USA:Academic Press,2006.
[20]黎丽容.基于Markov模型的大型PMS任务可靠性分析方法[D].长沙:国防科技大学,2011.LI L R.Method of mission reliability analysis of large PMS based on Markov model[D].Changsha:National University of Defense Technology,2011.
[21]闫华,高黎,王魁,等.大规模多阶段任务系统马尔可夫可靠性模型的存储和计算[J].兵工学报,2016,37(9):1715-1720.YAN H,GAO L,WANG K,et al.Storage and computation of Markov reliability model for large-scale phased-mission system[J].Acta Armamentarii,2016,37(9):1751-1720.
[2]刘斌,武小悦.基于多阶段贝叶斯网络的反导系统任务可靠性建模[J].装备指挥技术学院学报,2012,23(1):75-78.LIU B,WU X Y.Mission reliability modeling of missile defense system based on phase mission Bayesian[J].Journal of the Academy of Equipment Command&Technology,2012,23(1):75-78.
[3]狄鹏,黎放,杨晶,等.考虑多阶段任务的舰船任务可靠性分配方法[J].海军工程大学学报,2014,26(3):108-112.DI P,LI F,YANG J,et al.Reliability allocation method of ship multistage mission[J].Journal of Naval University of Engineering,26(3):108-112.
[4]LU J M,WU X Y.A new reliability evaluation method for spaceflight telemetry,tracking and control system[C]∥Proc.of the International Conference on Quality,Reliability,Risk,Maintenance,and Safety Engineering,2013:107-111.
[5]闫华,王魁,刘子林,等.基于Markov方法的多阶段任务系统可靠性分析综述[J].兵器装备工程学报,2016,37(6):92-96.YAN H,WANG K,LIU Z L,et al.Reliability analysis of phased-mission system using Markov approach[J].Journal of Ordnance Equipment Engineering,2016,37(6):92-96.
[6]MOORSEL A P A V,SANDERS W H.Transient solution of Markov models by combining adaptive and standard uniformization[J].IEEE Trans.on Reliability,1997,46(3):430-440.
[7]STEWART W J.Introduction of the numerical solution of Markov chains[M].Princeton,NJ:Princeton University Press,1994.
[8]RAUZY A.An experimental study on iterative methods to compute transient solutions of large Markov models[J].Reliability Engineering&System Safety,2004,86(1):105-115.
[9]WANG D Z,TRIVEDI K S.Reliability analysis of phased-mission system with independent component repairs[J].IEEE Trans.on Reliability,2007,56(3):540-551.
[10]LU J M,WU X Y,LIU Y L,et al.Reliability analysis of largephased-mission systems with repairable components based on success-state sampling[J].Reliability Engineering&System Safety,2015,142:123-133.
[11]梁添.基于GPU的稀疏矩阵运算优化研究[D].武汉:华中科技大学,2012.LIANG T.The research on optimizing sparse matrix computation based on GPU[D].Wuhan:Huazhong University of Science and Technology,2012.
[12]王迎瑞,任江勇,田荣.基于GPU的高性能稀疏矩阵向量乘及CG求解器优化[J].计算机科学,2013,40(3):46-49.WANG Y R,REN J Y,TIAN R.Efficient sparse matrix-vector multiplication and CG solver optimization on GPU[J].Computer Science,2013,40(3):46-49.
[13]柳有权,尹康学,吴恩华.大规模稀疏线性方程组的GMRESGPU快速求解算法[J].计算机辅助设计与图形学学报,2011,23(4):553-560.LIU Y Q,YIN K X,WU E H.Fast GMRES-GPU solver for large scale sparse linear systems[J].Journal of Computer-Aided Design&Computer Graphics,2011,23(4):553-560.
[14]闫华,崔谱龙,苏永东,等.基于CUSPARSE的多阶段任务系统可靠性并行计算方法[J].兵器装备工程学报,2018,39(3):121-125.YAN H,CUI P L,SU Y D,et al.Reliability parallel computing method of phased-mission system using CUSPARSE[J].Journal of Ordnance Equipment Engineering,2018,39(3):121-125.
[15]DUGAN J B.Automated analysis of phased-mission reliability[J].IEEE Trans.on Reliability,1991,40(1):45-52.
[16]ALAM M,AL-SAGGAF U M.Quantitative reliability evaluation of repairable phased-mission systems using Markov approach[J].IEEE Trans.on Reliability,1986,R-35(5):498-503.
[17]SOMANI A K,RITCEY J A,AU S H L.Computationally-efficient phased-mission reliability analysis for systems with variable configurations[J].IEEE Trans.on Reliability,1992,41(4):504-511.
[18]WU X Y,YAN H,LI L R.Numerical method for reliability analysis of phased-mission system using Markov chains[J].Communications in Statistics-Theory and Methods,2012,41(21):3960-3973.
[19]ROSS S M.Introduction to probability models[M].11th ed.Waltham,USA:Academic Press,2006.
[20]黎丽容.基于Markov模型的大型PMS任务可靠性分析方法[D].长沙:国防科技大学,2011.LI L R.Method of mission reliability analysis of large PMS based on Markov model[D].Changsha:National University of Defense Technology,2011.
[21]闫华,高黎,王魁,等.大规模多阶段任务系统马尔可夫可靠性模型的存储和计算[J].兵工学报,2016,37(9):1715-1720.YAN H,GAO L,WANG K,et al.Storage and computation of Markov reliability model for large-scale phased-mission system[J].Acta Armamentarii,2016,37(9):1751-1720.