Improvements of VQ Compression Algorithm for Parallel Systems

Recent processors utilize a variety of parallel processing technologies to boost its performance, and thus it is required that multimedia applications can be efficiently parallelized and can be easily implemented on such a processor with parallel processing features. 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 can be reduced and results of our experiments find that this method can keep the same performance as the original strip-mining method with regard to the quality of compression. Moreover, two optimization methods for sequential computers are described: the shortcut calculation and the modified expression. Our experimental results show that the elapsed time is improved by 20% to 40% by using the both sequential optimization methods, so the effectiveness of the above methods on sequential computers is empirically confirmed and can be also applied to parallel systems easily.