The steps involved in Huffman encoding are quite sequential. So, I was wondering how could I introduce parallelism while implementing Huffman encoding on any platforms supporting parallel implementation, like GPUs, many core processor etc.?
-
When you say "in hardware", do you mean design the architecture of a system/chip/whatever so that it would be designed to run Huffman in parallel?– DanielCommented Aug 3, 2015 at 21:06
-
Well, I mean designing the hardware architecture incorporating parallelism for implementing Huffman encoding on a system which supports parallel implementation like GPU, many core processor etc. Basically, I want to introduce parallelism in the architecture for Huffman encoding, whose steps are quite sequential.– beginnerCommented Aug 3, 2015 at 21:13
-
I'm still confused. You say "on hardware" in the title but "on a system which supports parallel implementation" in the comment. So are you asking about 1) creating a parallelized implementation of Huffman Encoding on computer already capable of running things in parallel or 2) creating a hardware architecture that is specifically designed for running Huffman in parallel?– DanielCommented Aug 3, 2015 at 21:18
-
Sorry about the confusion. Option 1 is what I want.– beginnerCommented Aug 3, 2015 at 21:34
2 Answers
Multicore/multiple processors:
It's possible to parallelize Huffman encoding using multi-core processors. The basic idea is just to split the source stream up into chunks, assign a chunk to each processor, encode the chunks in parallel into separate intermediate buffers, and then concatenate the encoded results from the intermediate buffers (which will have varying lengths) into the final output buffer.
One complication is that because Huffman encoding uses codes of varying bit lengths, each chunk will most likely not encode to a bit stream a whole number of bytes long. This means that when concatenating the results it may be necessary to use bit-shifting to correctly align the output of one intermediate buffer with that of the previous one. For example if buffer A produced a result 150 bytes and 3 bits long, then when copying buffer B, the data will have to be shifted 3 bits, with 5 bits of a byte and 3 bits of the next from the intermediate buffer being joined together to make each byte written to the output buffer.
One workaround for this is to make use of the particularities of the output format. For example, if you are Huffman encoding image data for the JPEG format, you can output the JPEG restart marker at the start of each chunk that you write to the output buffer, to align the stream to a byte boundary. According to the JPEG specs this marker is intended to allow parallel decoding, but it also makes parallel encoding easier.
Threading
Suppose you have a source data stream of 100Kb and 4 processors. The simplest thing to do is just to split it into chunks of 25Kb each, however this could lead to a worst-case scenario where the first chunk is the last to finish encoding, so all the other processors have to wait for it because the second chunk cannot be written to the output buffer until the length of the first chunk is known. To avoid this, split the input stream into smaller chunks, parceling the data out to the available processors on a first-come-first-served basis with each processor writing the contents of its intermediate buffer to the output buffer as soon as it is finished and all earlier chunks have completed encoding (so that the index to write to in the output buffer is known), and then being assigned the next available chunk in the input stream.
You will need to synchronize access to the read index of the input buffer and write index of the output buffer, but do not synchronize access to the output buffer itself. For example once a processor is finished, it can (using thread synchronization) read the output buffer index to know where to start writing, then (still using thread synchronization) update the index based on the size of the data it is about to write, and then (no longer using synchronization) start writing. This way more than one processor can write to the output buffer at once. A similar scheme can be used for the input buffer.
GPU and hardware acceleration
I'm not aware of any simple scheme for using GPUs for Huffman encoding. In general, GPUs are very good at operations that read from unevenly spaced memory locations and write to constantly spaced memory locations, but not vice versa (this is why displacement mapping is so hard, for example). Because Huffman encoding is an example of the latter, it's not well suited to GPU-based acceleration. However there are custom hardware solutions for the problem, such as used in the hardware accelerated video encoders that are found in many mobile phones.
Based on a quick google search parallelization of Huffman encoding is possible and the papers dates back decades ago.
- Constructing Huffman Trees in Parallel
- Parallel Lossless Image Compression Using Human and Arithmetic Coding
- http://arxiv.org/pdf/1107.1525.pdf
I have not ready any of them (just took a short glance to understand the relevancy).
Here is a small blog post on the topic where the guy claims that:
though, parallel Huffman Decoding shouldn't be hard if we have a suitably large number of processors, and we assume that communication time between processor elements is very short.
-
2Thanks. You are correct, there are several ways to implement Huffman decoder in parallel, but hardly any paper talks about parallel implementation of encoder.– beginnerCommented Aug 3, 2015 at 21:39