Optimal algorithms are given for matrix multiplication and problems involving graphs and mazes, where calculations are done in 3-dimensional space. Whatever the technology is, a bit requires a minimum volume and communication travels at a bounded speed. Thus multiplying n × n matrices over a ring takes Ω(n2/3) time, and we show that this can be achieved by a 3-d mesh of n2 processors. No previous algorithms fully considered the implications of volume and bounded communication speed. Multiplication of matrices not over a ring requires only Θ(n3/4) time by expanding to a larger mesh. In 2-d (such as the surface of a chip) this approach is useless and Θ(n) systolic algorithms are optimal. For path and maze problems there are approaches useful in 3-d but not 2-d.

We give efficient algorithms to solve fundamental data movement problems on mesh-connected computers augmented with limited global bandwidth. Adding a small amount of global bandwidth makes a practical design that combines aspects of mesh and fully connected models to achieve the benefits of each. We give algorithms for sorting, finding the median, finding a spanning tree, and determining various graph properties to show that the small amount of global communication can significantly reduce the time, and that concurrent read helps even more. Most of these algorithms are optimal. We also extend our results to mesh-connected computers with row and column buses.

In this paper we combine aspects of the PRAM and mesh models to achieve the benefits of each. Many fast algorithms are known for the PRAM, but it is unrealistic to build. Another well-known model is the 2-dimensional mesh, of which many have been built, but the algorithms are constrained by the mesh's diameter and bisection bandwidth, forcing algorithms for nontrivial problems to take time which is at least the square root of the number of processors. Here we use a minuscule amount of shared memory to make a practical design which is significantly faster than the standard mesh. We call this the shared memory mesh. We give several algorithms which show that a small amount of shared memory can significantly reduce the time for problems such as finding the median, labeling the connected components of an image, and labeling the connected components of a graph. Further, we show that many of these algorithms are optimal.

We describe a program that automatically generates a hybrid OpenMP + MPI program for a class of recursive calculations with template dependencies. Many useful generalized dynamic programming problems fit this category, such as Multiple String Alignment and multi-arm Bernoulli Bandit problems. Solving problems like these, especially those involving several dimensions, can use a significant amount of memory and time. Our generator addresses these issues by dividing the problem into many tiles that can be solved in parallel. Programs generated using this program generator are capable of solving large problems and achieve good scalability when run on many cores. The input supplied to the generator is a high level description of the problem, the output is a fully functioning parallel program for a cluster of shared memory nodes. This high level approach to parallel computation allows the generator to have a large amount of control over memory allocation, load balancing and calculation ordering.

Synchronization is often necessary in parallel computing, but it can create delays whenever the receiving processor is idle, waiting for the information to arrive. This is especially true for barrier, or global, synchronization, in which every processor must synchronize with every other processor. Nonetheless, barriers are the only form of synchronization explicitly supplied in OpenMP, and they occur whenever collective communication operations are used in MPI. Many applications do not actually require global synchronization; local synchronization, in which a processor synchronizes only with those processors from or to which information or resources are needed, is often adequate. However, when tasks take varying amounts of time, the behavior of a system under local synchronization is more difficult to analyze since processors do not start tasks at the same time. We show that when the synchronization dependencies form a directed cycle and the task times are geometrically distributed with $p=0.5$, then as the number of processors tends to infinity the processors are working $2-\sqrt{2}\approx0.59\%$ of the time. Under global synchronization, however, the time to complete each task is unbounded, increasing logarithmically with the number of processors. Similar results apply for $p\neq0.5$. We also present some of the combinatorial properties of the synchronization problem with geometrically distributed tasks on an undirected cycle. Nondeterministic synchronization is also examined, where processors decide randomly at the beginning of each task which neighbors(s) to synchronize with. We show that the expected number of task dependencies for random synchronization on an undirected cycle is the same as for deterministic synchronization on a directed cycle. Simulations are included to extend the analytic results. They show that more heavy-tailed distributions can actually create fewer delays than less heavy-tailed ones if the number of processors is small for some random-neighbor synchronization models. The results also show the rate of convergence to the steady state for various task distributions and synchronization graphs.

