我們有一個用霍夫曼編碼編碼的數據庫。這裏的目的是在GPU上覆制它的相關解碼器;然後在GPU上解碼數據庫，並在這個解碼的數據庫上做一些事情，而不用將其複製回CPU上。是否有可能在GPU中實現霍夫曼解碼？
我很快就成爲霍夫曼專家，但我所知道的少數人表明，它似乎是一種基本上基於控制結構的算法。用基本的算法，恐怕會有很多序列化的操作。
我的2個問題是：
我看其他的限制，但它們並不重要： - GPU不能非常有效的處理樹：二叉樹可以存儲在一個傳統的陣列 - 工作量可能難以平衡：我們將見
霍夫曼編碼的問題是你不能快進。即：你必須線性地逐位解碼。
因此，它不是並行的理想選擇。
如果您可以決定編碼，您可以完美地按塊編碼塊，以便能夠獨立解碼每個塊。
爲什麼您一點一點地認爲並行是不理想的？我認爲讀取幾個獨立的編碼值是不成問題的。問題是並行執行這些位的解碼。 – 2010-06-11 10:46:23
霍夫曼的問題是你不知道一個符號被編碼了多少位。你讀第一個，檢查它是否是符號，讀第二個，檢查它是否是符號，讀第三個AH是符號，好，所以我存儲了符號並倒回我的狀態機。繼續。這不是可並行化的。 – 2010-06-11 13:36:03
我對Huffman在GPU上不可能達成的明顯共識感到驚訝。
我呼籲格言：「如果發生了，它一定是可能的」。 （不同地歸因於阿加莎克里斯蒂，阿爾伯特愛因斯坦等）
因爲SuperXero在GPU上做霍夫曼，我想這一定是可能的。
CPU huffman compression faster after first execution?（SuperXero）
是的，你可以做並行Huffman解碼，所以你可以在GPU獲得優勢 - 提供的內存是不是一個問題。
對於下面的討論，我將討論huffman樹和huffman輸出 - 輸出是需要在huffman樹中查找以解碼的壓縮符號。
huffman算法要求你有一個霍夫曼樹解碼 - 該樹可以很大。您可以通過使用適合GPU中本地內存的小哈夫曼樹來解決此問題 - 但這會影響算法的壓縮效率。例如。您可以將樹限制爲最佳的2^n個節點，就像gpu處理器允許的那樣多。 （例如，使用限定的樹來表示1024個節點
如果你不限制huffman樹，這樣你就可以在每個gpu的本地存儲器中容納一個副本，那麼你將不會真正得到你期望的並行性，因爲所有gpu處理器將被阻塞訪問所有讀取相同共享樹的內存。
huffman輸出符號被打包在可變數量的位中。如果你從輸出的中間開始，就不知道你是否在符號上。但是你可以創造你自己的界限。例如，在輸出中，您可以強制每x個單詞對齊符號以進行字對齊。然後你知道你可以開始在輸出中的任何多個x字的解碼，並將該塊連同適當的樹一起發送到GPU處理節點。
您不必只使用一棵樹，但每塊一棵樹也可能會矯枉過正。也就是說，如果每塊有一棵樹，那麼如果塊很小，則會嚴格切入壓縮效率。
因此，您可以嘗試查看塊的相似性並使用同一棵樹對相似塊進行編碼，並存儲每個塊的樹索引。例如。輸出中可能有10000個塊，但只有50個1024個節點的樹。然後你發送一個塊和一個樹到每個GPU處理節點並行解碼。
使其更快的關鍵在於每個GPU處理節點僅在本地內存上工作。
我懷疑你會看到任何真正的好處，通過實施GPU - CUDA或其他。 GPU對於多個數據點具有並行性和均勻操作的問題的子集來說只是非常有用的。 – 2010-06-10 11:09:15
霍夫曼，因爲我知道它是完全串行的。你根本不能分解要解碼的代碼，因爲你不知道中斷是在哪裏進行的，除非你在中斷之前處理了所有的代碼。 – 2010-06-10 14:36:16
iOS Metal上的一個示例實現（鏈接）顯示，同時解碼多個塊比執行CPU上的邏輯要快得多。必須創建一個每塊查找表，所以會有一些開銷。請參閱https://stackoverflow.com/a/47954985/763355 – MoDJ 2017-12-28 01:40:38