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

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

基于总线桥协议的异构机群并行虚拟机的构造

ＢＢＰ＿ＰＶＭ是为北京航空航天大学计算机系基于总线桥协议的异构可扩展并行计算机群系统ＢＢＰ＿ＳＰＣ（ｂｕｓｂｒｉｄｇｅｐｒｏｔｏｃｏｌ－ｓｃａｌａｂｌｅｐａｒａｌｅｌｃｏｍｐｕｔｅｒ）研制的ＰＶＭ版本．ＢＢＰ＿ＰＶＭ以总线桥多机互联协议的消息传递层子协议（ＢＢＰ＿ＭＰＬ）为虚拟机内各处理机间的通讯协议．ＢＢＰ＿ＭＰＬ是在ＢＢＰ可靠链路的基础上实现的精简和可靠的机间通讯协议，ＢＢＰ＿ＭＰＬ的采用有效地降低了通讯过程中报文应答、重发和动态缓冲区管理的开销．ＢＢＰ＿ＰＶＭ与ＰＶＭ３．３．４及其以上版本兼容．     

异构分布系统的实时任务轮转式容错调度算法

建立了一个异构分布式系统实时调度模型,对异构分布式系统中的任务及不同处理机资源进行了形式化描述.结合基版本/副版本技术,给出了用于异构分布式系统的实时任务轮转式容错调度算法.实例分析表明,该算法有效提高了异构处理机环境下的资源利用率以及整体计算性能.     

面向异构多核系统的多任务流并行编程模型设计

目前的多任务流并行编程模型难以探测到异构多核系统中存的慢任务和落后任务,存在调用开销高、计算开销高和编程加速比低的问题。为此,设计了新的面向异构多核系统的多任务流并行编程模型。通过寄存器重定向、指令迁移、分离发射和线程切换4个部分组建多任务流并行编程模型,并设计了任务探测算法,探测异构多核系统中存在的慢任务和落后任务,提高了异构多核系统在多任务并行处理过程中的编程灵活性。测试结果表明,该模型的调用开销和计算开销均较低,且编程加速比高。     

CPU/GPU 异构环境下图像协同并行处理模型

随着GPU通用计算能力的不断发展,一些新的更高效的处理技术应用到图像处理领域.目前已有一些图像处理算法移植到GPU中且取得了不错的加速效果,但这些算法没有充分利用CPU/GPU组成的异构系统中各处理单元的计算能力.文章在研究GPU编程模型和并行算法设计的基础上,提出了CPU/GPU异构环境下图像协同并行处理模型.该模型充分考虑异构系统中各处理单元的计算能力,通过图像中值滤波算法,验证了CPU/GPU环境下协同并行处理模型在高分辨率灰度图像处理中的有效性.实验结果表明,该模型在CPU/GPU异构环境下通用性较好,容易扩展到其他图像处理算法.     

基于分布对象的冗余服务模型

针对现有的分布计算模型不能充分描述冗余服务的特点,文中基于分布对象的观点,提出一个面向冗余服务的计算模型ＨＯＲＩＳ。它利用类和实例的概念定义了冗余服务,并将状态服务和无状态服务区分开来,同时还刻画了分布计算环境中的请求和主机的概念。在ＨＯＲＩＳ的基础之上,文中创建了一个冗余服务的管理框架ＡＭＡ,并在ＣＯＲＢＡ平台上进行了实现,与其它冗余服务的管理框架相比,它具有接口开放,适应性强、能管理异构服务以     

存储受限异构机群系统的多目标串近似匹配并行算法

针对处理机节点具有不同的计算能力、通信延迟和存储容量的情形,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,分别建立单层和两层树结构模型的存储受限异构机群系统的目标串最优分配线性规划模型,给出相应的目标串最优分配方法,并讨论了处理机最优分配顺序.实验结果表明,本文提出的基于最优分配方法的多目标串近似匹配并行算法优于平均分配算法,获得了较好的加速并具有良好的可扩展性.     

