Abstract In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization. This paper presents a library called CHAOS, which helps users implement irregular programs on distributed‐memory message‐passing machines, such as the Paragon, Delta, CM‐5 and SP‐1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high‐level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real‐life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle‐in‐cell code, DSMC. Besides providing runtime support to users, CHAOS can also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.

This paper describes two new ideas by which a High Performance Fortran compiler can deal with irregular computations effectively. The first mechanism invokes a user specified mapping procedure via a set of proposed compiler directives. The directives allow use of program arrays to describe graph connectivity, spatial location of array elements, and computational load. The second mechanism is a conservative method for compiling irregular loops in which dependence arises only due to reduction operations. This mechanism in many cases enables a compiler to recognize that it is possible to reuse previously computed information from inspectors (e.g., communication schedules, loop iteration partitions, and information that associates off-processor data copies with on-processor buffer locations). This paper also presents performance results for these mechanisms from a Fortran 90D compiler implementation.>

In adaptive irregular problems, data arrays are accessed via indirection arrays, and data access patterns change during computation. Parallelizing such problems on distributed memory machines requires support for dynamic data partitioning, efficient preprocessing and fast data migration. This paper describes CHAOS, a library of efficient runtime primitives that provides such support. To demonstrate the effectiveness of the runtime support, two adaptive irregular applications have been parallelized using CHAOS primitives: a molecular dynamics code (CHARMM) and a code for simulating gas flows (DSMC). We have also proposed minor extensions to Fortran D which would enable compilers to parallelize irregular for all loops in such adaptive applications by embedding calls to primitives provided by a runtime library. We have implemented our proposed extensions in the Syracuse Fortran 90D/HPF prototype compiler, and have used the compiler to parallelize kernels from two adaptive applications.>

Mapping data to parallel computers aims at minimizing the execution time of the associated application. However, it can take an unacceptable amount of time in comparison with the execution time of the application if the size of the problem is large. In this paper, first we motivate the case for graph contraction as a means for reducing the problem size. We restrict our discussion to applications where the problem domain can be described using a graph (e.g., computational fluid dynamics applications). Then we present a mapping-oriented Parallel Graph Contraction (PGC) heuristic algorithm that yields a smaller representation of the problem to which mapping is then applied. The mapping solution for the original problem is obtained by a straight-forward interpolation. We then present experimental results on using contracted graphs as inputs to two physical optimization methods; namely, Genetic Algorithm and Simulated Annealing. The experimental results show that the PGC algorithm still leads to a reasonably good quality mapping solutions to the original problem, while producing a substantial reduction in mapping time. Finally, we discuss the cost-quality tradeoffs in performing graph contraction.

In this paper, we describe two new ideas by which HPF compiler can deal with irregular computations effectively. The first mechanism invokes a user specified mapping procedure via a set of compiler directives. The directives allow the user to use program arrays to describe graph connectivity, spatial location of array elements and computational load. The second is a simple conservative method that in many cases enables a compiler to recognize that it is possible to reuse previously computed results from inspectors (e.g. communication schedules, loop iteration partitions, information that associates off-processor data copies with on-processor buffer locations). We present performance results for these mechanisms from a Fortran 90D compiler implementation. 1 Introduction In sparse and unstructured problems the data access pattern is determined by variable values known only at runtime. In these cases, programmers carry out preprocessig to partition work, map data structures and schedule ...

The authors study the communication characteristics of the CM-5 (Connection Machine 5) and the performance effects of scheduling regular and irregular communication patterns on the CM-5. They consider the scheduling of regular communication patterns such as complete exchange and broadcast. They have implemented four algorithms for complete exchange and studied their performances on a 2-D FFT (fast Fourier transform) algorithm. They have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.>

Abstract This paper presents several static and dynamic data decomposition techniques for parallel implementation of common computer vision algorithms. These techniques use the distribution of features in the input data as a measure of load for data decomposition. Experimental results are presented by implementing algorithms from a motion estimation system using these techniques on a hypercube multiprocessor. Normally in a vision system a sequence of algorithms is employed in which output of an algorithm is input to the next algorithm in the sequence. The distribution of features computed as a by‐product of the current task is used to repartition the data for the next task in the system. This allows parallel computation of feature distribution, and therefore the overhead of estimating the load is kept small. It is observed that the communication overhead to repartition data using these run‐time decomposition techniques is very small. It is shown that significant performance improvements over uniform‐block‐oriented partitioning schemes are obtained.

Computer vision systems employ a sequence of algorithms that exhibit different computational characteristics. These algorithms require different data decomposition and load balancing techniques for efficient parallel implementations. This paper presents several techniques to perform static and dynamic data decomposition for common computer vision algorithms. They exploit the distribution of features as a measure of load for data decomposition. In these techniques, the distribution of features computed during the parallel execution of the current algorithm allows an informed partitioning for the next algorithm in the pipeline, keeping overhead involved in estimating the load small. Performance results obtained from a shared memory multiprocessor implementation using these techniques are presented. Furthermore, a classification of common vision algorithms based on their suitability for one or more data decomposition techniques is given. Improvements of up to four times over the performance of uniform block-oriented partitioning were obtained.

The authors present several parallel implementations of the Hough transform on a shared memory multiprocessor, namely, the Encore Multimax. Various implementation strategies are described, and results are discussed.>

Hough Transform is one of the most common methods for detecting shapes (lines, circles, etc.) in binary or gray-level images. In this paper we present several techniques for implementing hough transform computations on a shared-memory multiprocessor and present their performance. Implementation results are obtained using fine-grain and coarse-grain parallelism; uniform, static, parameter, and dynamic partitioning schemes; uniform and nonuniform images; several image sizes; and several multiprocessor sizes. A simple analysis of all the implementations is also presented. The results show that static and dynamic partitioning schemes perform comparably in most cases. Coarse-grain parallelism performs better than fine-grain parallelism in general. In fact, for very fine-grain computations, multiprocessors perform worse than a single processor implementation. There exists a granule size for which best performance is achieved. Finer or coarser granule sizes compared to this granule size result in worse performance. It is observed that for nonuniform images uniform partitioning does not perform well, whereas static and dynamic partitioning strategies perform well and comparably in most cases. Finally, the results also show that speedups are very sensitive to locking granularities for fine-grain parallelism.