INTRODUCTION

A year ago during the time of the SEG conference in San Francisco, Jon Claerbout was looking for a student inside SEP who would volunteer some time and examine the option to bring parallel computing to the Geophysics Department in Stanford. After a month or two of inspecting different vendors and architectures we narrowed the selection to two massively parallel computers: Maspar and the Connection Machine. At the end of December 1990 the final arrangements were made for the delivery of a CM-2. In the same month we installed our new server ``Oas'' planned to become the front end to the new parallel computer. In January 1991 the Thinking Machine Corporation people were busy installing the Darth Vader look alike Connection Machine.

Many students immediately started to write code for the new parallel machine, porting old programs or writing new algorithms which promised to show improved performance on the Connection Machine as compared to other serial computers. After almost a year in the middle of our hardware ranch, the CM has proved itself and is now routinely used by all the senior SEP students.

The introduction of parallel computers in geophysical data processing opens a new dimension in algorithm research. When designing a new algorithm we are usually limited in our approach by the amount of time we estimate it will take the program to run on available resources. Approaches that will take weeks of computer time are usually excluded automatically as the run-time of a program is usually just the exponent of the total time involved in debugging and optimizing a new algorithm. When the total time to run a three dimensional migration program on the Connection Machine is less than the total time to run the two dimensional version on the Convex, our horizons are greatly expanded.

Migration algorithms in the frequency-wavenumber domain are special candidates for implementation on parallel computers as the frequency components are independent, allowing the computations to be done in parallel in surface coordinates. The three dimensional case offers a perfect mapping on the parallel computer memory, by storing the data in a serial fashion along the time dimension and in parallel on different processors in the surface coordinates. After Fourier transforming the data along the time axis, we can process each frequency independently, a slice at a time.

I selected two Fourier domain migration algorithms which handle lateral velocity variations. The Phase Shift Plus Interpolation algorithm presented by Gazdag (1984) and the Split-step Fourier method presented by Stoffa et al. (1990) were natural nominees. The two algorithms are extremely similar, and the three dimensional extension of the two dimensional version is quick and painless. I coded the two migration programs on the Convex first, then I wrote the parallel FORTRAN 90 version of the code to run on the Connection Machine. I compared the migration results of the two programs on two dimensional and three dimensional synthetic models. I studied the execution time of the program kernels on the CM and evaluated the Mflop/s performance and examined the total run-time of the programs on the Convex versus the CM.