检索结果-内蒙古大学图书馆

作者：李佳佳中国科学院大学

学位级别：博士

近年来计算机体系结构的复杂化和计算平台的多样化，对程序优化产生了不容忽视的影响。通用编译器优化所得性能已经不能满足高性能计算的需求，开发人员越来越多地转向对程序和算法的手工优化。手工优化固然可以取得高性能，但对程序开... 详细信息

近年来计算机体系结构的复杂化和计算平台的多样化，对程序优化产生了不容忽视的影响。通用编译器优化所得性能已经不能满足高性能计算的需求，开发人员越来越多地转向对程序和算法的手工优化。手工优化固然可以取得高性能，但对程序开发者的要求较高，优化工作量大，并且其程序平台通用性较差。这种情况下出现了自动调优技术，它既可以在特定的体系结构上提升程序性能，不同平台之间也表现出很好的移植性。实际应用中非规则计算作为科学计算和社会计算的核心操作之一，其性能和效率对应用起着关键作用。鉴于它的访存密集型特征，浮点性能受限于访存带宽和访存延迟，相对缓慢的内存发展使得非规则计算问题的优化和研究显得尤为重要。\n 本论文针对典型的非规则计算——稀疏矩阵向量乘法，使用自动调优技术进行优化，主要工作包括以下几个方面:\n 本文对稀疏矩阵算法的实际应用层和核心优化层进行分析，发现了两者之间的性能鸿沟，并设计了应用感知和体系结构感知兼顾的自动调优架构。该架构提取实际应用和体系结构的特征，使用学习集对特征参数进行离线提取并构建预测模型，建立统一输入接口的基于模型的自动调优架构，从而找出最优的算法及实现。\n 基于实际应用中稀疏矩阵的非零元素分布模式不尽相同的特点，本文从佛罗里达稀疏矩阵集中提取2000多个矩阵组成学习矩阵集，进行稀疏矩阵向量乘法的性能测试、总结非零元分布规律，从中提取有代表性的稀疏矩阵特征参数。通过对学习集进行规律总结，确定特征参数的阈值，从而构建矩阵的分类模型，建立基于该模型的稀疏矩阵向量乘法自动调优器。相对Intel的MKL数学库，在单核CPU上获得了约50％的性能提升。\n 为提高兼容性和增强准确度，本文引入数据挖掘技术对稀疏矩阵学习集离线建立预测模型，使用该模型进行在线预测并结合运行反馈技术，建立了平台感知和应用感知兼顾的基于数据挖掘的稀疏矩阵向量乘法自动调优器。该自动调优器增加了对体系结构特征的感知，针对特定体系结构离线选择最好的优化方法，输出最优存储格式和最优算法实现。相对MKL多线程数学库，在多核CPU上获得了平均3倍多的加速比。由于数据挖掘技术的使用，该自动调优器具有良好的平台和应用适用性及扩展性。\n 本文在重要的数值求解器之一——代数多重网格算法上验证自动调优器的应用适用性，算法通过调用自动调优器获得了高于20％的性能提升。在Intel的新型Xeon Phi众核处理器和GPU上，验证了其平台适用性和对第三方数学库的良好兼容性。此外，将SpMV自动调优器进行存储格式扩展，说明了调优器良好的算法扩展性。

关键词：稀疏矩阵向量乘法自动调优技术代数多重网格多核处理器数据挖掘

来源：评论

学校读者我要写书评

暂无评论

选择粗化函数优化并行稀疏矩阵向量乘法

引用

中山大学学报（自然科学版） 2012年第5期51卷 50-53页

作者：叶纬材中山大学数学与计算科学学院//广东省计算科学重点实验室广东广州510275

讨论了如何分划稀疏矩阵的非零元素以减少并行矩阵向量乘法的通信代价。通过以粗化函数为工具,统一现有的数据分划方法;提出一种基于行列分划为初解的粗化函数选取方法,在理论上的证明其运行效率与分划质量不逊于一维数据分划方法;实验... 详细信息

讨论了如何分划稀疏矩阵的非零元素以减少并行矩阵向量乘法的通信代价。通过以粗化函数为工具,统一现有的数据分划方法;提出一种基于行列分划为初解的粗化函数选取方法,在理论上的证明其运行效率与分划质量不逊于一维数据分划方法;实验数据表明,该方法产生分划质量超过一维数据分划方法的结果,接近甚至超过二维细粒度方上法的结果。

关键词：选择粗化函数数据分划并行稀疏矩阵向量乘法

来源：评论

学校读者我要写书评

暂无评论

基于GPU对角稀疏矩阵向量乘法的动态划分算法

