The computation of traveling time of Pre-Stack Time Migration (PSTM) is the most time-consuming part of whole procedure. In this paper, we present a novel parallel algorithm to low the time of traveling-time computation. By using static interpolation with step of 8 points instead of dynamic step length, the new designed algorithm performs more accuracy and performance. Experimental results show that the speed-up number reaches 22.76 times. The statistical relative error demonstrates the better accuracy comparing with the commercial codebases.