当前位置：文档之家 › 并行计算稀疏矩阵乘以向量的负载平衡算法

并行计算稀疏矩阵乘以向量的负载平衡算法

  • 格式：pdf
  • 大小：167.23 KB
  • 文档页数：3

!!"#$%&’()!*+!,--"&../%&$.0!!!!计算机工程与科学!12+3*454"6,"445,"67-!,4"!4’..8年第’)卷第$期!!9:;Y ’)"":Y $"’..8"""""""""""""""""""""""""""""""""""""""""""""""""!文章编号!&../%&$.0#’..8$.$%../8%.’并行计算稀疏矩阵乘以向量的负载平衡算法#=_:C K %‘C ;C B F E B Q =;Q :I E H J DO :I -L C I G >2C H I E M %9>F H :I2P ;H E L ;E F C H E :B:B+C I C ;;>;!:D LP H >I G 刘!杰"迟利华"胡庆丰"李晓梅X Q +F ’&"<S QX ’(9-/"S +,’01(;&01"X Q*’/:(=&’#国防科技大学计算机学院"湖南长沙L 644N J$#789::.:;<:=>-?&@78’&08&"#/?’:0/.+0’D &@E ’?C :;!&;&0E &B &890:.:1C "<9/01E 9/L 644N J "<9’0/$摘!要!稀疏矩阵乘以一个向量!-L 2Z9"的问题是许多大型应用问题的核心计算问题#文中提出了一种在并行计算机上并行计算-L2Z9的负载平衡算法#计算复杂性为1!I "!I 为稀疏矩阵的阶"#而目前计算此类问题的最优负载平衡算法的计算复杂性为1!I $,"!,为处理机台数"%文章最后给出了并行数值实验%G )E ?@/8?%,B H J E G L C L >I "?>F :B G E K >I H J >;:C K %N C ;C B F E B Q D P ;H E L ;E F C H E :B:O C ;C I Q >G L C I G >D C H I E M?E H JC ;C I Q >G >W P >B F >:O R >F H :I G :B L C I C ;;>;F :D L P H >I G <b >L I :L :G >C ;:C K %N C ;C B F E B Q C ;Q:I E H J DN C G >K :BB :B %]>I :R C ;P >G >R >B H J >C ;;:F C H E :B :O H J >G >%W P >B F >I :?G :O G L C I G >D C H I E F >G <*J >F :D L ;>M E H A :O H J E G C ;Q :I E H J DE G1#I $"?J >I >I E G H J >B P D N >I :O I :?G E B H J >D C H I E M <,B F :B H I C G H H :H J >N >G H F P I I >B H C ;Q :I E H J D ?E H J H J >F :D L ;>M E H A :O1#I &,$"?J >I >,E G H J >B P D N >I :O L I :F >G G :I G "H J >L >I %O :I D C B F >:O :P IC L L I :C F JE G D P F JN >H H >I <4G L >F E C ;;A "N >F C P G >:P IC ;Q :I E H J DE GN C G >K:BH J >G >W P >B F >I :?C ;;:F C H E :B:O G L C I G >D C H I E F >G "?>F C B F :B R >B E >B H ;A F :D L :G >H J >L C I C ;;>;F :K >C B K:LH E D E ]>H J >F :D D P B E F C H E :B G <关键词!并行计算&稀疏矩阵乘以向量&负载平衡H &C I:@A E ’L C I C ;;>;F :D L P H E B Q &G L C I G >D C H I E M %R >F H :ID P ;H E L ;E F C H E :B &;:C KN C ;C B F E B Q 中图分类号!*+$.&Y 8!文献标识码!=6!引言大量的实际应用领域需要求解大型稀疏线性方程组"应用领域的复杂性使得稀疏线性方程组千差万别"很难在并行计算机上获得高性能’这使得如何在并行计算机上高效求解稀疏线性方程组成为目前高性能并行计算中的一个研究热点与难点"而利用迭代法求解稀疏线性方程组的计算量有T .f 集中在-L 2Z9上’因此"研究高效的-L 2Z 9并行算法就显得至关重要’设计好的并行算法要注意两个问题%#&$数据分布的局部化"目的是尽量减少通信量和增加计算性能(#’$负载平衡问题"目的是充分利用计算资源’目前"对-L 2Z9计算问题的研究主要集中在针对某类特殊稀疏矩阵在特殊的并行机结构上如何提高计算性能"即数据分布的局部化与串行计算的优化)&"’*"而对-L2Z9并行计算的负载平衡问题研究不多’事实上"负载不平衡已经成为影响许多问题并行性能的主要因素’对于此类问题的研究虽然很难"但又势在必行’由于稀疏矩阵元素分布的不均匀性"按行+按列或按块平均分配的方式造成了处理机间的负载不平衡"有必要研究高效的负载平衡算法’目前只有两篇这方面的文献%=;E C QC 和V >D C B K >])$*给出了一种迭代负载平衡算法"算法计算复杂性为1#I ’!,$("C G H >C 等人)#*给出了一种使用贪心算法的负载平衡算法"算法的计算复杂性为1#I &,$’我们通过理论分析提出了基于连续行和将稀疏矩阵非零元素平均分配到每台处理机的负载平衡算法"达到了很好的负载平衡效果"且算法的计算复杂性降为1#I $’2!负载平衡算法-L2Z9的计算量与稀疏矩阵非零元素的个数成正比"下面的叙述中用非零元素的个数来表示负载’因为-L2Z 8/#收稿日期!’..#%.’%&/(修订日期!’..#%./%.&基金项目!十五武器装备预研基金资助项目(计算物理国家重点实验室基金资助项目#’...\-/8Y #Y &[6.&&T$作者简介!刘杰#&T 8T $"男"江苏赣榆人"博士"副研究员(迟利华"副研究员(胡庆丰"教授(李晓梅"教授"博士生导师"研究方向均为并行算法与科学计算’通讯地址!#&../$湖南省长沙市国防科技大学计算机学院8&&教研室(*>;%&$8)/$)T /(TG A A @&E E %->F H E :B8&&"-F J ::;:O!:D L P H >I -F E >B F >""C H E :B C ;3B E R >I G E H A :O@>O >B G >*>F J B :;:Q A "!J C B QG J C "V P B C B#&../$"+<5<!J E B C 万方数据9的计算结果向量中每一个元素都是独立的!不具有相关性!可以并行执行"为了保证并行计算的负载平衡!自然的做法就是将稀疏矩阵非零元素平均分配到每台处理机"设I表示稀疏矩阵行数!,表示处理机台数!U表示稀疏矩阵非零元素总个数!U2#U!NI#!&I#1&I#2&#)&8$’方法=V+\_!V_=V+\_!V_=V+\_!V_=V+\_!V_15=" ,8/)D C M#(’/’’’(#.$.’&(&&’/.&8’$#(8$()(&’’)&) D E B T T/$’’($T#(/)&&’8)’’$T(8$#&&’&’)&8+-2, 65&D C M&)(/T&&$(/T&&.T$.T8/)T88’’$#$$T#T$(T)$&8T/( D E B T$#’#&$(/T.#(#’$8/)T#’’$&T$$T##&&.)T&8T/&‘!--*[’)D C M8.#’$(#/(/$.’)T’/$/T&((&’&$8T’/T’&8)#8 D E B#($’&(#/(#’’8&.’/$/#&&$..&$8))((&&8)#.!!图&给出了"C G H>C算法和_!V_算法分配数据所花费时间比较!所花费的时间包括负载平衡算法计算所花费的时间和分配数据的计算时间"万方数据图$!!碧金会所"电子商务应用系统业务模型片断图#!!碧金会所"业务模型所表现的页面L!结束语目前#使用32_%4‘+元模型的b>N应用开发平台4‘+可以实现对一般b>N应用的建模#并且可以生成在->I R;>H和\-+平台下的完整应用程序以及4\‘平台下的b>N应用程序框架$这些结果表明#对于一般的b>N应用#32_%4‘+可以很好地提供元建模支持#体现了b>N 应用领域的共性$和其他建模语言一样#32_%4‘+也需要在实践中不断被检验和完善$例如#对于数据库中的多表关联支持不够#提供的基本应用场景覆盖面不广#目前的平台应用也只限于->I R>;H%\-+和4\‘等$我们将不断扩充其功能#以实现对不同中间件平台和多表关联的支持$参考文献!&&’!\:C W P E B2E;;>I#\E G J B P2P S>I^E<2@=6P E K>9>I G E:B&<.<& &4‘(1_’<J H H L)((???<:D Q<:I Q(K:F G(:D Q(.$%.8%.&<L K O#’..$%.8Y&’’!田林一Y2@=入门必读***2@=架构详细介绍&4‘(1_’Y J H H L)((???<D K C G S A<F:D(D C Q C]E B>(K:F(2%+I:Q I C D D>I&<I C I#’..#%.&Y&$’!,B H>I C F H E R>,:1N^>F H!:D L C B A Y=I F-H A;>I=F F>G G:I*P H:I E C;&4‘(1_’Y J H H L)((???<E:%G:O H?C I><F:D(C G＿G P L L:I H(K:F P(=F F>G G:I＿*P H:I E C;<L K O#’..$%&.Y&#’!2‘I C D N E;;C#-!>I E#-!:D C E#>H C;<2:K>;%@I E R>B@>R>;:L D>B H:Ob>N->I R E F>GC B K V A L>I H>M H=L L;E F C H E:B G&4‘(1_’YJ H H L)((b>N D;<>;>H<L:;E D E<E H(b>N D;(P L;:C K(>B H((&(G F E E’..$＿O I C H>I B C%;E<L K O#’..$%&.Y&(’!-!>I E#+X I C H>I B C;E Y=‘:B Q E:b>N2:K>;E B Q_C B Q P C Q> +b>N2_,)=2:K>;E B Q_C B Q P C Q>O:I@>G E Q B E B Q b>N-E H>G&4‘(1_’<bbb!:B O&!’Y’...<&8’!1N^>F H2C B C Q>D>B H6I:P L Y2>H C1N^>F H X C F E;E H A+21X, -L>F E O E F C H E:B9>I G E:B&<#&4‘(1_’Y J H H L)((???<:D Q<:I Q(K:F G(O:I D C;(..%.#%.$<L K O#’..’%.#Y&/’!1N^>F H2C B C Q>D>B H6I:P L Y3B E O E>K2:K>;E B Q_C B Q P C Q> +32_,-L>F E O E F C H E:B9>I G E:B’<.&4‘(1_’Y J H H L)((???< :D Q<:I Q(F Q E%N E B(C L L G(K:F？L H F(.$%.T%&(<L K O#’..$%.T Y &)’!@C R E K-X I C B S>;Y鲍志云译Y应用2@=&2’Y北京)人民邮电出版社#’..$<&T’!1N^>F H2C B C Q>D>B H6I:P L Y!:D D:B b C I>J:P G>2>H C D:K>;+!b2,-L>F E O E F C H E:B9>I G E:B&<&&4‘(1_’Y J H H L)((???< :D Q<:I Q(K:F G(O:I D C;(.$%.$%.’<L K O#’..$%.$Y!上接第//页""C G H>C算法需要对不连续的数据块进行发送#此时需要对不连续的数据进行打包#而_!V_对连续的数据块进行发送时不需要打包$从图&可以看出#用_!V_算法进行数据分配的时间基本保持不变#而用"C G H>C算法进行数据分配的时间随处理机台数的增加呈线性增加$同时#用_!V_算法进行数据分配的时间比采用"C G H>C算法进行数据分配的时间要小#处理机台数越多对比效果越明显#$’台处理机时用"C G H>C算法进行数据分配的时间是用_!V_算法进行数据分配时间的三倍$L!结束语本文最后的测试结果表明#_!V_算法的负载平衡能力好#用_!V_算法进行数据分配的时间基本保持不变#而用"C G H>C算法进行数据分配的时间随处理机台数的增加呈线性增加$同时#用_!V_算法进行数据分配的时间比采用"C G H>C算法进行数据分配的时间要小#加速比也好于"C G H>C算法$这表明_!V_算法是一种比较好的负载平衡算法$参考文献!&&’!56>P G#-5:;;E B<*:?C I K G CX C G H+C I C;;>;-L C I G>-A D D>H I E F 2C H I E M9>F H:I2P;H E L;E F C H E:B&\’<+C I C;;>;!:D L P H E B Q#’..&#’/+’,)))$%)T8<&’’!@V>I C G#\!C N P;>E I:#X5E R>I C<2:K>;E B Q@C H C_:F C;E H A O:IH J>-L C I G>2C H I E M%9>F H:I+I:K P F H3G E B Q@E G H C B F>2>C G P I>G&\’<+C I C;;>;!:D L P H E B Q#’..&#’/+’,))T/%T&’<&$’!\=;E C Q C#9V>D h B K>]<-A D D>H I E F-L C I G>2C H I E M%9>F H:I +I:K P F H:B@E G H I E N P H>K2>D:I A2P;H E L I:F>G G:I G&=’<+I:F:OH J>!:B O:B+C I C;;>;!:D L P H E B Q C B K*I C B G L P H>I G=L L;E F C H E:B G&!’<&T T’<&#’!-"C G H>C#1X I E>K>I#4*C I>S<_:C K%‘C;C B F>K-L C I G>2C H I E M%9>F H:I2P;H E L;E F C H E:B:B+C I C;;>;!:D L P H>I G&\’<\:P I B C;:O+C I C;;>;C B K@E G H I E N P H>K!:D L P H E B Q#&T T/##8+’,)&).%&T$<&(’!,-@P O O#566I E D>G#\6_>?E G<3G>I G-6P E K>O:I H J>V C I% ?>;;%‘:>E B Q-L C I G>2C H I E M!:;;>F H E:B&5’<5>L:I H*5(+=(T’()8#!45X=!-#&T T’<&T万方数据。