This tutorial provides a comprehensive overview of parallel computing, emphasizing those aspects most relevant to the user. It is suitable for new users, managers, students and anyone seeking an overview of parallel computing. It discusses software and hardware, with an emphasis on standards, portability, and systems that are widely available.The tutorial surveys basic parallel computing concepts, using examples selected from large-scale engineering and scientific problems. These examples illustrate using MPI on distributed memory systems, Globus on the grid, OpenMP on shared memory systems, and MPI+OpenMP on hybrid systems. It discusses numerous parallelization approaches, and software engineering and performance improvement aspects, including the use of state-of-the-art tools.The tutorial helps attendees make intelligent decisions by covering the primary options that are available, explaining how they are used and what they are most suitable for. Extensive pointers to the literature and web-based resources are provided to facilitate follow-up studies.

Synchronization is often necessary in parallel computing, but it can create delays whenever the receiving processor is idle, waiting for the information to arrive. This is especially true for barrier, or global, synchronization, in which every processor must synchronize with every other processor. Nonetheless, barriers are the only form of synchronization explicitly supplied in MPI and OpenMP.Many applications do not actually require global synchronization; local synchronization, in which a processor synchronizes only with those processors from which it has an incoming edge in some directed graph, is often adequate. However, the behavior of a system under local synchronization is more difficult to analyze, since processors do not all start tasks at the same time.In this paper, we show that if the synchronization graph is a directed cycle and the task times are geometrically distributed with p = 0.5, the time it takes for a processor to complete a task, including synchronization time, approaches an exact limit of 2 + √2 as the number of processors in the cycle approaches infinity. Under global synchronization, however, the time is unbounded, increasing logarithmically with the number of processors. Similar results also apply for p ≠ 0.5.We give a new proof of the constant upper bounds that apply when tasks are normally distributed and the synchronization graph is any graph of bounded degree. We also prove that for some power-law distributions on the tasks, there is no constant upper bound as the number of processors increases, even for the directed cycle. Finally, we show that constant upper bounds apply for some cases of a different synchronization model in which a processor waits for only a subset of its neighbors.

We are interested in minimizing peak energy usage, an important factor in systems where power is supplied externally, such as chips and circuit boards. The goal is to reduce peak energy without increasing the time required, and as a byproduct to also reduce the total enery. Algorithms for meshconnected computers are developed for problems involving images and graphs. We can also simultaneously reduce the total energy used by any processor, an important factor in sensor networks.

We present a scalable, high-performance solution to multidimensional recurrences that arise in adaptive statistical designs. Adaptive designs are an important class of learning algorithms for a stochastic environment, and we focus on the problem of optimally assigning patients to treatments in clinical trials. While adaptive designs have significant ethical and cost advantages, they are rarely utilized because of the complexity of optimizing and analyzing them. Computational challenges include massive memory requirements, few calculations per memory access, and multiply-nested loops with dynamic indices. We analyze the effects of various parallelization options, and while standard approaches do not work well, with effort an efficient, highly scalable program can be developed. This allows us to solve problems thousands of times more complex than those solved previously, which helps make adaptive designs practical. Further, our work applies to many other problems involving neighbor recurrences, such as generalized string matching.

