Parallelization of an adaptive compression algorithm using the reduced model update frequency method

• Autorzy: Starosolski R.

Warianty tytułu

PL

Zrównoleglenie adaptacyjnego algorytmu kompresji z użyciem metody zmniejszonej częstości aktualizacji modelu danych

• Języki publikacji: EN

Abstrakty

EN

Modeling and coding is the most complex part of many adaptive compression algorithms; it is also an inherently serial process. The method of reduced model update frequency is a modification of the typical adaptive scheme, which was originally employed in order to improve the speed of modeling at the cost of a negligible worsening of the modeling quality. In this paper, we notice that the above method permits to parallelize the compression process. We find that for the Itanium 2 processor the speed of coding and modeling in a SFALIC image compression algorithm may be improved by about 50% through exploiting the fine-grained parallelism, also the medium-grained parallelism may be exploited in a significantly larger extent.

PL

Modelowanie i kodowanie to najbardziej złożone elementy wielu adaptacyjnych algorytmów kompresji, przy czym sam proces kompresji oparty o modelowanie i kodowanie musi być realizowany w sposób sekwencyjny. Metoda zmniejszonej częstości aktualizacji modelu danych to modyfikacja zastosowana do adaptacyjnego algorytmu kompresji, aby poprawić prędkość modelowania kosztem nieznacznego, z praktycznego punktu widzenia, pogorszenia jakości modelowania. W niniejszej pracy zauważono, iż zastosowanie tej metody umożliwia zrównoleglenie algorytmu kompresji. Badania eksperymentalne wykazały, ˙ze dzięki wykorzystaniu równoległości drobnoziarnistej dla procesora Itanium 2 i algorytmu SFALIC metoda zmniejszonej częstości aktualizacji modelu danych pozwala na zwiększenie prędkości kodowania i modelowania o około 50%. Przeprowadzone szacunki pokazały, że metoda ta pozwala również na wykorzystanie równoległości średnioziarnistej w znacznie większym stopniu.

Słowa kluczowe

EN

parallel processing; Fine- and medium-grained parallelism; adaptive modelling; data compression; image compression

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2007
• Tom: Vol. 19, No. 2
• Strony: 103--115
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Starosolski R.

• Institute of Computer Science, Silesian University of Technology Akademicka 16, 44-100 Gliwice, Poland,

Bibliografia

• [1] Advanced Micro Devices: AMD64 Architecture Programmer’s Manual Volume 1: Application Programming. Rev. 3.11, December 2005.
• [2] Allan V.H., Jones R.B., Lee R.M., Allan S.J.: Software Pipelining. ACM Computing Surveys, 27(3), 1995, pp. 367-432.
• [3] Carpentieri B., Weinberger M.J., Seroussi G.: Lossless compression of Continuous-Tone Images. Proceedings of the IEEE, 88(11), 2000, pp. 1797-809.
• [4] Flynn M.J.: Very high-speed computing systems. Proceedings of the IEEE, 54(12), 1966, pp. 1901-9.
• [5] Golomb S.W.: Run-Length Encodings. IEEE Trans. on Information Theory, IT-12, 1966, pp. 399-401.
• [6] Howard P.G., Vitter J.S.: Fast and efficient lossless image compression. Proceedings DCC ’93 Data Compression Conference, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, pp. 351-60.
• [7] Huffman S.A.: A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers, 40(9), 1952, pp. 1098-101.
• [8] Intel: IA-32 Intel Architecture Optimization Reference Manual. December 2003.
• [9] Intel: Intel Itanium 2 Processor Reference Manual For Software Development and Optimization. April 2003.
• [10] Moffat A., Neal R.M., Witten I.H.: Arithmetic Coding Revisited. ACM Transactions on Information Systems, 16(3), 1998, pp. 256-94.
• [11] Rice R.F.: Some practical universal noiseless coding techniques – part III. Jet Propulsion Laboratory tech. report JPL-79-22, 1979.
• [12] Shannon C.E.: AMathematical Theory of Communication. Bell System Technical Journal, 27, 1948, pp. 379-423, 623-56.
• [13] Starosolski R.: Performance evaluation of lossless medical and natural continuous tone image compression algorithms. Proc. SPIE, 5959, 2005, pp. 116-27.
• [14] Starosolski R.: Simple Fast and Adaptive Lossless Image Compression Algorithm. Software-Practice and Experience, 37(1), 2007, pp. 65-91.
• [15] SUN Microsystems: UltraSPARC III Cu User’s Manual. Version 2.2.1, January 2004.