Parallel Processing Letters

In the construction of algorithms for optimization problems the Branch-and-Bound paradigm is an essential tool. Furthermore, Branch-and-Bound algorithms are traditionally regarded as well suited for parallel implementation due to the subdivision of the problem considered into essentially independent subproblems. In this paper we present experimental results for a Branch-and-Bound algorithm for the Graph Partitioning Problem showing that the traditional parallelization of a Branch-and-Bound algorithm does not always lead to an efficient parallel algorithm. The main reason seems to be lack of meaningful work, i.e. concurrent existence of subproblems which have to be solved to ensure optimality of the solution. We support this claim with experimental results.

An asynchronous, CRCW PRAM (or APRAM) algorithm for linked list ranking, proposed by Martel and Subramonian, performs EO(n log log n) expected work employing processors. Motivated by their unique approach, this paper proposes two EREW list ranking algorithms – one deterministic and the other randomized. The deterministic algorithm performs in time using p processors, where n≥p log p. Thus, for p=O(n/log n), it requires O(log n log log n) time and O(n log log n) work. Although not work-optimal, this algorithm is very simple compared to the known work-optimal (deterministic) EREW algorithms for list ranking and has the added advantage of small constant factors in the time and space requirements. The randomized algorithm follows the same line of approach, but uses randomization in one step to decrease the time complexity, thus improving on the time complexity of the original algorithm. It requires expected time, and hence it is an EO(log n) expected time, work-optimal algorithm employing p=O(n/log n) processors. Furthermore, the randomized algorithm uses less space than the deterministic algorithm.

In this paper we present a randomized parallel algorithm for finding the connected components of a random input graph with n vertices in which the edges are chosen with probability p such that . The algorithm has O(log² n) expected time using only O(n) processors on the EREW PRAM model. The probability that the output of our algorithm is correct is at least 1–0.6^k, where k is a constant.

We present a parallel algorithm for the Concave Least Weight Subsequence (CLWS) problem that exhibits the following work-time trade-off: Given a parameter p, the algorithm runs in time using p processors. By a known reduction of the Huffman Tree problem to the CLWS problem, we obtain the same complexity bounds for the Huffman Tree problem. However, as we show, for the later problem there exists a simpler (and, in fact, slightly better) algorithm that exhibits a similar trade-off: Namely, for a given parameter p, p≥1, the algorithm runs in time using p processors.

An efficient Hough transform algorithm on a reconfigurable mesh is proposed in this paper. For a problem with N edge pixels and an n×n parameter space, our algorithm runs in constant time on a 4-dimensional N×log²N×n×n reconfigurable mesh. The previous best algorithm for the same problem runs in a constant time on a 4-dimensional n×N×N×N reconfigurable mesh. Since n is always smaller than N in real world (in fact, n is in the order of N^1/2), our algorithm reduces the number of processors used drastically while keeping the same time complexity.

A partitioning algorithm for solving tridiagonal system of linear equations which is suitable for implementation on multiprocessor systems with small to moderate number of processors is described in this paper. The method is based on decomposing a matrix of order n×n into p partitions of size n×k, where n=pk. The fundamental idea of the proposed algorithm is that the elimination is performed using alternatively superdiagonal and subdiagonal elements, contrary to the Gaussian elimination which uses main diagonal elements. Performance results obtained when the proposed algorithm is implemented on the p-processor orthogonal and linear arrays, both of MIMD type, are presented.

A self-stabilizing algorithm for the shortest paths problem in distributed systems is proposed. The proposed algorithm runs on systems with a fully distributed demon.

Given a sequence of m items α₁, α₂,…, α_m from a semigroup S with an associative operation ⊕, the semigroup computation problem involves computing α₁ ⊕ α₂ ⊕…⊕ α_m. We consider the semigroup computation problem involving m (2≤m≤n) items on a mesh with multiple broadcasting of size . Our contribution is to present the first lower bound and the first time-optimal algorithm which apply to the entire range of m (2≤m≤n). Specifically, we show that any algorithm that solves the semigroup computation problem must take Ω(log m) time if and time for . We then show that our bound is tight by designing an algorithm whose running time matches the lower bound. These results unify and generalize all semigroup lower bounds and algorithms known to the authors.

An external watchman route in the presence of a polygonal obstacle is a closed path such that each point in the exterior of the polygon is visible to some point along the route. We adapt the merging slopes technique of parallel computational geometry to develop a parallel algorithm for computing a shortest external watchman route in the presence of a convex polygon of n sides. The algorithm runs in O(log n) time using processors in the CREW-PRAM computational model; this is optimal within a constant factor. The algorithm can be easily adapted to compute a shortest watchman route in O(log n) time on a hypercube with O(n) processors. We also discuss the computation of a shortest external watchman route on star and pancake networks. Finally, a constant time algorithm for solving the merging slopes problem on a BSR with n processors is described. This leads to algorithms with the same time and processor count for solving the external watchman route problem, for computing Minkowski sum, critical support lines, and separability of two convex polygons, for finding the maximum distance between two convex polygons, and for computing the smallest enclosing box, diameter, and width of a convex polygon.