One of the ways that the Sun interacts with the Earth is through the solar wind, which is an ionized multi-component fluid that emanates from the Sun and travels radially outward at hundreds of kilometers per second. Solar-wind transients, such as Coronal Mass Ejections (CME's), can be particularly important. In rare cases, CME's have affected the lower atmosphere of the Earth, causing regional power-grid failures. More regularly, CME's pose threats to satellites and spacecraft. Due to the extreme range of temporal and spatial scales involved in solar-wind phenomena, it had previously been impossible to predict CME propagation to Earth with faster-than-real-time, well-resolved calculations. Our team has now developed a highly scalable solution-adaptive scheme for predicting CME propagation. The solution-adaptive technique is an adaptive mesh refinement (AMR) scheme for magneto- hydrodynamic (MHD) calculations. The physical domain is decomposed into three- dimensional blocks, where each block forms a regular grid. In regions of relatively high gradients, blocks are successively refined. Blocks are distributed to processors, with communication between neighboring blocks is handled by asynchronous message passing. The benchmark calculation achieved 212 Gflops on a 1024-processor Cray T3E-1200, with the grid adapting over the course of the calculation from 2048 blocks to 11,729 blocks, where each block was composed of 10x10x10 cells. On a 512-processor Cray T3E-600, our benchmark simulations were performed 16 times faster than real time.

We examine a data structure which uses flexible "adaptivity" to obtain high performance for both serial and parallel computers. The data structure is an adaptive grid which partitions a given region into regular cells. Its closest relatives are cell-based tree decompositions, but there are several important differences which lead to significant performance advantages. Using this block data structure to support adaptive mesh refinement (AMR), we were able to sustain 17 GFLOPS in ideal magnetohydrodynamic (MHD) simulations of the solar wind emanating from the base of the solar corona, using a 512 processor Cray T3D at NASA Goddard.

We give tight bounds on the parallel complexity of some problems involving random graphs.Specifically, we show that a Hamiltonian cycle, a breadth first spanning tree, and a maximal matching can all be constructed in ~(log" n) expected time using n/ log* n processors on the CRCW PRAM.This is a substantial improvement over the best previous algorithms, which required @((log log n)2) time and n log2 n processors.We then introduce a technique which allows us to prove that constructing an edge cover of a random graph from its adjacency matrix requires Q(log' n) expected time on a CRCW PRAM with O(n) processors.Constructing an edge cover is implicit in constructing a spanning tree, a Hamiltonian cycle, and a maximal matching, so this lower bound holds for all these problems, showing that our algorithms are ontimal.This new lower bound techniaue is one .of the very few lower bound techniques known which apply to randomized CRCW PRAM algorithms, and it provides the first nontrivial parallel lower bounds for these problems.

The mesh with reconfigurable bus is presented as a model of computation. The reconfigurable mesh captures salient features from a variety of sources, including the CAAPP, CHiP, polymorphic-torus network, and bus automation. It consists of an array of processors interconnected by a reconfigurable bus system that can be used to dynamically obtain various interconnection patterns between the processors. A variety of fundamental data-movement operations for the reconfigurable mesh are introduced. Based on these operations, algorithms that are efficient for solving a variety of problems involving graphs and digitized images are also introduced. The algorithms are asymptotically superior to those previously obtained for the aforementioned reconfigurable architectures, as well as to those previously obtained for the mesh, the mesh with multiple broadcasting, the mesh with multiple buses, the mesh-of-trees, and the pyramid computer. The power of reconfigurability is illustrated by solving some problems, such as the exclusive OR, more efficiently on the reconfigurable mesh than is possible on the programmable random-access memory (PRAM).>

This paper is a brief introduction to a new class of computers, the reconfigurable massively parallel computer. Its most distinguishing feature is the utilization of the reconfigurability of the interconnection network to establish a network topology well mapped to the algorithm communication graph so that higher efficiency can be achieved, and to remove faulty processors from the network so that the system operation can be kept uninterrupted while maintaining the same or slightly degraded efficiency. Several existing reconfigurable single instruction multiple data (SIMD) parallel architectures and their reconfiguration mechanism are described, the effectiveness of algorithm mapping, through reconfiguration, is demonstrated, and fault-tolerant schemes via reconfiguration are discussed.>

No abstract available.

Seymour, a high-level data parallel programming language that can be used to design, express, and implement efficient portable parallel algorithms, is introduced. Seymour is based on the approach of designing parallel algorithms based on standardized global operations such as prefix, broadcast, sort, compression, and associative read. Seymour also incorporates fundamental paradigms, such as divide-and-conquer, reduce-and-create-cross-product, and reduce-and-compress, which are derived from theoretical parallel algorithms. Seymour redirects the difficulties of portability and efficiency into similar difficulties for the global operations and paradigms. However, the cost of developing efficient implementations of standardized operations on the various target architectures can be amortized over numerous algorithms.>

Asymptotically optimal parallel algorithms are presented for use on a mesh computer to determine several fundamental geometric properties of figures. For example, given multiple figures represented by the Cartesian coordinates of n or fewer planar vertices, distributed one point per processor on a two-dimensional mesh computer with n simple processing elements, Theta (n/sup 1/2/>or=-time algorithms are given for identifying the convex hull and smallest enclosing box of each figure. Given two such figures, a Theta (n/sup 1/2/>or=-time algorithm is given to decide if the two figures are linearly separable. Given n or fewer planar points, Theta (n/sup 1/2/>or=-time algorithms are given to solve the all-nearest neighbor problems for points and for sets of points. Given n or fewer circles, convex figures, hyperplanes, simple polygons, orthogonal polygons, or iso-oriented rectangles, Theta (n/sup 1/2/>or=-time algorithms are given to solve a variety of area and intersection problems. Since any serial computer has worst-case time of Omega (n) when processing n points, these algorithms show that the mesh computer provides significantly better solutions to these problems.>

The authors consider image computations on a mesh with reconfigurable bus (reconfigurable mesh). The architecture consists of an array of processors overlaid with a reconfigurable bus system. The reconfiguration scheme can be used to dynamically obtain various interconnection patterns among the processor elements. The reconfiguration scheme supports several parallel techniques developed on the CRCW PRAM (concurrent read, concurrent write parallel random-access machine) model, leading to asymptotically superior solution times to image problems compared to those on the mesh with multiple broadcasting, the mesh with multiple buses, the mesh-of-trees, and the pyramid computer.>

When an image contains multiple objects of interest simple algorithms try to simultaneously use the apex for each object, creating a severe bottleneck; previous asymptotically efficient algorithms have tended to be quite complicated. A novel approach is presented which systematically simulates a separate 'essential' pyramid over each object. This simplifies algorithm development, since algorithms can be written assuming that there is only a single object. This approach can yield optimal or nearly optimal algorithms for the pyramid computer, and can also be used for many nonpyramid architectures. For several of these, the simulated pyramids over all objects can perform an algorithm nearly as fast as pyramid computer over a single object.>

The authors present a parallel algorithms to identify (i.e., detect and enumerate) the extreme points of the convex hull of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus, EREW PRAM (exclusive read, exclusive write parallel random-access machine) and AKS sorting network. For the situation where the input set of n planar points is given ordered one per processor on a machine with Theta (n) processors, the authors introduce a worst-case hypercube algorithm that finishes in Theta (log n) time, a worst-case algorithm for the pyramid, tree, and mesh-of-trees that finishes in Theta (log/sup 3/ n/log logn)-time, and a worst-case algorithm for the mesh with reconfigurable bus that finishes in Theta (log/sup 2/ n) time. For the situation where the input set is given unordered one per processor, several optimal worst-case algorithms are given. It is shown that the Theta (log n) time hypercube algorithm for ordered data will extend to yield a worst-case optimal EREW PRAM algorithm and AKS sorting network algorithm for the case where the set of planar points is distributed in random fashion one point per processor.>

Some of the problems encountered in mapping a parallel algorithm are examined, emphasizing mappings of vision algorithms onto mesh, hypercube, mesh-of-trees, pyramid, and parallel random-access machines (PRAMs) having many simple processors, each with a small amount of memory. Approaches that have been suggested include simulating the ideal architectures, and using general data movement operations. Each of these is shown to occasionally produce unacceptably inefficient implementations. It appears that as long as PRAMs cannot achieve the desired cost and performance goals, programmers must contend with carefully designing algorithms for specific architectures.>

Parallel algorithms are presented to identify (i.e. detect and enumerate) the extreme points of the convex hull of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus, exclusive-read-exclusive-write parallel random-access machine (EREW PRAM), and modified AKS network. It is shown that the problem of identifying the convex hull for a set of planar points given arbitrarily, cannot be solved faster than sorting.>

Pyramid computers, and more generally pyramid algorithms, for image processing have the advantage of providing regular structure with a base naturally identified with an input image and a logarithmic height that permits rapid reduction of information. It is shown that it is possible to simulate systematically the effect of having a separate, so-called 'essential' pyramid over each object, greatly simplifying algorithm development since algorithms can be written assuming that there is only a single object. This approach can yield optimal or nearly optimal algorithms for the pyramid computer and can also be used on nonpyramid architectures such as the hypercube, mesh-of-trees, mesh, mesh with row and column buses, mesh with reconfigurable buses, and PRAM (parallel random-access machine). For several of these architectures, the simulated essential pyramids can simultaneously execute an algorithm nearly as fast as a pyramid computer over a single object.>

The pyramid computer was initially proposed for performing high-speed low-level image processing. However, its regular geometry can be adapted naturally to many other problems, providing effective solutions to problems more complex than those previously considered. We illustrate this by presenting pyramid computer solutions to problems involving component labeling, minimal spanning forests, nearest neighbors, transitive closure, articulation points, bridge edges, etc. Central to these algorithms is our collection of data movement techniques which exploit the pyramid’s mix of tree and mesh connections. Our pyramid algorithms are significantly faster than their mesh-connected computer counterparts. For example, given a black/white square picture with n pixels, we can label the connected components in $\theta (n^{{1 / 4}} )$ time, as compared with the $\Omega (n^{{1 / 2}} )$ time required on the mesh-connected computer.

This paper considers mesh computers with buses, where each bus provides a broadcasting capability to the processors connected to it. We first disprove a published claim by showing that on a 2-dimensional mesh with a bus for each row, where each row must solve its own problem with data that is independent of all other rows, there are problems where the rows can cooperatively solve all subproblems faster than any single row can solve its own problem. As a corollary we obtain efficient solutions to some graph problems. We also consider the optimal layout of buses for a given dimension and number of buses per processor, where optimality is defined in terms of the time needed to simulate any other machine with the same constraints. Using new families of layouts, optimal or nearly optimal families of layouts are determined for each possible choice of dimension and number of buses per processor.

This paper gives several pyramid computer algorithms for determining geometric properties of black/white digitized pictures stored in the base of the pyramid. These algorithms determine properties such as convexity and nearest neighbors of black figures. We show that the pyramid is faster than either a tree of mesh machine, but, like the tree, the time needed by algorithms is quite sensitive to the amount of data movement required. We also consider modified pyramids in which each base processor stores many pixels, and machine models which are related to the pyramid.

Although mesh-connected computers are used almost exclusively for low-level local image processing, they are also suitable for higher level image processing tasks. We illustrate this by presenting new optimal (in the O-notational sense) algorithms for computing several geometric properties of figures. For example, given a black/white picture stored one pixel per processing element in an n × n mesh-connected computer, we give ¿(n) time algorithms for determining the extreme points of the convex hull of each component, for deciding if the convex hull of each component contains pixels that are not members of the component, for deciding if two sets of processors are linearly separable, for deciding if each component is convex, for determining the distance to the nearest neighboring component of each component, for determining internal distances in each component, for counting and marking minimal internal paths in each component, for computing the external diameter of each component, for solving the largest empty circle problem, for determining internal diameters of components without holes, and for solving the all-points farthest point problem. Previous mesh-connected computer algorithms for these problems were either nonexistent or had worst case times of ¿(n2). Since any serial computer has a best case time of ¿(n2) when processing an n × n image, our algorithms show that the mesh-connected computer provides significantly better solutions to these problems.

There is a lot of practical and theoretical interest in designing algorithms to process digital pictures. Of particular interest are problems arising when one starts with an nxn array of pixels and stores it, one pixel per processor, in some sort of array-like parallel computer. In this paper we give an optimal θ(n) time solution, based on a simpler θ(n) time solution for a more powerful computer called a mesh computer. Beyer suggested that this problem was a prime candidate for a non-linear recognition problem, but our result shows that this is not true.

We consider the effects of augmenting an arbitrary mesh-connected computer with a second communication system called broadcasting. In broadcasting, a processor sends a value to all the other processors simultaneously, taking unit time, with the restriction that only one broadcast occurs at any one time. We show that this significantly decreases the time to do sample problems such as semigroup calculations or finding the median, but it cannot significantly improve sorting. For example, in a one-dimensional mesh-connected computer without broadcasting, if there are n numbers, each stored separately in consecutive processors, then θ(n) time is needed to find their minimum, find their median, or sort them, while with broadcasting, this can be done in θ(n1/2), θ((n log n)1/2), and θ(n) time, respectively.

Some models of parallel computation consist of copies of a single finite automaton, connected together in a regular fashion. In such computers clerks can be a useful data structure, enabling one to simulate a more powerful computer for which optimal algorithms are easier to design. Clerks are used here to give optimal algorithms for the 3-dimensional connected is problem on a parallel processing array, and a circle construction problem on a pyramid cellular automaton.

Two classes of encodings of the natural numbers are introduced, all of which are universal asymptotically optimal. The asymptotically best encodings in these classes are determined and are found to improve on previous encoding. The results are related to channel capacity and unbounded searching.