基于平衡划分的并行集合交算法

对集合交运算,基于划分点定位算法提出并分析了一种新的并行算法INTERSECT-DL.在INTERSECT-DL算法中,数据被平衡地划分,分配给所有处理机,所以各处理机的工作负载相同.给出了在网络并行计算环境下的实验结果,并与INTERSECT-S、INTERSECT-NS算法进行了对比.理论分析和实验的结果都表明INTERSECT-DL算法具有很高的并行效率和扩展性.     

高性能网络并行计算模型LogP的剖析

并行计算模型是设计和分析并行算法的基础和关键,在实现高性能网络计算中起重要作用。ＬｏｇＰ是一个面向高性能并行计算的现实模型,它可以用来作为的,可移植的并行算法的基础,这个模型基于四个参数,即。Ｌ,ｏ,ｇ,Ｐ．这些参数反映了高性能网络并行计算的计算带宽,通信带宽,通信延迟,以及传输和计算的结合效率．     

一个网络并行计算新平台

编写网络并行计算程序对一般人来说是艰难的,用户任务的分解、分配以及在子任务间的交互等问题都需要具有高超的技巧。从改善用户并行程序设计环境出发,给出了在网络并行计算的一种新平台。说明了该系统平台的结构实现,组成该平台的任务描述器、任务的调度和任务控制器。而在网络并行计算的一种新架构中,用户只需提交数据和对它们的操作,而复杂问题让系统处理,这无疑是网络并行计算方法发展的有益尝试。     

一种实用的并行计算模型

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

工作站网络环境下的并行计算

当前工作站网络环境（ＮＯＷｓ）下高性能科学与工程计算是并行计算的一个热门话题，本文借助于ＬｏｇＰ并行计算模型，提出了一套新的效率评价准则，用于优化并行算法效率以达到最佳实现效果，揭示了影响算法并行效率发挥的关键因素，并从算法和程序设计角度提出了相应措施，探讨了急需解决的几个关键性问题，三个典型应用问题的数值实验结果文中给出。     

一种基于PVM的矩阵相乘并行算法

研究了一种运行于PVM并行计算平台的矩阵相乘的并行算法。在工作站数量不为某个数的平方数时，Cannon算法在PVM环境下不能充分地利用机群系统中的资源。根据PVM并行编程环境中任务间通信的特点，文中设计了一种基于PVM的矩阵相乘并行算法，该算法根据工作站数量来确定子任务的数量，并对矩阵A进行分块，每个子任务可以计算一个分块。实验表明，该算法提高了机群并行环境中资源的利用率，提高了程序的运行效率。     

随机模式匹配并行算法在工作站机群上的实现

对随机模式匹配算法进行了改进,并根据MPICH并行编程环境中任务间通信的特点,设计了一种基于MPICH的改进的随机模式匹配并行算法。根据运行在COW（工作站机群）上的进程数目将文本串进行重叠划分,每个进程完成一个文本子串的模式匹配。实验结果表明,该改进的随机模式匹配并行算法有效地加快了模式匹配的速度,提高了工作站机群的资源利用率。     

在工作站机群系统上并行求解抛物型偏微分方程

作者首次在分布存储的网络互连工作站机群系统上实现了抛物型偏微分方程的有限差分逼近并行算法交替分段显－隐式（ＡＳＥ－Ｉ：Ａｌｔｅｒ－ｎａｔｉｎｇＳｅｇｍｅｎｔＥｘｐｌｉｃｉｔ－Ｉｍｐｌｉｃｉｔ）方法的并行计算。本文介绍了工作站机群系统和ＡＳＥ－Ｉ算法，设计了不同数据划分方式，阐述了如何组织并行计算。从理论和实验上详细分析了在各种问题规模、并行程度、数据划分方式、机器和网络型号下的计算速度和效率。实验证明，偏微分方程的有限差分新解法分段显隐法，具有良好的并行性。其２维问题的求解有很好的效果，适于在分布存储的并行可扩展机群系统上实现。     

一种基于平衡划分的集合差并行算法

基于精确划分的思想提出了一种新的集合差并行算法DIFF—DL。利用DL子算法查找最终全局序列中等分位置上的划分点,将数据平均划分并分配给所有处理机,使每个处理机具有相同的工作负载。给出了网络并行计算环境下的实验结果,并与DIFF-S、DIFF-NS算法进行了对比。理论分析和实验的结果都表明,DIFF-DL算法具有很高的并行效率和扩展性,原因是划分类算法的性能和划分后区间数据量的平均程度正相关。     

求解大规模矩阵特征问题的并行算法研究

基于数据并行的重启动Arnoldi并行算法,基于使用数据并行模型的重启动Arnoldi并行算法,提出一个精化重启动Arnoldi并行算法。为了降低弱扩展性对并行性能的负面影响,该算法使用任务图模型并行计算精化向量,减少处理器进程之间的通信次数,有效地实现并行计算。在KD-50-I万亿次机上的测试结果表明,该算法具有较好的可扩展性和并行 效率。     

