Parallel Processing Letters

Tree open ear decomposition has been proposed as a potentially useful technique in parallel graph algorithms. We present an efficient parallel algorithm implementing depth-first search in a graph, given its tree open ear decomposition. The algorithm runs in O(log n) time with O(m) processors on the CREW PRAM, where m is the number of edges in the graph. We also show that the problem of computing such a decomposition is NP-complete, demonstrating the limited utility of the technique.

We investigate the problem of permuting n data items on an EREW PRAM with p processors using little additional storage. We present a simple algorithm with run time O((n/p)log n) and an improved algorithm with run time O(n/p + log n log log(n/p)). Both algorithms require n additional global bits and O(1) local storage per processor. If prefix summation is supported at the instruction level, the run time of the improved algorithm is O(n/p). The algorithms can be used to rehash the address space of a PRAM emulation.

We consider the problem of sorting an input of size n² with keys restricted to the set {0, 1} on an n × n mesh-connected computer. We present a deterministic algorithm that sorts to an arbitrary indexing scheme, using constant size queues, requiring 2.5n + o(n) steps. This is a significant improvement over the best previous algorithm for this problem which runs in 4n + o(n) steps [7], The problem has applications in divide-and-conquer algorithms and to "packing" problems.

In this paper, we make efficient use of asynchronous communications on the LU decomposition algorithm with pivoting and a column-scattered data decomposition to derive precise computational complexities. We then compare these results with experiments on the Intel iPSC/860 and Paragon machines and show that very good performances can be obtained on a ring with asynchronous communications.

We present an implementation of Global-Flush Primitives using counters. This implementation costs comparable to the most lightweight implementation of causal ordering. Thus, at a comparable cost, the presented implementation enriches functionality compared to causal ordering; as Global-Flush Primitives permit making an assertion about messages sent in the past of sending m, in the future of sending m, about both, or neither, where the past and the future of an event is defined using the relation "happened before." Using Global-Flush, a message can be sent to any subset of processes specified as a parameter.

The Bird-Meetens formalism is an approach to software development and computation based on datatype theories. In this paper we build new operators for the theory of lists that compute generalized recurrences and show that they have logarithmic parallel time complexity. As many applications can be cast as forms of recurrences, this allows a large range of parallel algorithms to be derived within the Bird-Meertens formalism. We illustrate by deriving a parallel solution to the maximum segment sum problem.

We review the use of the Bird-Meertens Formalism as a vehicle for the construction of programs with massive implicit parallelism. We show that a simple result from the theory, concerning the expression of list homomorphisms, can help us in our search for parallel algorithms by suggesting an informal methodology which is applicable when the original result is not, and demonstrate its application to a variety of problems. One of these, a language recognition algorithm, produces a program which exploits nested parallelism. Our main purpose is to show that an understanding of the homomorphism lemma can be helpful in producing parallel programs for problems which are "not quite" list homomorphisms themselves. A more general goal is to illustrate the benefits which can arise from taking a little theory with a pinch of pragmatic salt.

The Euclidean Distance Transform is an important computational tool for the processing of binary images, with applications in many areas such as computer vision, pattern recognition and robotics. We investigate the properties of this transform and describe an O(n²) time optimal sequential algorithm. A deterministic EREW-PRAM parallel algorithm which runs in O(log n) time using O(n²) processors and O(n²) space is also derived. Further, a cost optimal randomized parallel algorithm which runs within the same time bounds with high probability, is given.

We consider the problem of broadcasting on an n-dimensional hypercube with wormhole e-cube routing, intermediate reception capability, and one-port communication. We give an algorithm, optimal to within a multiplicative constant, that broadcasts in this model in Θ(n/log₂(n+1)) routing steps. We also give routing algorithms that achieve tight time bounds for n-cubes where n ≤ 6.

The fundamental problem of minimum computation has several well-studied generalizations such as prefix minima, range minima, and all nearest smaller values computations. Recent papers introduced parallel algorithms for these problems when the n input elements are given from an integer domain [1..s], obtaining O(lglglgs) running time and linear work for s ≥ n. However, most of these algorithms have the running time of O(lglglgn) (rather than O(lglglgs)) for all values of s ≤ n, except for the case of s = O(1) in which case the running time is O(α(n)). In this paper we focus on the range s ≤ n and provide linear-work algorithms whose running time O(lglglgs + f(n)) is for all s ≥ 0, where f(n) is either one of the slow growing functions lg*n or α(n). We show how to generalize our algorithms to the case that the domain size s is unknown, with the same complexities. (All previous algorithms work only under the assumption that the domain size s is known.) Moreover, we make our algorithms output-sensitive with the lglglgs term replaced by lglglgM, where M is the maximum input value. In fact, for the minimum computation problem the running time is O(lglglgm) for all s ≥ 0, where m is the minimum input value.