引用

计算机应用 2024年第11期44卷 3521-3529页

作者：涂进兴李志雄黄建强青海大学计算机技术与应用学院西宁810016 青海省智能计算与应用实验室(青海大学) 西宁810016

在图形处理器(GPU)上实现对角稀疏矩阵向量乘法(SpMV)可以充分利用GPU的并行计算能力,并加速矩阵向量乘法;然而,相关主流算法存在零元填充数据多、计算效率低的问题。针对上述问题,提出一种对角SpMV算法DIA-Dynamic(DIAgonal-Dynamic)... 详细信息

在图形处理器(GPU)上实现对角稀疏矩阵向量乘法(SpMV)可以充分利用GPU的并行计算能力,并加速矩阵向量乘法;然而,相关主流算法存在零元填充数据多、计算效率低的问题。针对上述问题,提出一种对角SpMV算法DIA-Dynamic(DIAgonal-Dynamic)。首先,设计一种全新的动态划分策略,根据矩阵的不同特征进行分块,在保证GPU高计算效率的同时大幅减少零元填充,去除冗余计算量;其次,提出一种对角稀疏矩阵存储格式BDIA(Block DIAgonal)存储分块数据,并调整数据布局,提高GPU上的访存性能;最后,基于GPU的底层进行条件分支优化,以减少分支判断,并使用动态共享内存解决向量的不规则访问问题。DIA-Dynamic与前沿Tile SpMV算法相比,平均加速比达到了1.88;与前沿BRCSD(Diagonal Compressed Storage based on Row-Blocks)-Ⅱ算法相比,平均零元填充减少了43%,平均加速比达到了1.70。实验结果表明,DIA-Dynamic能够有效提高GPU上对角SpMV的计算效率,缩短计算时间,提升程序性能。

关键词：图形处理器对角稀疏矩阵稀疏矩阵向量乘法动态划分共享内存

来源：评论

学校读者我要写书评

暂无评论

面向稀疏矩阵向量乘法的全局共享存储器研究与实现

面向稀疏矩阵向量乘法的全局共享存储器研究与实现

引用

作者：崔剑峰国防科技大学

学位级别：硕士

稀疏矩阵向量乘法(Sparse Matrix Vector Multiplication,Sp MV)长期以来都是一种重要的计算内核,在工程计算、科学计算等领域有着广泛的应用。在近年来火热的人工智能领域,随着神经网络参数的大幅增加,产生了规模庞大的稀疏矩阵,无论... 详细信息

稀疏矩阵向量乘法(Sparse Matrix Vector Multiplication,Sp MV)长期以来都是一种重要的计算内核,在工程计算、科学计算等领域有着广泛的应用。在近年来火热的人工智能领域,随着神经网络参数的大幅增加,产生了规模庞大的稀疏矩阵,无论是从时间效率还是能耗效率上,都对Sp MV提出了更高的优化需求。因此许多研究者聚焦于如何提升Sp MV的计算性能。SpMV是典型的I/O密集型计算任务,访存带宽压力极大,在绝大部分计算平台上访存带宽都是限制其效率的瓶颈所在。片上存储器是缓解访存压力的有效手段之一,采用无缓存结构的片上存储器配合矩阵预处理分块,在处理规整稀疏矩阵计算时,可以获得出色的性能,但实际工程应用中的稀疏矩阵非零元分布更加稀疏且不规则,难以找到合适的分块方式,无缓存结构在这种情况下效率将会大幅降低。M处理器是国防科技大学自主研发的一款高性能多核处理器,其设计需求包括了对卷积神经网络等人工智能计算效率的优化,因此需要提供一种泛用的片上存储器设计,可以为不同模式的稀疏矩阵提供Sp MV性能优化,为了解决这个问题,本文做了如下的工作:(1)分析了涵盖多种实际应用领域的稀疏矩阵,探索其中非零元的分布状况,详细评估了这些矩阵是否拥有较好的数据局部性,从而使得缓存结构能够充分发挥优势。从结果来看,被评估的矩阵都拥有部分规整非零元以及部分随机分布的非零元,适合缓存结构;(2)以软件模拟的方式探索了缓存的设计空间,尝试在开销和性能上找到平衡,并分析了缓存容量、缓存行容量、映射方式和替换策略4个对缓存性能影响较大的参数,确定了合适的数值范围;(3)设计并实现了一种具备精简主控流水线的全局共享存储器(Global Shared Memory,GSM),同时还设计了一种链式存储的缺失缓冲(Miss Buffer),可以灵活地为缺失请求提供存储空间,尽可能减少了缺失缓冲空间不足导致的流水线停顿。在本设计中,GSM处理的所有请求被分为三种类型,通过请求仲裁单元判定优先级,按照统一的流水线程序处理,有效减少了旁路带来的主流水线停顿;(4)对GSM设计进行了模块级验证和逻辑综合,基于设计文档总结了验证功能点列表,搭建基于System Verilog的验证平台,并根据验证需求设计激励信号生成和约束规则。最后配合代码覆盖率分析,找出代码设计漏洞或激励信号的不完善之处,加以修正,最终达到所有功能点验证无误,代码覆盖率100%,面积、功耗与时序均符合设计要求;(5)基于验证平台对本GSM设计的缓存性能进行评估,与采用无缓存结构配合矩阵预处理的Sp MV计算模式的理论性能进行对比,证实本文的设计在面对实际应用中的Sp MV计算任务时,大部分情况下效率更高,且具有更好的适应性。

