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     

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.     

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.     

Parallel Heap Operations on an EREW PRAM

We consider parallel heap operations on the exclusive-read exclusive-write parallel random-access machine. We first present an O(n/p + log p) time parallel algorithm to construct a heap of n elements using p processors, which is optimal for p θ(n/log n). We then propose a parallel root deletion algorithm. In a preparatory step, a data structure for dynamic processor allocation is constructed using O((n/log n)^{1 − 1/k}) processors in O(log k) time for some constant k, 1 ≤ k ≤ ⌈log(n/log n)⌉. A sequence of root deletions can then be performed, each of which takes O((log n)/p + log p + log log n) time using p processors. Finally, we discuss a parallel algorithm running in O((log n)/p + log p) time for inserting an element into a heap, which is optimal for p = θ((log n)/log log n). Both deletion and insertion algorithms run in O(log log n) time when p = θ((log n)/log log n).     

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.     

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     

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.     

Efficient algorithms for geometric control of systems over rings

The computational algebra techniques described in this paper constitute a tool, efficient and easy to implement using the freely available software CoCoA. They open the way to an effective use of the geometric approach in dealing with dynamical systems over rings. Systems with coefficients in a ring can be used to model several interesting classes of dynamical systems such as parameter dependent systems or delay differential systems. The paper describes in detail, how the algorithms contained in the package “control.cpkg” can be used to practically solve decoupling problems for delay differential systems.     

Efficient PRAM simulation on a distributed memory machine

We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. Thedelay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of anm processor PRAM on ann processor DMM will necessarily have delay at leastm/n. A randomized simulation is calledtime-processor optimal if the delay isO(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delayO(log log(n) log*(n)). The best previous simulations use a simpler scheme based on hashing and have much larger delay: (log(n)/log log(n)) for the simulation of an n processor PRAM on ann processor DMM, and (log(n)) in the case where the simulation is time-processor optimal.Our simulations use several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM. The stochastic processes modeling the behavior of our algorithms and their analyses based on powerful classes of universal hash functions may be of independent interest.Research partially supported by NSF/DARPA Grant CCR-9005448. Work was done while at the University of California at Berkeley and the International Computer Science Institute, Berkeley, CA.Research partially supported by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT BR Grant EC-US 030.Part of work was done during a visit at the International Computer Science Institute at Berkeley; supported in part by DFG-Forschergruppe Effiziente Nutzung massiv paralleler Systeme, Teilprojekt 4, and by the Esprit Basic Research Action Nr. 7141 (ALCOM II).     

Visualization of geometric algorithms

Investigates the visualization of geometric algorithms. We discuss how limiting the domain makes it possible to create a system that enables others to use it easily. Knowledge about the domain can be very helpful in building a system which automates large parts of the user's task. A system can be designed to isolate the user from any concern about how graphics is done. The application need only specify “what” happens and need not be concerned with “how” to make it happen on the screen. We develop a conceptual model and a framework for experimenting with it. We also present a system, GASP (Geometric Animation System, Princeton), which implements this model. GASP allows quick generation of 3D geometric algorithm visualizations, even for highly complex algorithms. It also provides a visual debugging facility for geometric computing. We show the utility of GASP by presenting a variety of examples     

Parallel geometric algorithms on a mesh-connected computer

We show that a number of geometric problems can be solved on a n × n mesh-connected computer (MCC) inO(n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires (n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.This work was supported in part by the National Science Foundation under Grant DCR 8420814. A preliminary version was presented in the 1987 FJCC, Dallas, TX.     

Parallel geometric algorithms on a mesh-connected computer

We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) inO(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.     

一类基于几何分析的迭代学习控制算法

基于几何分析，对迭代学习控制方法的几何框架进行探索．首先通过对Arimoto算法所构成的向量图进行几何分析，导出了一类新的迭代学习算法结构；然后从理论上对所导出的算法进行完整的收敛性分析．该算法结构与已有算法完全不同，但其收敛速度和精度明显提高．仿真结果表明了新算法的有效性和优越性．     

A paradigm for robust geometric algorithms

This paper explores a paradigm for producing geometrical algorithms in which logical decisions that depend on finite-precision numerical calculation cannot lead to failure. It applies this paradigm to the task of intersecting two convex polyhedral objects. A key tool in this work is a method of perturbing embedding polyhedra in ways consistent with their topology.Work on this paper was supported in part by NSF Grant DMC-86-17355, NSF Grant DMS-87-02070, ONR Grant N00014-86-0281, ONR Grant N00014-88-0591, and the U.S. Army Research Office through MSI, Cornell University.     

A paradigm for robust geometric algorithms

This paper explores a paradigm for producing geometrical algorithms in which logical decisions that depend on finite-precision numerical calculation cannot lead to failure. It applies this paradigm to the task of intersecting two convex polyhedral objects. A key tool in this work is a method of perturbing embedding polyhedra in ways consistent with their topology.     

Randomized geometric algorithms and pseudorandom generators

It is shown that the bounds on the expected running times of most of the randomized incremental algorithms in computational geometry do not change by more than a constant factor when they are made pseudorandom using a very simple scheme. This reduces the number of random bits used by these algorithms from (nlogn) toO(logn).This research was supported by Packard fellowship.     

Efficient and Scalable PRAM Algorithms for Discrete-Event Simulation of Bounded Degree Networks

We describe two new parallel algorithms, one conservative and another optimistic, for discrete-event simulation on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). The target physical systems are bounded degree networks which are represented by logic circuits. Employing p processors, our conservative algorithm can simulate up to O(p) independent messages of a system with n logical processes in O(log n) time. The number of processors, p, can be optimally varied in the range 1 ≤ p ≤ n. To identify independent messages, this algorithm also introduces a novel scheme based on a variable size time window. Our optimistic algorithm is designed to reduce the rollback frequency and the memory requirement to save past states and messages. The optimistic algorithm also simulates O(p) earliest messages on a p-processor computer in O(log n) time. To our knowledge, such a theoretical efficiency in parallel simulation algorithms, conservative or optimistic, has been achieved for the first time.