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

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

基于动态规划的序列比对的并行算法研究

针对序列比对算法进行了深入地研究,分析比较了两序列和多序列、局部和全局、渐进和迭代的序列比对算法.利用动态规划序列比对算法内在的并行性,提出了自适应的动态规划序列比对的并行策略.该策略在计算初期和计算末期采用较小的高度和宽度值使得大部分处理器参与计算,在计算中期采用较大的高度和宽度值降低处理器间的通信开销;运用上述自适应的动态规划序列比对的并行策略,提出了一种基于动态规划的序列比对的并行算法,将读入的比对序列负载均衡地分布至不同的计算结点.基于集群系统和MPI环境的实验数据及分析表明,该算法在给定进程数量的条件下,其执行时间随序列长度的增长而急剧上升;在给定序列长度的条件下,其执行时间随并行进程数量的增大而大幅减小;充分反映出该算法较好地发挥了序列比对问题的内在并行性,有效地降低了序列比对算法的时间复杂度.     

PMkSK:一种空间关键字移动近邻查询并行处理方法

为了提高空间关键字移动k近邻查询处理效率,提出关键字影响集的概念,并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法.该方法包含一种并行查询算法和一种并行验证算法.首先,采用并行查询算法计算近邻结果;然后,确定查询区域,并在区域内查找包含的关键字影响集;最后,在查询者移动时不断通过并行验证算法验证影响集,以实现空间关键字移动近邻查询处理.实验结果表明:这2种算法的时间复杂度分别为O((log D+k)/k)和O(logk),均为现有对应算法的O(1/k),其中D为空间对象数目.在多核系统上,这2种算法的运行时间均比现有算法低一个数量级.基于影响集的并行查询处理方法避免了基于安全区域的移动k近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点,可以高效地处理关键字移动k近邻查询.     

拉格朗日插值多项式的一种并行算法

