共查询到13条相似文献,搜索用时 62 毫秒
1.
2.
在介绍带有宽总线网络的可重构计算模型(RAPWBN)的二进制值的前缀和操作的基础上,提出了该模型上的抽取压缩操作算法,并由此得到了该模型上的并行归并排序算法。在具有N个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>log N字节,对长度为N的序列进行归并排序,在最坏情况下以O(logN·loglogN)时间完成。 相似文献
3.
带有宽总线网络的可重构计算模型上的并行排序算法 总被引:1,自引:0,他引:1
在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的快速高效并行排序算法,在具有N个处理机和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,则对元素位数固定的N个元素可以在O(1)时间完成排序,对元素位数不固定的N个元素,可以在O(k)时间完成排序,这里k为元素的最大位数. 相似文献
4.
该文介绍了带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作,提出了一种快速并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,可以在O(1)时间完成排序。该算法的成本达到了最优。 相似文献
5.
文章提出了一种LARPBS模型上的并行归并排序算法,利用该算法对长度为N的序列进行排序,使用N~(1+)着(0<着<1)个处理机可以在O((loglogN)~2)时间完成。 相似文献
6.
并行归并排序算法 总被引:3,自引:0,他引:3
来智勇 《计算机研究与发展》1995,32(6):46-49,54
构造效率为O(1)的并行算法是一个引人注目的问题。[1]和[2]分别提出了并行度为O(logn)和O(n^1/2)的、效率为O(1)的并行排序算法。本文提出一种新的并行排序算法,其效率为O(1),而并行步数小于[1]和[2]的算法的并行步数。经过改进后,在保持效率为O(1)的情况下,可进一步将并行度扩大到O(n^1/2log n)。 相似文献
7.
钟诚 《计算机工程与科学》1998,20(4):42-45
本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法:将长度为n的待排序数据划分成p个长度为n/p的子序列,引入散列技术并行地对这p个子序列的数据进行二次散列排序,这一阶段所需的平均时间为O(n/p);最后并行地将p个有序子序列归并成一个长度为n的有序序列,归并阶段所需的时间为O(n-n/
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。 相似文献
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。 相似文献
8.
一种新的并行归并排序算法 总被引:5,自引:0,他引:5
文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。 相似文献
9.
基于倾斜与振荡法多路归并排序算法,提出了纵横多路并行归并算法,与已有方法递归应用两路归并过程不同.该算法直接对m×k的矩阵(m,k为任意整数)进行排序,消除了对两路递归过程的依赖,是一种新的多路归并排序算法.通过和倾斜与振荡法多路归并排序算法和高效的任意路并行归并算法的性能分析比较,当3k40时,该算法的时间复杂性低于同类算法.同时,该算法在专用硬件实现的设计复杂性上也具有明显的优势. 相似文献
10.
11.
基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型。本文提出了一种基于LARPBS模型的快速排序并行算法,该算法使用n个处理器,对关 键字位数固定的n个记录可以在O(1)时间完成排序;对于关键字位数不固定的n个记录,可以在O(d)时间完成排序,这里d为关键字的最大位数。 相似文献
12.
13.
文中提出一个IPBPS(Interconnected Processor-Based Parallel Sorting)并行分类算法,运行在由独立处理器构成的计算机网络上,以解决网络分布式数据库的分类计算问题。基于并行算法应与并行计算的拓扑结构相匹配的思想,设计了一种旨在减小处理器间通信开销的网络结构。在此并行计算环境中,每个处理器执行同样的程序,计算负载均匀分布在每个处理器中,具有较高的加速比。同时,这种基本的处理器互联结构可灵活扩展,且随着网络的扩大,算法的并行加速比更高。 相似文献