多处理机上异步并行算法设计(Ⅰ)

本文介绍多处理机上并行算法一些基本问题,同步和异步并行算法基本概念,异步并行算法的正确性和效率分析,并用若干个例子加以分析。     

多处理机同步和异步并行算法

多处理机的并行算法可归结为同步和异步二类并行算法。我们根据这两种算法的设计和分析,对它们的重要特性给出区分并加以讨论。文中还要研究这两种并行算法的若干例子。     

正定矩阵在MIMD计算机上的并行因子分解

本文研究利用多处理机的MIMD型计算机计算方型实对称正定矩阵的三角因子问题。文章从算法的加速比和效率的角度,导出并分析了当所用的处理机台数为(ⅰ)无限和(ⅱ)O(n)时,基于Cholesky分解法和Gaussian消元法的并行算法,其中n是矩阵的阶。对于第(ⅱ)种情况,它表明并行消元法能够达到与并行Cholesky方法相同的加速比,而仅需Cholesky方法所用处理机台数的一半。     

组显式格式及其并行计算(Ⅰ)

组显式方法是求解抛物型偏微分方程的一种新的有限差分方法,本文简单地介绍了一维抛物型偏微分方程的组显式格式,给出了各格式的并行(向量)计算方法,并对各并行算法的并行效率进行了分析,附录中给出了一些计算结果。     

解稠密对称特征值和奇异值分解用的多处理机Jacobi算法

本文介绍两种基于 Jacobi 算法的并行算法,用于多处理机上解稠密实对称矩阵的全部特征值以及对直角矩阵进行奇异值分解。我们的目的是研究和介绍在 Alliant FX/8多处理机环境下 Jacobi 算法和类 Jacobi 算法与当前最新 EISPACK、LINPACK 例行程序相比的突出优点。我们对稠密特征值问题列出了矩阵阶数小情况下的较为理想的结果;并说明对直角矩阵(矩阵的行数大于列数)采用单边类 Jacobi 算法进行奇异值分解也可提供较为理想的性能。     

基于多处理机平台—TM S320C80的并行算法实现方法的研究

本文结合 ＴＭＳ３２０Ｃ８０（简称 Ｃ８０）的编程结构,提出了基于该多处理机平台的并行算法的开发所面临的关键技术是：底层通信协议、细粒度并行、内存访问冲突、ＴＣ的多维数据传输和“双缓冲”数据传输方式．概括出基于此平台并行算法的开发层次     

应用Richardson外插的梯形公式的并行计算

本文为求解刚性常微分方程初值问题构造了一个并行算法,它的基础公式为梯形公式。通过Richardson外插和Lindberg内插的技巧,得到了节点上精度较高的近似值,其计算量比隐式Runge-kutta方法要小(按右函数每步求值的次数算),并且若干点的右函数值可并行计算,在向量机和多处理机上实现是高效的。文中对算法的稳定性也进行了讨论。     

1980年的计算机是微型计算机网络吗?

本文讨论利用微型计算机网络来解决大型计算机所处理的问题,在这里,历史地考察了计算机结构的发展趋势,同时概述了为增强计算能力所使用的方法。并分析了当前在使用并行算法方面(以阵列、流水线和多处理机等形式出现)所作的努力。文中提出了微型计算机网的建议,略述了它的局限性,并从应用的角度讨论了这些局限性。还给出了所提出的系统的进一步的细节及部件总数,估算未来可能的系统价格。然后与现有计算机的价格进行了比较。     

优先队列的并行插入和删除

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。     

全球(z)双三次数值模式并行算法设计与实现

针对双三次数值天气预报模式进行了并行算法研究。采用一维区域分解算法,借鉴块棋盘划分矩阵转置算法,设计和实现了数据转置通信算法,并采取计算与通信重叠技术减小通信时间对并行效率的影响,最终实现了双三次数值天气预报模式的并行算法,并在机群系统上进行了并行性能测试评估。结果表明,实现的双三次数值预报模式并行算法的并行效率较高,设计实现的数据转置通信算法、计算与通信重叠技术取得了较好的效果。     

离散Fourier变换并行算法综述

本文详细介绍了1－D DFT精确计算的六步框架并行算法和按位并行计算法,以及按位计算法在2－D Mesh和Torus上的模拟实现,同时介绍了近似计算中的基于奇异值分解的算法和基于快速多极方法的算法。对于2－D DFT,本文介绍了并行行列算法和并行多项式变换算法,并分析了其优缺点。     

