Three-dimensional prestack seismic reservoir characterization may benefit from high resolution velocity analyses. The intensive computational effort required to perform 3-D velocity analysis requires implementation on a supercomputer. I have developed and implemented two velocity analysis algorithms on a massively parallel Connection Machine. The first algorithm performs stacking velocity semblance analysis, and tends to be I/O bound. The second algorithm performs prestack time migration velocity semblance analysis, and tends to be cpu bound. The inner core computational loop of the stacking velocity analysis code runs at about 120 Mflop/s, whereas the migration velocity analysis code runs at about 420 Mflop/s, on an 8k processor CM-2. On a full size 64k CM-2, the stacking velocity code scales to about 1 Gflop/s, and the migration velocity code scales to about 3 Gflop/s. These rates are fast enough to make high-resolution 3-D velocity analyses feasible in an applications research environment.