并行计算机系统下的矩阵乘法

在过程控制、图像处理等应用领域中需要用到大量的矩阵乘法操作,并且矩阵乘法计算性能是系统性能的关键因素。本文根据矩阵相乘的特点,提出了带状划分的矩阵相乘的并行算法。同时着重分析和推导了当并行机的处理器个数小于和远小于矩阵规模的情况下实现快速的矩阵乘法。     

矩阵相乘并行算法的MPI实现

介绍行列划分算法和矩阵相乘并行算法MPI程序,给出基于矩阵相乘并行算法的MPI实现,分析和讨论处理器数目、复杂性、矩阵划分、B子块传递、死锁避免和矩阵数据的获取等问题。     

基于TMS320C80的矩阵并行乘法研究

介绍了在TMS320C80上实现并行算法需要解决的两个问题:存储器访问冲突、数据“双缓冲”传送,然后讨论了在其上实现矩阵相乘的并行算法.     

基于共享内存的高效OpenMP并行多层快速多极子算法

提出并实现了一种基于共享内存并行平台的OpenMP并行多层快速多极子算法.结合OpenMP并行算法开发的要点和多层快速多极子算法数据分布的特性,对多层快速多极子的填充矩阵模块、矩阵向量相乘中的远相互作用部分进行了OpenMP并行化设计.在分析调度方式和循环次序对计算效率的影响的基础上,提出了一种高效的OpenMP并行多层快速多极子方案.数值实验表明,并行算法与串行精度一致,OpenMP并行算法具有较好的并行效率.     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.     

弹性波动方程数值解的有限元并行算法

在求解弹性波动方程中,有限元法的高内存量和巨大运算量的需求在基于单CPU串行算法中一直难于满足,制约其优势的发挥.根据有限元法的"化整为零、集零为整"的基本思想与并行处理技术的"分而治之"的原则基本一致,采用基于多CPU的并行算法,从有限元参数矩阵计算和线性方程组求解两个方面入手,把求解区域分到多个CPU上并行计算参数矩阵,对线性方程组采用循环块三对角线方程组进行并行求解.对比了不同大小空间和不同CPU个数下的加速比,证实了多CPU的并行算法能够克服基于单CPU串行算法的物理限制,满足了有限元法的巨大空间量和运算量的需求.此算法具有理论上的正确性和实践上的可行性.     

拟希尔伯特阵和一般阵相乘的快速串行与并行计算

本文给出了拟希尔伯特阵和一般阵相乘的快速串行与并行算法。对于串行计算,时间复杂性是O((nlogn)~2),对于并行计算,在有n台处理机的条件下,其计算步数是O(nlog~2n),而效率是O(1)。     

多核计算环境下的LiDAR数据DEM内插方法研究

为了分析并提高在多核计算环境下大数据量激光雷达数据内插DEM效率问题,利用多线程技术,设计了在多核计算环境下DEM分块内插并行算法,讨论了并行算法的流程和技术要点,并实验分析了分块大小和搜索半径对并行算法的加速比影响.实验表明:在分块较小时,加速比与核数具有线性增长关系;而内插搜索半径越大,加速比越小,但影响不十分显著.总体上,多核并行算法一定程度上提高了DEM内插效率,但是会受到计算机内存速度的限制.     

一种动态编程法解决矩阵链相乘问题

文章介绍一种新的动态编程法解决矩阵链相乘问题,动态编程法可以极大节省计算成本及资源,通过实验程序结果证明,用动态编程法解决矩阵相乘问题相对于一般正常的算法,计算效率得到极大提高.     

电力系统网络方程并行算法研究及潮流并行计算的实现

结合Ｔｒａｎｓｐｕｔｅｒ硬、软件的特点，研究了电力系统网络方程的并行算法。在撕裂节点法、系数矩阵写成对角加边的基础上，发展了系数矩阵完全分解算法。在由４片Ｔ８００－２０组成的并行计算机系统上，实现了快速分解潮流的并行计算，并针对不同规模的网络进行了试算，计算结果表明，上述算法有较好的效果，证明并行算法能显著提高电力系统计算的速度，有广阔的应用前景。     

A binary images watermarking algorithm based on adaptable matrix

