Multisets排序的最优并行算法

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

Parallel merging with restriction

In this paper, we study the merging of two sorted arrays and on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ₁,n ₂). (2) The elements are taken from either uniform distribution or non-uniform distribution such that , for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in time using p processors on EREW PRAM. For ; the running time of the algorithm is O(log ^(g) n) which is faster than the previous results, where log ^(g) n=log log ^(g−1) n for g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to [1,n ^k ], where k is a constant.

Context‐based compression of binary images in parallel

Binary images can be compressed efficiently using context‐based statistical modeling and arithmetic coding. However, this approach is fully sequential and therefore additional computing power from parallel computers cannot be utilized. We attack this problem and show how to implement the context‐based compression in parallel. Our approach is to segment the image into non‐overlapping blocks, which are compressed independently by the processors. We give two alternative solutions about how to construct, distribute and utilize the model in parallel, and study the effect on the compression performance and execution time. We show by experiments that the proposed approach achieves speedup that is proportional to the number of processors. The work efficiency exceeds 50% with any reasonable number of processors. Copyright © 2002 John Wiley & Sons, Ltd.     

一种基于互联处理器网络的并行分类算法

文中提出一个IPBPS(Interconnected Processor-Based Parallel Sorting)并行分类算法，运行在由独立处理器构成的计算机网络上，以解决网络分布式数据库的分类计算问题。基于并行算法应与并行计算的拓扑结构相匹配的思想，设计了一种旨在减小处理器间通信开销的网络结构。在此并行计算环境中，每个处理器执行同样的程序，计算负载均匀分布在每个处理器中，具有较高的加速比。同时，这种基本的处理器互联结构可灵活扩展，且随着网络的扩大，算法的并行加速比更高。     

An Efficient General In-Place Parallel Sorting Scheme

We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.     

THSORT:单机并行排序算法

排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.     

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

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

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

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

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

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

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

Fast Four‐Way Parallel Radix Sorting on GPUs

Efficient sorting is a key requirement for many computer science algorithms. Acceleration of existing techniques as well as developing new sorting approaches is crucial for many real‐time graphics scenarios, database systems, and numerical simulations to name just a few. It is one of the most fundamental operations to organize and filter the ever growing massive amounts of data gathered on a daily basis. While optimal sorting models for serial execution on a single processor exist, efficient parallel sorting remains a challenge. In this paper, we present a hardware‐optimized parallel implementation of the radix sort algorithm that results in a significant speed up over existing sorting implementations. We outperform all known General Processing Unit (GPU) based sorting systems by about a factor of two and eliminate restrictions on the sorting key space. This makes our algorithm not only the fastest, but also the first general GPU sorting solution.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

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

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

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

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

基于流水光总线阵列上Valiant并行归并排序的实现

基于流水总线的可重构线性阵列系统（LARPBS）是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Vnliant并行归并的实现算法,利用该法对长度为N的序列进行排序,最坏情况下可以使用N个处理器在O（logNloglogN)时间完成。     

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n -vertex graph the algorithm runs in o(( log n) ^{1+ ɛ} ) expected time for any ɛ >0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation—the QSM and the BSP.     

高效的随机访问分块倒排文件自索引技术

针对倒排索引空间开销大、查询时间效率低以及难以同时支持连接布尔查询和排序查询的问题,提出了一种同时提高空间效率与查询时间效率的高效随机访问分块倒排文件自索引RABIF.为了在降低空间消耗的同时支持连接布尔查询与排序查询,RABIF将倒排列表进行合理地分块,然后对每个子块的不同部分采用相应的压缩方式,在不需要插入任何附加辅助信息的前提下实现压缩索引的快速定位与随机访问.理论分析及实验结果表明,与忽略倒排文件自索引SIF相比,提出的RABIF空间开销平均减少5.3%,布尔查询时间平均减少17.8%;对于0.2%与1%排序查询,查询时间分别平均减少34.4%与27.5%.     

AVS标准中整数DCT变换的CUDA并行算法

随着图形处理器(GPU)的处理能力的不断增强,图形处理器越来越多的运用在计算密集型的数据处理中.AVS标准视频压缩算法中一些步骤存在典型的并行特性,高清、超清视频压缩的串行算法执行时间开销较大,难以满足实时编码的需要,因此利用GPU的并行处理能力和CUDA的编程框架对AVS标准中的整数DCT变换算法进行了并行实现.经过实验测试,并行算法与串行算法相比具有较高的加速比.     

Efficient Parallel Algorithms for Planar st -Graphs

   Abstract. Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.     

PARALLEL GIVENS SEQUENCES FOR SOLVING THE GENERAL LINEAR MODEL ON A EREW PRAM∗

Abstract

Parallel Givens sequences for solving the General Linear Model (GLM) are developed and analyzed. The block updating GLM estimation problem is also considered. The solution of the GLM employs as a main computational device the Generalized QR Decomposition, where one of the two matrices is initially upper triangular. The proposed Givens sequences efficiently exploit the initial triangular structure of the matrix and special properties of the solution method. The complexity analysis of the sequences is based on a Exclusive Read-Exclusive Write (EREW) Parallel Random Access Machine (PRAM) model with limited parallelism. Furthermore, the number of operations performed by a Givens rotation is determined by the size of the vectors used in the rotation. With these assumptions one conclusion drawn is that a sequence which applies the smallest number of compound disjoint Givens rotations to solve the GLM estimation problem does not necessarily have the lowest computational complexity. The various Givens sequences and their computational complexity analyses will be useful when addressing the solution of other similar factorization problems.