合集下载

解决大规模稀疏线性方程组的迭代法

解决大规模稀疏线性方程组的迭代法

解决大规模稀疏线性方程组的迭代法在计算科学和工程学领域中，大规模稀疏线性方程组是一种常见的问题，包括许多领域，如电力系统、材料科学、药物发现、计算流体力学等。

这些问题的解决对科学研究和工程设计都具有重要意义。

然而，当问题规模增大时，求解这些线性方程组变得困难。

因此，研究高效的迭代算法和求解方法是至关重要的。

稀疏线性方程组求解的挑战：大规模稀疏线性方程组求解是一个复杂的问题，其中最主要的挑战是如何有效地处理稀疏矩阵。

由于其稀疏性，大多数元素都为零，这使得传统的直接求解方法，如高斯消元，LU分解等不再适用。

因此，迭代算法是求解该类问题的首选方法。

迭代算法的工作原理：迭代算法的基本思想是利用一个初值解，通过不断地逐次修正，最终得到线性方程组的解。

其基本工作原理是计算误差的后效性，也就是说，每次求解都是在上一次求解结果的基础上进行修正。

最受欢迎的迭代算法：- Jacobi迭代：该方法使用对角矩阵的逆作为迭代矩阵。

这个逆矩阵只需要在算法的一开始计算一次，随后每次迭代都可以直接使用。

