几乎最快与渐近最优的并行分枝界限算法

分枝界限算法是求解组合优化问题的技术之一,它被广泛地应用在埃运筹学与组合数学中.对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω(m/p+hlogp),其中p为可用处理器数,h为扩展的结点数,m为状态空间中的活结点数.通过将共享存器设计成p个立体堆,提出了PRAM-EREW上一个新的一般并行分枝界限算法,理论上证明了对于h<p^2p,该算法为最快且渐近最优的并行分枝界限算法.最后对0-r背包问题给出了模拟实验结果.     

基于工作站集群环境的可扩放性度量标准

1.引言可扩放性是指并行算法有效利用可扩充的处理机数目的能力,目前已经提出了许多可扩放性度量方法,其中最典型的是:等效率方法、等平均速度方法和平均延迟方法。等效率的方法严格地说只是一种分析的方法,在实际应用中不够准确,而且该方法给出的是工作量与处理器数的关系函数,反映了工作量随处理器数变化的趋势,并没有一个量化的数据。等平均速度的方法将平均速度作为衡量可扩放性的主要指标,是一种将算法与机器相结合的基于测量的方法,但是在实际情况中很难精确地测量出程序运行的速度。平均延迟的方法使用平均计算延迟作为衡量可扩放性的主要指标,精确地考虑了算法与体系结构两者的特性,也是一种基于测量的方法,但该方法需要使用专用的硬件或者专门的系统级软件来测量并行程序运行时每个处理器上的延迟时间,因此难以广泛地应用于各种并行机上。     

一种基于MPP的并行归并算法

文中提出并分析了并行归并算法ＰＭＦＳ;基于曙光－１０００大规模并行计算机系统,给出了ＰＭＦＳ算法应用实例的实验结果,并将ＰＭＦＳ算法推广得到的并行归并排序算法与ＰＳＲＳ算法进行了比较。     

分布式动态负载平衡调度的一个通用模型

在大规模并行分布处理系统，特别是网络工作站机群（ＮＯＷ）系统中，各结点机之间的负载平衡调度是最为常见的关键性问题之一．本文在简单分析了动态负载平衡调度中接收者驱动和发送者驱动这两个常用策略基础上，提出了一个通用的基于混合驱动策略的动态负载平衡调度模型，并给出了曙光１０００并行机上的部分实验结果.     

一种实用的并行计算模型

对于当前流行的工作站集群环境和各类并行机系统,文中提出了一种实用的并行计算模型,即基于LogGP的非独占异质同步模型NHBL（Nondedicated Heterogeneous Barrier LogGP）,它旨在反映具有异质性和非独占性的NOW计算环境对并行算法设计和分析的影响,然后用NHBL模型分析了PSRS算法在国家高性能计算中心（合肥）的工作站集群NHPCC-Cluster和曙光－1000MPP由的代价,并用实测结果进行了验证。     

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

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