并行归并排序算法

构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ＾１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数小于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ＾１／２ｌｏｇ ｎ）。     

一种新的多种归并排序网络

文中提出了一种新的多种归并排序网络,该网络基于倾斜与振荡多路归并排序算法。     

一种新的多路归并排序网络

文中提出了一种新的多路归并排序网络,该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ,即ｋ个数的排序器,ｋ为任意素数,而传统的排序网络的基本构件为两个数的排序,即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现;作为实例给出了Ｎ＝２７,ｋ＝３时的排序网络;分析了该网络的时间延迟;通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ,表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．     

一种归并排序算法的阵列映射

本文介绍一种归并排序算法－－插入归并算法的基本原理，并通过该算法的Ｓｙｓｔｏｌｉｃ阵列映射，重点阐述了正则映射生成ＶＬＳＩ阵列的理论和方法，最后，还指出了改进脉动阵列通用性和灵活性的途径。     

链表递增归并排序算法

归并排序是一种稳定,高效的排序算法。归并排序算法一般是用顺序存储结构实现的。如Sun公司JDK中Java Collection库中对数组、List的排序。使用顺序存储结构实现归并排序需要空间复杂度为O(n)的辅助存储空间,对于链表来说,还需要转换为顺序存储结构,所以共需要2n的辅助存储空间。本文提出一种链表非递归归并排序算法,可以对链表进行原地(In Place)排序,只需要O(logn)的辅助存储空间,时间复杂度不变。     

一种基于MPP的并行归并算法

文中提出并分析了并行归并算法ＰＭＦＳ;基于曙光－１０００大规模并行计算机系统,给出了ＰＭＦＳ算法应用实例的实验结果,并将ＰＭＦＳ算法推广得到的并行归并排序算法与ＰＳＲＳ算法进行了比较。     

一种奇序列并行排序算法

提出了一种奇序列双调排序算法,通过分析发现,该算法对某些奇双调序列不能得到正确的排序结果。在该算法的基础上,通过增加CCI操作,得到一种改进算法,改进后的算法能对任意奇双调序列进行正确排序,且不增加存储空间,计算复杂度级别也不变。     

链式归并排序法

介绍一种链式存储的逐步归并排序算法,其最佳时间复杂度为O(n),空间复杂度为O(1).     

RAPWBN计算模型上的快速并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1＜α＜2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成.     

基于散列和归并技术的有效并行排序方法

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列，引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序，这一阶段所需的平均时间为Ｏ（ｎ／ｐ）；最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列，归并阶段所需的时间为Ｏ（ｎ－ｎ／
／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓以网络并行机群环境。     

带有宽总线网络的可重构计算模型上的并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的二进制值的前缀和操作的基础上,提出了该模型上的抽取压缩操作算法,并由此得到了该模型上的并行归并排序算法。在具有N个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>log N字节,对长度为N的序列进行归并排序,在最坏情况下以O(logN·loglogN)时间完成。     

一种优化BITONIC算法:"并行-优化-串行"合并和分类向量算法

串行算法并行化是发挥各种巨型机的效率的关键技术之一。“并行－优化－串行”归并向量算法（OSVM），是一种串行算法并行化的优化方法，它用O（N／p)时间把总长为N的两个有序序列归并或把总长为N的一个Bitonic序列排序。“并行－优化－串行”排序向量算法（POSVS）用O（NlogN)/p）时间在实际SIMD机上把N个数排序，这些是第1个满足以下两个条件的向量Optimal算法（加速比＝O（p))，（1）它能在实际SIMD计算机上实现，处理机的台数p的范围很宽1≤N^1-ε，这里，ε是任意的小的正数。（2）它统一了3种不同类的合并算法：Batcher的Bitonic算法（最快但效率随参数变大而向于0），优化(Optimal)算法（效率为常数的算法）和最佳的串行算法。而且综合了3个算法的优点，“并行－优化－串行”（POS）方法是一个通用方法，它还可以应用到其它类型问题上。     

有向图并行计算中一种新的结点调度算法

在基于有向图的并行计算中,给定图剖分后,如何设计结点调度方案使得并行执行时间最短,是典型的NP完全问题.针对此问题,文中提出一种新的基于顺逆交替迭代技术的启发式调度算法,并给出该算法的并行实现.严格的理论推导证明,新算法在一定的假设条件下,从任何初始调度方案出发,均可以单调收敛.在数百个处理器上的并行数值实验表明,与常用的调度算法相比,新算法可在付出很少的开销代价下显著提高整体并行效率.     

带有宽总线网络的可重构计算模型上的并行排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的快速高效并行排序算法,在具有N个处理机和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,则对元素位数固定的N个元素可以在O(1)时间完成排序,对元素位数不固定的N个元素,可以在O(k)时间完成排序,这里k为元素的最大位数.     

基于流水光总线阵列的快速并行排序算法

基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型。本文提出了一种基于LARPBS模型的快速排序并行算法,该算法使用n个处理器,对关 键字位数固定的n个记录可以在O(1)时间完成排序;对于关键字位数不固定的n个记录,可以在O(d)时间完成排序,这里d为关键字的最大位数。     

Multisets排序的最优并行算法

排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 相似文献   

一种带数据整数规划的新型并行自平衡PSO算法

为有效解决标准粒子群(PSO)算法在进化后期缺乏多样性且精度不高的问题,利用多核系统及实际高校地理数据,给出一种高校数据的整数规划方法及并行自平衡PSO算法模型来并行求解高校路网问题,同时体现算法性能。将自平衡机制采用多核系统并行处理方式生成相互独立的子群体,每个子群体间并行求解,最终生成主群体最优路径即高校路网。在Visual Studio2005.NET环境下用C++编程实现仿真。实验结果表明,此算法从求解精度及计算时间两个重要方面综合改善了算法性能。     

蔓叶线的一种并行生成算法

主要研究了著名的几何曲线——蔓叶线的一种并行生成算法,以Bresenham算法为基础,对蔓叶线的并行生成算法进行了分析和讨论。首先,从蔓叶线图像的一个已知点开始,根据递推公式逐点选择最靠近蔓叶线的像素点;然后引入并行机制生成蔓叶线的图像;最后,利用C#多线程模拟实现了该算法。模拟结果表明,这是关于蔓叶线图像的一种快速、高效的并行算法。