Parallel Processing Letters

In this work we address the parallel complexity of two combinatorial problems, specifically the problems of the existence and of the construction of a parity base of preassigned weight (exact parity base for short) in a 0-1 weighted, represented matroid, subject to parity conditions. We prove that these problems lie in the parallel complexity class RNC², i.e. they are solvable with one-sided error by a logspace uniform family of bounded fan-in circuits of polynomial size and quadratic logarithmic depth which receive, in addition to the problem input, a polynomial number of random input bits. We also show that the more general cases of these problems, defined over matroids weighted with integral instead of 0-1 weights, also belong to RNC², as long as the weights are given in unary notation. As a consequence some special cases of these problems, which are of independent interest, belong to the same parallel complexity class: examples of these are the problem of the construction of a perfect matching of preassigned weight in a 0-1 weighted graph, recently addressed in [1], or that of the construction of a base of preassigned weight, in the intersection of two 0-1 weighted represented matroids.

We study parallel solutions to the problem of implementing priority queues and priority deques. It is known that data structures for the implementation (e.g. the heap, the min-max heap, and the deap) can be constructed in linear sequential time. In this paper, we design optimal Θ((log log n)²) time parallel algorithms with processors for the constructions in the parallel comparison tree model.

In this paper, we present an algorithm for a generalization of list ranking called computation list evaluation. As a consequence of the generalization and the existence of this algorithm for computation list evaluation, we obtain a generalization of Euler Tour technique. Finally, we present several applications of the generalized Euler Tour technique. Of interest in the applications is the identification of a set of problem instances that are solvable using tree contraction and which can alternatively be solved using a simple algorithm based on the generalized Euler Tour technique.

The Euclidean Distance Transform is an important, but computationally expensive, technique of computational geometry, with applications in many areas including image processing, graphics and pattern recognition. Since the data sets used are typically large, one might hope that parallel computers would be suitable for its determination. We show that existing parallel algorithms perform poorly on certain data sets and introduce new strategies. These achieve high speed on diverse data sets, but fail occasionally in pathological cases. We determine the maximum error in such cases and demonstrate that it is satisfactorily low. Although adequate efficiency is achievable on SIMD machines, we demonstrate that problems of this kind are data parallel yet best suited to MIMD architectures.

Two deterministic selection algorithms on an n × n mesh-connected processor array are developed. The model of computation is restricted in the following sense: at every step each processor buffers exactly one of the original keys, and every one of the original keys is buffered by a processor. The first algorithm operates in time 2.5n + o(n). It is a general selection algorithm, that is, its complexity bound does not depend on the rank of the element searched for. The second algorithm has its time bound depending on the rank of the item sought. This bound is , where the rank is x²n². This algorithm is superior to the previous one for approximately 10% of the smallest and 10% of the largest keys.

In previous papers, we have developed the theoretical background for the design of deadlock-free adaptive routing algorithms for store-and-forward and wormhole networks. Some definitions and theorems have been proposed, developing conditions to verify that an adaptive algorithm is deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies have been proposed.

In this paper, we propose a partial order between channels as well as an equivalence relation. This relation splits the set of channels into equivalence classes. Then, we extend our previous theory by considering equivalence classes (channel classes) instead of channels. This extension drastically simplifies the verification of deadlock freedom for adaptive routing algorithms with cyclic dependencies between channels. Finally, we present an example.

One node of a communication network holds a message which should reach all other nodes. In a unit of time a node can communicate with all neighbors but some transmissions may be faulty. In the model which assumes a bounded number of failures per time unit, all nodes must get the message for any location of faults, while for random independent failures the goal is to reach all nodes with high probability, for large networks. We establish relations between the number of links in networks and the time of fault-tolerant broadcasting.

We propose a new scheduling algorithm for a three-dimensional grid precedence graph of size n, and we prove that the communication overhead is just in Θ(log log n). Finally, we show that a lower bound for the overhead of any schedule with a fixed number of processors (p ≥ 3) is Ω(log log n).

In this paper, we propose a general method for mapping Affine Recurrence Equations (ARE's) on a Multi-Rate Array (MRA). We show that the mapping is valid if and only if it maps the problem domain on the null space of the matrix (D − I) along the range space of this matrix (D is the dependency matrix, I is the identity matrix). We also prove that in the resulting array, variables are flowing at different speeds.

In this paper, a Parallel Genetic Algorithm has been developed and mapped onto a coarse grain MIMD multicomputer whose processors have been configured in a fully connected chordal ring topology. In this way, parallel diffusion processes of good local information among processors have been carried out. The Parallel Genetic Algorithm has been applied, specifically, to the Travelling Salesman Problem. Many experiments have been performed with different combinations of genetic operators; the test results suggest that PMX crossover can be avoided by using only the inversion genetic operator and that a diffusion process leads to improved search in Parallel Genetic Algorithms.

Shared memory multiprocessor systems need efficient dynamic storage allocators, both for system purposes and to support parallel programs. Memory managers are often based on the buddy system, which provides fast allocation and release. Previous parallel buddy memory managers made no attempt to coordinate the allocation, splitting and release of blocks, and as a result needlessly fragment memory. We present a fast and simple parallel buddy memory manager that is also as space efficient as a serial buddy memory manager. We test our algorithms using memory allocation/deallocation traces collected from a parallel sparse matrix algorithm.