Systolic矩阵乘并行算法的改进及其在HPF中的应用

本文在分析Ｓｙｓｔｏｌｉｃ算法原理及其不足的基础上，提出了一种改进的算法，并讨论了该算法在ＨＰＦ并行库中的应用。在国产并行机上，将该算法与优化数字扩展数学库（ＤＸＭＬ）的调用相结合进行实际测试，取得了较好的性能。     

一种基于De Bruijn网络结构的并行矩阵乘算法

在De Bruijn网络中进行并行矩阵乘法运算,算法简单,容易实现。首先介绍了De Bruijn网络结构,然后提出了一种基于De Bruijn网络结构的矩阵乘法的并行算法,分析了它的加速比、效率等性能及可扩展性,通过与Cannon算法的比较,证明它的时间复杂度等效于Cannon算法,最后通过实验验证了这个结论的正确性。     

一种基于Biswapped网络的并行矩阵乘算法

为了解决矩阵乘算法并行化的问题,根据Biswapped网络结构的特点,提出了一种基于Biswapped网络结构的矩阵乘并行算法.该算法采用一种新的矩阵映射方式,该算法操作简单且容易实现.理论分析和实验表明:该算法近似等效于Cannon算法.     

基于CUDA编程模型的稀疏对角矩阵向量乘优化

稀疏矩阵向量乘是很多科学计算问题中的核心问题。本文针对稀疏对角矩阵,在DIA存储格式的基础上,设计了一种新型压缩存储格式CDIA,结合CUDA编程模型的特点,在计算线程上进行了细粒度的任务分配,同时为满足CUDA对存储器的合并访问要求,将压缩矩阵做了相应的转置处理,设计了细粒度算法与程序,并根据稀疏矩阵向量乘特点,做了相应的程序优化。实验数据显示,这种存储格式能够很好地发挥CUDA在数据处理方面的优势,在测试数据中,最高获得了单精度39.6Gflop/s和双精度19.6Gflop/s的浮点计算性能,性能在Nathan Bell和Michael Garland的基础上分别提高了7.6%和17.4%。     

RAPWBN的矩阵乘法并行算法

