This paper extends work presented at the PMAM'16 workshop 2016, to use integrated graphics processors (IGPs) for parallel entropy decoding. We introduce a novel, dynamic partitioning scheme for JPEG decoding which takes into account the considerably lower compute-power of IGPs relative to the on-chip CPU. We present new insights from an extended experimental evaluation that includes the achieved energy savings on an i7-6700k CPU with an HD Graphics 530 IGP. We report on the performance improvements achieved on a Tesla K80 GPU.

Read the full text

About

PDF

Tools

Share a link

Email
Wechat
Bluesky

Summary

The JPEG format employs Huffman codes to compress the entropy data of an image. Huffman codewords are of variable length, which makes parallel entropy decoding a difficult problem. To determine the start position of a codeword in the bitstream, the previous codeword must be decoded first. We present JParEnt, a new approach to parallel entropy decoding for JPEG decompression on heterogeneous multicores. JParEnt conducts JPEG decompression in two steps: (1) an efficient sequential scan of the entropy data on the CPU to determine the start-positions (boundaries) of coefficient blocks in the bitstream, followed by (2) a parallel entropy decoding step on the graphics processing unit (GPU). The block boundary scan constitutes a reinterpretation of the Huffman-coded entropy data to determine codeword boundaries in the bitstream. We introduce a dynamic workload partitioning scheme to account for GPUs of low compute power relative to the CPU. This configuration has become common with the advent of SoCs with integrated graphics processors (IGPs). We leverage additional parallelism through pipelined execution across CPU and GPU. For systems providing a unified address space between CPU and GPU, we employ zero-copy to completely eliminate the data transfer overhead.

Our experimental evaluation of JParEnt was conducted on six heterogeneous multicore systems: one server and two desktops with dedicated GPUs, one desktop with an IGP, and two embedded systems. For a selection of more than 1000 JPEG images, JParEnt outperforms the SIMD–implementation of the libjpeg-turbo library by up to a factor of 4.3×, and the previously fastest JPEG decompression method for heterogeneous multicores by up to a factor of 2.2×. JParEnt's entropy data scan consumes 45% of the entropy decoding time of libjpeg-turbo on average. Given this new ratio for the sequential part of JPEG decompression, JParEnt achieves up to 97% of the maximum attainable speedup (95% on average).

On the IGP-based desktop platform, JParEnt achieves energy savings of up to 45% compared to libjpeg-turbo's SIMD-implementation.

References

