首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 109 毫秒
1.
稀疏矩阵向量乘(SpMV)采取压缩行存储格式的算法性能非常差,而寄存器分块算法可以使得数据尽量在靠近处理器的存储层次中访问而提高性能.利用RAM(h)模型进行分析和比较不同算法形式的存储访问复杂度,可以比较两种算法的优劣.通过RAM(h)分析SpMV两种实现形式的存储访问复杂度,同时在奔腾四平台上,测试了7个稀疏矩阵的SpMV性能,并统计了这两种算法中L1,L2,和TLB的缺失率,实验结果与模型分析的数据一致.  相似文献   

2.
稀疏矩阵向量乘法(sparse matrix vector multiplication,SpMV)是科学和工程领域中重要的核心子程序之一,也是稀疏基本线性代数子程序(basic linear algebra subprograms,BLAS)库的重要函数.目前很多SpMV的优化工作在不同程度上获得了性能提升,但大多数优化工作针对特定存储格式或一类具有特定特征的稀疏矩阵缺乏通用性.因此高性能的SpMV实现并没有广泛地应用于实际应用和数值解法器中.另外,稀疏矩阵具有众多存储格式,不同存储格式的SpMV存在较大性能差异.根据以上现象,提出一个SpMV的自动调优器(SpMV auto-tuner,SMAT).对于一个给定的稀疏矩阵,SMAT结合矩阵特征选择并返回其最优的存储格式.应用程序通过调用SMAT来得到合适的存储格式,从而获得性能提升,同时随着SMAT中存储格式的扩展,更多的SpMV优化工作可以将性能优势在实际应用中发挥作用.使用佛罗里达大学的2 366个稀疏矩阵作为测试集,在Intel上SMAT分别获得9.11GFLOPS(单精度)和2.44GFLOPS(双精度)的最高浮点性能,在AMD平台上获得了3.36GFLOPS(单精度)和1.52GFLOPS(双精度)的最高浮点性能.相比Intel的核心数学函数库(math kernel library,MKL)数学库,SMAT平均获得1.4~1.5倍的性能提升.  相似文献   

3.
稀疏矩阵存储格式中的稀疏矩阵向量乘(SpMV)计算效率低下,且分块行列(BRC)存储格式的计算结果缺少再现性和确定性。为此,提出一种改进的BRCP存储格式。采用不同的二维分块策略,根据矩阵各行非零元素分布的统计特性自适应调节分块参数,提高SpMV在GPU平台上的并行性,并设计基于快速分段求和算法的GPU内核函数,保证计算结果的确定性及其在不同GPU平台上的再现性。实验结果表明,BRCP存储格式具有较高的计算效率,相比BRC存储格式可减少并行环境中的SpMV计算误差,并提高PageRank排序的准确率。  相似文献   

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

5.
本文研究大型稀疏矩阵向量乘法的并行化措施。主要包括高效的存储方法,核心代码用汇编语言编写,循环展开,宏任务和微任务方式,重排序和分块技术。根据实际问题的需要,分别给出了一般稀疏矩阵和对称正定带状矩阵向量乘法内核子程序,ELLPACK,ITPAKC及LINPACK等库和许多应用程序可直接调用它们。  相似文献   

6.
基于GPU的稀疏矩阵向量乘优化   总被引:1,自引:0,他引:1  
针对稀疏矩阵运算难以发挥图形处理器的强大运算能力的现状,基于图形处理器的统一计算架构,在线程映射、数据复用等方面研究了一系列并行计算优化方法,从而完成了一种行压缩存储表示下的稀疏矩阵向量乘并行算法.这些优化方法包括:(1)利用Warp内线程天然同步特性,Half-warp完成结果向量一个元素的计算;(2)取整读取数据,实现合并访问;(3)输入向量放入纹理存储器,数据复用;(4)申请分页锁定内存,加速数据传输;(5)使用共享存储器,加速数据存取.实验分析表明,提出的各种手段起到了优化的作用.与已有的CUDPP和SpMV library中的CSR-vector算法相比,本算法获得了更高的存储器带宽和浮点运算吞吐量;整体性能比CPU串行执行版本快了3倍以上.  相似文献   

