Parallel Processing Letters

(Ordered) binary decision diagrams are a powerful representation for Boolean functions and are widely used in logical synthesis, verification, test pattern generation or as part of CAD tools. NC-algorithms are presented for the most important operations on this representation, e.g. evaluation for a given input, minimization, satisfiability, redundancy test, replacement of variables by constants or functions, equivalence test and synthesis. The algorithms have logarithmic run time on CRCW COMMON PRAMs with a polynomial number of processors.

We present an efficient algorithm for computing the matching polynomial of a series-parallel graph in O(n²) time. This algorithm improves on the previous result of O(n³). We also present a cost-optimal parallel algorithm for computing the matching polynomial of a series-parallel graph using an EREW PRAM computer with the number of processors p less than n²/ log n.

We consider a message-passing system of n processors, each of which initially holds one piece of data. The goal is to compute an associative and commutative census function f on the n distributed pieces of data and to make the result known to all processors. To perform the computation, processors communicate with each other by sending and receiving messages in specified communication rounds. We describe an optimal algorithm for this problem that requires the least number of communication rounds and that minimizes the time spent by any processor in sending and receiving messages.

We introduce the notion of Update-Last scheme as a distributed method of storing an index, and derive exact bounds on their space complexity.

The scattering problem refers to the gossiping and the broadcasting problems [1, 2]. It consists in distributing a set of data from a single source such that each component is sent to a distinct address. The gathering operation is the reverse of the scattering operation. This paper studies the problem of pipelining a scattering-gathering sequence in order to overlap these operations. We first give a general solution for distributed memory parallel computers, and next we particularly study this problem on hypercubes.

Two different bit-level systolic arrays for digital contour smoothing by Abel-Poisson kernel which minimize the execution time and the number of functional elements required are suggested. The arrays are fully pipelined on the bit-level achieving very high clock frequency. They are implementable in VLSI and are dedicated for real-time applications.

Papadimitrjou and Yannakakis showed that unit execution time tasks in interval orders can be scheduled in linear time on N processors when communication cost is ignored. The objective function was to minimize the schedule length. They have also shown that the generalization of this problem to arbitrary execution times is NP-complete. In this paper, we study the problem of scheduling task graphs with communication on N processors when the task graph is an interval order. We prove that this scheduling problem can be solved in polynomial time when the execution cost of the system tasks is identical and equal to the communication cost between any pair of processors. We introduce an algorithm of O(Ne) to minimize the schedule length, where e is the number of arcs in the interval order.

The purpose of this paper is to present non-trivial lower bounds for two classes of enhanced meshes. To achieve this goal we present efficient simulations of these two classes of enhanced meshes on the CREW-PRAM and Common-CRCW. From this, known computational lower bounds for the PRAM are transferred to the enhanced meshes. Our approach of transferring lower bounds from the PRAM to enhanced meshes is novel. Specifically, we show that any computation that takes O(t(n)) steps on an n-processor mesh with multiple broadcasting can be performed in O(t(n)) steps on an n-processor CREW-PRAM with O(n) extra memory. Similarly, with α standing for the inverse Ackermann function, we show that any computation that takes O(t(n)) computational steps on an n-processor basic reconfigurable mesh can be performed in O(α(n)t(n)) computational steps on an n-processor Common-CRCW with O(n) extra memory. We also show that some of the lower bounds that we derive are tight by providing matching upper bounds; as an example, we show that n items stored in one row of a mesh with multiple broadcasting can be sorted in O(log n) time and that this is time optimal. The best previously-known algorithm for this problem takes O(log² n) time.

A reconfigurable mesh is a two-dimensional processor array equipped with a reconfigurable bus system that can be changed dynamically to suit different computational needs. In this paper we present a parallel algorithm for the summation of N numbers each in the range [0, 2^b). The algorithm runs in O(b+log log N) time on reconfigurable mesh. This is an improvement over the best previously known algorithm that solves the same problem in O(b log log N) time. The algorithm is finally extended to compute the prefix sums of the given numbers in the same time.

We show that the Largest Empty Rectangle problem can be solved by reducing it, in a natural way, to the All Nearest Smaller Values problem. We provide two classes of algorithms: the first one assumes that the input points are available sorted by x (resp. y) coordinate. Our algorithm corresponding to this case runs in O(log log n) time using processors in the Common-CRCW-PRAM model. For unsorted input, we present algorithms that run in time using processors in the Common-CRCW-PRAM, or in O(log n) time using processors in the EREW-PRAM model. No sub-logarithmic time parallel algorithms have been previously reported for this problem.

This paper presents a sequential traversal of a network in an environment with crash-failures. This communication primitive is basic and may be used to solve easily many problems like identification, termination detection, and agreement, etc. Contrary to a possible intuition, this primitive is non-trivial since crash-failures involve tricky problems. Moreover, the implementation proposed in this paper is optimistic in the sense that, in the absence of fault, it is as efficient as the underlying non-fault-tolerant one.

The intention of the paper is to study prime event structures as models of nondeterministic processes. We characterize and examine some properties known as discreteness, density and crossing which allow inconsistency to be avoided between syntactic and semantic representations of processes. A number of close relationships between density and crossing properties of the chosen class of event structures are shown.