Introduction

Research in reflection seismology is dependent, as in all computational sciences, on the computer tools available. Seismology is an ``experimental'' science, that is, the ``theory'' (new algorithms) must be checked against the results of the ``experiments'' (real data results). Therefore, the speed of the available computers determines the limits of the computational cost of the new methods that is practical to investigate. Massively parallel computers hold the promise of expanding these limits by increasing the computational power available to researchers by some order of magnitude. But, to actually keep this promise, massively parallel computers must show themselves to be capable of solving the numerical problems that are of interest to Geophysicists, and to do so without requiring a large effort in programming from the users.

Among the seismic algorithms that are most widely used, and most computationally intensive, are algorithms related to the solution of the wave equation. Wave-equation algorithms are fundamental to seismic data processing, as well as of data modeling. The wave equation is usually solved or by one of the following basic methods, or by a combination of them: Fourier methods, finite-difference schemes, and Kirchhoff integrals. In this paper, I describe an efficient implementation of each of these three basic algorithms. The algorithms that I present are very simple but they are useful for illustrating the ideas underlying the efficient implementation of wave-equation algorithms on a parallel computer. They achieve high efficiency because they respect the two rules of parallel algorithms: low communications overhead and load balancing.

I implemented the example algorithms on the Connection Machine (Hillis, 1985) that SEP recently acquired. The algorithms were coded in Fortran 90 (Brainerd et al., 1990); I show some code fragments from my programs.