论文研究-基于SIMD结构的矩形行列式并行算法研究.pdf

所需积分/C币:9 2019-09-08 17:21:57 506KB .PDF
18
收藏 收藏
举报

在运用行列式Schur余子式算法的理论基础上,提出了对SIMD结构的并行机,可适用于对行列式按行分块并行处理算法,把一个n阶行列式的求值过程分解成相对独立的若干个二阶行列式的求值过程,而且它们的求值过程是相对独立的,具有并行性,从而设计出n阶行列式求值的并行算法。给出了该算法的实现步骤,分析了算法的加速比;对算法进行了模拟实验,结果说明了其性能。
50 2012,48(25) Computer Engineering and Applications计算机工程与应用 1a2-a21a12a123-a211 1432-a3112a123-a31413 aua3n-a3iain= 分别为d(41),detS(H2/41)和de(S(H3/41) a-a9)sm2/4)S(y/A)-nP2将结果 00 传送回主控机cp3,由cp3完成最后的判断,并输出 au a 通过对cpl、cp2和cp3计算任务的合理分配,缩短对 2a31a detA的计算时间。 11 定理4设A=A2A2A2用设H2 l!412 A1,S(H2A1) A,A 4 A S(H2/A1) S(H2/A) H A. A deta=det(a. det(S(Haa/ An)) detAndet(S(H3An)S(H/An1)S(H2A1)-S(H31))detS(H2/A1) di(n3/41)-S(ny/A)S(H2/41)S(H2y/41) 证明设 输出结果 图1计算流程图 AnAh+S(H,/A1)S(H,/A1)Ax1A1-S(H,/A)S(H,/4n)l 该算法遵循矩阵计算并行处理的基本原则:降 低运算量的阶,把一个n阶行列式分成3块,由3个处 1-4A2-443+A42S(H2/A1)S(H2/41 D 理器并行处理。但分解后的形式复杂,实际工作量 Hz2/41)S(H2/A 并未减少。因为在3个处理器上,cp2所运行的计算 则A|=CAD|=CAD= 量最大,则整个系统的运行时间由cp2运算时间所决 A 定。在cp2上先后有5个Schu余子式的运算,每个 0A2-A,1A1A 余子式中包括一个n/3阶矩阵的求逆,3个n/3阶矩 S(H3/A1)-S(H2/Au)S(H22/A1)S(H2 /4, 阵的乘积。两个n阶方阵相乘的时间复杂度是 det(a ) det(S(H2/an)) O(n),算法运行时间为(m)=n(2n-1)。那么cp2 d(p/)-S(H/Af(yA1)SH3/4)所需要运行时间为: 22问题提出 13(2(n13)-1)=5n2(2n-3)27 根据以上由Sch余子式推导出的结论,设计出 23算法设计 求行列式值的算法。具体过程如下: 根据以上文献所设计方法的思路,本文由 Schur 根据定理4,采用将矩阵分块的方法(将矩阵分 定理推导出不同形式的求行列式值的方法。当n很 为4块和9块)达到使高阶矩阵降阶的目的,得出用 Schur余子式求矩阵行列式的定理,给出求矩阵迸大时,本文算法的时间复杂度降为O(n2),休现了并 矩阵行列式的并行算法和相应算例。 行算法的优越性。 因为由定理3知把A分为9块,故当n=3k时,取 由定理3,得到一个n阶行列式求值过程可以分 A,A2,A3均为k阶。若n=3k+1(n=3k+2)时,取解成(n-1)个一阶行列式求值,而二阶行列式求值 41nA2均为阶,A13为k+1(k+2阶。此时须计算A1,非常简单,只需对角线元素作两次乘法和一次加法, s(Hn/4),及S(H1y/4)-(/4)H2/A1而且随着运算的深入,n值逐渐减小,直至最终结 果。对有P个处理器的SIMD多处理器系,根据前面 S(H2/An),3个模块由3个计算单元cpl、cn2cn3分 的理论,设计其并行算法,具体过程如 别完成,其体的计算流程见图1。在图1中cp3为主 设A为一个n阶方阵,处理机台数为P。设k为循 控机,完成矩阵的划分,求出A1和S(H2/41)并将环次数变量,初始k=n。行列的值为D初始D 结果分别传送到cp2cpl此时 cpl cp2cp3同时计算, (1)数据存储:把任一台处理机作为主控机,存 王艾昕:基于SIMD结构的矩形行列式并行算法研究 2012,48(25) 储矩阵A,并计算D=Dx1D=Dx1,D=D×P,则并行开销将会增大,使系统效率降低。而当系 统规模P不变,只增加问题规模W,由于并行开销增 2;设这台处理机为P 长得比W慢,从而使效率增加。因此,可以让W和P 同时增长,以保持效率不变。为了保持效率不变,随 (2)传输数据:由P向p个处理机平均分配和发 着系统规模的增加,问题规模以多项式规律增长,可 送二阶行列式的4个元素:a1a1+1.41+41+1+1能超过并行机有限存储容量使得有限ⅠO能力成为 11i+1,j+1 11,+1111.j+1i+1,1 瓶颈。等效率函数的度量方法的缺陷:没有反映出 〔3)数据的并行计算:每台处理机并行计算系统规模增加时,体系结构的计算与通信能力的变 a11+1-a,aA的a11值,并分别存储在化对算法内在并行性与通信需求的影响没有提供 中 不可扩系统的不可扩的信息。 (4)信息接收:P从p个处理机接收其运算结果, 25算法实现 并按指定位置覆盖原矩阵中元素,存在矩阵A中。 根据上述计算的特点,本文设计用PC机与一个 (5)k=k-1,如果k>2,转到(2),并行计算,如果速数字信号处理器组成两机并行处理系统,其结 构如图2所示。高速数字信号处理器具有独立的内 k2,则P计算最后一步a1a2-a1a2,并与D相乘, 存单元,40ns单周期指令,并且具有32位浮点数据 得出结果;运算结束。 格式,浮点运算精度高。处理器为独立的子系统,通 24算法分析 过PC机ISA总线与PC机相连,处理器与主控机之间 对于一个n阶方阵,进行串行计算需(n-1)+的通讯采用共享存储技术,双端口RAM作为共享 2)2+…+2+1=(2n3-3n2+n)/6步,每步计算两存储器。该系统运行时算法采用静态调度的方法 个乘法运算设次乘法运算的时间为r,则串行运算PC机作为主控机p,PC机进行任务分配协调并计算 的总时间为(2n2-3n2+n)/3。如果采用并行计算,和存储,并用从处理器发回的计算结果更新矩阵相 中将要计算的(2n2-3m2+m/6个矩阵分成p份,分给每应位置的元素,处理器和并行计算原矩阵分解成的4 若千二阶行列式的值。所有的程序都用C语言开发, 个处理机,并设n-1可被p整除。P个处理机并行计PC机发出命令,程序联机加载,PC机将初始数据通 算所分到部分矩阵的连乘积,每次相乘需要两个乘 过双端口RAM传送到子系统,子系统与PC机并行 法,共要(2n2-3m2+n/-(n-)次,则并行运算的计算独立完成自已的任务后,把结果再传送回PC 总时间为(2n2-372+n)/3=2(n-) 机,由PC机完成最后的判断。 设启动发送的时间为B,传递个浮点数的时 处 间为τ,从第(2)步开始通信,每次通信,传送4个浮点 双口RAM SRAM 札 理 数共(n-1)+(n-1)+…+1)-(n-1)=(n2-5m-2)/2 器 次则通信开销为(B6+4x)2-5m-2)2,该算法 图2多处理器并行处理系统图 如果在SMP上实现,将会减少很多通信时间.并 (2n3-3n2+n)r/3 行效果会更好。 (2n3-32+n)/-2(-1]+(p +4x(n--5n 26数值实验结果 当n远人于p时约为po加速比S<p,当p<2(n-1)/4 在两个处理器的多处理机系统上对该算法进行 时,加速比Sn>1。 模拟性实验,实验结果如表1、表2所示。 可扩展性分析。可扩展性是指如果在一个给定 表1单处理机和两个处理机的运行时间 的体系结构上实现并行算法,且随系统规模的增加 5001000100001000001000000 00890.2331.07410.34940.769 而适当增加冋题规模,并行系统的平均系统开销保 20.1840.3270.862 7.15023.554 持不变。具体来讲,并行系统的可扩展性度量方法, 表2两个处理机的加速比 可以采用等效率度量方法。所谓等效率是指系统规 5001000100001000001000000 模增加时,无论测量增加多少运算量会保持效率不 加速比048407131.2461.4471.731 变。如果问题规模丌保持不变,只増加系统的规模 (下转56页)

...展开详情
试读 4P 论文研究-基于SIMD结构的矩形行列式并行算法研究.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于SIMD结构的矩形行列式并行算法研究.pdf 9积分/C币 立即下载
1/4
论文研究-基于SIMD结构的矩形行列式并行算法研究.pdf第1页

试读结束, 可继续读1页

9积分/C币 立即下载