共查询到17条相似文献,搜索用时 171 毫秒
1.
迭代空间交错条块并行Gauss-Seidel算法 总被引:1,自引:0,他引:1
针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性. 相似文献
2.
高效的并行有限差分Stencil 算法对于求解大型线性方程组是十分重要的.针对并行有限差分Stencil 算法中数据局部性差、同步和通信开销大的问题.首先改进传统有限差分Stencil 算法,提出了多层对称遍历有限差分Stencil 算法.然后给出了以迭代空间条块序作为执行序的串行算法,通过沿时间轴对迭代空间进行时滞划分,在不改变迭代算法性质的同时,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行算法,该算法利用改进的多面体模型对迭代空间网格划分,并通过网格条块重排序减少了Cache 缺失率、通信启动和同步次数.理论分析和实验结果表明,该并行模型比传统的区域分解方法和红黑排序并行算法具有更好的数据局部性,并行效率和可扩展性. 相似文献
3.
4.
5.
针对大数据环境下传统并行密度聚类算法中存在的数据划分不合理,聚类结果准确度不高,结果受参数影响较大以及并行效率低等问题,提出一种MapReduce下使用均值距离与关联性标记的并行OPTICS算法——POMDRM-MR。算法使用一种基于维度稀疏度的减少边界点划分策略(DS-PRBP),划分数据集;针对各个分区,提出标记点排序识别簇算法(MOPTICS),构建数据点与核心点之间的关联性,并标记数据点迭代次数,在距离度量中,使用领域均值距离策略(FMD),计算数据点的领域均值距离,代替可达距离排序,输出关联性标记序列;最后结合重排序序列提取簇算法(REC),对输出序列进行二次排序并提取簇,提高算法局部聚类的准确性和稳定性;在合并全局簇时,算法提出边界密度筛选策略(BD-FLC),计算筛选密度相近局部簇;又基于n叉树的并集型合并与MapReduce模型,提出并行局部簇合并算法(MCNT-MR),加快局部簇收敛,并行合并局部簇,提升全局簇合并效率。对照实验表明,POMDRM-MR算法聚类效果更佳,且在大规模数据集下算法的并行化性能更好。 相似文献
6.
7.
基于半经典分子动力学模型,在SMP集群中实现激光化学反应双层并行模拟系统。结合粗粒度的原子分解算法和细粒度的矩阵并行乘法实现激光化学反应模拟中力计算部分的并行化,分析粒度划分对半经典分子动力学模拟并行效率的影响。在SMP集群中测试表明,采用128个处理器模拟由500个C原子构成的分子体系,并行效率可达70%。在CPU数量固定的情况下,SMP节点内的细粒度的并行对提高半经典分子动力学模拟并行效率影响较大。该系统能够模拟大分子体系的激光化学反应,在提高加速比的同时保证计算资源的利用效率,满足激光化学反应模拟需求。 相似文献
8.
吴明光 《中国图象图形学报》2013,18(10)
空间数据划分是空间索引、并行GIS数据分解以及分布式数据管理与调度等问题的核心环节之一。本文针对点数据集多目标空间划分问题,在Hilbert空间填充曲线的基础上建立随机、规则、聚集三类空间分布模式的判定模型,设计针对均匀和随机分布模式的等差划分以及针对聚集分布模式的迭代寻优划分。实验表明该方法能够在缺少覆盖范围信息的条件下准确判定空间分布类型,该方法能够兼顾空间聚集性、数据量均衡与空间重叠度三种约束条件。 相似文献
9.
为了研究GPU的通用计算能力和适合SMP集群的编程模型,首次提出MPI+CUDA多粒度混合并行编程的新方法,节点间采用MPI实现粗粒度并行,节点内采用CUDA实现细粒度并行的混合编程方式.利用此方法在搭建的3节点SMP集群环境中,测试了大规模矩阵乘问题的并行计算能力.实验结果表明,该方法能够显著提升并行效率,同时证明MPI+CUDA混合编程模型能够充分发挥SMP集群节点间分布式存储和节点内共享内存的优势,为装有CUDA-enabled GPU的SMP集群提供了一种有效的并行策略. 相似文献
10.
逐次松弛迭代算法(SOR)是求解线性方程组的一种常用迭代算法,当系数矩阵正定时,它具有较快的收敛速度。但是,由于每个迭代步内存在数据相关,它难以实现并行计算。目前的SOR并行算法采用数据分解的方法,但由于该法并行区域过小,同步通讯代价大,并行效率低。本文提出了SOR的一种新型并行算法,该算法与传统SOR方法等价,具有相同的收敛性和迭代结果。该并行算法通过矩阵分块增大了可并行计算的区域,并引入流水线技术,利用各处理器间通讯与计算时间的重叠,获得较理想的并行加速效率。通过多核微机以及小规模集群上的数值实验证明,本文提出的SOR并行算法在求解大型稠密线性方程组时具有较好的并行效率。 相似文献
11.
Guangping Tang Wangdong Yang Kenli Li Yu Ye Guoqing Xiao Keqin Li 《Concurrency and Computation》2015,27(17):5076-5095
An optimized parallel algorithm is proposed to solve the problem occurred in the process of complicated backward substitution of cyclic reduction during solving tridiagonal linear systems. Adopting a hybrid parallel model, this algorithm combines the cyclic reduction method and the partition method. This hybrid algorithm has simple backward substitution on parallel computers comparing with the cyclic reduction method. In this paper, the operation count and execution time are obtained to evaluate and make comparison for these methods. On the basis of results of these measured parameters, the hybrid algorithm using the hybrid approach with a multi‐threading implementation achieves better efficiency than the other parallel methods, that is, the cyclic reduction and the partition methods. In particular, the approach involved in this paper has the least scalar operation count and the shortest execution time on a multi‐core computer when the size of equations meets some dimension threshold. The hybrid parallel algorithm improves the performance of the cyclic reduction and partition methods by 19.2% and 13.2%, respectively. In addition, by comparing the single‐iteration and multi‐iteration hybrid parallel algorithms, it is found that increasing iteration steps of the cyclic reduction method does not affect the performance of the hybrid parallel algorithm very much. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献
12.
Original methods to solve an iterative sequence of Lyapunov equations are detailed. The first one is based on the eigenvalue–eigenvector approach. The second one considers the Schur reduction method. The third one takes into account the linearity of the equations. These methods are based on classical approaches, by optimizing the elapsed time by minimizing computation quantity. In fact, in classical approaches, there are some computations repeated in each iteration. The proposed approaches are based on the fact that these computations are executed just before the first iteration. In such case, a corresponding algorithm is developed, and is decomposed into two steps. The first step considers all common computations. In the second step, the solution is directly given at each iteration. Simulation results confirm the performance of the presented approaches, which decrease the computational quantity and increase the algorithm speed. 相似文献
13.
边缘海静力数值模式是国内针对边缘海特点自主开发的数值预报模式,但该模式因物理求解方程较多且采用不宜并行化的SOR求解算法而程序计算时间过长。针对上述问题,提出基于三维网格和海洋模式特点的SOR并行求解算法,该算法在保留三维网格数据间依赖关系的同时,有效解决了SOR迭代算法难以并行化的问题。同时,引入通信避免算法,采用MPI非阻塞通信方式,细分计算和通信过程,利用计算有效隐藏通信开销,提高了并行程序效率。实验结果表明,并行后的边缘海静力数值模式程序的性能相对串行程序提升了60.71倍,3天(25920计算时间步)预报结果的均方根误差低于0.001,满足海洋数值预报的时效性和精度要求。 相似文献
14.
CORDIC算法是一种适合硬件电路实现的循环迭代算法,可用简单的加减和移位运算完成复杂函数运算。本文介绍了CORDIC算法理论的矢量模式,在分析比较得出位串行CORDIC结构优于位并行CORDIC结构之处的基础上,提出了解决位串行迭代结构溢出的方法,并设计了结构图。设计实现反正切函数模块,在Modelsim平台上仿真验证了其准确度和精度。 相似文献
15.
A parallelized point rowwise Successive Over-Relaxation (SOR) iterative algorithm is developed for the Heterogeneous Element Processor (HEP) multiple instruction stream computer. The classical point SOR method is not easily vectorizable with rowwise ordering of the grid points, but it can be effectively parallelized on a multiple instruction stream machine without suffering in computational and convergence rate. The details of the implementation including restructuring of a serial FORTRAN program and techniques needed to exploit the parallel processing architectural concept of the HEP are presented. The parallelized algorithm is analyzed in detail. The lessons learned in this study are documented and may provide some guidelines for similar future coding since new approaches and restructuring techniques are required for programming a multiple instruction stream machine, which are totally different than those required for programming an algorithm on a vector processor. To assess the capabilitiesof the parallelized algorithm it was used to solve the Laplace's equation on a rectangular field with Dirichlet boundary conditions. Computer run times are presented which indicate significant speed gain over a scalar version of the code. For a moderate to large size problem seventeen or more processes are required to make efficient use of the parallel processing hardware. Also, to demonstrate the capability of the algorithm for a realistic problem, it was used to obtain the numerical solution of a viscous incompressible fluid in a square cavity. Since point iterative relaxation schemes are at the core of many systems of elliptic as well as non-elliptic partial differential equations occuring in engineering and scientific applications, the present study suggests the possibility of both reducing the real time processing and increasing the scope of computational modeling. 相似文献
16.
全局同步计算模型简单易用,但是路障同步导致收敛速度变慢。以顶点为中心的异步迭代虽然提高了收敛速度,但在计算节点之间需要频繁发送信息。在Spark环境下提出一种基于子图的异步迭代更新方法。在子图之间建立异步消息通信连接后,子图能以异步方式发送数据块;通过多线程同步避免数据读写冲突,保证异步更新时顶点状态的一致性。在大规模样本数据集上分别从收敛结果、收敛速度和通信代价验证方法有效性。实验结果表明,与全局同步迭代相比,该方法有效提高了计算收敛速度。与顶点为中心的异步更新方式相比,该方法在收敛时间上略有增长,但是显著降低了通信开销。 相似文献