Parallel Processing Letters

Reconfigurability is a desirable characteristic in parallel computer architecture that supports the structural parallelism inherent to multiple parallel algorithms. This paper presents a novel approach to achieve reconfigurability via a multiple-domain wavelength-division multiplexed optical interconnection network. A network structure is defined to host a set of point-to-point guest interconnection topologies. Fast complete reconfiguration takes place by re-labeling node identifiers and re-tuning receiver filters according to a local table at each node. For a network of size N, the connecting fiber complexity is O(N), the same order of the link complexities of the individual topologies. The proposed network avoids the possible edge dilation, congestion, and cumulative switching latencies associated with previously proposed approaches.

The hypercube architecture is a popular topology for many parallel processing applications. For continued operation of the hypercube multiprocessors after the failure of one or more i-subcubes and/or links, fault tolerance by reconfiguration is an important problem. This paper considers the reconfiguration issue and presents an algebraic technique to analyze the problem extending the concepts in [9]. The technique uses algebraic operators to identify the maximum dimensional fault-free subcube, and thus helps in achieving graceful degradation of the system. We analyze the complexity of our algorithm and show that it is efficient as compared to previous algorithms [1, 8, 14].

This paper explores the viability of object migration for massively parallel architectures. The aim is the comparison between global and local perspectives in migration policies. The paper reports several implemented migration algorithms and the performance obtained. The main result is that local migration policies are more viable than global ones as soon as the system size goes up.

It is well known that the nearest-neighbor connections of the mesh (especially the two-dimensional meshes) are very useful in parallel computations. Consequently, it is desirable to show that the graph representing the interconnection network of a parallel computer embeds the mesh. Most existing results of mesh-embedding are only applicable to a single kind of network. Here we demonstrate that a large family of interconnection networks called the generalized Fibonacci cubes all embed the mesh.

The purpose of this short note is to show that the problem of reconstructing a directed forest from a collection of leaf-to-root paths can be done efficiently in parallel by reducing the problem to integer sorting. Specifically, given M the total length of the paths in the collection, and n the number of distinct node labels, our algorithm reconstructs the corresponding forest (if such a forest exists) in O(M/p) time using p ≤ M/n processors or time using M/n < p < M processors, and O(M) space on the EREW-PRAM.

Most recently, multicast communication has been included in multicomputer systems. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. The performance of multicomputers is highly dependent on the message routing scheme and the communication mechanism. Wormhole routing is the most promising switching technique used in the new generation multicomputers. In this paper, we propose a multicast wormhole routing algorithm for 2D-torus multicomputers. The multicast routing algorithm is based on a path-like routing scheme and offers deadlock-free routing. Our simulation which compared the 2D-mesh multicomputers shows that the multipath routing algorithm for 2D-torus multicomputers can reduce the communication traffic and the maximum distance in multicast communication.

We propose a simple and efficient self-stabilizing distributed algorithm to construct the breadth first search (BFS) spanning tree of an arbitrary connected symmetric graph. We develop a completely new direct approach of graph theoretical reasoning to prove the correctness of our algorithm. The approach seems to have potential to have applications in proving correctness of other self-stabilizing algorithms for graph theoretical problems.

A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITY problem is presented. This algorithm runs in O(log²(n + |F|)) parallel time on a CREW PRAM machine using O(n + |F|) processors, where n is the number of variables and |F| is the number of clauses. Performance guarantees are considered for three slightly differing definitions of this problem.

The Different Than Majority Labeling (DTML) problem has a simple polynomial time algorithm, but is not known to be in NC. In this paper, we show that the DTML problem is extremely unlikely to have an NC¹ algorithm.

In this paper, we propose a linear time parallel algorithm (in the number of edges of the transitive closure) that computes the transitive closure of a directed graph on a linear network of n processors. The underlying architecture is a linear network of processors with neighbouring communications, where the number of processors is equal to the number of vertices of the graph.