1Sodsong W, Jung M, Park J, Burgstaller B. JParEnt: Parallel entropy decoding for JPEG decompression on heterogeneous multicore architectures. Proceedings of the 7th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM'16. Barcelona, Spain: ACM; 2016: 104–113.
Google Scholar
2 US Securities and Exchange Commission. FORM 10-K (Annual Report); 2013.
Google Scholar
3 Instagram Blog. http://blog.instagram.com/post/80721172292/200m. Accessed Nov. 2015.
Google Scholar
4 Alexa Top 500 Global Sites. http://www.alexa.com/topsites. Accessed Feb. 2015.
Google Scholar
5Sodsong W, Hong J, Chung S, et al. Dynamic partitioning-based JPEG decompression on heterogeneous multicore architectures. Proceedings of the 2014 PPOPP International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2014. Orlando, Florida, USA: ACM; February 15, 2014: 80–91.
Google Scholar
6Sodsong W, Hong J, Chung S, et al. Dynamic partitioning-based JPEG decompression on heterogeneous multicore architectures. Concurrency Computat: Pract Exper. 2016; 28(2): 517–536.
10.1002/cpe.3620
Web of Science® Google Scholar
7Klein ST, Wiseman Y. Parallel Huffman decoding with applications to JPEG files. The Comput J. 2003; 46(5): 487–497.
10.1093/comjnl/46.5.487
Web of Science® Google Scholar
8Capocelli RM, Gargano L, Vaccaro U. On the characterization of statistically synchronizable variable-length codes. IEEE Trans Inf Theory. 1988; 34(4): 817–825.
10.1109/18.9779
Web of Science® Google Scholar
9Gregg C, Hazelwood K. Where is the data? Why you cannot debate CPU vs. GPU performance without the answer. 2011 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), Austin, Texas, USA; 2011: 134–144.
Google Scholar
10Wallace GK. The JPEG still picture compression standard. Commun ACM. 1991; 34(4): 30–44.
10.1145/103085.103089
Web of Science® Google Scholar
11Pu IM. Fundamental Data Compression. Newton, MA, USA: Butterworth-Heinemann; 2005.
Google Scholar
12 Libjpeg Turbo. http://sourceforge.net/projects/libjpeg-turbo. Accessed Sep. 2015.
Google Scholar
13 Libjpeg. http://libjpeg.sourceforge.net/ Accessed Aug. 2015.
Google Scholar
14Schwartz ES, Kallick B. Generating a canonical prefix encoding. Commun ACM. 1964; 7(3): 166–169.
10.1145/363958.363991
PubMed Web of Science® Google Scholar
15Harris M, Sengupta S, Owens JD. Parallel prefix sum (scan) with CUDA. GPU gems. 2007; 3(39): 851–876.
Google Scholar
16 NVIDIA. CUDA C programming guide v7.5. Technical Report, NVIDIA Corporation; 2015.
Google Scholar
17 Cygwin. https://www.cygwin.com/. Accessed April 2016.
Google Scholar
18 International Telecommunication Union. CCITT recommendation. Information technology—digital compression and coding of continuous-tone still images: Requirements and guidelines; 1993.
Google Scholar
19 Wikimedia Commons. https://commons.wikimedia.org. Accessed Nov. 2015.
Google Scholar
20 List of test images from Wikimedia Commons. http://elc.yonsei.ac.kr/~wsodsong/images.html. Accessed Nov. 2015.
Google Scholar
21 Intel Power Gadget. https://software.intel.com/en-us/articles/intel-power-gadget-20. Accessed April 2016.
Google Scholar
22Hashemian R. Condensed table of Huffman coding, a new approach to efficient decoding. IEEE Trans Commun. 2004; 52(1): 6–8.
10.1109/TCOMM.2003.822145
Web of Science® Google Scholar
23Lee JS, Jeong JH, Chang TG. An efficient method of Huffman decoding for MPEG-2 AAC and its performance analysis. IEEE Trans Speech Audio Process. 2005; 13(6): 1206–1209.
10.1109/TSA.2005.852989
Web of Science® Google Scholar
24Latendresse M, Feeley M. Generation of fast interpreters for Huffman compressed bytecode. Sci Comput Program. 2005; 57(3): 295–317.
10.1016/j.scico.2004.07.005
Web of Science® Google Scholar
25Hong K, Park J, Kim S, et al. TinyVM: An energy-efficient execution infrastructure for sensor networks. Softw Pract Exper. 2012; 42(10): 1193–1209.
10.1002/spe.1123
Web of Science® Google Scholar
26Wei BWY, Meng TH. A parallel decoder of programmable Huffman codes. IEEE Trans Circuits Syst Video Technol. 1995; 5(2): 175–178.
10.1109/76.388067
Web of Science® Google Scholar
27Liddell M, Moffat A. Decoding prefix codes. Softw Pract Exper. 2006; 36(15): 1687–1710.
10.1002/spe.741
Web of Science® Google Scholar
28Jang H, Kim C, Lee JW. Practical speculative parallelization of variable-length decompression algorithms. Proceedings of the 14th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, LCTES '13. ACM; 2013: 55–64.
Google Scholar
29Ko Y, Jung M, Han Yo-Sub, Burgstaller B. A speculative parallel DFA membership test for multicore, SIMD and cloud computing environments. Int J Parallel Program. 2014; 42(3): 456–489.
10.1007/s10766-013-0258-5
Web of Science® Google Scholar
30Mytkowicz T, Musuvathi M, Schulte W. Data-parallel finite-state machines. Architectural Support for Programming Languages and Operating Systems, ASPLOS '14, Salt Lake City, UT, USA; 2014: 529–542.
Google Scholar
31Lin HD, Messerschmitt DG. High throughput reconstruction of Huffman-coded images. Proceedings, 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1989, ICCD '89, Cambridge, Massachusetts, USA; 1989: 172–175.
Google Scholar
32Cloud RL, Curry ML, Ward HL, Skjellum A, Bangalore P. Accelerating lossless data compression with GPUs. arXiv preprint arXiv:1107.1525. 2011.
Google Scholar
33Patel R, Zhang Y, Mak J, Davidson A, Owens J. Parallel lossless data compression on the GPU. Innovative Parallel Computing (InPar), 2012, San Jose, California; 2012: 1–9.
Google Scholar
34Rahmani H, Topal C, Akinlar C. A parallel Huffman coder on the CUDA architecture. Visual Communications and Image Processing Conference, 2014 IEEE. Valletta, Malta: IEEE; 2014: 311–314.
Google Scholar

Citing Literature

Volume29, Issue15

Combined Special Issues on Euro‐Par 2016 and the Workshop on the seventh international workshop on programming models and applications for multicores and manycores (PMAM 2016)

10 August 2017

e4111

JParEnt: Parallel entropy decoding for JPEG decompression on heterogeneous multicore architectures^†

Summary

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

JParEnt: Parallel entropy decoding for JPEG decompression on heterogeneous multicore architectures†

Summary

References

Citing Literature

References

Related

Information

JParEnt: Parallel entropy decoding for JPEG decompression on heterogeneous multicore architectures^†