Quadtree data structure, popular in 2-D applications, has not been studied in the context of VLSI embedding. This paper proposes two generic layout strategies for quadtree layout. Layout attributes are derived with primary focus on area-I/O trade-off. We demonstrate a simple layout mixing strategy to obtain improved boundary I/O characteristics. This is followed by development of a recursive layout mixing strategy which yields an order of improvement.

This paper introduces the family of scalable multifolded hypercube (SMH) architectures for parallel computers. Scalability and versatility at resonable cost are the major characteristics of these architectures. SMHs perform comparable to generalized hypercubes for important classes of algorithms that use regular communication patterns. In addition, they often achieve better performance than the popular direct binary hypercubes because they can emulate efficiently a powerful family of multifolded direct binary hypercubes. Extensive comparison of cost with binary and generalized hypercubes is also included. The hardware cost of SMH's is shown to be even lower than that of fat trees. Therefore, SMH's are viable candidates for the construction of versatile parallel computers.

We present a shift register-based systolic array for a class of recurrences, with dynamic dependencies called knapsack problem recurrences. All previous arrays or parallel implementations led to either low efficiency or to complicated control. To the best of our knowledge, the proposed design is the first realistic pure systolic and optimal array for this pseudo-polynomial, NP-hard problem. The key feature of the array is that it requires almost no control circuitry.

Presented is a parallel algorithm based on the fast multipole method (FMM) for the Helmholtz equation. This variant of the FMM is useful for computing radar cross sections and antenna radiation patterns. The FMM decomposes the impedance matrix into sparse components, reducing the operation count of the matrix-vector multiplication in iterative solvers to O(N^3/2) (where N is the number of unknowns). The parallel algorithm divides the problem into groups and assigns the computation involved with each group to a processor node. Careful consideration is given to the communications costs. A time complexity analysis of the algorithm is presented and compared with empirical results from a Paragon XP/S running the lightweight Sandia/University of New Mexico operating system (SUNMOS). For a 90,000 unknown problem running on 60 nodes, the sparse representation fits in memory and the algorithm computes the matrix-vector product in 1.26 seconds. It sustains an aggregate rate of 1.4 Gflop/s. The corresponding dense matrix would occupy over 100 Gbytes and, assuming that I/O is free, would require on the order of 50 seconds to form the matrix-vector product.

For circuits the expected delay is a suitable measure for the average case time complexity. In this paper, new upper and lower bounds on the expected delay of circuits for disjunction and conjunction are derived. The circuits presented yield asymptotically optimal expected delay for a wide class of distributions on the inputs even when the parameters of the distribution are not known in advance.

We address the problem of performing a pipelined broadcast on a mesh architecture. Meshes require a different approach than other topologies, and their very nature puts a tighter bound on the performance that one can hope to achieve. By using the appropriate techniques, however, one can obtain excellent performance for sufficiently long messages. The resulting algorithm will work on meshes of any dimension with any number of nodes. Our model assumes that the mesh is a torus and/or that it has bidirectional links and uses wormhole routing. Performance data from the Cray T3D are included.

We prove that the sequential approximation algorithms for the problems and proposed in [9] are -hard with respect to the logarithmic space reducibility. As a corollary, these two algorithms cannot be implemented efficiently in parallel unless .

We investigate parallel algorithms to compute recursively defined functions. Our computational model are parallel random access machines (PRAM's). We preferably make use of the OROW-PRAM (owner read, owner write), a model supposed to be even weaker and more realistic than the EREW-PRAM (exclusive read, exclusive write) and that still provides the opportunities of a completely connected processor network. For OROW-PRAM's we show that our parallel algorithms are work-optimal.

A parallel algorithm exhibits a fixed-processor communication-time tradeoff if lower bounds on communication and time cannot be simultaneously realized by any schedule using p processors. For unrestricted schedules, lower bounds on communication are trivial, so all researchers in this area have made assumptions about what kinds of schedules to consider. The usual restriction is that all processors perform approximately equal work. The problem with this restriction is that it can overstate the number of processors that are needed to realize the claimed time and communication bounds. Since the communication and time bounds are expressed as a function of p, using an inflated value for p can lead us to believe that there is a tradeoff when none exists. In this paper we reexamine previously published communication results for several algorithms and show that the existence of tradeoffs is still an open question. We also introduce the concept of effective schedules, and argue that both tight communication bounds and fixed-processor communication-time tradeoffs are only meaningful for effective schedules.

The spanning binomial tree is one of most frequently used spanning tree structures to implement various parallel applications in multiprocessor systems, such as hypercubes. In this paper, we define an l-node as a root node of an incomplete spanning binomial tree of a hypercube, which is defined as a connected subtree of a spanning binomial tree with the same root node that connects all the nonfaulty nodes in the hypercube. We show that in an n-dimensional hypercube with m faulty nodes there are at least 2ⁿ − 2^ml-nodes. This implies that at least half of the nodes of the hypercube are l-nodes if the number of faulty nodes is less than the dimension of the hypercube.