一种针对GPU上的油藏数值模拟的高效SpMV

油藏数值模拟和很多其他科学计算问题一样需要求解大型稀疏线性代数方程组.在求解稀疏线性代数方程组的迭代法中,稀疏矩阵向量乘法(SpMV)是影响计算效率的核心函数之一.随着计算机硬件架构异构化,科学计算从单核、多核CPU计算架构逐渐发展到多核CPU+众核加速卡(GPU卡或MIC等)的计算架构.SpMV的实现效率与稀疏矩阵的存储格式及硬件架构关系密切.本文针对油藏模拟中常见的Jacobian矩阵的稀疏模式,利用GPU核心的合并访问和并发计算等特点,结合油藏模拟线性解法器的算法要求,设计了一种BHYB矩阵存储格式及其对应的线程组并行策略.数值实验测得基于该存储格式的SpMV相对串行BCSR格式的SpMV的加速比可达19倍,比cuSPARSE库中效率最高的HYB格式的SpMV快30%到80%.此外,本文所提出的BHYB存储格式对块状矩阵在GPU上的存储以及线程组并行策略对其它GPU并行程序中内核函数的设计和优化能起到一定的借鉴作用.     

二元域大型稀疏矩阵向量乘的FPGA设计与实现

作为Wiedemannn算法的核心部分,稀疏矩阵向量乘是求解二元域上大型稀疏线性方程组的主要步骤。提出了一种基于FPGA的二元域大型稀疏矩阵向量乘的环网硬件系统架构,为解决Wiedemannn算法重复计算稀疏矩阵向量乘,提出了新的并行计算结构。实验分析表明,提出的架构提高了Wiedemannn算法中稀疏矩阵向量乘的并行性,同时充分利用了FPGA的片内存储器和吉比特收发器,与目前性能最好的部分可重构计算PR模型相比,实现了2.65倍的加速性能。     

面向磁流体动力学方程组的异构众核全隐求解器研究

磁流体动力学方程组被广泛应用于受控核聚变装置托卡马克、天体物理、磁流体发电等问题的研究中,其往往具有非线性、多尺度、多物理等特征,大规模数值难度较大.目前国际上对不可压缩流体问题的大规模数值求解主要采用全隐或半隐方法,但都是在同构的超级计算机而不是目前主流的异构众核系统上进行计算.论文面向国产神威"太湖之光"超级计算机,开展面向磁流体动力学方程组的异构众核全隐求解器研究.针对Newton-Krylov这类全隐求解器,提出了面向申威26010众核处理器的异构众核并行算法,并对其核心函数开展了众核并行和优化.对核心函数稀疏矩阵向量乘采用Matrix Free的方法来提升性能,对稀疏三角求解采用基于几何信息的异构众核并行算法,针对其访存密集的特点提出了存储格式、数据读取与计算依赖分离、核间寄存器通信等多种优化方法,对非线性残差计算等stencil类计算及10多个向量函数进行了异构众核并行,该异构众核并行算法可被其它应用软件重用.论文采用二维磁场重联问题进行测试,实验结果表明16进程时加速比可达13.6倍,能够支持高分辨率长时间模拟,并准确捕捉磁场重联现象.另外整体并行扩展性已经达到53万核,强可扩展性并行效率达到了33.8%,弱可扩展性并行效率达到了80.7%.     

一类大规模稀疏矩阵特征问题求解的并行算法

本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率,设计了负载平衡的行划分方式,实现了计算和通信重叠的稀疏矩阵重排序方法,通过预处理减少计算过程中各进程间消息传递的通信量.另外,基于多核处理器高性能并行计算,实现了MPI和细粒度(线程级)OpenMP混合并行算法.在深腾7800并行计算机上对并行算法进行了测试,结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性,适合大规模稀疏特征问题的求解.     

基于神威·太湖之光的非结构网格众核优化技术

为解决高性能计算中的非结构网格离散访存问题,以神威·太湖之光国产超级计算机为平台,根据异构众核处理器SW26010的体系结构特点,提出一种基于排序思想的通用众核优化算法,以减少非结构网格计算中的随机访存。基于网格划分原理,在O(n)时间内对生成的稀疏矩阵非零元素进行并行重排序。采用一种内部映射方式对计算向量实现扩展或变换,将细粒度访存转化为无写冲突的粗粒度访存。对多个实际应用算例的通量计算进行众核优化,结果表明,相比主核上的串行算法,该算法能够获得平均10倍以上的加速效果。     

