Hierarchical Bulk Synchronous Parallel Model and Performance Optimization

Based on the framework of BSP, a Hierarchical Bulk Synchronous Parallel (HBSP) performance model is introduced in this paper to capture the per formance optimization problem for various stages in parallel program development and to accurately predict the performance of a parallel program by considering fac tors causing variance at local computation and global communication. The related methodology has been applied to several real applications and the results show that HBSP is a suitable model for optimizing parallel programs.

异构BSP模型及其通信协议

异构并行计算由于其较高性能价格比而在高性能科学计算和通用应用领域受到广泛研究 .但由于异构并行程序设计与性能分析仍处于经验阶段 ,开发实用程序较为困难 .本文提出异构环境中的HBSP模型 ,并导出相应的开销预测方法 ,能有效指导异构并行程序的设计与分析 .所设计并实现的HBSP模型的通信协议能运行于所有支持MPICH软件包的计算平台 .最后以并行FFT算法为例 ,给出相应的算法设计和实际测试结果 .

一种异步BSP模型及其程序优化技术

基于 BSP模型 ,该文提出了异步计算模型 (CSA- BSP) .该模型更准确地描述了并行机的性能参数 ,引导用户编写高效率的并行程序 ;在 CSA- BSP模型下 ,两个进程异步执行的位置至多相差 p- 1个超步 ;基于程序的执行时间 ,作者分析了 BSP、A- BSP和 CSA- BSP程序的效率 ,得出 CSA - BSP程序的效率是最高的 .在曙光并行机上 ,用“红黑格法”和“矩阵乘法”进行了验证 ,和 BSP模型相比 ,这两个 CSA- BSP程序的效率分别提高 2 0 %和 37% ;同时 ,其进程执行时间的和最大可以降低 8% .因此 ,按照 CSA- BSP模型编程对于提高程序效率和改善系统的吞吐率 ,都有良好的效果 .

并行BSP模型在实时集群系统中的应用

分析BSP并行计算模型在多源数据处理中的应用特点。构建实时集群计算机系统的并行计算BSP模型。对多源任务数据处理的粒度进行了分析设计。给出了实时集群计算机系统中BSP模型的实现算法。实际应用验证了算法的有效性。

基于BSP的并行对象-关系型数据库的分析和设计

以含幺半群演算（Ｍｏｎｏｉｄ ｃａｌｃｕｌｕｓ）为基础，构造了统一的数据模型．该模型形式简单，表达能力强，容易扩充，几乎能表示所有ＳＱＬ３ 和对象查询语言（ＯＱＬ）查询．以块同步并行（ＢＳＰ）模型为通用并行环境，设计、分析了多种一维数据分布方法，采用较适合ＢＳＰ的（ａ，ｂ）树作为存储结构，并对查询优化、事务处理及主要数据库操作（如Ｊｏｉｎ 算法、外部排序算法）等进行了分析．结果表明，结合Ｍｏｎｏｉｄ

异构环境HBSP模型及其在FFT算法中的应用

提出了异构块同步并行 ( HBSP)模型和程序开销计算方法 ,依据通信开销线性模型和处理机利用率来研究异构环境中算法的设计和分析 .以快速傅立叶变换 ( FFT)为例 ,给出了相应的算法设计和分析结果 .当构成块同步并行 ( BSP)计算机的各处理机速度相同 ,且原有 BSP算法达到最优 (即各处理机上所分配的计算量与通信量完全均衡 )时 。

一个有效的并行模型——BSP并行模型

为了设计各种体系结构的通用并行模型,本文分析了现有并行模型中存在的问题,提出了一个有效的BSP并行模型,详述了BSP计算机的组成及其运行过程。

基于BSP并行计算模型的并行微粒群算法

在对标准微粒群算法分析的基础上,将它与BSP并行计算模型相结合,设计并实现了一种基于BSP并行计算模型的并行微粒群算法。这种基于BSP并行计算模型的并行微粒群算法改变了标准微粒群算法的结构,提高了算法求解效率。实验结果表明,该并行算法的性能比标准微粒群算法有了很大的提高。

基于MPI环境的A-BSP模型的性能评测

针对一种异步的BSP模型(A-BSP),选用6种常用的通信模式代替随机h关系,在曙光集群MPI环境和不同的处理器数量条件下,对A-BSP模型的2个主要参数g和L进行评估,并根据快速傅立叶变换(FFT)的并行化方法,以一种基2并行FFT算法,验证利用A-BSP模型进行MPI程序代价分析的正确性和有效性。在曙光TC1700集群服务器上测得A-BSP模型的参数g为6.07×10-8s/byte,L为1.47×10-4s。在曙光集群上,A-BSP模型所有参数的变化范围基本被限定在某一区间内,且h关系时间受通信模式的影响要比受处理器数量的影响更为明显。A-BSP模型能够有效地指导MPI并行程序设计。

BHP:面向BSP模型的负载均衡Hash图数据划分

图数据划分是基于BSP(bulk synchronous parallel)编程模型的大规模图处理系统中一个关键技术问题。传统的图划分技术需要多次迭代,时间复杂度过高,且划分结果不具有图顶点到分区的映射信息,因此这些算法并不适用于BSP模型下的数据划分。提出了一种新的面向BSP模型的负载均衡Hash数据划分算法(balanced Hash partition,BHP)。为了实现各个分区的出边数尽可能均衡,该算法引入了虚拟桶的概念,通过贪婪算法将虚拟桶重组为实际分区,保证了每个实际分区负载均衡,同时数据本地化策略使本分片上的数据尽可能地保留在本节点上,从而减小在数据加载时的数据迁移开销。从三个方面对比了BHP算法和经典Hash算法的性能,结果表明BHP算法能够提高作业的执行效率,减少消息发送的数量,有效解决了经典Hash算法的负载不均衡和分区间交互边过多的问题,当数据量变大时,效果尤为明显。