7.
HPCG基准测试程序是一种新的超级计算机排名度量标准.该测试基准主要用于衡量超级计算机解决大规模稀疏线性系统的能力,更贴近实际应用,近年来广受关注.基于国产超级计算机研究异构众核并行HPCG软件具有非常重要的意义,其不仅可以提升国产超级计算机HPCG的排名,还对很多应用提供了并行算法、优化技术等方面的参考.面向某国产复杂异构超级计算机开展研究,首先采用了分块图着色算法对HPCG进行并行,并提出一种适用于结构化网格的图着色算法.该算法并行性能高于传统的JPL、CC等算法,且着色质量高,运用于HPCG后,迭代次数减少了3次,整体性能提升了6%.分析了复杂异构系统各个部件传输的开销,提出一套更适用于HPCG的任务划分方法,并从稀疏矩阵存储格式、稀疏矩阵重排、访存等角度开展了细粒度的优化.在多进程计算时,还采用内外区划分算法将核心函数SpMV、SymGS中的邻居通信操作进行了隐藏.最终整机测试时,性能达到了国产超级计算机峰值性能的1.67%,与单节点相比,整机弱可扩展性并行效率达到了92%.  相似文献   

8.
刘芳芳  杨超  袁欣辉  吴长茂  敖玉龙 《软件学报》2018,29(12):3921-3932
世界首台峰值性能超过100P的超级计算机——神威太湖之光已经研制完成,该超级计算机采用了国产申威异构众核处理器,该处理器不同于现有的纯CPU,CPU-MIC,CPU-GPU架构,采用了主-从核架构,单处理器峰值计算能力为3TFlops/s,访存带宽为130GB/s.稀疏矩阵向量乘SpMV(sparse matrix-vector multiplication)是科学与工程计算中的一个非常重要的核心函数,众所周知,其是带宽受限型的,且存在间接访存操作.国产申威处理器给稀疏矩阵向量乘的高效实现带来了很大的挑战.针对申威处理器提出了一种CSR格式SpMV操作的通用异构众核并行算法,该算法从任务划分、LDM空间划分方面进行精细设计,提出了一套动静态buffer的缓存机制以提升向量x的访存命中率,提出了一套动静态的任务调度方法以实现负载均衡.另外还分析了该算法中影响SpMV性能的几个关键因素,并开展了自适应优化,进一步提升了性能.采用Matrix Market矩阵集中具有代表性的16个稀疏矩阵进行了测试,相比主核版最高有10倍左右的加速,平均加速比为6.51.通过采用主核版CSR格式SpMV的访存量进行分析,测试矩阵最高可达该处理器实测带宽的86%,平均可达到47%.  相似文献   

9.
稀疏矩阵向量乘(SpMV)是科学计算中常用的内核之一,其运行速率跟非零元分布相关.针对对角线稀疏矩阵,提出了压缩行片段对角(compressed row segment diagonal,CRSD)存储格式.它利用“对角线格式”有效描述矩阵的对角线分布,区别于以往通用的计算方法,CRSD通过对给定应用的对角线稀疏矩阵采样再进行特定的优化.并且在软件安装阶段,通过自适应的方法选取适合具体运行平台的最优SpMV实现.在CPU端进行多线程并行化实现时,自适应调优过程中收集的信息还被用于线程间任务划分,以实现负载平衡.同时完成CRSD存储格式在GPU端的实现,并根据GPU端计算与访存的特点进行优化.实验结果表明:在Intel和AMD的多核平台使用相同线程数的情况下,与DIA相比,使用CRSD的加速比可以达到2.37X(平均1.7X);与CSR相比,可以达到4.6X(平均2.1X).  相似文献   

10.
HPCG基准测试程序是一种新的超级计算机排名度量标准.该测试基准主要用于衡量超级计算机解决大规模稀疏线性系统的能力,更贴近实际应用,近年来广受关注.基于国产超级计算机研究异构众核并行HPCG软件具有非常重要的意义,其不仅可以提升国产超级计算机HPCG的排名,还对很多应用提供了并行算法、优化技术等方面的参考.本文面向某国产复杂异构超级计算机开展研究,首先采用了分块图着色算法对HPCG进行并行,并提出一种适用于结构化网格的图着色算法,该算法并行性能高于传统的JPL、CC等算法,且着色质量高,运用于HPCG后,迭代次数减少了3次,整体性能提升了6%.本文还分析了复杂异构系统各个部件传输的开销,提出一套更适用于HPCG的任务划分方法,并从稀疏矩阵存储格式、稀疏矩阵重排、访存等角度开展了细粒度的优化.另外在多进程计算时,还采用了内外区划分算法将核心函数SpMV、SymGS中的邻居通信操作进行了隐藏.最终整机测试时,性能达到国产超级计算机峰值性能的1.67%,相比单节点,整机弱可扩展性并行效率达到了92%.  相似文献   

