Title :
A VQ compression algorithm for a multiprocessor system with a global sort collective function
Author :
Wakatani, Akiyoshi
Author_Institution :
Fac. of Sci. & Eng., Konan Univ., Kobe
Abstract :
One of the most expensive part of a VQ compression algorithm is a codebook generation. PNN algorithm constructs a codebook by merging the "nearest" vectors and its parallel algorithm needs "Allsort" procedure that sorts locally-sorted lists of all processors into a globally-sorted list and broadcasts the list to all processors on a multiprocessor system. We propose a new collective function, called Allsort for such a procedure and preliminarily implement the collective based on the dissemination method. We confirm the effectiveness of our proposed collective analytically and empirically. The results of our experiments show that the elapsed time of our implementation of the Allsort collective is improved by a factor of 2.0 to 2.7 compared with the combination of the ordinal MPI Allgather collective and the global sort on both power-of-2 number processors and non-power-of-2 number processors. We also show that the speedup of the aggressive PNN algorithm for a codebook generation for VQ compression is improved by around 8% to 20% on an 8 CPU cluster.
Keywords :
codes; data compression; message passing; multimedia systems; multiprocessing systems; vector quantisation; Allsort procedure; PNN algorithm; VQ compression algorithm; codebook generation; dissemination method; global sort collective function; multiprocessor system; ordinal MPI Allgather collective; Broadcasting; Compression algorithms; Computational complexity; Merging; Multiprocessing systems; Nearest neighbor searches; Parallel algorithms; Pipelines; Streaming media; Yarn;
Conference_Titel :
Computer and Information Science, 2006 and 2006 1st IEEE/ACIS International Workshop on Component-Based Software Engineering, Software Architecture and Reuse. ICIS-COMSAR 2006. 5th IEEE/ACIS International Conference on
Conference_Location :
Honolulu, Hawaii, HI
Print_ISBN :
0-7695-2613-6
DOI :
10.1109/ICIS-COMSAR.2006.14