GPU加速不完全Cholesky分解预条件共轭梯度法

不完全 Cholesky 分解预条件共轭梯度（incomplete Cholesky factorization preconditioned conjugate gradient ,ICCG）法是求解大规模稀疏对称正定线性方程组的有效方法。然而ICCG法要求在每次迭代中求解2个稀疏三角方程组,稀疏三角方程组求解固有的串行性成为了ICCG法在GPU上并行求解的瓶颈。针对稀疏三角方程组求解,给出了一种利用GPU 加速的有效方法。为了增加稀疏三角方程组求解在GPU上的多线程并行性,提出了对不完全Cholesky分解产生的稀疏三角矩阵进行分层调度（level scheduling ）的方法。为了进一步提高稀疏三角方程组求解的并行性能,提出了在分层调度前通过近似最小度（approximate minimum degree ,AMD）算法对系数矩阵进行重排序、在分层调度后对稀疏三角矩阵进行层排序的方法,降低了分层调度过程中产生的层数,优化了稀疏三角方程组求解的GPU内存访问模式。数值实验表明,与利用NVIDIA CUSPARSE实现的ICCG法相比,采用上述方法性能可以获得平均1倍以上的提升。     

Matlab的图形处理器并行计算及其在拓扑优化中的应用

针对传统并行计算方法实现结构拓扑优化快速计算的硬件成本高、程序开发效率低的问题,提出了一种基于Matlab和图形处理器(GPU)的双向渐进结构优化(BESO)方法的全流程并行计算策略。首先,探讨了Matlab编程环境中实现GPU并行计算的三种途径的优缺点和适用范围;其次,分别采用内置函数直接并行的方式实现了拓扑优化算法中向量和稠密矩阵的并行化计算,采用MEX函数调用CUSOLVER库的形式实现了稀疏格式有限元方程组的快速求解,采用并行线程执行(PTX)代码的方式实现了拓扑优化中单元敏度分析等优化决策的并行化计算。数值算例表明,基于Matlab直接开发GPU并行计算程序不仅编程效率高,而且还可以避免不同编程语言间的计算精度差异,最终使GPU并行程序可以在保持计算结果不变的前提下取得可观的加速比。     

并行矩阵乘的光化学反应模拟研究

在Linux环境下,为缩短激光诱导光化学反应模拟运行时间,针对光化学反应模拟中力矩阵的稀疏特征,将力矩阵进行分块划分,采用优化的行列分解算法对分块矩阵进行并行化,运用OpenMP实现光化学反应力计算并行化。实验结果表明,在500个C原子参与运算的情况下,单步计算时间缩短到优化前计算时间的10-2数量级,在十六核处理器上获得了十四倍的加速比和80%以上的效率,为高效模拟大分子体系光化学反应提供平台。     

基于GPU的稀疏矩阵Cholesky分解

稀疏矩阵Cholesky分解是求解大规模稀疏线性方程组的核心算法,也是求解过程中最耗时的部分.近年来,一系列并行算法通过图形处理器(GPU)获得了显著的加速比,然而,由于访存的不规则性以及任务间的大量数据依赖关系,稀疏矩阵Cholesky分解算法在GPU上的计算效率很低.文中实现了一种新的基于GPU的稀疏矩阵Cholesky分解算法.在数据组织方面,改进了稀疏矩阵超节点数据结构,通过超节点合并和分块控制计算粒度;在计算调度方面,将稀疏矩阵Cholesky分解过程映射为一系列的数据块任务,并设计了相应的任务生成与调度算法,在满足数据依赖性的前提下提高任务的并行性.实验结果表明,该算法能够显著提高稀疏矩阵Cholesky分解算法在GPU上的实现效率,在单个GPU上获得了相对4核CPU平台2.69~3.88倍的加速比.     

马尔科夫链蒙特卡洛算法并行化设计与性能分析

