I am developing techniques to perform a detailed reservoir characterization given 3-D prestack surface seismic data. In this paper, I develop and implement two velocity analysis algorithms on an 8k processor Connection Machine CM-2. The first algorithm performs a weighted semblance stacking velocity analysis, and is general for 3-D bin geometries. It is heavily I/O bound, and the inner computational core currently runs at about 120 Mflop/s. The second algorithm performs a full 3-D prestack time migration velocity semblance analysis. It is mostly cpu bound and currently runs at about 420 Mflop/s. These results are expected to scale fairly linearly on a full 64k processor CM-2 to 1 Gflop/s for stacking velocity analysis and over 3 Gflop/s for prestack time migration velocity analysis. I tested the algorithm on a marine data set recorded over a producing gas reservoir in the Gulf of Mexico. This example shows a variation of at least 100 m/s in migration velocity, or about 500 m/s in interval velocity, in about 700 m distance along the gas reservoir unit. The estimated velocity variation correlates with AVO bright and dim spots, suggesting a technique for mapping 3-D spatial reservoir gas saturation and hydrocarbon pore volume.