异构机群系统上并行计算双序列的最长公共子序列*

针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法。实验结果表明,基于最优序列串分配方法的双序列最长公共子序列并行算法优于平均分配序列串算法,获得了较好的加速,并具有良好的可扩展性。     

网络计算环境下并行算法及其可扩放性分析

并行算法的可扩放性是提其有效利用计算节点的能力，它可以预测算法在处理机数目变化时的性能，在网络环境下用ＰＶＭ实现了并行矩阵乘法及ＰＳＲＳ算法，分析了在网络计算环境下这两个算法的可扩放性，并利用试验数据进行了验证。     

异构计算中一种图的非均衡划分算法

现有的图的划分算法大多是均衡划分,要求划分块的权值相等,划分块之间的连接代价尽量最小。但是在异构计算环境中,不同的处理机的计算能力不尽相同,从而在并行任务调度时所分配的计算任务量也应随之不同。所以为了适应更广泛意义上的异构负栽均衡,本文提出了异构计算中的一种任务图的非均衡划分算法。该算法根据任意给定的需求,使得划分好的各个子集权值不均等。其中划分子集的个数等于异构环境中处理机的个数,各子集的大小比例于不同处理机的计算能力。算法包括3步：粗化阶段、非均衡划分阶段以及精化还原阶段。本文通过用格林威治大学提供的系列开放图来测试该算法,实验结果表明算法是准确有效的。     

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 performance optimization problem for various stages in parallel program development and to accurately predict the performance of a parallel program by considering factors 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.     

H-BSP: A Hierarchical BSP Computation Model

This paper presents a new parallel computing model, called H-BSP, which adds a hierarchical concept to the BSP(Bulk Synchronous Parallel) computing model. An H-BSP program consists of a number of BSP groups which are dynamically created at run time and executed in a hierarchical fashion. H-BSP allows algorithm designers to develop more efficient algorithms by utilizing processor locality in the program. Based on the distributed memory model, H-BSP provides a group-based programming paradigm and supports Divide & Conquer algorithms efficiently. This paper describes the structure of the H-BSP model, complexity analysis and some examples of H-BSP algorithm. Also presented is the performance characteristics of H-BSP algorithms based on the simulation analysis. Simulation results show that H-BSP takes advantages of processor locality and performs well in low bandwidth networks or in a constant-valence architecture such as 2-dimensional mesh. It is also proved that H-BSP can predict algorithm performance better than BSP, due to its locality-preserving nature.     

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

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

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

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

计算网格中动态负载平衡的分布调度模式

网格计算下对资源进行有效的管理和调度可以提高系统的利用率.在对现有若干调度方法的研究和分析基础上,针对计算网格中的负载平衡问题,提出了一种分布式网格作业调度模型,并给出相关算法.算法通过建立主从模式的负载信息收集机制,提供给节点全局负载信息,加速重负载节点的负载转移速度.通过有效的负载平衡模式,解决资源调度中负载平衡及其可靠性问题.     

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

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

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

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

The <Emphasis Type="Italic">systems edge</Emphasis> of the Parameterized Linear Array with a Reconfigurable Pipelined Bus System (LARPBS(p)) optical bus parallel computing model

This paper is about exploring the various systems related aspects pertinent in the recent Parameterized Linear Array with a Reconfigurable Pipelined Bus System (LARPBS(p)) model. The two principal features of the LARPBS(p) model is, firstly, its bridging model definition similar to that of the BSP model leading to a more detailed algorithm cost analysis than other models, and secondly, the incorporation of several new communication primitives not defined in earlier models. This paper reviews the systems related aspects of earlier optical bus models and summarizes the LARPBS(p) model. The main part of this paper considers some practical systems related aspects of the LARPBS(p) model, specifically: fiber and free space based implementations, feasibility study, communication traffic analysis, bus collision avoidance, and the cost analysis of a MIMD algorithm. An overview perspective of the work is presented, thereby: the edge of systems related research is identified.

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

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