基于COW系统的并行求和算法研究

针对并行求和问题,在Linux环境下组建了一个COW系统,并介绍了在COW系统上的并行求和算法的设计和实现,分析了影响算法性能的因素并提出改进方法,最后给出了并行求和算法在改进前后的实验数据。实验结果表明,当n=2000000时,用改进的算法在两台联想启天4000上测得并行求和效率为80%,而算法改进前在相同的条件下测得并行效率为66.7%,并行效率明显提高。     

基于COW系统的并行求和算法研究

针对并行求和问题,在Linux环境下组建了一个COW系统,并介绍了在COW系统上的并行求和算法的设计和实现,分析了影响算法性能的因素并提出改进方法,最后给出了并行求和算法在改进前后的实验数据.实验结果表明,当n=2000000时,用改进的算法在两台联想启天4000上测得并行求和效率为80%,而算法改进前在相同的条件下测得并行效率为66.7%,并行效率明显提高.     

基于Winograd卷积的并行深度卷积神经网络优化算法

针对并行深度卷积神经网络算法在大数据环境下存在冗余特征计算过多、卷积运算性能不足和参数并行化合并效率低等问题，提出了基于Winograd卷积的并行深度卷积神经网络优化算法。首先，该算法提出基于余弦相似度与归一化互信息的特征过滤策略，通过先筛选后融合的方式消除了通道间对于冗余特征的计算，以此解决了冗余特征计算过多的问题；然后，结合MapReduce提出了并行Winograd卷积策略，通过使用并行化Winograd卷积运算替换传统卷积运算的方式来提升卷积运算的性能，以此解决了卷积运算性能不足的问题；最后，提出基于任务迁移的负载均衡策略，通过动态负载迁移的方式来均衡集群中各节点之间的负载，降低了集群总体的平均反应时长，以此解决了参数并行化合并效率低的问题。实验表明，WP-DCNN算法显著降低了DCNN在大数据环境下的训练代价，而且对并行DCNN的训练效率也有大幅提升。     

分子动力学模拟中负载平衡方法的应用

文章针对三维分子动力学并行数值模拟中出现的负载不平衡现象,在静态负载平衡基础上,提出了一种简单有效的动态负载平衡算法。通过对三维分子动力学的并行数值模拟试验,此算法可以使得负载基本达到动态平衡,并进一步提高了并行效率。     

块三对角线性方程组的一种并行迭代算法

系统工程计算在科学计算中,单台处理机不能满足需要,为提高计算效率和精度,采用并行处理是一个非常好的块三对角线性方程组的办法,提出了分布式环境下求解块三对角线性方程组的一种并行计算,算法是充分利用系数矩阵结构的特殊性,通过对系数矩阵进行适当地分解构造的迭代算法,使得算法需要在相邻处理机之间进行并行通信三次.并从理论上给出了算法收敛的一个充分条件.最后,在HP rx2600集群上进行了数值仿真,结果表明,实算与理论是一致的,提高了并行效率和精度.     

多核系统下并行节点复制垃圾收集算法

为了提高垃圾收集效率,减少用户程序等待时间,提出了一种在多核系统下基于LISP2算法的并行节点复制算法。该算法通过把LISP2算法的4个垃圾收集阶段分别并行化来实现并行垃圾收集。实验结果显示,该算法在多核系统下能有效提高垃圾收集效率。     

并行数据库中JOIN运算的并行算法

JOIN运算的并行算法一直是并行数据库领域中研究的热点问题,先后出现了一系列并行JOIN算法或改进算法,但它们都存在着通信效率较低、负载调度频繁等问题。本文针对这些问题,在分析比较前人工作的基础上对湖＋算法与ABJ＋算法加以改进,得到了效率更高的并行JOIN算法ABJ＋＋。     

基于时间分解求解时间依赖问题的并行算法研究

基于Lions等建立的Parareal模型,提出了改进的时间分解并行算法,并给出收敛性证明．采用主从模式构造了通用的MPI算法流程,通过分析算法的并行加速比给出了最佳的粗细网格步长之比．在集群系统下分别对热传导方程和对流扩散方程进行并行计算,证明了算法无论对线性还是非线性的问题均具有良好的适应性和扩展性．数值模拟结果表明:时间分解并行算法仅需极少的迭代次数即能取得很高的计算精度,且具有较好的并行加速比和并行效率．     

高阶矩量法的超级电磁计算研究

矩量法是广泛使用的高精度电磁数值算法之一。在仿真复杂电磁问题时,该算法需要处理大型复数稠密矩阵方程,这导致其面临内存需求高、计算时间长的问题。与传统基函数相比,本文采用的高阶多项式基函数能够在保证计算精度的前提下大幅度降低未知量,进而降低矩阵阶数。在此基础上,本文设计了基于分块矩阵的高效并行策略,在国内超级计算机平台开展了并行高阶矩量法的超级电磁计算研究,大幅度提升了矩量法的仿真能力。在国产神威蓝光超级计算机上,以机载天线阵列的辐射特性计算为例,对并行规模高达30720 CPU核时的算法性能进行了评估,测试结果表明算法在并行规模扩大20倍以上时仍可获得50%以上的并行效率。在当前排名世界第一的天河2号超级计算机上,以飞机散射特性计算为例,对并行规模高达201600 CPU核时的算法性能进行了评估,测试结果表明算法在并行规模扩大约8倍时可获得50%以上的并行效率。数值仿真结果表明并行高阶矩量法可以在不同架构的超级计算机上高效完成复杂电大目标的精确电磁计算。     

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。     