Parallel Join algorithms partition the workload into buckets and assign each bucket to a node of the multiprocessor system. The existing algorithms use the volume of the load as a metric to determine the bucket boundaries. When the input relations exhibit a high degree of skew, the above metric does not achieve uniform partitioning. We propose a new method to partition the workload of the Join operation that guarantees near equal execution time of the created buckets. We present results obtained from the Intel 1860 hypercube system that support our theory.

This paper presents a VLSI array for labeling the connected components of a graph on N nodes in O(r) steps using a reconfigurable bus of width m bits, such that and 1≤r≤m. The network architecture consists of an array of simple logic nodes which are connected by a reconfigurable bus. To solve a problem on N nodes, the array uses N processors and N(N−1)/2 switches. The proposed connectivity and transitive closure algorithms are based on a processor indexing scheme which employs constant-weight codes. It is shown that when r is a constant, then the algorithm takes O(1) time using a bus of width O(N^1/r), and when r=[log N/ loglog N], the algorithm takes O(log N/ loglog N) time using a bus of width O(log N) bits.

The class of problems solved within given time and processor bounds on a Parallel Random Access Machine (PRAM) varies with the instruction set. Previous research has classified the contributions of various instructions, such as multiplication, shifts, and string manipulation operations, to the PRAM. This paper examines the significant contribution of Boolean operations, which play essential roles in many PRAM algorithms and in simulations by the PRAM of other models of computation.

Fault-tolerant systems aim at providing continuous operations in the presence of faults. Multicomputers rely on an interconnection network between processors to support the message-passing mechanism. Therefore, the reliability of the interconnection network is very important for the reliability of the whole system.

This paper analyses the effective redundancy available in a wormhole network by combining connectivity and deadlock freedom. Redundancy is defined at the channel level, giving a sufficient condition for a channel to be redundant and computing the set of redundant channels. The redundancy level of the network is also defined, proposing a theorem that supplies a lower bound for it. Finally, a fault-tolerant routing algorithm based on the former theory is proposed.

The diffusion method is a simple distributed load balancing method for distributed memory multiprocessors. It operates in a relaxation fashion for point-to-point networks. Its convergence to the balanced state relies on the value of a parameter—the diffusion parameter. An optimal diffusion parameter would lead to the fastest convergence of the method. Previous results on optimal parameters have existed for the k-ary n-cube and the torus. In this paper, we derive optimal diffusion parameters for mesh networks.

The fast progress of large integration technology has made distributed computing economically attractive for many computer applications. Task allocation is one of the most important and challenging problems in distributed computing systems that has received considerable attention in recent years. Several researchers have introduced different heuristics to solve this problem with the assumption that it is computationally intractable. These researchers have been referring to an early work by Stone and some private communication as their sources of the problem’s intractability. However, neither Stone’s paper nor any other related work in the literature provided a formal proof of intractability. Due to the importance of the task allocation problem, we believe that a formal proof of its complexity must be provided. In this paper we provide a proof that the problem of task allocation is intractable even in the restricted case when there are only two values of the the communication cost: zero or one. We introduce a new model to represent the problem of allocating tasks on heterogeneous distributed systems using split graphs. This model allows us to relate the task allocation problem with the problem of weighted clique partitioning in complete split graphs. We provide a two-step reduction method to prove the intractability of task allocation in the restricted case mentioned above. In the first step, we prove that the problem of weighted clique partitioning in complete split graph is NP-complete using a transformation from the problem of partition into triangles. In the second step, we show that the task allocation problem is NP-complete using a transformation from the weighted clique partitioning problem.

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.

Term rewriting is a popular computational paradigm for symbolic computations such as formula manipulation, theorem proving and implementations of nonprocedural programming languages. In rewriting, the most demanding operation is repeated simplification of terms by pattern matching them against rewrite rules. We describe a parallel architecture, R²M, for accelerating this operation. R²M can operate either as a stand-alone processor using its own memory or as a backend device attached to a host using the host’s main memory. R²M uses only a fixed number (independent of input size) of processing units and fixed capacity auxiliary memory units, yet it is capable of handling variable-size rewrite rules that change during simplification. This is made possible by a simple and reconfigurable interconnection present in R²M. Finally, R²M uses a hybrid scheme that combines the ease, and efficiency of parallel pattern matching using the tree representation of terms, and the naturalness of their dag representation for replacements.

We present a very simple new distributed algorithm for the classical Dining Philosophers problem.

Our algorithm is the first algorithm with the following important properties:

(1) It is fully distributed; i.e., there is no central memory or central process to which every other process may have access.

(2) It is symmetric; i.e., all processes behave identically, and do not use any process identifiers.

(3) It has a response time ≤ 3ℓ, independent of the size of the ring, where ℓ is an upper bound on the time a resource may be used by a process. Moreover, we establish the optimality of our algorithm with respect to this last measure by proving that no distributed algorithm can guarantee a response time less than 3ℓ.