关键词：稀疏矩阵向量乘法全局共享存储器缓存流水线缺失缓冲数字信号处理高性能计算

来源：评论

学校读者我要写书评

暂无评论

面向稀疏矩阵向量乘法的高带宽利用率FPGA加速器研究

面向稀疏矩阵向量乘法的高带宽利用率FPGA加速器研究

引用

作者：刘博文重庆大学

学位级别：硕士

稀疏矩阵向量乘法(Sp MV)是在图计算、人工智能等领域中广泛使用的算法。因为Sp MV任务性能甚至会影响整个工程应用的性能,所以使用硬件加速Sp MV任务性能是十分有必要的。由于Sp MV中具有并行随机访问的典型特征,使用CPU和GPU来进行加... 详细信息

稀疏矩阵向量乘法(Sp MV)是在图计算、人工智能等领域中广泛使用的算法。因为Sp MV任务性能甚至会影响整个工程应用的性能,所以使用硬件加速Sp MV任务性能是十分有必要的。由于Sp MV中具有并行随机访问的典型特征,使用CPU和GPU来进行加速易于导致缓存缺失,且存在较高的能耗开销。ASIC可以实现高能效的Sp MV加速,但是它硅后配置的灵活性低且研发和制造成本高。相比于CPU和GPU,FPGA具有更高的能效比。相比于ASIC,FPGA开发成本低、灵活性高。综上所述,FPGA是加速Sp MV任务的合适硬件平台。带宽利用率是被广泛使用的基于FPGA的Sp MV任务加速性能评价指标。提高FPGA上Sp MV任务的带宽利用率将面临如何获得较好的压缩比、解决并行随机访问、保证负载平衡和提高通用性四个维度的挑战。目前,大部分FPGA上的Sp MV加速工作都难以平衡以上四个挑战中的每个维度,只能改善其中的两个或者三个维度,导致带宽利用率低。本文提出了Dup Sp MV和Hcsr Sp MV两种解决方案。Dup Sp MV提出了面向Sp MV的基于部分向量复制的高带宽利用率FPGA加速器,它首先使用坐标压缩存储格式实现细粒度划分来保证负载平衡,然后基于部分向量复制设计无读冲突的输入向量缓存解决端口冲突,最后通过矩阵划分改善通用性。为了进一步改善片上存储消耗、降低部分和开销和提升通用性,Hcsr Sp MV提出了基于高压缩稀疏行格式的高带宽利用率FPGA加速器,它首先通过向量跟随在消除随机访问的同时降低片上存储资源消耗,然后简化矩阵划分降低部分和开销,其次通过细粒度划分保证负载平衡,最后通过同或行索引保证压缩比。本文使用FPGA实现Dup Sp MV和Hcsr Sp MV架构开展实验。实验中将本文工作与最先进的工作在压缩格式压缩比、加速器性能和资源利用率方面进行比较。与最先进的工作相比,Dup Sp MV和Hcsr Sp MV分别实现了1.10倍和1.16倍的平均带宽利用率性能加速。并且它们都能够取得较好的压缩比,所使用的硬件资源也在合理的范围内。实验证明本文中两个方案能够在消除并行随机访问造成的端口冲突的同时保证良好的压缩比、负载平衡和通用性。

关键词：稀疏矩阵向量乘法可编程逻辑门阵列带宽利用率

来源：评论

学校读者我要写书评

暂无评论

基于GPU的稀疏矩阵向量乘和凸包算法研究

基于GPU的稀疏矩阵向量乘和凸包算法研究

引用

作者：杨世伟南京邮电大学

学位级别：硕士

