Ist es möglich, Huffman-Decodierung in GPU zu erreichen?

Question

Wir haben eine Datenbank mit Huffman-Codierung codiert. Ziel ist es, die GPU mit dem zugehörigen Decoder zu kopieren; dann auf der GPU, dekodieren Sie die Datenbank und machen Sie Sachen auf dieser entschlüsselten Datenbank, ohne sie auf der CPU zu kopieren.

Ich bin weit entfernt ein Huffman-Spezialist zu sein, aber die wenigen, die ich kenne, zeigen, dass es ein Algorithmus zu sein scheint, der im Wesentlichen auf Kontrollstrukturen basiert. Mit dem grundlegenden Algorithmus fürchte ich, dass es viele serialisierte Operationen geben wird.

My 2 Fragen sind:

• wissen Sie, wenn es eine effiziente GPU-Version für Huffman
Codierung existiert
• wenn nicht, glauben Sie, dass es einen Huffman-Algorithmus existiert, die auf GPU (dh angepasst werden. mit weniger Kontrollstrukturen). Oder vielleicht wissen Sie (und Sie könnten eine Referenz angeben), dass effiziente Huffman-Decodierung auf GPU nicht effizient sein kann.

Ich sehe andere Einschränkungen, aber sie sind nicht kritisch: - GPU nicht sehr effizient sein könnte zu handhaben Baum: Binärbaum kann in einem klassischer Array gespeichert werden - Arbeitsbelastung könnte schwierig sein, zu balancieren: Wir werden siehe nach

Answer 1

Das Problem mit Huffman-Codierung ist, dass Sie nicht schnell vorspulen können. Dh: Du musst Stück für Stück linear dekodieren.

Als solches ist es nicht ideal für die Parallelität.

Wenn Sie sich für die Kodierung entscheiden, können Sie Chunk für Chunk perfekt kodieren, um jeden Chunk unabhängig dekodieren zu können.

Answer 2

Ich bin erstaunt über den scheinbaren Konsens, dass Huffman auf einer GPU unmöglich ist.

Ich appelliere an den Aphorismus: "Wenn es passiert, muss es möglich sein". (verschiedentlich zugeschrieben Agatha Christie, Albert Einstein, etc.)

Da SuperXero Huffman auf einer GPU macht, nehme ich an, dass es möglich sein muss.

CPU huffman compression faster after first execution? (SuperXero)

Google: GPU huffman decompression

Answer 3

Ja Sie Huffman-Decodierung parallel tun können, und so können Sie Vorteile in einer GPU bekommen - Speicher vorgesehen ist kein Thema.

Für die Diskussion unten werde ich über den Huffman-Baum und die Huffman-Ausgabe sprechen - die Ausgabe sind die komprimierten Symbole, die im Huffman-Baum nachgeschlagen werden müssen, um entschlüsselt zu werden.

Der Huffman-Algorithmus erfordert, dass Sie einen Huffman-Baum zum Dekodieren haben - dieser Baum kann groß sein. Sie können dies umgehen, indem Sie einen kleinen Huffman-Baum verwenden, der auf den lokalen Speicher in einer GPU passt - dies beeinflusst jedoch die Komprimierungseffizienz des Algorithmus. Z.B. Sie können den Baum auf die besten 2^n Knoten begrenzen, so viel wie Ihre GPU-Prozessoren erlauben. (Verwenden Sie zum Beispiel einen Baum, der auf 1024 Knoten beschränkt ist.

Wenn Sie den Huffman-Baum nicht so begrenzen, dass Sie eine Kopie in den lokalen Speicher auf jedem GPU passen, erhalten Sie nicht wirklich die erwartete Parallelität Die GPU-Prozessoren werden beim Zugriff auf den Speicher gesperrt, wenn sie denselben gemeinsamen Baum lesen.

Die Huffman-Ausgabe Die Symbole sind in einer variablen Anzahl von Bits gepackt. Es gibt keine Möglichkeit, wenn Sie in der Mitte der Ausgabe beginnen, um zu wissen, ob Sie sich auf einer Symbolboudary befinden. Aber Sie können Ihre eigenen Grenzen erstellen. Zum Beispiel in der Ausgabe könnten Sie nur die Ausrichtung der Symbole erzwingen jede x Wörter Wort ausgerichtet werden. Dann wissen Sie, dass Sie mit der Dekodierung eines beliebigen x-Wortes in der Ausgabe beginnen und diesen Block zusammen mit dem entsprechenden Baum an einen GPU-Verarbeitungsknoten senden können.

Sie müssen nicht nur einen Baum verwenden, aber ein Baum pro Block kann auch übertrieben sein. Das heißt, wenn Sie einen Baum pro Block haben, schneiden Sie die Kompressionseffizienz stark ab, wenn die Blöcke klein sind.

So können Sie versuchen, die Ähnlichkeit von Blöcken zu betrachten und ähnliche Blöcke mit dem gleichen Baum zu codieren und einen Baumindex pro Block zu speichern. Z.B. Sie haben möglicherweise 10000 Blöcke in der Ausgabe, aber nur 50 1024-Knoten-Bäume. Dann senden Sie einen Block und einen Baum an jeden GPU-Verarbeitungsknoten, um parallel zu dekodieren.

Der Schlüssel, um es schnell zu machen, ist, dass jeder GPU-Verarbeitungsknoten nur auf dem lokalen Speicher arbeitet.