A variety of parallel processing technologies have been implemented in a processor, and thus a cutting edge algorithm for multimedia applications should be aware of parallel processing features. We implemented parallel algorithms for VQ compression on a sharedmemory parallel environment and evaluated the effectivess of the parallel algorithms. On such a system, we evaluate two parallel algorithms for the codebook generation of the VQ compression: parallel LBG and parallel tPNN and find that the parallel tPNN is superior in terms of space complexity, whereas the parallel LBG is superior in terms of time complexity and parallelism.