International Journal of High Speed Computing

Implicit finite difference schemes are often the preferred numerical methods in computational fluid dynamics, requiring less stringent stability bounds than the explicit schemes. Each iteration in an implicit scheme, however, involves global data dependencies in the form of second and higher order recurrences. Efficient parallel implementations of such methods, therefore, are more difficult and can be non-intuitive. Moreover, in practical applications, some sections of the computations are explicit while other sections are implicit in nature. Developing techniques that extract maximum parallelism simultaneously from all sections of an application is considerably harder than extracting parallelism from just an implicit section or an explicit section of the computations.

In this paper, we consider issues in the parallelization of techniques that are used for solving Euler and thin-layer Navier-Stokes equations and that require, as a part of the computation, solving large linear systems in the form of block tri-diagonal and/or scalar penta-diagonal matrices. We focus our attention on three-dimensional cases and present schemes that minimize the total execution time when implemented on a message passing system. We describe various partitioning and scheduling strategies for alleviating the effects of the global data dependencies. Analyses of the computation, the communication, and the memory requirements of these methods are presented. The ARC-3D code, developed at NASA Ames, is used as an example application. Performance of the proposed methods is verified on the Victor multiprocessor system, a message passing architecture developed at the IBM T.J. Watson Research Center.

Beginning in 1988, the Numerical Aerodynamic Simulation (NAS) organization at NASA Ames Research Center has studied the usability of highly parallel computers on computational fluid dynamics and other aerophysics applications. Presently this organization operates a CM-2 with 32,768 nodes and an Intel iPSC/860 with 128 nodes. This note gives an overview of the experience in using these systems, highlights both strong points and weak points of each, and discusses what improvements will be required in future highly parallel systems in order that they can gain acceptance in the mainstream of scientific computing.

Operational numerical weather prediction requires that all available main-frame computing power be harnessed to the one task, in order to maintain operational schedules. ECMWF therefore became involved in parallel processing as soon as it became available on supercomputers. The main operational programs were restructured to use multitasking on a limited number of processors, currently 8.

The availability of supercomputers with massively parallel architecture which is expected in the near future raises quite a number of major problems. These areas have been discussed in the biennial workshops held at ECMWF since 1984. Besides the user environment, the inter-dependency of hardware architecture and algorithms needs most attention. To study these questions, ECMWF became involved in the GENESIS project sponsored by the European Community. Initial results of this co-operation in the form of benchmark results will be presented.

The challenges posed by new developments in weather prediction strategies will be highlighted and an assessment of the impact parallel computing will have on their being met will be made.

Simple generalized closed-form analytic solutions, using t-out-of-s system principle, are presented for tightly coupled multiprocessor systems employing multiplebus and crossbar interconnection networks. The system bandwidth is obtained taking into account the memory and bus interference. A single equation represents both uniform and local reference models of memory access. This expression holds for any demand pattern of memory access by the processors unlike the solutions given by others, which consider only some restricted memory access patterns. The results predicted by these models have been shown to be very close to the results of simulation studies done by others.

In this paper, a heuristic mapping approach which maps parallel programs, described by precedence graphs, to MIMD architectures, described by system graphs, is presented. The complete execution time of a parallel program is used as a measure, and the concept of critical edges is utilized as the heuristic to guide the search for a better initial assignment and subsequent refinement. An important feature is the use of a termination condition of the refinement process. This is based on deriving a lower bound on the total execution time of the mapped program. When this has been reached, no further refinement steps are necessary. The algorithms have been implemented and applied to the mapping of random problem graphs to various system topologies, including hypercubes, meshes, and random graphs. The results show reductions in execution times of the mapped programs of up to 77 percent over random mapping.