11.
为提高生物序列比对算法的性能和效率,提出一种异构处理平台下可移植的大规模生物序列比对算法及其优化方法.通过改变原有Smith-Waterman算法的计算流程和数据依赖关系,增加序列比对的并行性;通过改变存储器布局后使用向量数据类型,提高全局存储器的带宽利用率;通过增加偏移量改变存储器模块的映射方式,避免模块访问冲突,提高局部存储器的使用效率.实验结果表明,优化后的生物序列比对性能提升了近100倍.  相似文献   

12.
Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.  相似文献   

13.
建立一个适用于整数序列排序的数据分配模型,在多核计算节点组成的异构机群上设计通信高效的整数序列并行算法。所提出的数据分配模型依据机群中各节点不同的计算能力、通信速率和存储容量,动态计算出调度分配给各节点的数据块的大小以平衡各个节点的负载。所设计的并行排序算法利用整数序列的特性,主节点采取两轮分发数据与接收结果的方法,从节点运用分桶打包方式返回有序的整数子序列给主节点,主节点采用桶映射方法将各个有序子序列直接整合成最终有序序列,以减少需要耗费较多通信时间的数据归并操作。分析与实验测试结果表明,给出的多核机群上的整数序列并行排序算法高效,具有良好的可扩展性。  相似文献   

14.
用C语言编写DSP软件时,优化设计尤为重要。近年来提出了多种针对DSP代码生成阶段的偏移分配优化算法,这些算法通过调整局部变量在存储器中的布局来提高变量地址的计算效率。该文提出一种将微粒群算法与遗传算法相结合的算法(类PSO算法),对变量访问序列中各变量地址的分配进行优化,使计算地址所需的代码数量最小,从而减少程序的运行时间,提高DSP的工作效率。  相似文献   

15.
基于散列和归并技术的有效并行排序方法   总被引:1,自引:1,他引:1       下载免费PDF全文
本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法:将长度为n的待排序数据划分成p个长度为n/p的子序列,引入散列技术并行地对这p个子序列的数据进行二次散列排序,这一阶段所需的平均时间为O(n/p);最后并行地将p个有序子序列归并成一个长度为n的有序序列,归并阶段所需的时间为O(n-n/
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。  相似文献   

16.
陈敏  李徽翡 《计算机工程》2009,35(20):71-72
针对FP-Growth算法面临大规模数据库时空效率不高的问题,提出一种面向计算机集群的并行算法。采用投影方法直接寻找频繁项的条件数据库,将挖掘条件数据库的工作分化成若干独立的子任务,分配到集群中的节点上并行实现,由中央节点汇总结果并输出。结果证明,该算法不仅能够提高计算速度,解决数据库规模过大时内存溢出的情况,且具有良好的延展性。  相似文献   

17.
DNA序列拼接的分布式并行处理   总被引:1,自引:1,他引:1  
针对分布式存储环境,本文提出一种DNA序列拼接的并行算法,分别对序列拼接中OVERAP、LAYOUT和CONSENSUS阶段的串行处理过程和并行算法进行了描述,并给出了算法复杂性分析。数值试验结果表明,算法是高效的。  相似文献   

18.
随着生物序列数据库中序列数据的激增, 开发兼有高度生物敏感性和高效率的算法显得极为迫切. 通过对生物序列比对问题中Needleman-Wunsch算法和Smith-Waterman算法深入分析, 提出了Smith-Waterman算法的改进算法, 并通过实验验证该算法, 对改进前后的运行性能进行比较分析. 实验证明, 改进后的算法实现了双序列局部最优解个数的优化, 有效降低了生物序列比对算法时间与空间的复杂性, 提高序列比对的得分率和准确率.  相似文献   

19.
非定常Monte Carlo输运问题的并行算法   总被引:1,自引:0,他引:1  
文中给出了非定常MonteCarlo(下文简写为MC)输运问题的并行算法 ,对并行程序的加载运行模式进行了讨论和优化设计 .针对MC并行计算设计了一种理想情况下无通信的并行随机数发生器算法 .动态MC输运问题有大量的I/O操作 ,特别是读取剩余粒子数据文件需要大量的I/O时间 ,文中针对I/O问题 ,提出了三种并行I/O算法 .最后给出了并行算法的性能测试结果 ,对比串行计算时间 ,使用 6 4台处理机时的并行计算时间缩短了 30倍  相似文献   

20.
研究了一种基于多粒度锁的并发控制算法,包括其多粒度锁锁、锁表数据结构及锁操作的算法步骤。算法可以降低冲突发生的概率和事务的夭折数,减少事务重启,有利于满足事务截止期的要求,提高事务的并发度。在验证算法有效性时,通过测试类对内存数据库记录的插入速度、索引查找的速度、记录的删除速度三方面的性能进行了测试,结果表明,事务并发控制优化算法对内存数据库性能的提升是有效可行的。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号