Maintaining B-Trees on an EREW PRAM

Efficient and practical algorithms for maintaining general B-trees on an EREW PRAM are presented. Given a B-tree of order b with m distinct records, the search (respectively, insert and delete) problem for n input keys is solved on an n-processor EREW PRAM in O(log n + b log_b m) (respectively, O(b(log n + log_b m)) and O(b²(log_b n + log_b m))) time.     

Efficient geometric algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM     

Fast integer merging on the EREW PRAM

We investigate the complexity of merging sequences of small integers on the EREW PRAM. Our most surprising result is that two sorted sequences ofn bits each can be merged inO(log logn) time. More generally, we describe an algorithm to merge two sorted sequences ofn integers drawn from the set {0, ...,m?1} inO(log logn+log min{n, m}) time with an optimal time-processor product. No sublogarithmic-time merging algorithm for this model of computation was previously known. On the other hand, we show a lower bound of Ω(log min{n, m}) on the time needed to merge two sorted sequences of lengthn each with elements drawn from the set {0, ...,m?1}, implying that our merging algorithm is as fast as possible form=(logn)^Ω(1). If we impose an additional stability condition requiring the elements of each input sequence to appear in the same order in the output sequence, the time complexity of the problem becomes Θ(logn), even form=2. Stable merging is thus harder than nonstable merging.     

Efficient EREW PRAM algorithms for parentheses-matching

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log² n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms     

An EREW PRAM algorithm for image component labeling

An important midlevel task for computer vision is addressed. The problem consists of labeling connected components in N^1/2 ×N^2/2 binary images. This task can be solved with parallel computers by using a simple and novel algorithm. The parallel computing model used is a synchronous fine-grained shared-memory model where only one processor can read from or write to the same memory location at a given time. This model is known as the exclusive-read exclusive-write parallel RAM (EREW PRAM). Using this model, the algorithm presented has O(log N) complexity. The algorithm can run on parallel machines other than the EREW PRAM. In particular, it offers an optimal image component labeling algorithm for mesh-connected computers     

A randomized sublinear time parallel GCD algorithm for the EREW PRAM

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(nloglogn/logn) time using O(n6+?) processors for any ?>0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure.We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.     

Improved Bounds for Integer Sorting in the EREW PRAM Model

A new simple method of exploiting nonstandard word length in the nonconservative RAM and PRAM models is considered. As a result, improved bounds for parallel integer sorting in the EREW PRAM model with standard and nonstandard word length are obtained.     

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.     

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.     

Parallel Polynomial Operations on SMPs: an Overview

SMP-based parallel algorithms and implementationsfor polynomial factoring and GCD are overviewed. Topics include polynomial factoring modulo small primes, univariate and multivariatep-adic lifting, and reformulation of lift basis. Sparse polynomial GCD is also covered.     

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

基于PRAM并行模型最大值查找的方法与改进

随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM （Parallel Random Access Machine）下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本（cost）更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.     

基于PRAM模型的CFGs并行识别与语法分析的扩充算法

本文介绍了一种PRAM模型上的上下文无关文法的并行识别和改进的并行语法分析方法金字塔结构,并对该方法进行了修改和补充,使其对非Chomsky规范形式,即文法的产生式右部候选式（即规则）有两个以上的非终结符连接的,或者候选式中既有非终结符,又有终结符的情况,扩充的算法也能识别和分析。     

基于PRAM模型的二叉树A序列并行算法的研究

运用并行计算的PRAM模型研究二叉树A序列问题,提出了二又树的A序列的一种并行算法,并以应用实例对并行算法的过程进行详细描述和验证性分析.二叉树A序列的并行算法,为应用到二叉树序列遍历的系统与应用程序的并行化问题的解决提供借鉴和参考.     

Echo Algorithms: Depth Parallel Operations on General Graphs

This paper describes a method for the detection of properties of general graphs in an environment in which each node can be considered an autonomous processor, interacting with its neighbors by passing messages.     

数字图像几何变换的数据并行方法研究

针对SIMD计算机上的数字图像的几何变换问题,提出了一个新颖的基于阵列平移的数据并行实现方法。在此基础上,给出了数字图像几何变换的数据并行实现算法,并详细分析和讨论了算法的复杂性以及精度要求。     

A Parallel Algorithm for Computing Polygon Set Operations

We present a parallel algorithm for performing boolean set operations on generalized polygons that have holes in them. The intersection algorithm has a processor complexity of O(m²n²) processors and a time complexity of O(max(2log m, log²n)), where m is the maximum number of vertices in any loop of a polygon, and n is the maximum number of loops per polygon. The union and difference algorithms have a processor complexity of O(m²n²) and time complexity of O(log m) and O(2log m, log n) respectively. The algorithm is based on the EREW PRAM model. The algorithm tries to minimize the intersection point computations by intersecting only a subset of loops of the polygons, taking advantage of the topological structure of the two polygons. We believe this will result in better performance on the average as compared to the worst case. Though all the algorithms presented here are deterministic, randomized algorithms such as sample sort can be used for the sorting subcomponent of the algorithms to obtain fast practical implementations.     

A Parallel Priority Queue with Constant Time Operations

We present a parallel priority queue that supports the following operations in constant time:parallel insertionof a sequence of elements ordered according to key,parallel decrease keyfor a sequence of elements ordered according to key,deletion of the minimum key element, anddeletion of an arbitrary element. Our data structure is the first to support multi-insertion and multi-decrease key in constant time. The priority queue can be implemented on the EREW PRAM and can perform any sequence ofnoperations inO(n) time andO(mlogn) work,mbeing the total number of keyes inserted and/or updated. A main application is a parallel implementation of Dijkstra's algorithm for the single-source shortest path problem, which runs inO(n) time andO(mlogn) work on a CREW PRAM on graphs withnvertices andmedges. This is a logarithmic factor improvement in the running time compared with previous approaches.     

Work-time optimal k-merge algorithms on the PRAM

For 2⩽k⩽n, the k-merge problem is to merge a collection of ksorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of this work is to give simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models, thus settling the status of the k-merge problem. We first prove that Ω(n log k) work is required to solve the k-merge problem on the PRAM models. We then show that the EREW-PRAM and both the CREW-PRAM and the CRCW require Ω(log n) time and Ω(log log n+log k) time, respectively, provided that the amount of work is bounded by O(n log k). Our first k-merge algorithm runs in Θ(log n) time and performs Θ(n log k) work on the EREW-PRAM. Finally, we design a work-time optimal CREW-PRAM k-merge algorithm that runs in Θ(log log n+log k) time and performs Θ(n log k) work. This latter algorithm is also work-time optimal on the CREW-PRAM model. Our algorithms completely settle the status of the k-merge problem on the three main PRAM models