图形处理器(Graphics Processing Unit,GPU)在功能和性能上逐步增强,在浮点计算性能和存储带宽已远超CPU。如今GPU不只局限于传统的图形渲染功能,已成为一种流行的通用计算设备。自NVIDIA公司推出计算统一设备架构(Compute Unified Devi... 详细信息

图形处理器(Graphics Processing Unit,GPU)在功能和性能上逐步增强,在浮点计算性能和存储带宽已远超CPU。如今GPU不只局限于传统的图形渲染功能,已成为一种流行的通用计算设备。自NVIDIA公司推出计算统一设备架构(Compute Unified Device Architecture,CUDA),基于CUDA的高性能并行计算已成为各领域的研究热点。本文从传统问题着手,选择典型算法,优化其在GPU上的执行效率。论文主要选择了稀疏矩阵向量乘法(Sparse Matrix-Vector Multiplication,SpMV)和平面点集凸包算法。SpMV常用于挖掘网络数据信息的算法中,对分析网络抗毁性、鲁棒性以及控制谣言传播有重要作用。稀疏矩阵的存储格式对SpMV的性能影响巨大,为了提升其运算性能,对稀疏矩阵存储格式的优化至关重要。凸包算法是计算几何的重要构成,在非图像领域它也广泛应用于信息安全系统。快速凸包算法(QuickHull)是一种典型的分治法,将分治法映射到GPU架构上还没有一般性的高效方法。针对上述问题,本文基于CUDA高性能计算平台,对GPU上的SpMV和凸包算法进行了改进和优化。论文基于分块行列存储(Blocked Row-Column,BRC),提出一种改进的数据结构,用于存储稀疏矩阵以便在GPU上准确高效计算。该存储格式通过一种二维分块策略和一个基于快速分段求和的GPU内核函数,极大减少了BRC格式在并行环境中的计算误差。采用多种真实世界矩阵数据,在GPU上评估该方法,对于SpMV和使用该操作的PageRank中,实验结果表明,本文提出的方法得到的SpMV结果比BRC格式更具有准确性和再现性,同时保持了良好的运算性能。论文基于一种针对现代GPU的并行分治法实现策略,提出一种改进的并行凸包算法,以实现对大规模点集的快速凸包构造。算法通过引入分段的概念,对最初分配的输入数据进行直接操作,并将其划分至不同的分段来执行分而治之的过程。通过设计分段划分和分段压缩这两种数据并行操作,提出基于GPU的并行QuickHull算法。基于几个广泛使用的基准数据集进行了丰富的实验,实验结果表明,与目前最先进的Qhull库相比,本文提出的方法在耗时上明显更少,充分利用了GPU的性能。

关键词：图形处理器计算统一设备架构并行计算稀疏矩阵向量乘法凸包

来源：评论

学校读者我要写书评

暂无评论

GF(2)域上大型稀疏矩阵乘以向量的硬件实现探讨

引用

高性能计算技术 2009年第2期 41-43页

作者：邹友金朱向晖江南计算机研究所无锡214083

GF(2)域上大型稀疏矩阵乘以向量的运算是解复杂线性方程组的重要部分,本文通过定性分析大型稀疏矩阵的存储和运算,从平衡计算与通信两方面.提出了大型稀疏矩阵乘以向量的硬件实现方法,对于进行定量分析具有一定的意义.但其成本随着n增加.

关键词： GF(2)域稀疏矩阵向量乘法硬件实现

来源：评论

学校读者我要写书评

暂无评论

基于HYB格式SpMV在新一代申威架构上的实现与优化

引用

计算机工程与科学 2023年第10期45卷 1754-1762页

作者：王鑫彭健江南大学物联网工程学院江苏无锡214122

稀疏矩阵与稠密向量乘SpMV在高性能计算领域有着广泛的应用。稀疏矩阵因其非零元素分布的稀疏性和不规则性,使得运算的并行化较稠密矩阵难度更大。因此,稀疏矩阵向量乘法的性能优化一直都是高性能计算领域中的研究重点。基于稀疏矩阵的... 详细信息

稀疏矩阵与稠密向量乘SpMV在高性能计算领域有着广泛的应用。稀疏矩阵因其非零元素分布的稀疏性和不规则性,使得运算的并行化较稠密矩阵难度更大。因此,稀疏矩阵向量乘法的性能优化一直都是高性能计算领域中的研究重点。基于稀疏矩阵的HYB存储格式,面向国产新一代申威异构众核处理器SW26010P,设计了一种并行SpMV算法及其性能优化方案。并针对HYB存储格式的阈值选取难点,提出了一种多次迭代最大类间方差的方法,以确定HYB格式的阈值。实验结果表明,相比主核上的串行算法,并行SpMV算法可以获得23.36的平均加速比和34.85的最高加速比。

关键词：申威众核处理器稀疏矩阵向量乘法最大类间方差法并行计算

来源：评论

学校读者我要写书评

暂无评论

稀疏算法的并行优化研究

稀疏算法的并行优化研究

引用

作者：涂登彪中国科学院研究生院

学位级别：博士

稀疏算法是一类广泛存在于各类应用中的核心算法。在目前的高性能计算机系统上，稀疏算法的浮点效率经常不到10％，影响了高性能计算机计算能力的发挥。本文在传统应用领域和新兴应用领域分别选择一个典型的稀疏算法一稀疏矩阵向量乘法(... 详细信息

稀疏算法是一类广泛存在于各类应用中的核心算法。在目前的高性能计算机系统上，稀疏算法的浮点效率经常不到10％，影响了高性能计算机计算能力的发挥。本文在传统应用领域和新兴应用领域分别选择一个典型的稀疏算法一稀疏矩阵向量乘法(SpMV)和介度中心算法(BC算法)，通过这两个算法来研究稀疏算法的并行优化问题。本文的主要工作包括以下几个方面：\n 本文设计了一种精确的细粒度性能分析工具，通过这个工具可以实时读取处理器内部的性能计数器的值，精确获得核心算法导致的处理器事件，如Cache Miss、分支预测、硬件预取等各类事件发生的精确次数。弥补了基于统计的性能分析工具(如：Oprofile)的不足之处。本文详细深入研究了稀疏矩阵向量乘和介度中心算法的性能特征，分析了影响稀疏算法性能的主要因素。通过分析发现，稀疏矩阵向量乘的性能瓶颈主要是由于硬件和算法不匹配导致，介度中心算法的锁同步是影响性能的主要开销。\n 本文在汇编语言层次对稀疏矩阵向量乘法做了细粒度的性能优化研究。通过对指令序列的调整，改变指令序列之间的控制相关和数据依赖关系，优化后的算法在Intel平台和AMD平台分别有20％和5％的性能提高。本文提出了一种具有可变分块结构的稀疏矩阵向量乘算法。在很多应用中，稀疏矩阵具有多个分块模式，传统的分块方法很难为这种稀疏矩阵选择合适的分块大小。本文提出了一种基于矩阵分解的方法，针对这类矩阵做性能优化，优化后的算法在Intel平台和AMD平台分别有35％和45％的性能提高。通过在任务划分和负载平衡上的优化，稀疏矩阵向量乘法的多线程并行优化在主流多核平台上有接近线性的加速比，相对于基于多进程的实现平均有21％的性能提高。\n 本文提出了一种消除锁同步的并行介度中心算法，相对于基于锁同步的最优并行实现，新算法有2～3倍的性能提高。这种消除锁同步的优化方法，可以推广到其他与图相关算法的并行实现中，用来消除锁同步带来的时间开销。本文提出了一种基于稀疏矩阵向量乘的并行介度中心算法，对更大规模网络的分布式并行求解做了初步的探索。

关键词：稀疏算法稀疏矩阵向量乘法介度中心算法局部性开发并行优化浮点效率

来源：评论

学校读者我要写书评

暂无评论

一种用于图形渲染的高性能SpMV专用加速器结构

引用

小型微型计算机系统 2021年第3期42卷 584-588页

作者：邓军勇马青青西安邮电大学电子工程学院西安710121

图形渲染中涉及的几何变换、投影变换、视口变换等需要大量稀疏矩阵向量乘法(Sparse Matrix-Vector Multiplication,SpM V)运算,如何实现SpMV高性能计算成为了图形处理器设计中的关键性问题之一,然而,当前的SpMV运算存在并行度较差,资... 详细信息

图形渲染中涉及的几何变换、投影变换、视口变换等需要大量稀疏矩阵向量乘法(Sparse Matrix-Vector Multiplication,SpM V)运算,如何实现SpMV高性能计算成为了图形处理器设计中的关键性问题之一,然而,当前的SpMV运算存在并行度较差,资源占用较多等问题.为提升硬件运算的性能,本文基于矩阵列向量的线性组合,充分利用数据的并行性,设计了一种专用加速器结构.实验表明,在XC6VLX550T开发板上与其他两种结构相比,速度分别能够提高28%、37%,资源占用率分别减少约48%、18%,应用于图形渲染中的变换操作后,速度分别能够提高28%、30%,资源占用率分别最高减少约48%、60%.

关键词：图形渲染稀疏矩阵向量乘法并行度矩阵列向量的线性组合

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：