共查询到19条相似文献,搜索用时 0 毫秒
1.
2.
本文介绍一种归并排序算法--插入归并算法的基本原理,并通过该算法的Systolic阵列映射,重点阐述了正则映射生成VLSI阵列的理论和方法,最后,还指出了改进脉动阵列通用性和灵活性的途径。 相似文献
3.
基于倾斜与振荡法多路归并排序算法,提出了纵横多路并行归并算法,与已有方法递归应用两路归并过程不同·该算法直接对m×k的矩阵(m,k为任意整数)进行排序,消除了对两路递归过程的依赖,是一种新的多路归并排序算法·通过和倾斜与振荡法多路归并排序算法和高效的任意路并行归并算法的性能分析比较,当3k40时,该算法的时间复杂性低于同类算法·同时,该算法在专用硬件实现的设计复杂性上也具有明显的优势· 相似文献
4.
一种线性原地二路归并算法 总被引:2,自引:0,他引:2
和其它排序算法相比,二路归并最适合于两个有序子表的排序。但经典原地二路归并算法的时间性能是乘积型的,尚有改进空间。文章介绍了改进经典原地二路归并算法所需的基本技术,提出了一种线性原地二路归并算法。归并长度分别为m和n的两个有序子表,谈算法最多需要2.5m 1.5n 4.5√m n次比较和8m 7n-3√m n次移动。 相似文献
5.
一种新的并行归并排序算法 总被引:5,自引:0,他引:5
文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。 相似文献
6.
7.
在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1<α<2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成. 相似文献
8.
一种实用的数值型伪Hash函数排序方法 总被引:2,自引:0,他引:2
张亚南 《计算机研究与发展》1993,30(10):33-36
本文给出一种具有实用价值的数值型伪Hash函数排序方法。该方法通过尽量避免比较而直接计算定位的方式提高排序速度。测试结果表明:该算法的排序时间好于比较式排序的代表性算法Quicksort,Shellsort。与现有算法相比,该算法简洁,灵活,易于实现,适合于某些应用领域的特殊需求。 相似文献
9.
10.
11.
A multiway merge sorting network is presented, which generalizes the technique used in the odd-even merge sorting network. The merging network described here is composed of m k-way mergers and a combining network. It arranges k ordered lists of length n each into one ordered lists in T(k)+[log2k] [log2m] [log2m] steps, where T(k) is the number of steps needed to sort k keys in order; and k and m are any integers no longer restricted to 2 相似文献
12.
介绍CPN(Colorea Petri Nets)的基本概念,用CPN建模实现动态的、并发的多路归并外排序算法。算法利用多个缓冲区解决外部文件读入的等待延时,通过调整缓冲区的大小和数量可在不同的机器上获得最佳效果。 相似文献
13.
Ronald I Becker David Nassimi Yehoshua Perl 《Journal of Parallel and Distributed Computing》1998,54(2):1601
Aperiodic sorteris a sorting network that is a cascade of a number of identicalblocks, where outputiof each block is inputiof the next block. Previously, Dowd, Perl, Rudolph, and Saks introduced thebalancedmerging network, withN=2kinputs/outputs and log Nstages of comparators. Using a very intricate proof, they showed that a cascade of log Nsuch blocks constitutes a sorting network. In this paper, we introduce a large class of merging networks with the same periodic property. This class contains 2N/2−1networks, whereN=2kis the number of inputs. The balanced merger is one network in this class. Other networks use fewer comparators. We provide a very simple and elegant correctness proof based on the recursive structure of the networks. 相似文献
14.
Joel 《Journal of Parallel and Distributed Computing》2005,65(12):1601-1606
Lee and Batcher have designed networks that efficiently merge k separately provided sorted sequences of known lengths totalling n. We show that the design is still possible, and in fact easier to describe, if we do not make use of the lengths, or even the directions of monotonicity, of the individual sequences—the sequences can be provided in a single undelimited concatenation of length n. The depth of the simplest resulting network to sort sequences that are “k-tonic” and of length n is , generalizing Batcher's 1968 results for the extreme values of k (k=2 corresponding to merging, and k=n/2 corresponding to general sorting).The exposition is self-contained and can serve even as an introduction to sorting networks and Batcher's results. 相似文献
15.
16.
钟诚 《计算机工程与科学》1998,20(4):42-45
本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法:将长度为n的待排序数据划分成p个长度为n/p的子序列,引入散列技术并行地对这p个子序列的数据进行二次散列排序,这一阶段所需的平均时间为O(n/p);最后并行地将p个有序子序列归并成一个长度为n的有序序列,归并阶段所需的时间为O(n-n/
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。 相似文献
/p)。整个排序算法的并行执行代价为O(np)。本排序方法可以拓以网络并行机群环境。 相似文献
17.
Many sorting algorithms have been studied in the past, but there are only a few algorithms that can effectively exploit both single‐instruction multiple‐data (SIMD) instructions and thread‐level parallelism. In this paper, we propose a new high‐performance sorting algorithm, called aligned‐access sort (AA‐sort), that exploits both the SIMD instructions and thread‐level parallelism available on today's multicore processors. Our algorithm consists of two phases, an in‐core sorting phase and an out‐of‐core merging phase. The in‐core sorting phase uses our new sorting algorithm that extends combsort to exploit SIMD instructions. The out‐of‐core algorithm is based on mergesort with our novel vectorized merging algorithm. Both phases can take advantage of SIMD instructions. The key to high performance is eliminating unaligned memory accesses that would reduce the effectiveness of SIMD instructions in both phases. We implemented and evaluated the AA‐sort on PowerPC 970MP and Cell Broadband Engine platforms. In summary, a sequential version of the AA‐sort using SIMD instructions outperformed IBM's optimized sequential sorting library by 1.8 times and bitonic mergesort using SIMD instructions by 3.3 times on PowerPC 970MP when sorting 32 million random 32‐bit integers. Also, a parallel version of AA‐sort demonstrated better scalability with increasing numbers of cores than a parallel version of bitonic mergesort on both platforms. Copyright © 2011 John Wiley & Sons, Ltd. 相似文献
18.
An evolutionary algorithm is combined with an application-specific developmental scheme in order to evolve efficient arbitrarily
large sorting networks. First, a small sorting network (that we call the embryo) has to be prepared to solve the trivial instance of a problem. Then the evolved program (the constructor) is applied on the embryo to create a larger sorting network (solving a larger instance of the problem). Then the same constructor
is used to create a new instance of the sorting network from the created larger sorting network and so on. The proposed approach
allowed us to rediscover the conventional principle of insertion which is traditionally used for constructing large sorting networks. Furthermore, the principle was improved by means of
the evolutionary technique. The evolved sorting networks exhibit a lower implementation cost and delay. 相似文献
19.
This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster. 相似文献