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

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

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

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

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

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

BSP模型及其并行程序设计

当前并行计算领域的研究重点和热眯是研究“通用”并行计算的适用范围，而其中心议题是既具有可扩展并行性又同时具有体系结构独立必的可移植软件开发方法和工具的研究。解决体系结构独立的途径是通过引入的一个过渡模型使得软件和硬件得以较好的分离。ＢＳＰ（Ｂｕｌｋ Ｓｙｎｃｈｕｏｎｏｕｓ Ｐａｒａｌｌｅｌ）模型正是这样一个理论模型，它不但可提供既具有可扩展的并行性又独立于体系结构的并行软件开发方法，而且可为并行和     

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

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

并行计算模型研究

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

基于BSP的并行事务处理模型

BSP模型独立于并行体系结构,既可作为并行计算模型,又可作为并行程序设计模型。提出了基于BSP模型的H－V事务模型,适用于长、短事务和长短事务混杂的情况。给出了在无共享结构下实现并行事务处理的进程结构。该结构不仅实现了事务内及事务间并行性,而且使人有可用性（availability）和可扩充性（scalability）,而后给出了适用于该模型的基于时间戳的多版本并发控制协议,最后描述了事务在超步结构下的运行过程。性能测试表明,使用该模型进行事务处理时可获得良好的事务响应时间和加速比。     

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

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

基于BSP模型的大规模线性规划并行算法研究

在许多实际工程问题中经常遇到一些大型线形规划问题,通常的计算过程需要占用大量的计算时间,效率低下.文中提出了一种基于BSP模型的大规模线性规划并行算法--修正单纯形并行算法,分析了其代价函数和加速比,在所研制的集群计算机上进行了实现和测试.结果表明:当问题规模比较大时,此并行算法能获得较好的加速比.     

集群系统中BSP模型上的并行FFT设计

在并行计算模型中,BSP模型由于具有编程简单、独立于体系结构和执行性能可预测等特点而在总体上优于其它模型。NOWs正成为并行计算领域的一个新的发展热点,以太网构成的微机集群系统是NOWs的一种重要实现形式。文中研究了集群系统中BSP模型上的并行算法设计,以FFT算法为例,进行了设计和分析,并给出了测试结果。     

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.     

NestStep: Nested Parallelism and Virtual Shared Memory for the BSP Model

NestStep is a parallel programming language for the BSP (bulk–synchronous–parallel) model of parallel computation.Extending the classical BSP model, NestStep supports dynamically nested parallelism by nesting of supersteps and a hierarchical processor group concept. Furthermore, NestStep adds a virtual shared memory realization in software, where memory consistency is relaxed to superstep boundaries. Distribution of shared arrays is also supported.A prototype for a subset of NestStep has been implemented based on Java as sequential basis language. The prototype implementation is targeted to a set of Java Virtual Machines coupled by Java socket communication to a virtual parallel computer.     

BSP versus LogP

A quantitative comparison of the BSP and LogP models of parallel computation is developed. We concentrate on a variant of LogP that disallows the so-called stalling behavior, although issues surrounding the stalling phenomenon are also explored. Very efficient cross simulations between the two models are derived, showing their substantial equivalence for algorithmic design guided by asymptotic analysis. It is also shown that the two models can be implemented with similar performance on most point-to-point networks. In conclusion, within the limits of our analysis that is mainly of an asymptotic nature, BSP and (stall-free) LogP can be viewed as closely related variants within the bandwidth-latency framework for modeling parallel computation. BSP seems somewhat preferable due to its greater simplicity and portability, and slightly greater power. LogP lends itself more naturally to multiuser mode. Received June 1, 1997; revised November 18, 1998.     

面向高性能数值计算的并行计算模型DRAM(h)

提出了一个基于存储层次的新并行计算模型DRAM(h)，并在该模型下对两个经典并行数值计算算法的不同实现形式：四种形式并行下三角方程求解(PTRS)和六种形式无列选主元并行LU分解(PLU)，进行了分析．模型分析表明，具有近乎相同时间和空间复杂性的同一算法不同实现形式，在该模型下会有完全不同的存储复杂度．作者在日立公司SR2201MPP并行机、曙光3000超级服务器和中国科学院科学与工程计算国家重点实验室(LSEC)的128节点Linux Cluster等三种并行计算平台上对模型分析结果进行了实验验证．结果表明，该模型分析在绝大多数情况下都能较好地与不同实验平台上的实验结果吻合．个别出现偏差的分析结果，在根据计算平台的存储层次特点修改模型分析的假定后，也能够进行解释．这说明了该模型对不同形式的算法实现进行存储访问模式区分的有效性．对在计算模型中加入指令／线程级并行的可行性和方法的研究是下一步的工作．     

PC集群的结构和性能分析

讨论了PC集群中的信道绑定和节点优化等方法及其对集群系统结构和性能的影响,设计和实现了几种基于BSPLib的PC集群性能测试算法,通过对研制的3个PC集群的性能评估,验证了提出的方法和算法的有效性,这些对设计低成本的PC集群能提供有益的帮助。     

分布式并行处理中的异步通信技术及其分析

在基于网络环境的分布式并行计算中,因为一般情况下,局域网的底层通信协议多为以太网协议,而以太网采用的是总线通信和信道竞争两种技术,因此基于网络环境的分布式并行计算中最大的问题可能就是要解决好通信开销的问题。根据以太网的特性,提出了一种子任务计算和通信错开的解决方案,并已成功用于求解一个经典的流体力学问题,取得了良好的效果。该文着从理论上分析该方案的加速比和并行效率等。     

A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing

In this paper,we propose a decentralized parallel computation model for global optimization using interval analysis.The model is adaptive to any number of processors and the workload is automatically and evenly distributed among all processors by alternative message passing.The problems received by each processor are processed based on their local dominance properties,which avoids unnecessary interval evaluations.Further,the problem is treated as a whole at the beginning of computation so that no initial decomposition scheme is required.Numerical experiments indicate that the model works well and is stable with different number of parallel processors,distributes the load evenly among the processors,and provides an impressive speedup,especially when the problem is time-consuming to solve.