这使得Jacobi算法特别适用于在处理较小的稀疏线性方程组时。

- Gauss-Seidel迭代：该方法是Jacobi算法的改进版本。

Gauss-Seidel算法会在每次迭代中更新解向量的所有元素，而不是只更新一个，从而使得每次迭代都较为精确。

- 共轭梯度法：是一种迭代算法，旨在求解系数矩阵为对称、正定矩阵的线性方程组。

其聚焦于求解富有特色的欧几里得范数下的误差最小化问题，使用一种成熟的迭代策略来加速计算。

提高矩阵向量乘和解向量稠密化：在实际应用中，稀疏矩阵向量乘和解向量的稠密化是影响迭代算法效率的两个主要瓶颈。

一些技术，如并行计算、矩阵压缩、矩阵重排序、缓存预取等，可以大大提高矩阵向量乘的效率。

此外，在解向量稠密化方面，使用过渡方案或基于层次的内存管理方案可以大大减少内存使用量，并提高迭代算法的效率。

总结：大规模稀疏线性方程组的迭代算法是一个十分重要的研究领域，具有广泛的应用前景。

并行计算 期末考试复习背诵要点

并行计算 期末考试复习背诵要点

复习要点1、Parallel computing并行计算，sequential computing串行计算，instruction指令，multiple多数据，communication通信，exclusive互斥，concurrent 并发，recursive递归，data数据，exploratory探索，speculative投机，block cyclic循环块，randomized block随机块，distribution分配，graph partitioning 图划分，speedup加速比，efficiency效率，cost费用，Amdahl’s law，architecture构架，fundimental functions基本函数，synchronization同步，matrix mulitiplication矩阵乘，matrix transposition 矩阵转置，bitonci sorting双调排序，odd-even sorting奇偶排序，Shortest path，minimum spanning tree，connected components，maximal independent set，2、SMP（对称多处理机连接）MPP (Massive Parallel Processors 大规模并行）Cluster of Workstation（工作站机群）Parallelism（并行化）, pipelining（流水线技术）, Network topology（网络拓扑结构）, diameter of a network（网络直径）, bisection width（对分宽度）, data decomposition（数据分解）, task dependency graphs（任务依赖图）, granularity（粒度）, concurrency（并发）, process（进程）, processor（处理器）, linear array（线性阵列）, mesh（格网）, hypercube（超立方体）, reduction（规约）, prefix-sum（前缀和）, gather（收集）, scatter（散发）, threads（线程）, mutual exclusion（互斥）, shared address space（共享地址空间）, synchronization（同步）, the degree of concurrency（并发度）, Dual of a communication operation（通信操作的对偶操作）3、并行计算与串行计算在算法设计主要不同点：(1)具有强大的处理器互连关系(2)并行计算依赖并行计算模型上的，如共享内存，共享地址空间或消息传递。

矩阵稀疏化的理解

矩阵稀疏化的理解

矩阵稀疏化的理解矩阵稀疏化是指将矩阵中大部分元素为零的情况下，通过压缩存储方式减少存储空间和计算量的技术。

在很多实际问题中，矩阵往往具有稀疏性，即矩阵中绝大多数元素都是零。

利用矩阵稀疏化技术可以有效减少存储空间和运算量，提高计算效率和性能。

矩阵稀疏化的应用广泛，特别是在大规模数据处理和机器学习领域。

例如，在自然语言处理中，文本数据通常表示为矩阵形式，其中每一行代表一个文档，每一列代表一个词汇，而矩阵元素表示该词汇在文档中的出现频率或权重。

然而，由于大量词汇和文档的存在，导致矩阵非常稀疏。

如果按照普通的方式存储和计算，将会占用大量的存储空间和计算资源。

因此，矩阵稀疏化技术在这种情况下显得尤为重要。

矩阵稀疏化的方法有很多种，常见的有压缩稀疏矩阵（Compressed Sparse Matrix，简称CSM）和字典编码（Dictionary Encoding）等。

压缩稀疏矩阵是一种常见的矩阵稀疏化存储方式，它通过压缩存储非零元素的位置和值，从而减少存储空间。

其中，最常用的压缩方式有三种，分别是COO（Coordinate Format）、CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column）。

COO格式将非零元素的位置和值分别存储在两个数组中，CSR和CSC则将非零元素的位置和值分别存储在一个数组和一个指针数组中。

这些压缩稀疏矩阵的存储方式在不同的应用场景中具有不同的优势，可以根据实际需求选择合适的方式。

字典编码是另一种常见的矩阵稀疏化方法，它通过构建一个字典来存储矩阵中的非零元素。

字典中的每一项包含了非零元素的位置和值。

通过这种方式，可以将矩阵中的非零元素进行编码和压缩，从而减少存储空间。

字典编码在某些特定的应用场景中具有较好的效果，例如在图像处理中，当图像中存在大量的相似或重复的像素时，字典编码可以将这些像素进行编码和压缩，从而减少存储空间。

gmres算法范文

gmres算法范文

gmres算法范文GMRES（Generalized Minimal RESidual）算法是一种用于求解稀疏线性方程组的迭代算法。

它可以用于求解大规模稀疏矩阵的线性方程组问题，特别适用于非对称且非正定矩阵的情况。

GMRES算法能够通过矩阵向量乘法来逐步逼近线性方程组的解，从而在求解过程中保持向量的稀疏性，节约了计算和存储资源。

GMRES算法的核心思想是基于Krylov子空间的最小化残差，通过在Krylov子空间中找到一个最优的近似解向量来逼近线性方程组的解。

Krylov子空间是由矩阵A和初始向量b生成的线性空间，通过不断迭代计算可以得到Krylov子空间的一组正交基。

GMRES算法的具体步骤如下：1. 初始化：给定一个初始解向量x0和初始残差r0=b-Ax0，将正交化后的r0作为初始Krylov子空间的基向量v12. Arnoldi迭代：对于k=1到m，进行以下步骤：a. 计算w=Avk；b. 通过Gram-Schmidt过程对w与之前的基向量进行正交化，得到新的正交基向量v_k+1；c. 构造大小为(k+1)×k的Hessenberg矩阵H，其中H=Q_k^T*A*Q_k，Q_k是由正交基向量v1,v2,...,vk构成的正交矩阵；d.使用QR分解求解H的最小二乘问题，得到近似解向量y。

3.更新解向量：更新解向量为x_k=x_0+Q_k*y。

4.检测终止条件：如果达到了预定的收敛条件或者迭代次数达到了最大限制，则结束迭代；否则返回步骤2GMRES算法的核心在于利用Krylov子空间的正交基向量来构造Hessenberg矩阵，并通过最小二乘法求解近似解向量。

通过在每一步迭代中更新解向量，可以逐步逼近线性方程组的解。

当算法能够达到预定的收敛条件时，解向量可以近似地满足线性方程组。

GMRES算法的优点是可以求解大规模稀疏矩阵的线性方程组，并且能够保持向量的稀疏性。

它还可以通过调整收敛条件来控制算法的精度和计算资源的消耗。