A new sorting network with exactly the same size and depth as the odd-even sorting network is presented. This sorting network is designed using the zero-one principle, and proceeds by first sorting pairs of bits and then sorting the pairs into lexicographic order.

We consider the following periodic sorting procedure on two-dimensional meshes of processors: Initially, each node contains one number. We proceed in rounds each round consisting of sorting the columns of the grid, and, in the second phase, of sorting the rows according to the snake-like ordering. We exactly characterize the number of rounds necessary to sort on an l × m-grid in the worst case, where l is the number of the rows and m the number of the columns. An upper bound of ⌈ log l⌉ + 1was known before. This bound is tight for the case that m is not a power of 2. Surprisingly, it turns out that far fewer rounds are necessary if m is a power of 2 (and m ≪ l) in this case, exactly min {log m + 1, ⌈ log l⌉ + 1} rounds are needed in the worst case.

This paper deals with the problem of finding the K smallest elements out of a totally ordered but non-sorted set of N elements. This problem, called K-selection, arises often in statistics, image processing and distributed computing. We propose two algorithms to solve this problem in hypercubes. Our first algorithm is asymptotically optimal when K = O((log N)^β), for any constant β. The second enlarges the range of optimality to K = N^∊, ∊ < 1, using a recursive strategy. These are major improvements on previous results.

We describe a simple parallel algorithm for generating all permutations of n elements. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. The algorithm is cost-optimal, assuming the time to output the permutations is counted.

A systolic algorithm is described for generating, in lexicographically ascending order, all combinations of m objects chosen from an arbitrary set of n elements. The algorithm is designed to be executed on a linear array of m processors, each having constant size memory (except processor m, which has O(n) memory), and each being responsible for producing one element of a given combination. There is a constant delay per combination, leading to an O(C(m, n)) time solution, where C(m, n) is the total number of combinations. The algorithm is cost-optimal (assuming the time to output the combinations is counted), and does not deal with very large integers.

We propose time-optimal algorithms for a number of convex polygon problems on meshes with multiple broadcasting. Specifically, we show that on a mesh with multiple broadcasting of size n × n, the task of deciding whether an n-gon is convex, deciding whether two convex n-gons edge-intersect, deciding whether one convex n-gon lies in the interior of another, as well as variants of the tasks of computing the intersection and union of two convex n-gons can be accomplished in Θ(log n) time. We also show that detecting whether two convex n-gons are separable takes O(1) time.

A transputer-based parallel processing paradjgm for real-time extraction of road traffic data from video images of roadway scenes is proposed. The model can monitor three lanes of motorway traffic in real-time by processing images from two windows associated with each lane. Parallel algorithms are distributed among a network of transputers to perform similar and/or different tasks concerning image data analysis and traffic data extraction. The model can be expanded to cover more lanes or duplicated to monitor a further multi-lane carriageway.

Speculative parallelism is the parallelism that one finds when parallel tasks are spawned in the hope that they will later be of use. While this aggressive form of parallelism promises high levels of parallelism, there are numerous problems involved. In this letter, we propose a model of handling speculative parallelism in Lisp. Some properties of the model, related issues in parallelism and implementation considerations are also discussed. The model described is already incorporated into BaLinda Lisp and the techniques used in its simulation were first used in writing the prototype interpreter on an IBM PC.

The parallelization of loops can be made formal by basing it on an algebraic theory of loop transformations. In this theory, the concept of unimodularity arises. We discuss the pros and cons of insisting on unimodularity.

In this paper, we present an algorithm to achieve mutual exclusion in distributed systems. Our algorithm tolerates up to t − 1 arbitrary node failures without executing any recovery procedure and requires messages in a network of n nodes.

A number of approaches to asynchronous communication in parallel programs based on both data dependence analysis and buffering techniques are briefly described. A criterion for automatically resolving some classes of deadlocks by means of asynchronous data exchanges is established and examples showing the comparative power of the approaches for deadlock avoidance are presented.