Recently, parallel processing technologies have been applied to a variety of applications to boost its performance. We implemented a parallel algorithm with ?double strip-mining? method of optimal codeword search for VQ compression on a shared-memory parallel environment and evaluated the effectiveness of the parallel algorithm. Namely, by applying strip-mining method to a loop with regard to vectors as well as that to codewords (double strip-mining), the buffer area, which keeps the intermediate results, can be dramatically reduced and the results of our experiments find that this method can keep the same performance as the original strip-mining method in terms of the elapsed time. As shown in Figure 1-(b), the p-dist algorithm with the double strip-mining method outperforms the c-dist algorithm by over 10%, when the size of strip-mining is enough large.