马尔科夫链蒙特卡洛MCMC(Markov Chain Monte Carlo)算法广泛应用于地球系统模型中参数不确定性分析和模拟。由于地球环境科学数据的高维度、大容量特性,迫切需求高性能的MCMC算法满足应用需求。采用数据分治法实现该算法的多核并行化。利用静态和动态分配策略将算法中的多个输入链分配到各CPU;独立计算并通过共享内存实现进程间通信;主进程回收各单元计算结果,合成最终的马尔可夫链输出矩阵。采用控制变量法分析不同样本和马尔可夫链数量下的算法加速情况。结果表明在计算规模较大、动态负载均衡的条件下易于获得较好的加速比,在4个CPU以内时效果显著,之后随着CPU增加加速效果出现波动或趋于稳定。研究表明并行化MCMC能够利用多核CPU硬件设施获得加速效果,更多核数的加速性能存在进一步优化的空间。     

SOPC技术在计算全息中的应用

基于计算全息术的三维动态实时显示受到越来越多的关注, 而制约其发展的一大难题是其运算速度. 针对这一问题, 本文提出基于SOPC(System On Programmable Chips)技术的计算全息硬件加速系统, 使多片FPGA硬件进行分块并行运算. 为了实现这一目标, 每片FPGA运算单元必须独立具备数据传输与计算全息算法加速两种功能. 在已有计算全息算法加速模块的基础上, 搭载NIOS II软核并移植uC/OS II操作系统及LWIP以太网协议栈. NIOS II软核作为FPGA的主控, 控制计算全息算法加速模块及以太网口的数据传输, 实验结果证明该方法为实现计算全息三维动态实时显示提供了一种新的思路.     

基于神威·太湖之光的非结构网格计算加速算法

在国产异构众核平台神威·太湖之光上的非结构网格计算具有稀疏存储、离散访存、数据依赖等特点,严重制约了众核处理器的性能发挥。为解决稀疏存储和离散访存问题,提出一种N阶对角染色算法,以有效平衡主从核计算并利用从核将全局访存转化为LDM访问。针对数据依赖造成的计算竞争问题,采用自适应和无依赖的任务划分方法,避免并行计算时的数据冲突。为对处理器架构和非结构网格计算进行优化,采用主核与从核异步并行的方式,差异化使用主从核以充分利用硬件资源,同时,取消处理器提供的寄存器通信机制,降低从核阵列的同步开销同时便于扩展到新一代神威平台。此外,使用计算访存异步重叠技术来充分隐藏访存延迟。利用SpMV、Integration、calcLudsFcc算子进行实验,结果表明,相比主核实现,组合加速算法在不同算例规模下平均取得了10倍的加速效果,加速比最高可达24倍,N阶对角染色算法相比非染色分块算法取得了超过5.8倍的性能加速,有效提升了数据局部性和计算并行度。该算法对有依赖关系的计算冲突算子同样具有良好的加速性能,验证了自适应和无依赖任务划分方法的有效性。     

面向人脸检测MTCNN网络的加速硬件设计

为加快深度学习人脸检测算法MTCNN(multi-task convolution neural network)的推理速度,满足许多应用场合检测的实时性的要求,基于Xilinx FPGA ZCU102开发板设计针对MTCNN专门优化的卷积和全连接加速硬件.该加速硬件不仅适用于MTCNN网络,其它神经网络推理算法也可以...     

Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors

This paper studies the parallel solution of large-scale sparse linear least squares problems on distributed-memory multiprocessors. The key components required for solving a sparse linear least squares problem are sparse QR factorization and sparse triangular solution. A block-oriented parallel algorithm for sparse QR factorization has already been described in the literature. In this paper, new block-oriented parallel algorithms for sparse triangular solution are proposed. The arithmetic and communication complexities of the new algorithms applied to regular grid problems are analyzed. The proposed parallel sparse triangular solution algorithms together with the block-oriented parallel sparse QR factorization algorithm result in a highly efficient approach to the parallel solution of sparse linear least squares problems. Performance results obtained on an IBM Scalable POWERparallel system SP2 are presented. The largest least squares problem solved has over two million rows and more than a quarter million columns. The execution speed for the numerical factorization of this problem achieves over 3.7 gigaflops per second on an IBM SP2 machine with 128 processors.     

动态重构硬件加速中的性能开销建模

近年来,随着可重构计算方法和可重构硬件特性的不断演进,基于FPGA动态部分重构技术构建运行时可重构加速器已经成为解决传统加速器设计中硬件资源限制问题的重要途径.然而,区别于传统静态重构加速器,FPGA的动态重构开销是影响硬件加速整体性能的重要因素,而目前尚缺少能够在可重构硬件设计的早期阶段进行动态重构开销精确估算的相关...     