在介绍带有宽总线网络的可重构计算阵列(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了 RAPWBN 阵列上的整数求和算法,并由此得到了 RAPWBN 阵列上的两种快速高效的矩阵乘法运算并行算法。在具有 N3个处理器和 N2条行总线的 RAPWBN 阵列上,若总线带宽ω>logN 字节,矩阵乘法可以在 O(1)时间完成;在具有 N2个处理器和 N 条行总线的 RAPWBN 阵列上,矩阵乘法可以在 O(N)时间完成。它们的效率都为 O(N3),达到了最优。     

一种基于PVM的矩阵相乘并行算法

研究了一种运行于PVM并行计算平台的矩阵相乘的并行算法。在工作站数量不为某个数的平方数时,Cannon算法在PVM环境下不能充分地利用机群系统中的资源。根据PVM并行编程环境中任务间通信的特点,文中设计了一种基于PVM的矩阵相乘并行算法,该算法根据工作站数量来确定子任务的数量,并对矩阵A进行分块,每个子任务可以计算一个分块。实验表明,该算法提高了机群并行环境中资源的利用率,提高了程序的运行效率。     

高效的带状线性方程组分布式并行算法

提出了一种新的带状线性方程组的分布式并行算法(New Distributed Parallel Algorithm for Banded Linear Equations,简称为NDPAB算法)。当带状线性方程组的系数矩阵满足对角占优时,算法在运行过程中不会中断,算法的加速比接近于处理器数目。给出了基于局域网的MPI异构环境下数值实验结果,数值实验结果表明算法是高效的。     

矩阵乘法的一个最优并行算法

本文给出了向是一机上计算两个n阶矩阵乘法的并行算法。处理机台数P=n;并行步数T＝(n);效率＝0（1）。此算法从阶上已达到并行矩阵乘法的复杂性下界，同时在保证效率为0（1）的前提下，使处理机台数的上界达到最优。     

基于SIMD结构的矩形行列式并行算法研究

在运用行列式Schur余子式算法的理论基础上,提出了对SIMD结构的并行机,可适用于对行列式按行分块并行处理算法,把一个n阶行列式的求值过程分解成相对独立的若干个二阶行列式的求值过程,而且它们的求值过程是相对独立的,具有并行性,从而设计出n阶行列式求值的并行算法。给出了该算法的实现步骤,分析了算法的加速比;对算法进行了模拟实验,结果说明了其性能。     

基于MPI的Strassen矩阵乘法算法的并行计算研究与实现

本文在Windows系统并行计算平台下,利用MPICH环境并结合Visual C 6.0编程语言,实现Strassen矩阵乘法算法的并行程序,实验表明该算法能有效地提高矩阵乘法的运行效率.     

基于MPSoC并行调度的矩阵乘法加速算法研究

矩阵乘法是数值分析以及图形图像处理算法的基础,通用的矩阵乘法加速器设计一直是嵌入式系统设计的研究热点。但矩阵乘法由于计算复杂度高,处理效率低,常常成为嵌入式系统运算速度的瓶颈。为了在嵌入式领域更好地使用矩阵乘法,提出了基于MPSoC(MultiProcessor System-on-Chip)的软硬件协同加速的架构。在MPSoC的架构下,一方面,设计了面向硬件约束的矩阵分块方法,从而实现了通用的矩阵乘法加速器系统;另一方面,通过利用MPSoC下的多核架构,提出了相应的任务划分和负载平衡调度算法,提高了并行效率和整体系统加速比。实验结果表明,所提架构及算法实现了通用的矩阵乘法计算,并且通过软硬件协同设计实现的多核并行调度算法与传统单核设计相比在计算效率方面得到了显著的提高。     

基于BLACS的2.5D并行矩阵乘法

并行矩阵乘法是线性代数中最重要的基本运算之一,同时也是许多科学应用的基石.随着高性能计算(HPC)向E级计算发展,并行矩阵乘法的通信开销所占比重越来越大.如何降低并行矩阵乘法的通信开销,提高并行矩阵乘的可扩展性是当前研究的热点之一.本文提出一种新型的分布式并行稠密矩阵乘算法,即2.5D版本的PUMMA(Parallel...     

从大型体数据集中生成等值面的并行算法

从体数据集中生成等值面是体可视化的主要技术之一。当体数据集的数据量很大时，计算量也随之增大，单处理机的存储与计算能力难以胜任其可视化要求，基于并行与分布式计算环境设计并行可视化算法是有效的办法。本文基于工作站群机系统的ＰＶＭ环境，设计并实现了一种有效的、从大型体数据集中生成等值面的并行算法。     

对称矩阵三对角化的混合并行算法设计

基于Householder转换,给出了稠密对称矩阵三对角化的MPI＋OpenMP混合并行算法。内容集中在SMP集群系统环境下算法的负载平衡、通信开销和性能评价。OpenMP共享内存并行采用了粗粒度方法,解决了MPI算法中的负载平衡问题,降低了通信开销。在深腾6800上的试验结果表明,MPI＋OpenMP版本比纯MPI版本具有更好的性能和可扩展性。     

基于直径为2的摩尔图网络的并行矩阵乘算法

提出了一个并行矩阵乘算法IPBPMM(Interconnected Processor-Based Parallel Matrix Multiplication).该算法运行在以五角形、Petersen图和Hoffman-Singleton图等直径为2的摩尔图(满足n=d2+1,n为节点数,d为度)为拓扑结构的由n个独立处理器构成的机群并行计算环境中.与基于二维环绕网孔阵列拓扑结构的Cannon和Fox等并行矩阵乘法算法相比较,IPBPMM算法通信开销较小,加速比更高,同时还具有矩阵分块可随机分布在各个节点中,无需事先按一定规律装入各节点中的特点.同时IPBPMM算法也能很好地扩充到由多个直径为2的摩尔图为拓扑结构组合构成的并行计算环境中,且随着网络的扩大,算法的并行加速比更高.     

基于搜索空间划分的并行概念生成算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。本文提出了一种基于搜索空间划分的并行概念生成算法,它对整个闭包搜索空间进行划分,并引入一种有效的测试方法,只搜索那些能生成正规闭包的子搜索空间,从而有效提高搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度;由于所有子搜索空间相对独立,因此很容易得到一个井行的概念生成算法。     

一种基于MPI与OpenMP的矩阵乘法并行算法

阐述MPI与OpenMP进行并行计算的特点,并在Visual Studio 2010上构建一个基于两者的混合编程平台。程序在该平台上执行时能够同时实现多进程与进程内多线程编程,设计并实现一种基于数据划分的矩阵乘法的并行算法,将数据分解为两部分交给两个计算节点分别完成,并在每个计算节点内将数据进一步划分,交给多个线程同时执行。通过与非并行矩阵乘法、MPI矩阵乘法、OpenMP矩阵乘法运算性能进行比较,验证该算法可以有效地挖掘计算机的处理能力。     

多核计算机上非递归并行计算矩阵乘积

提出延迟隐藏的数据预取模型,实现计算与访存的重叠操作,以达到共享二级缓存零缺失;给出基本块的概念,以简化算法的数据结构和减少存储开销;按基本块连续存储方式存储矩阵元素,从存储层次上优化算法,显著地减少页表缓冲缺失;采取非递归调度基本块的策略,充分利用多核计算机的共享二级缓存来减少访问主存的次数,并且不局限于某种特定的存储结构,实现算法缓存无关.多核计算机上的实验结果表明,给出的非递归计算矩阵乘积的线程级并行算法高效、可扩展.