【作者】 陈勇；

【导师】 金海；

【作者基本信息】 华中科技大学 ， 计算机系统结构， 2020， 博士

【摘要】 电力系统分析是电力系统规划设计、调度控制的决策基础和科学依据,是保障电力系统安全稳定运行的基本手段之一。电力系统分析以数字模型代替实际电力系统,用数值计算方法对系统的运行特性进行实验和研究。随着电力系统规模的增大,系统元件模型日益复杂,对系统机理研究越来越精细,电力系统分析的规模和复杂度空前增长,迫切需要利用并行计算技术提升电力系统分析应用效率。与此同时,高性能计算硬件技术得到飞速发展,以GPU为代表的专用加速器成为最具吸引力的高性能处理部件。利用CPU-GPU异构体系结构所具备的大规模并行性来提升电力系统分析效率成为了当前的一个研究热点。电力系统分析应用在CPU-GPU异构平台上的并行实现常面临两方面的挑战,一是在节点层面(单个节点内部),必须充分利用异构体系结构特点深入挖掘算法多层次并行性,高效利用GPU的存储层次,或者容易造成应用性能低下;二是在系统层面(节点和节点之间),随着GPU集群规模的扩大,异构系统难以编程的问题日益突出,需要为开发者提供简单高效的异构并行编程模型和方法。针对以上挑战,选取电力系统稳态分析中最为常用的潮流分析、静态安全分析、调度计划静态安全校核等三类应用,结合CPU-GPU异构平台,对应用程序并行化中的若干异构并行技术进行深入研究。电力系统潮流分析问题是通过牛顿-拉夫逊法转化为稀疏线性方程组的迭代求解,其中稀疏矩阵分解是求解过程中最为耗时的部分。为消除稀疏矩阵运算带来的计算和访存不规则性,在节点层面提出一种基于CPU-GPU的大规模稀疏矩阵分解多波前并行方法,将稀疏矩阵的分解转化为大量稠密矩阵运算任务在CPU-GPU上的高效并行执行。针对节点内多任务稠密矩阵乘法运算,在CPU-GPU间设计基于阈值判断的最优化任务划分模型,利用多线程模型和无锁环形任务队列实现了任务协同执行和数据交换机制,提升了CPU-GPU多任务整体执行性能;在GPU内提出设备内核函数空间划分的任务抢占式多执行单元(Task Execution Unit,TEU)并行处理方法,该方法实现了一种全新的任务线程组织方式,支持多个矩阵乘法运算在一个内核函数中并行执行,同时在执行中进一步对矩阵乘法运算进行多层次存储访问优化,显著提升了GPU计算吞吐率。实验结果表明,在2万条母线规模电网算例上,基于以上技术实现的CPU-GPU潮流分析并行程序,相较于CPU多线程程序达到了3.95倍的加速比。电力系统灵敏度分析法是静态安全分析中最为常用的一种方法。针对GPU灵敏度法低维矩阵运算带来的线程空转所造成的计算效率不高的问题,在节点层面从提高线程并行度和计算强度的角度设计GPU低维矩阵运算算法线程映射策略,利用横向和纵向合并技术提出低维矩阵乘法、低维矩阵求逆、低维矩阵向量乘法各自在GPU上的高效合并并行执行方法,在执行过程中为提升GPU访存效率实现了片上内存数据重用、全局存储器访问合并、存储体冲突消除、寄存器分块等访存优化。实验结果表明,在6000条母线规模电网算例上,基于以上技术实现的GPU灵敏度法静态安全分析并行程序,相较于CPU多线程程序达到了1.8～1.9倍的加速比。电力系统调度计划静态安全校核多采用MPI(Message Passing Interface)、Open MP(Open Multi-Processing)、CUDA(Compute Unified Device Architecture)等编程模型混合的方式实现多算例任务在GPU集群上的并行执行。为了克服混合编程模型可编程性和性能方面的不足,在系统层面基于全局数组(Global Arrays,GA)设计与实现一种异构并行内存编程模型CUDA-GA,包括GA异构接口扩展、基于可靠UDP通信机制的底层通信库优化、异构并行执行框架等实现,并利用CUDA-GA以任务预分配法实现了调度计划静态安全校核在GPU集群上的并行算法。实验结果表明,CUDA-GA可以有效提升异构程序的可编程性和运行性能,基于CUDA-GA实现的调度计划静态安全校核并行程序,相较于MPI+CUDA方法整体计算用时缩短了20%～30%。综上所述,围绕电力系统稳态分析应用的计算效率和可编程性,提出了基于CPU-GPU的稀疏矩阵分解多波前并行方法、GPU低维矩阵运算并行方法、以及异构并行内存编程模型等,实现了电力系统稳态分析高效异构并行算法。研究成果在国家电网实际生产运行中落地应用,为保障电网安全稳定运行发挥了重要作用。更多还原