布尔矩阵乘的分布式异构并行优化

布尔多项式求解是当今密码代数分析中的关键步骤,F4算法是布尔多项式求解的高效算法。分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中布尔矩阵乘这一耗时的计算步骤,设计并实现了分布式异构(CPU+MIC)并行算法。布尔矩阵相对于普通矩阵主要体现在矩阵元素取值区间不一样上,由于布尔矩阵元素(0,1)导致矩阵乘操作的特殊性,普通矩阵乘的优化方法不能很好地满足布尔矩阵乘的需求。分别从布尔矩阵的存储、OpenMP多线程组织、访存、任务划分和调度等方面进行了性能优化,实现了布尔矩阵乘的分布式异构并行算法。通过随机生成布尔矩阵测试,优化后的分布式异构并行程序相较于分布式同构并行程序达到了2.45的加速比,体现了良好的性能提升。     

自适应SSDA图像匹配并行算法设计与实现

为了充分利用多核处理器的硬件资源和计算能力来提高图像匹配应用的实时性,通过对自适应阈值SSDA图像匹配算法原理的分析,基于任务分解的多核并行编程模式思想,设计了一种自适应阈值SSDA图像匹配并行算法,并在多核计算机上采用OpenMP模型编程实现该并行算法,同时还进行了相关的代码优化。实验结果表明,优化后的并行算法在保持匹配算法精度的同时大大提高了匹配速度和多核利用率,取得了良好的效果。     

TLP-LDPC: Three-Level Parallel FPGA Architecture for Fast Prototyping of LDPC Decoder Using High-Level Synthesis

Low-Density Parity-heck Codes (LDPC) with excellent error-correction capabilities have been widely used in both data communication and storage fields, to construct reliable cyber-physical systems that are resilient to real-world noises. Fast prototyping field-programmable gate array (FPGA)-based decoder is essential to achieve high decoding performance while accelerating the development process. This paper proposes a three-level parallel architecture, TLP-LDPC, to achieve high throughput by fully exploiting the characteristics of both LDPC and underlying hardware while effectively scaling to large-size FPGA platforms. The three-level parallel architecture contains a low-level decoding unit, a mid-level multi-unit decoding core, and a high-level multi-core decoder. The low-level decoding unit is a basic LDPC computation component that effectively combines the features of the LDPC algorithm and hardware with the specific structure (e.g., Look-Up-Table, LUT) of the FPGA and eliminates potential data conflicts. The mid-level decoding core integrates the input/output and multiple decoding units in a well-balancing pipelined fashion. The top-level multi-core architecture conveniently makes full use of board-level resources to improve the overall throughput. We develop an LDPC C++ code with dedicated pragmas and leverage HLS tools to implement the TLP-LDPC architecture. Experimental results show that TLP-LDPC achieves 9.63 Gbps end-to-end decoding throughput on a Xilinx Alveo U50 platform, 3.9x higher than existing HLS-based FPGA implementations.     

半导体器件模拟线性方程组求解算法研究

在半导体器件模拟程序中，需要求解线性方程组，直接法在矩阵规模较大时逐渐暴露出对存储空间要求过大的缺点，从而导致运算速度的下降，而采用迭代算法，如广义最小偏差算法（GMRES）法，在处理大规模稀疏矩阵时对存储空间要求较小，有效地解决了存储空间不足的问题，并能显著地提高运算速度，迭代算法有望成为新一代器件模拟软件的主流数值计算方法。     

并行高斯消去法在云计算平台上的研究

为了解决串行部分选主元的高斯消去算法不能充分利用多核处理器的问题，提出并实现了并行多线程的部分选主元的高斯消去算法，并将整个算法进行了分析和优化，使数据的存储布局和算法的访存模式匹配，从而大幅提高了程序的性能。通过对本地Linux服务器以及美国亚马逊EC2云的多种平台上的实验结果的比较和分析，确定了部分选主元的高斯消去算法受缓存影响较大，所以在CPU和内存/缓存配置较为均衡的平台上运行性能最好。文中展现了一种高效率、扩展性好的多线程并行部分选主元的高斯消去算法以及将一般性串行算法进行并行化和优化的方法。