异构BSP模型及其通信协议

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

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

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

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

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

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

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

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

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

基于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程序的运行效率 .给出了在这两种模型下实现并行排序算法的时间代价比较 .

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.

云平台下图数据处理技术

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

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

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

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

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

并行计算模型在异构计算环境中的研究

近年来异构并行计算在高性能科学计算和通用应用领域受到广泛研究。本文结合多种代表性并行计算模型,给出异构环境中的HBSP模型和程序开销计算方法。采用基于消息长度的线性模型使通信开销的计算更精确,解除原有BSP模型对h-rela-tion的限制,使程序和算法在异构环境中的设计更加灵活。当构成BSP计算机的各处理机速度相同且原有BSP算法达到最优(即各处理机上所分配的计算量与通信量完全均衡)时,HBSP模型等同于原有模型。

大规模图数据划分算法综述

对大规模图数据划分算法进行了总结,介绍了并行环境下图计算模型,详述了大规模静态图划分算法和动态图划分算法,归纳了这些算法的优缺点以及适应性。最后,指出了关于大图划分尚未探索的有意义的研究课题。

面向大数据应用的多层次混合式并行方法

基于很多大数据应用存在对数据进行多种并行处理的需求,提出两层混合式并行方法,即执行单元的混合并行和计算模型的混合并行.通过在同一个计算节点上执行单元的混合并行,充分挖掘基础设施的计算能力,从而提高数据处理性能;采用在同一个执行引擎中集成多个计算模型的并行方法,以适合应用多样异质处理模式.不同的混合并行方法可以契合不同的数据和计算特点,以满足不同的并行目标.介绍了混合式并行方法的基本思想,并以前期开发的并行编程模型BSPCloud为基础,阐述了进程和线程混合并行、BSP和Map Reduce混合并行的主要实现机制.

基于图计算的快速非线性迭代法求解潮流计算

为快速求解潮流计算问题,文章给出一种基于整体同步并行计算模型(Bulk Synchronous Parallel Computing Model,BSP)的全节点并行迭代算法。在利用佩奇排序实现并行机制的基础上,用图数据模型实现了电力网络全节点的并行的潮流迭代计算。基于实际电网算例和国际标准算例进行验证,其结果说明该方法可以在常规服务器上实现万级节点系统百毫秒级、十万节点秒级、百万节点10 s级的计算速度,极大提升现有EMS系统的计算分析效率。

Towards adaptable and tunable cloud-based map-matching strategy for GPS trajectories

智慧城市为智能交通管理和交通网络智能应用的发展提供了巨大推动力。近来,智能交通系统(Intelligent transportation systems,ITSs)和移动位置服务(Location-based services,LBSs)也成为了研究领域的热点。交通领域数据量在快速不断增长,云计算在巨量数据的存储、接入、管理和处理方面有着巨大作用。交通领域相当比例的数据为GPS数据,此类数据具有非频繁、含噪声等特性,这使得维护基于GPS的实时交通软件的服务质量较为困难。在诸多智能交通系统应用中,地图匹配处理起着将GPS观测点准确排列于路网中的关键作用。考虑到准确性时,地图匹配策略的性能由两个连续的GPS观测点间的最短路径决定;另一方面,处理最短路径查询(Processing shortest path queries,SPQs)耗费着较高计算量。现有的地图匹配技术采用固定参数(固定的候选点数量,固定的误差圆半径)的办法,这可能导致确认线路分段时产生不确定性,也可导致低精度结果(或需进行大量SPQ处理以保证精度)。此外,由于采样错误的存在,较高采样时间(大于10 s)内的GPS数据常含有冗余数据,这也导致需要额外的SPQ处理。由于SPQ处理导致的高运算量问题,现有的地图匹配策略并不能实现实时应用。在本文中,我们提出一种实时地图匹配方法(Real-time map-matching,RT-MM)。该方法以云计算为基础,是一种全自适应地图匹配策略,能够应对实时GPS轨迹地图匹配中SPQ处理的关键问题。本研究还通过基于虚拟数据和实际数据的仿真,对所述方法与现有方法的性能进行了比较。