Narrow Results

Parallel algorithms for solving a knapsack problem of size n on PRAM and distributed memory machines are presented. The algorithms are work-efficient in the sense that they achieve optimal speedup with regard to the best known solution to this problem. Moreover, they match the best current time/memory/processors tradeoffs, while requiring less memory and/or processors. Since the PRAM is considered mainly as a theoretical model, and we want to produce practical algorithms for the knapsack problem, its solution in distributed memory machines is also studied. For the first time in literature, work-efficient parallel algorithms on local memory — message passing architectures — are given. Time bounds for solving the problem on linear arrays, meshes, and hypercubes are proved.

The problem of merging two intransitive sorted sequences (that is, to generate a sorted total order without the transitive property) is considered. A cost-optimal parallel merging algorithm is proposed under the EREW PRAM model. This algorithm has a run time of O(log² n) using O(n/log² n) processors. The cost-optimal merge in the strong sense is still an open problem.

The Parallel Random Access Machine is a very strong model of parallel computing that has resisted cost-efficient implementation attempts for decades. Recently, the development of VLSI technology has provided means for indirect on-chip implementation, but there are different variants of the PRAM model that provide different performance, area and power figures and it is not known how their implementations compare to each others. In this paper we measure the performance and estimate the cost of practical implementations of four PRAM models including EREW, Limited Arbitrary CRCW, Full Arbitrary CRCW, Full Arbitrary Multioperation CRCW on our Eclipse chip multiprocessor framework. Interestingly, the most powerful model shows the lowest simulation cost and highest performance/area and performance/power figures.

The log cost measure has been viewed as a more reasonable method of measuring the time complexity of an algorithm than the unit cost measure. The more widely used unit cost measure becomes unrealistic if the algorithm handles extremely large integers. Parallel machines have not been examined under the log cost measure. In this paper, we investigate the Parallel Random Access Machine under the log cost measure. Let the instruction set of a basic PRAM include addition, subtraction, and Boolean operations. We relate resource-bounded complexity classes of log cost PRAMs to complexity classes of Turing machines and circuits. We also relate log cost PRAMs with different instruction sets by simulations that are much more efficient than possible in the unit cost case. Let LCRCW^k(CRCW^k) denote the class of languages accepted by a log cost (unit cost) basic CRCW PRAM in O(log^k n) time with the polynomial in n number of processors. We position the log cost PRAM in the hierarchy of parallel complexity classes as: AC^k=CRCW^k⊆(NC^k+1, LCRCW^k+1)⊆AC^k+1=CRCW^k+1.

We develop efficient parallel maximum matching algorithms in interval graphs by exploiting special properties of interval graphs. For general interval graphs, our algorithm requires O(log²v+(n log n/v) time and O(nv²+n²) operations on the CREW PRAM, where n is the number of intervals and v≤n is a parameter. By choosing , we obtain an -time algorithm in O(n²) operations. For v=n/log n, we have an O(log²n)-time algorithm in O(n³/log²n) operations. The best previously known solution takes O(log²n) time using O(n³log²n) operations. For proper interval graphs, our algorithm runs in O(log n) time using O(n) operations if input intervals are sorted and using O(nlog n) operations otherwise on the EREW PRAM.

This paper introduces a calculus of weakest specification for supporting reuse of established components in deriving a design (in the sense of formal methods). The weakest specifunction generalizes the notions of weakest pre-specification and weakest parallel environment; but instead of calculating the weakest required component of a target specification, it calculates the weakest specification function whose value refines the target when applied to an established component. In particular it overcomes the restriction of those other calculi to taking merely one required component at a time.

The theory of specifunctions is applied to a new weakest-design calculus in the context of BSP. The calculus is based on the par-seq specifunction which involves two required components: it places one established component in parallel with one required component and the result in sequence with another required component to meet a given specification. A calculus is provided for the par-seq specifunction and it is applied to the derivation of a distributed BSP algorithm for greatest common divisor.

We present simple and efficient parallel algorithms for obtaining a chordless cycle of length greater than or equal to k in a graph whenever such a cycle exists. Our results generalize and simplify existing results for detecting chordless cycles.

Two techniques for managing memory on a parallel random access machine (PRAM) are presented. One is a scheme for an n/log n processor EREW PRAM that dynamically allocates and deallocates up to n records of the same size in O(log n) time. The other is a simulation of a PRAM with initialized memory by one with uninitialized memory. A CREW PRAM variant of the technique justifies the assumption that memory can be assumed to be appropriately initialized with no asymptotic increase in time but a factor of n increase in space. An EREW PRAM solution incurs a factor of O(log n) increase in time but only a constant factor increase in space.

We consider the problem of copying information stored initially in a single memory cell by Exclusive Read Exclusive Write Parallel Random Access Machines (EREW PRAMs). We prove lower bounds for this problem and present algorithms matching them tightly (in many cases up to an additive constant). The bounds presented depend on the number of cells used and size of information copied. The lower bounds apply also to functions where a change of a single argument influences the output in many memory locations.

We describe a randomized parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n) operations with high probability on the Priority CRCW PRAM. The previous best known algorithms run in O(log² n) time using O(n log² n) operations on the CREW PRAM and O(log n) time using O(n log log n) operations on the Arbitrary CRCW PRAM. The technique presented can be used to generate the Euler tour of a rooted tree optimally from the parent representation.

Distance hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. In this paper, we study properties of distance hereditary graphs from the view point of parallel computations. We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree, which take O(log n) time using O(n + m) processors on CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance hereditary graph in O(log² n) time using O(n + m) processors on a CREW PRAM.

In this paper, we show the interest of the 3D discrete surface notion for the extraction of object contours. We introduce some notions related to surfaces of 18-and 26-connected objects in 3D discrete images, and a new sequential algorithm to extract the surface and contours of 26-connected objects. Then, we present a PRAM related algorithm to construct the successor function of the surface graph. The complexity of the algorithm is O(log N) for an N×N×N image, with N³ processors.

In this paper we prove the correctness of a “local” criterion for computing the convex hull of the union ( “merging”) of two disjoint convex polyhedra. This criterion is structural. Therefore it can be algorithmically tested in several ways, not necessarily involving the determination of support (tangent) planes; indeed, it can be implemented by just testing for the intersection of certain planes and lines with convex polytopes. This criterion is amenable to parallel implementation and leads to a provably correct algorithm that computes the convex hull of any n points in three-dimensional space in O(log² n) time using O(n) processors on a CREW PRAM.

We present a parallel algorithm for finding the convex hull of a sorted point set. The algorithm runs in O(log log n) (doubly logarithmic) time using n/log log n processors on a Common CRCW PRAM. To break the Ω(log n/log log n) time barrier required to output the convex hull in a contiguous array, we introduce a novel data structure for representing the convex hull. The algorithm is optimal in two respects: (1) the time-processor product of the algorithm, which is linear, cannot be improved, and (2) the running time, which is doubly logarithmic, cannot be improved even by using a linear number of processors. The algorithm demonstrates the power of the “the divide-and-conquer doubly logarithmic paradigm” by presenting a non-trivial extension to situations that previously were known to have only slower algorithms.

In this paper, we show the interest of the 3D discrete surface notion for the extraction of object contours. We introduce some notions related to surfaces of 18-and 26-connected objects in 3D discrete images, and a new sequential algorithm to extract the surface and contours of 26-connected objects. Then, we present a PRAM related algorithm to construct the successor function of the surface graph. The complexity of the algorithm is O(log N) for an N × N × N image, with N³ processors.