一种实用的所有点对之间最短路径并行算法

针对有向图中每对顶点之间的最短路径问题,在基于扩充了路径矩阵的串行Floyd算法上,提出了二维网格结构上的并行算法。选用的任务划分方法为二维均匀块分配方法。该并行算法已经在NOW上的MPI平台上实现,理论分析和数值实验表明它具有较高的扩展性和并行效率。     

一种针对结构化并行控制机制的任务调度算法

缩短程序的执行时间是并行处理的首要目标,有效的任务分配算法是实现这一目标的关键,对机群系统来说更是如此.研究机群系统上针对结构化并行控制机制的任务调度问题,并基于贪心算法、粒度控制、反馈式分派的原则,提出近优的任务调度算法SSA(sub-optimal scheduling algorithm).实验结果表明,在机群环境下,该算法的并行计算性能与其他算法相比均有所提高.     

基于LAN的并行计算环境

文章给出厂一个这种模型的并行计算机系统，设计了一个简单的工作算法．并对该算法的性能进行了分析，最终发现影响并行计算的性能的主要因素——传输速度。为了提高其性能，必须对传输介质、传输设备和通信协议等进行改造。     

一个调度Fork-Join任务图的新算法

任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,     

动态环拓扑多机系统上DBP学习算法并行计算模型的构造与实现

人工神经网络模型的软件模拟，其并行算法的设计、实现及性能评价对于神经网络计算机和各种专用神经网络ＶＬＳＩ芯片的研制具有十分重要的意义．本文首先构造了一个分布式存储器、信息传递方式的多机系统作为软件模拟人工神经网络的平台，并用一个环拓扑结构的多Ｔｒａｎｓｐｕｔｅｒ网络予以实现．接着提出并实现了一个适用于动态环拓扑形式的ＤＢＰ并行计算模型，它主要包括神经元的划分和映射策略；ＤＢＰ中活性值、误差反向传播及权值修改的多机并行算法．然后讨论该ＤＢＰ算法的时间复杂度和加速比．     

A non-blocking locking method and performance evaluation on network of workstations

A network of workstation(NOW) can act as a single and scalable powerful computer by building a paralle and distributed computing platform on top of it.WAKASHI is such a platform system that supports persitent object management and makes full use of resources of NOW for high perforance transaction processing,One of the main difficulties to overcome is the bottleneck caused by concurrency control mechanism.Therefore,a non-bloking locking method is designed,by adopting several novel techniques to make it outperform the other typical locking methods such as 2PL:1) an SDG (Semantic Dependency Graph)based non-blocking locking protocol for fast transaction scheduling;2) a nmassively virtual memory based backup-page undo algorithm for fast restart;and 3) a multi-processor and multi-thread based transaction manager for fast execution.The new mechanisms have been implemented in WAKASHI and the performance comparison experiments have been implemented in WAKASHI and the performance comparison experiments with 2PL and DWDL have been done.The results show that the new method can outperform 2PL and DWDL under certain conditons.This is meaningful for choosing effective concurrency control mechanisms for improving transaction-rpocessing performance in NOW environments.     

基于Web并行计算环境的自适应任务分派算法AHRRN

基于Ｗｅｂ或ＮＯＷ分步式环境上的并行计算的研究正成为热点,一个大的计算任务可划分成多个子任务分派给网络上的工作站,由它们合作计算来完成。该文介绍了一种自适应的计算任务分派算法ＡＨＲＲＮ,它包括任务选择算法和任务分派算法,它对任务的选择和分派能反应可用工作站的负载的动态变化情况。文章最后给出了 ＡＨＲＲＮ与 ＳＴＦＳ、ＦＩＦＳ、ＨＲＦＳ的仿真比较结果,证明其能提供较高的服务质量并具有较快的响应。     

一种面向多核系统的并行计算任务分配方法

随着多核处理器的普及,目前的大规模并行处理系统普遍采用多核处理器,这对于资源管理和调度提出了更高的要求.提出了基于共享Cache资源划分的方法,建立了面向多核处理器支持Cache资源分配的进程调度模型,设计并实现了并行任务到多核处理器的映射算法,更好地解决了大规模资源管理系统中面向多核处理器的任务分配问题,降低了使用共享Cache的多个进程运行时的相互干扰,提升了应用程序性能.     

并行编译中数据分布的线性划分模式计算

由于计算机访问本地存储器的速度远远快于通过网络访问异地计算机存储器的速度，因此，在分布式存储环境中，如何对程序中引用的数据进行合理的分布，从而达到在本地进行计算时只需访问存储在本地的数据（即无通信的数据分布）的目的，已成为提高并行计算速度的关键问题，本文主要讨论如何在数组下标表达式为线性的条件下，对一种种锘于线性代数中超平面概念的数组线性划分技术进行扩充，并给出了完整的数据划式计算算法。