【Abstract】 Power system analyses are an essential part of electrical power system planning,design and dispatch control.Many experiments and research can be conducted based on power system analysis method.The rapid development of electric power systems with the advancements made in new technologies and new devices has brought about unseen complexity to power system analysis.Parallel computing became one of promising methods to improve power system analysis efficiency.Graphics Processing Units(GPUs)are now ubiquitous and provide unprecedented computational power for scientific applications.How to boost up the powerful GPU parallel processing capability to solve power system analysis problem has become a hot research topic.However,the architecture complexity of the hybrid system poses many challenges to the parallel algorithms designed on the infrastructure.First,it must exploit multi-level parallelism to improve the efficiency of programs on CPU-GPU node,or it will degrade program performance,and hardware resources aren’t fully utilized.Secondly,current programing model is substantially difficult to use on massive GPU cluster.It is necessary to provide unified and easy-to-use programming model on the heterogeneous parallel computing systems for programmers.To address the above challenges,this thesis discusses key technologies of heterogeneous parallel computing based on power system steady-state analysis applications which include power flow analysis,static state security analysis and static security checking of dispatching plans.Newton-Raphson method is a common power flow solver.The heavy computational part of the method is to solve the sparse linear equations.The time-consuming part of large sets of linear equations is often the LU factorization of sparse,symmetric Jacobian matrix.The performance of sparse Jacobian matrix decomposition decreases due to irregular compute and memory access pattern.This thesis introduces a parallel multifrontal solver algorithm on GPU.Parallel multifrontal sparse matrix factorization method turns the sparse problem into a tree of dense matrix operations which are suitable for massively parallel multi-core CPUs and GPUs.This thesis proposes a hybrid CPU-GPU task allocation model and task scheduling policy.Many Task Execution Units(TEUs)are created and can execute multiple GEMM tasks in parallel in a kernel of GPU.And some important optimization methods such as the multi-level memory access patterns,the overlap of communication with computation are used.The new parallel power flow solver on hybrid CPU-GPU system fully exploits all available compute resources of a heterogeneous system and achieves a speedup of 3.95 on MATPOWER case24906 when compared to a multifrontal multithreaded power flow solver on CPU.Contingency analysis method is in common use for power system static security assessment application.Contingency analysis involves low-rank matrix-matrix multiplication,low-rank matrix inversion and low-rank matrix-vector multiplication.Current algorithms for low-rank matrix operations often suffer from poor GPU utilization.This thesis proposes a novel low-rank matrix-matrix combined multiplication algorithm,a novel low-rank matrix inversion algorithm by partitioning,and a novel low-rank matrix-vector combined multiplication algorithm.The GPU-optimized data structures and scheduling policy for threads are designed to improve load balancing and exploit thread level parallelism on GPU.Data reuse,access coalescing to global memory,eliminating share-memory bank conflict and some other memory access optimization techniques are used to effectively improve the efficiency of data access and occupancy rate of GPUs.So that the new static security assessment algorithm gets a speedup of 1.8～1.9 on hybrid CPU-GPU platforms compared to CPU on MATPOWER case6240.Static Security Checking(SSC)of large grid’s dispatching plans aims to assess the system steady state performance for all possible postulated contingencies.It is different from the above-mentioned algorithms of power flow calculation and static security assessment on one hybrid CPU-GPU node.SSC applications run on the GPU clusters.Both shared-memory and message-passing architectures are the conventional shared-address space programming models on large-scale,distributed-memory multiprocessors.Those programming models are difficult to use on massive GPU cluster for programmers.We argue that the transparent,global-view access to arrays data distributed across the memories of a distributed system is a better choice for programming on a heterogeneous system.This thesis implements a library based on PGAS programming model on GPU cluster –CUDA-GA,which extends GA library for a hybrid CPU-GPU system.It extends Com Ex/ARMCI library with reliable UDP messaging,and builds a distributed-executor framework on GPU cluster.A novel static security check algorithm of large grid’s dispatching plans has been developed with CUDA-GA and saves 20%～30% calculation time on GPU compared to MPI+CUDA.In summary,this thesis studies multifrontal LU factorization of sparse symmetric Jacobian matrix,low-rank matrix operations,heterogeneous PGAS programming model on CPU-GPU platform and implements power system steady-state analysis algorithms on hybrid CPU-GPU system.These technologies greatly improve the performance of the power system steady-state analysis applications and are of great significance for keeping the power grid stable.更多还原