动态规划问题的高效并行算法

在具有p(1≤p≤n)个处理机的CREW PRAM并型计算模型上,对一类动态规划问题给出了一处理机利用率为E(n)=0(1),并行加速比为S(n)=0(p)的并行算法(n表示问题的尺寸);计算了问题求解的最少费用,并同时给出了问题求解的方法。     

有限型多阶段决策问题的并行算法

讨论了在ＭＩＭＤ并行系统上，基于嘉量原理的摹矩阵连摹乘积求多阶段有向图最优路的并行算法，给出了选择顺推方式或逆推方式计算连摹乘的一个计算过程，提出了一个分派到各台处理机的任务基本均衡的ｐ－分划算法，并详细讨论了并行计算的实现，给出数值试验实例。     

高超声速热化学非平衡绕流分布式并行计算

讨论了非结构网格高超声速热化学非平衡绕流流场的分布式并行数值模拟方法．流动控制方程为多组分Navier-Stokes方程,化学反应模型为考虑了弱电离效应的七组元空气反应模型及双温模型．控制方程的空间离散采用Jameson有限体积法,时间推进为显式5步Runge—Kutta法．采用基于区域分裂的分布式并行计算方法,对整体计算区域进行了以各子区单元数为负载均衡条件的划分．使用PVM并行机制在PCs—Cluster机群上对二维钝头体高超声速热化学非平衡绕流进行了分布式并行计算,得到了与串行计算及文献相符合的计算结果．     

NS方程全离散非线性Galerkin格式异步并行算法的计算稳定性分析

给出了Ｎａｖｉｅｒ－Ｓｔｏｋｅｓ方程全离散非线性Ｇａｌｅｒｋｉｎ格式,提出了一种新的异步并行算法,并对其计算稳定性进行分析,文中证明了此格式的计算稳定性。     

用微机构建高性能集群计算系统

给出了利用操作系统Linux和并行虚拟机PVM在微机局域网上构建高性能集群计算机系统的具体方法,如网络平台的搭建、Linux和PVM的安装与配置和并行算法的开发等.     

基于LARPBS模型的快速并行归并排序算法

提出了一种基于LARPBS模型上的并行归并排序算法,该算法使用M1 ε(0<ε<1)个处理器可以在O(lb lbM)时间内对Mε个有序序列进行归并.利用该归并算法对长度为N的序列进行排序,使用N1 ε个处理器可以在O((lb lb N)2)时间内完成.     

基于PVM求奇异两点边值问题的局部加密并行算法

主要讨论了一维奇异两点边值问题的局部加密并行算法,并基于PVM并行编程环境,在1~4台桌面PC机连接而成的局域网上编程对该算法进行了数值试验,试验表明该算法对于处理一维奇异问题是有效的。     

在SIMD－EREW计算模型上的并行排序算法

本文提出一种在ＳＩＭＤ－ＥＲＥＷ计算模型上实现的并行排序算法．算法采用基数交换排序方法，在处理过程中无存贮访问冲突．对长度为ｎ的序列，算法使用不超过个处理单元，时间复杂度为Ｏ（ｕ．ｌｏｇ２ｎ），其中ｕ为不超过处理器字长的常数．该算法适合于具有较多重复元素的序列排序．     

改进的并行高斯全主元消去法

为减少Gauss全主元消法的运行时间，用多进程与多线程混合的方式对其进行了并行化，同时对该算法进行了改进．采用MPI并行I／O技术提高读取数据文件的速度，降低对内存的需求；采用标志数组避免了选主元后换行带来的通信开销；使用线程模型确定最优线程数，提高运行消去的速度；通过预先发布机制降低回代求解步骤的时间复杂度．实际运行结果表明，随着方程组阶数增大，加速比也逐渐增大，对于5000元的方程组，8进程同时运行，加速比可达6．68，并行效率稳定在0．85左右．这表明该算法具有可扩展性和稳定的并行效率，适用于大规模并行计算．     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.