A watermarking algorithm of binary images using adaptable matrix is presented. An adaptable matrix is designed to evaluate the smoothness and the connectivity of binary images. The watermark is embedded according to the adaptable matrix in this algorithm. In the proposed watermarking algorithm, each image block implements a XOR operation with the binary adaptable matrix, which has the same size with the image block, and in order to embed the watermark data, a multiplication operation are also implemented with the weight matrix. The experimental results show that proposed scheme has a good performance.     

用于复合服务的白盒加密算法

针对基于移动Agent的服务复合的脆弱性,给出一种白盒加密算法.通过引入有限域上的分块矩阵乘法和带输入输出变换的安全加法器,算法将密钥隐藏在一系列的数据表中,由此实现了基于加密函数的安全数据加密,能够应对白盒攻击环境下密钥泄漏的安全风险.该算法代码体积较小,适合于移动Agent在非固定式服务复合时使用.     

基于存储的矩阵乘积优化算法

提出了一种基于存储的矩阵乘积优化算法.该算法转置矩阵,提高cache命中率,从而降低矩阵乘积时间. 实验结果表明此算法是行之有效的.     

基于MATLAB矩阵运算的大整数乘法设计与实现

大整数运算在信息安全、数学验证、基因工程等领域有着广泛的应用,设计有效的方案提高运算效率成为学者关注的热点。大整数乘法是大整数运算中的核心运算,对如何提高大整数乘法运算效率进行了分析总结,并利用MATLAB矩阵运算结合格子乘法等算法进行了设计与实现。实验表明通过MATLAB矩阵运算进行大整数乘法运算能有效的提高运算效率。     

实对称循环Toeplitz矩阵相乘的算法探讨

应用初等的组合方法和三角矩阵知识,给出了两n阶实对称循环Toeplitz矩阵相乘的一种快速算法.该算法的时间复杂性为nr次乘法和(n-1)r次加法,其中r=[n2]+1.     

几种矩阵乘并行算法的对比分析

描述了DNS、Cannon、Fox、Systolic矩阵乘并行算法的原理,并对其时间复杂度进行了理论分析。通过对并行算法的各项性能参数的对比分析,得到的结论是DNS算法的时间复杂度最好,但加速比、效率和成本不是最优的。Cannon算法和Fox算法的算法思想类似,但是Cannon算法比Fox算法在数据播送上的花费少,因此整体性能较好。Systolic算法是基于流水线技术的并行矩阵乘算法,有较好的综合性能。     

矩阵乘在通用DSP上的峰值性能模型

DSP具有能效比高的特点,可以用于通用高性能计算.矩阵乘是许多科学与计算问题的核心算法,在DSP上取得高性能具有重要的理论和现实意义.面向通用DSP,提出了矩阵乘并行算法,建立了矩阵乘峰值性能模型,根据性能模型,构建了矩阵乘性能达Tflops级DSP体系结构参数配置,对通用DSP的设计参数给出了明确的性能指标要求,包括乘加流水线数量、寄存器数目、带宽和延迟.     

MapReduce based computation of the diffusion method in recommender systems

The performance of existing diffusion-based algorithms in recommender systems is still limited by the processing ability of a single computer .In order to conduct the diffusion computation on large data sets, a parallel implementation of the classic diffusion method on the MapReduce framework is proposed.At first, the diffusion computation is transformed from a summation format to a cascade matrix multiplication format , and then , a parallel matrix multiplication algorithm based on dynamic vector is proposed to reduce the CPU and I/O cost on the MapReduce framework , which can also be applied to other parallel matrix multiplication scenarios .Then, block partitioning is used to further improve the performance , while the order of matrix multiplication is also taken into consideration . Experiments on different kinds of data sets have verified the efficiency of the proposed method .     

一种ELMMSE信道估计算法的简化计算方法

提出一种ELMMSE信道估计算法的简化计算方法。为简化ELMMSE信道估计算法的复杂度,首先利用信道自相关矩阵的固有特性,简化了信道自相关矩阵求解;然后利用算法中逆矩阵满足共轭对称Toeplitz特性,简化了矩阵求逆。结果表明:当OFDM子载波数为128时,提出的ELMMSE算法简化计算方法的复乘、复加次数分别减小为ELMMSE算法的5.84%和5.79%。其中,信道自相关矩阵求解的复乘、复加次数分别减少了33.14%和16.64%;矩阵求逆的复乘、复加次数均由原来的o(N3)变为o(N2)。