I selected two Fourier domain migration algorithms, Phase Shift Plus Interpolation and Split-step, and implemented them on a serial computer (Convex) and a parallel computer (Connection Machine). I compared the migration results of the two methods on 2-D and 3-D laterally varying velocity models. The PSPI handles lateral velocity discontinuities better, but the run time tends to be 1.5 times higher than for the Split-step method. For smoothly varying lateral velocity, the two algorithms produce very similar results and therefore the faster one (Split-step) should be preferred. The run-times on the Convex and the Connection Machine are examined and a 33 to 1 improvement in run-time for the parallel version of the PSPI and a 14 to 1 improvement in run-time for the parallel version of the Split-step algorithm are found for the three dimensional model.