PRAM,BSP和LogP并行模型之间的关系及其比较

本文详细讨论了ＰＲＡＭ，ＢＳＰ和ＬｏｇＰ三种并行模型．我们提出用一个五元组（Ｐ， Ｇ， Ｏ， Ｌ， Ｓ）来概括这三种模型，并指出它们之间的关系．本文还讨论了这三种模型各自的优缺点。

基于BSP的SPARQL基本图模式查询算法

随着语义网的不断发展,发布在互联网上的资源描述框架(RDF)数据达到百亿级三元组规模,并且呈现几何增长趋势,针对RDF数据的单机SPARQL查询方法已经不再适用。为此,提出一种基于整体同步并行(BSP)模型的SPARQL基本图模式查询算法。根据RDF有向图数据特性及基本图模式定义,将整个查询过程分成匹配和迭代2个阶段,在匹配出所需查询的三元组模式后,通过迭代使部分解逐步逼近完全解,得到最终查询结果。利用HAMA分布式计算框架进行算法实现,实验结果表明,与基于MapReduce的SPARQL查询算法相比,该算法具有较高的查询效率,能为大规模RDF数据的快速SPARQL查询提供支持。

StepMatch:一种基于BSP计算模型的SPARQL基本图模式匹配算法

随着语义网的发展,越来越多的数据通过资源描述框架(resource description framework,RDF)格式发布出来.目前有很多研究使用MapReduce计算模型处理大规模RDF数据,将SPARQL查询拆分成多步迭代.对于更适合使用消息传递模型来解决的图计算问题,MapReduce并非是最佳的选择.StepMatch算法基于整体同步并行(bulk synchronous parallel,BSP)计算模型,能有效解决SPARQL的基本图模式匹配查询.StepMatch是一个面向顶点的算法,RDF图中每一个顶点都被视为一个计算单元,顶点可以执行计算并向其他顶点发送消息.对于一个给定的SPARQL查询,StepMatch算法的超步数量与SPARQL查询包含的子句数目相等.最后,实现了StepMatch算法,并在合成的LUBM(Lehigh University Benchmark)数据集和真实的DBpedia数据集上进行了性能实验.

一个块同步并行(BSP)的改进I/O代价模型

提出了一个改进的 BSP的 I/ O代价模型 ,不但易于实现 ,而且利用该模型能减少 I/ O、通信及同步时间 ,显著地提高 BSP程序的运行效率 .给出了在这两种模型下实现并行排序算法的时间代价比较 .

3D点云BSP并行计算模型及算法设计

根据3D点云数据处理计算特点,按照BSP模型的技术思想,建立了3D点云BSP并行计算模型。讨论了HAMA框架下的3D点云BSP并行计算模型的实现方法,构建了一个由普通PC组成的HAMA计算集群。以3D点模型构建计算为例,给出了一种3D点云数据处理BSP算法设计方法。实例的计算结果表明:BSP并行计算方法能高效地完成3D点模型构建计算,与其它计算方法相比,计算效率有所提高。

并行计算模型研究

并行计算模型是并行计算机基本特征的抽象,是并行算法设计和分析的基础,其重要性类似于顺序计算的存储程序模型,因而受到广泛的关注。虽然提出了大量的并行计算模型,但是仍无一通用模型。本文概述了并行计算模型的一些基本概念,介绍了理想计算模型的特征,讨论了一些典型的并行计算模型,综述了目前并行计算模型在异构计算环境的发展情况。

云平台下图数据处理技术

针对Hadoop云平台下MapReduce计算模型在处理图数据时效率低下的问题,提出了一种类似谷歌Pregel的图数据处理计算框架——My BSP。首先,分析了MapReduce的运行机制及不足之处;其次,阐述了My BSP框架的结构、工作流程及主要接口;最后,在分析PageRank图处理算法原理的基础上,设计并实现了基于My BSP框架的PageRank算法。实验结果表明,基于My BSP框架的图数据处理算法与基于MapReduce的算法相比,迭代处理的性能提升了1.9~3倍。My BSP算法的执行时间减少了67%,能够满足图数据高效处理的应用前景。

一个可预测并行程序效率的评价模型

并行程序的性能分析 ,特别是效率分析往往需要程序在实际运行后 ,根据实验结果再对并行算法进行优化 ,或改变数据的分配策略 ,甚至重新选择并行算法 .结合通用并行计算模型 BSP( bulk- synchronousparallel) ,提出一种有效的并行程序效率评测模型 ,使得程序员在设计、分析阶段即可对程序效率进行分析和评估 ,并据此进一步优化程序 .实验结果表明 ,该模型的预测是精确的 .

并行计算模型在集群环境下的适应性

分析了并行计算机模型和集群系统的特点，研究了BSP并行计算模型在集群环境下的适应性，指出通过合理地设计并行算法，某些算法在集群环境下可以获得近似线性的加速比，并用常用的线性规划标准形改进单纯型求最优解，在集群系统上的并行算法验证了该结论。

更实际的异构并行计算模型

通过结合多种代表性并行计算模型，给出异构环境中的HBSP模型和程序开销计算方法。采用基于消息长度的线性模型具有通信开销的计算更精确、程序和算法在异构环境中的设计灵活、且可解除原有BSP模型对h-relation的限制等优点。当构成BSP计算机的各处理机速度相同且原有BSP算法达到最优（即各处理机上所分配的计算量与通信量完全均衡）时，HBSP模型等同于原有模型。