提出在机群系统并行环境下的构造拉格朗日插值多项式的一种并行算法.该算法以n个节点(x0,y0),(x1,y1),…,(xn-1,yn-1)的拉格朗日插值多项式公式为基础.当处理机数量为n2时,它的时间复杂度为3log(n) O(1);当处理机数量为p2(p相似文献   

多处理器上（m,n）选择问题的一个并行算法

给出求解从任意给定的n个数据中选取m个最小(最大)者即(m,n)选择问题的一个并行算法(m相似文献   

两序列比对的Hirschberg算法

回追序列比对算法需要在内存中保存完整的得分矩阵，其空间复杂度是O(mm)，而在生物信息科学中，空间复杂度是超长DNA序列比对的瓶颈，本文介绍的Hirschberg算法较好的解决两序列比对的空间复杂度问题。其空间复杂度是O(min(m，n))。     

两种带约束的序列比对算法

通过理论证明,得出了当距离函数中惩罚因子φ=0时的解应满足的条件,并在此基础上改进两种最长公共子序列的优化算法,使之能够求解出带约束的序列比对问题.这两种改进算法的时间复杂度分别为O(nmr)和O(nm(r+1)),空间复杂度分别为O(nmr)和O((n+m)(r+1)).推导出算法应满足在两序列中插入的空位符数目分别为(m-l)和(n-l),使比对结果中不会出现错配,保证了比对的质量.实现了基于回溯的改进算法,验证了其求解带约束的序列比对问题的有效性.     

基于流水光总线阵列的快速矩阵运算

基于流水光总线的可重构线性阵列系统（LARPBS）是一种建立在光总线上的并行高效计算模型，介绍LARPBS模型上的一些快速而又高效的矩阵运算并行算法，包括矩阵转置、矩阵连加、矩阵与向量和乘积、矩阵乘法、矩阵幂以及矩阵连乘等，除矩阵幂运算和矩阵的连乘运算在O（logN）时间完成之外，其余矩阵运算均可在O（1）时间完成，这与以往的其他同类并行算法相比，效率都提高了O（log N），而且速度达到了最优。     

一个最优并行选择算法

最优并行算法系指其所用时间与处理器数目之乘积等于相应串行算法之时间下界的那一类并行算法。对于求解从n个数中选取前m个或第m个最小(或最大)数的选择问题(m相似文献   

SIMD-SM模型上的奇偶排序算法

Batcher排序网络在排序深度上不是最优的,但由于有较好的并行性和时间复杂度,因此许多并行排序算法都基于Batcher排序网络.通过观察Batcher奇偶排序网络,提出在SIMD SM模型上的一种奇偶排序算法.该算法占用n/2个处理器,在○(log22n)时间里排序n个关键字.     

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（（ｎ＋ｍ）／ｌｏｇｎ）处理器的最佳、高速并行算法     

A time-space optimal parallel sorting on a hypercube

In this paper we discuss a parallel sorting algorithm on a hypercube. Its time complexity isO(n logn/p) +O(n). Here,P is the number of processors avaliable and n, the amount of items to be sorted. Take the problem of time-space optimization into consideration, whenP≤O(logn), this algorithm is both time-space optimal and cost optimization. But this means only speedup isO(p) and it is not linear speedup. Therefore, we further discuss relevant parallel efficiency problems.     

计算加权Moore-Penrose逆A+M,N的一个改进的并行算法

利用PREPARTAFP和SARWATEDV[6] 的一些结果 ,给出一个计算加权Moore Penrose逆A MN 的改进的并行算法 ,改善了文献 [8]中提出的算法。在与PREPARTAFP和SARWATEDV文 [6 ]中相同的假设下证明了改进的并行算法的时间复杂性和处理机台数分别为 T =0 ((logn) 2 ) ,　 P =max m/n 2 nα/logn ,2r1 / 2 nα(logrlogn)时空积 (成本最优性 ) T× P小于T×P(T和P分别为 [8]中原有并行算法的时间复杂性和处理机台数 )。     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

机组组合的扩散并行遗传算法

研究了在细粒度并行机上的扩散并行遗传算法．遗传算法中个体为矩阵个体,选种采用竞争法．并行处理机拓扑结构为三维网格．对一个十机系统的机组组合问题进行了串行模拟,结果表明,当最大遗传代数或并行处理机个数增大时,均可找到更好的解,同时加速比也得以提高,且异步法优于同步法．     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

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

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

三角Stein方程的systolic算法

提出一种新的ｓｙｓｔｏｌｉｃ实现方法计算三角Ｓｔｅｉｎ方程．可将原复杂性为Ｏ（ｍ２ｎ２）的串行算法在处理器为Ｏ（ｍ２）的ｓｙｓｔｏｌｉｃ阵列上并行计算，时间复杂性降为Ｏ（ｍｎ），而处理器具有很高的利用率．利用文中给出的方法，可以并行求解一大类最优控制中有关矩阵运算的问题，如Ｌｙａｐｕｎｏｖ方程、Ｓｙｌｖｅｓｔｅｒ方程等     

基于OpenCL的图像灰度化并行算法研究

随着图像数据量的增加,传统单核处理器或多处理器结构的计算方式已无法满足图像灰度化实时处理需求.该文利用图像处理器(GPU)在异构并行计算的优势,提出了基于开放式计算语言(OpenCL)的图像灰度化并行算法.通过分析加权平均图像灰度化数据处理的并行性,对任务进行了层次化分解,设计了2级并行的并行算法并映射到“CPU+GPU”异构计算平台上.实验结果显示:图像灰度化并行算法在OpenCL架构下NVIDIA GPU计算平台上相比串行算法、多核CPU并行算法和CUDA并行算法的性能分别获得了27.04倍、4.96倍和1.21倍的加速比.该文提出的并行优化方法的有效性和性能可移植性得到了验证.     

带形线性系统的并行算法

本文提出了带形系统两种并行算法，带主元高斯划分法，只需要系数阵非奇异即可，另对三对角系统给出了一个特别并行算法，并计算共并行效率和并行加速。