基于MPI的伪随机序列并行加密算法研究

伪随机序列并行加密算法是科学与工程领域中极为重要的问题，拥有广泛的应用领域。而MPI是现在最流行的并行编程的工具，基于MPI的并行计算是现在被关注的热点。伪随机序列并行加密算法存在研究和实现上的困难，主要原因就是没有一个有效对它进行支持的工具。本文将伪随机序列并行加密算法与MPI结合起来，研究如何提高伪随机序列并行加密算法的效率。通过实验模拟和算法分析，证明这是有效的。因此，基于MPI的伪随机序列并行加密算法将会为相关应用和研究领域提供新的方法和方向。     

一种适于串行机实现的图像并行细化算法

为解决现有的图像并行细化算法在串行机上的高效实现问题 ,首先提出了一种 4× 4邻域二值图像的双字节图像编码方案 ,由于在该方案中将每个 4× 4邻域的像素用一个双字节的整数来表示 ,从而将基于整个邻域 16个像素的细化处理转化为一个双字节整数的读、写和比较运算的问题 ;然后在此基础上提出了一种可在串行机上实现的并行细化算法。实验证明 ,该算法适用于当前通用的各种基于模板匹配的并行细化算法 ,其不仅可以取得完全相同的细化结果 ,而且可以大幅度提高图像细化过程在串行机上的执行速度 ;最后简要讨论了该算法利用 PC机中的 MMX技术来进一步提高并行粒度和运算效率方面所具有的潜力     

基于CUDA的Prewitt算子并行实现

Prewitt算子是数字图像分割中最常用的边缘检测算法,由于计算量大,传统的基于CPU的串行算法耗时较长.为了提高算法的计算效率,本文把Prewitt算子在CUDA架构下并行实现,并通过对不同分辨率图像的处理实验,与串行算法的处理时间进行比对,列出加速比.实验结果表明并行算法的加速效果显著,对提高图像处理系统的运行效率具有实际意义.     

利用改进遗传算法的参数估计

基于极大似然法的参数估计实质上是一个复杂的非线性优化问题,传统的优化方法计算效率较低且容易陷入局部极值。而遗传算法是一种有导向的随机搜索方法,能以较大的概率收敛到全局最优解。本文将单纯形法引入到并行遗传算法中,提出了一种改进的遗传算法,可以有效地提高算法的收敛速度、防止搜索过程中的早熟现象。应用于系统初始状态未知时的参数估计问题,获得了满意的结果。     

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

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

一类基于Euler－Richardson外插的并行算法

构造了一类基于Ｅｕｌｅｒ－Ｒｉｃｈａｒｄｓｏｎ局部外插的并行算法，设计了使各处理机计算量分配更加平衡的方案，分析了方法的精度，稳定性，计算复杂性以及加速比和效率。数值试验结果表明方法是有效的，文中所构造的算法可用于大系统的数字仿真和科学计算。     

基于并行的快速碰撞检测算法的研究

为了提高检测速度,提出了一种基于并行的快速碰撞检测算法,该算法首先将任意多面体的剖分为多个四面体,然后对四面体进行并行碰撞检测,并通过建立包围盒树进一步提高算法的效率,并行算法采用基于MPI库方式来实现.结果表明,该算法显著提高检测速度并具备较高精度.     

全球(z)双三次数值模式并行算法设计与实现

针对双三次数值天气预报模式进行了并行算法研究。采用一维区域分解算法,借鉴块棋盘划分矩阵转置算法,设计和实现了数据转置通信算法,并采取计算与通信重叠技术减小通信时间对并行效率的影响,最终实现了双三次数值天气预报模式的并行算法,并在机群系统上进行了并行性能测试评估。结果表明,实现的双三次数值预报模式并行算法的并行效率较高,设计实现的数据转置通信算法、计算与通信重叠技术取得了较好的效果。     

基于CUDA的k-means算法并行化研究

k-means算法在面对大规模数据集时,计算时间将随着数据集的增大而成倍增长。为了提升算法的运算性能,设计了一种基于CUDA(Compute Unified Device Architecture)编程模型的并化行k-means算法,即GS_k-means算法。对k-means算法进行了并行化分析,在距离计算前,运用全局选择判断数据所属聚簇是否改变,减少冗余计算;在距离计算时,采用通用矩阵乘加速,加快计算速度;在簇中心点更新时,将所有数据按照簇标签排序分组,将组内数据简单相加,减少原子内存操作,从而提高整体性能。使用KDDCUP99数据集对改进算法进行实验,结果表明,在保证实验结果的准确性的情况下,改进算法加快了计算速度,与经典的GPUMiner算法相比加速比提升5倍。     

Tree-Based Parallel Algorithm Design

In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation trees and/or expressions is presented. This method involves the use of uniform closure properties of certain classes of unary functions. Using this method, optimal parallel algorithms are given for many computation tree problems which are important in parallel algebraic and numerical computation, and parallel code generation on exclusive read and exclusive write parallel random access machines. Our algorithmic result is complemented by a P-complete tree problem. Received February 13, 1995; revised March 25, 1996.