title: Is it possible to achieve Huffman decoding in GPU?
body: <p>We have a database encoded with Huffman coding. The aim here is to copy on the GPU it with its associated decoder; then on the GPU, decod the database and do stuff on this decoded database without copying back it on the CPU.</p>
  
  <p>I am far to be a Huffman specialist, but the few I know shows that it seems to be an algorithm essentially based on control structures. With the basic algorithm, I am afraid that there will be a lot of serialized operations.</p>
  
  <p>My 2 questions are:</p>
  
  <ul>
  <li>do you know if there exists any efficient GPU version for Huffman coding</li>
  <li>if not, do you think there exists a Huffman algorithm which be adapted on GPU (ie. with less control structures). Or maybe you know (and you could provide a reference) that efficient Huffman decoding can not be efficient on GPU.</li>
  </ul>
  
  <p>I see other constraints, but they are not critical:
   - GPU could not be very efficient to handle tree: binary tree can be stored in a classical array
   - workload could be difficult to balance: we'll see after</p>