二维离散哈特莱变换的乘法复杂性

本文研究了长度为2~n×2~n(n为正整数)二维离散哈特莱(Hartley)变换的乘法复杂性。虽然DHT(2~n;2)的变换核cas[2π(kp+lq)/2~n]不象DFT(2~n,2)的变换核exp[—2πj(kp+lq)/2~n]那样可以分离成一维DHT变换核的乘积,但是DHT(2~n;2)可以利用线性同余组和环结构转换成1个DHT(2~(n-1);2)和(3/2)2~n个一维奇DHT.一维奇DHT可以简化为一维DHT的核CHT的直和,在有理数域Q上计算长度为2~n的二维离散DHT(2~n;2)所需的最少实乘次数为2~(2n+1)—6(n—1)2~n—8。所以二维DHT(2~n;2)和相应的实DFT(2~n;2)具有相同的乘法复杂性。     

利用多抽样率滤波实现DHT的实值离散Gabor变换

基于多抽样率滤波原理,设计了分析和综合滤波器组,分别用于实现（基于DHT核函数的）离散Gabor展开与变换,提出了新的实值离散Gabor展开与变换快速并行算法。在并行算法中,由于总计算复杂性分摊于多个结构一致并能够利用快速一维离散快速Hartley变换（N点1-D DHT）的并行通道,因此并行算法的计算时间取决于单个并行通道的计算复杂性。而每一并行通道的计算复杂性非常小,所以分析和综合滤波器组的处理速度是相当快的。将所提出的算法与当前最快的并行算法进行了比较,结果表明基于多抽样率滤波实现的实值离散Gabor展开与变换快速并行算法对实时信号处理十分有利。     

回溯控制策略的并行实现

本文提出了一种用于并行实现VLSI专家系统中的回溯控制策略的一维二级控制流多处理机结构。     

计算几何与并行算法

本文首先介绍了计算几何的基本概念,论述了计算几何的四个基本问题,即几何搜索问题、相交问题、邻接问题及凸壳问题。然后重点分析了凸壳构造问题,介绍了其最佳串行算法、及相应的并行算法。接着对一些计算几何的串行及并行算法进行了分析比较。最后提出了笔者对新一代并行计算机系统上设计计算几何并行算法的看法。     

一种快速的基于并行的碰撞检测算法

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树形成对一任务树的遍历,采用并行算法中的流水线技术,利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。     

长为PL的快速递归付里叶变换算法

一、引言离散付里叶变换(DFT)的实际应用愈来愈广泛,但直接计算DFT需要正比于N~2的运算次数。显然当N很大时,直接计算DFT要花费大量的计算时间.一九六五年,Cooley和Tukey提出的快速付里叶变换(FFT)使计算DFT的运算次数正比于N logN,从而使运     

FIRST和FOLLOW集合的并行算法设计

描述了多处理机环境中FIRST和FOLLOW集合求解的一种并行处理方法，并讨论了FIRST和FOLLOW集合的并行算法设计思想和它的实现策略，在构造文法G的LL(1)分析表以及判定文法G是否LL(1)文法时，求解FIRST和FOLLOW集合是很重要的内容，由于文法中终结符和非终结符个数很多，考虑FIRST和FOLLOW集合的并行处理方法，对并行编译处理和提高效率有其理论和现实意义。     

基于小波变换的并行图像分割算法分析与优化

研究了基于小波变换图像处理的可行性,在分析了二维小波变换的数学模型后,改进了基于多处理机的均匀分块并行算法,有效减少了算法中的通信量。该算法具有通信量小、负载均衡等特点,适合实现多级小波变换,符合实际应用中对分辨率的要求。     

多核计算机上的快速傅里叶变换并行算法

针对现有多核结构上快速傅里叶变换(FFT)并行算法没有利用多级缓存和线程级并行等多核特性问题,通过运用多核多级存储特性合理划分数据,采取子序列FFT计算和多线程并行逐对计算FFT相结合的方法,给出一个N点、一维、有序和基数为2的多核多线程并行计算FFT非递归算法。理论分析和实验结果表明,该算法实用、高效,能获得较好的加速比和可扩展性。