International Journal of High Speed Computing

This paper develops sharp convergence rate estimates of the Schwarz alternating procedure. We do this for a model Poisson problem in one and two dimensions with multiple subdomains We then use these estimates to assess the serial and parallel complexity of the optimal Schwarz algorithm. We finish with a comparison of this optimal algorithm, using multigrid as the subdomain solver, and multigrid by itself, without domain decomposition.

A data parallel implementation of the finite element method on the Connection Machine system CM-2^® is presented. This implementation assumes that the elementary unit of data is an unassembled nodal point. In the context of the CM-2, each virtual processor represents an unassembled nodal point and nodal points shared between elements are replicated on different virtual processors. An algorithm for computing each elemental stiffness matrix concurrently, as well as different elemental stiffness matrices concurrently, without inter-processor communication is presented. The performance of the elemental stiffness matrix computation is in the range 1.6–1.9 GFlops s⁻¹. The sparse system of linear equations that results from the finite element discretization has been solved by a conjugate gradient method with a diagonal preconditioner. The rate of convergence of the conjugate gradient iterations for boundary conditions which correspond to uniaxial deformations depends nonlinearly on the order of interpolation of the elements and linearly on the mesh discretization. Sample code segments are provided to illustrate the programming environment on a data parallel architecture.

Parafrase-2 is a vectorizing/parallelizing compiler implemented as a source to source code restructurer. This paper discusses the organization of Parafrase-2 and goals of the project. Specific topics discussed are : dependence analysis, timing and overhead analysis, interprocedural analysis, automatic scheduling and the graphical user interface.

This paper describes and compares three parallel algorithms for solving sparse triangular systems of equations. These methods involve some preprocessing overhead and are primarily of interest in solving many systems with the same coefficient matrix. The first approach is to use a fixed blocksize and form the inverse of the diagonal blocks. The second approach is to use a variable blocksize and reorder the unknowns so that the diagonal blocks are diagonal matrices. We call the latter technique level scheduling because of how it is represented in the adjacency graph, and we consider both row-wise and jagged diagonal storage for the offdiagonal blocks. These techniques are analyzed for general parallel computers and experiments are presented for the eight-processor Alliant FX/8.

The usual QR algorithm for finding the eigenvalues of a Hessenberg matrix H is based on vector-vector operations, e.g. adding a multiple of one row to another. The opportunities for parallelism in such an algorithm are limited. In this paper, we describe a reorganization of the QR algorithm to permit either matrix-vector or matrix-matrix operations to be performed, both of which yield more efficient implementations on vector and parallel machines. The idea is to chase a k by k bulge rather than a 1 by 1 or 2 by 2 bulge as in the standard QR algorithm. We report our preliminary numerical experiments on the CONVEX C-1 and CYBER 205 vector machines.

The discretization of separable elliptic partial differential equations leads to linear systems with special block tridiagonal matrices. Several methods are known to solve these systems, the most general of which is the Block Cyclic Reduction (BCR) algorithm which handles equations with nonconstant coefficients. A method was recently proposed to parallelize and vectorize BCR. In this paper we discuss the mapping of BCR on distributed memory architectures and compare its complexity with that of other approaches including the Alternating-Direction method. We also describe a fast parallel solver, based on an explicit formula for the solution, which has parallel computational complexity lower than that of parallel BCR.

The parallelizing compiler for the B-HIVE loosely-coupled multiprocessor system uses a medium grain model to minimize the communication overhead. A medium grain model is shown to be an optimum way of merging fine grain operations into parallel tasks such that the parallelism obtained at the grain level is retained and communication overhead is decreased. A new communication model is introduced in this paper, allowing additional overlap between computation and communication. Simulation results indicate that the medium grain communication model shows promise for automatic parallelization for a loosely-coupled multiprocessor system.

Elementary operations such as inner products and vector norms used in conjugate gradient methods and for iteration error checking have an amazingly high complexity (computer time) on mesh connected arrays of processors because they require global information. Therefore iterative methods which require only local, nearest neighbor communications can be more efficient. The simplest such method, the Jacobi iterative method converges too slowly but we show how faster convergent methods based on Chebyshev iterative methods, with or without preconditioning can be applied efficiently for elliptic difference equations The preconditionings provide the bounds for the extreme eigenvalues, which are needed for the Chebyshev method and the number of iterations can be determined a priori, so no error checking is needed.

In this paper, we report the recent progress in parallel processing research in Japan.