ハフマン符号展開処理を最大で「1万1000倍」高速化 広島大学の研究チームが「ギャップ配列」を考案

広島大学大学院先進理工系科学研究科の教授である中野浩嗣氏らの研究チームは2020年8月31日、富士通研究所と共同で、GPUによる「ハフマン符号」の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案したと発表した。従来の最速展開手法に比べて2.5～1万1000倍の高速化が見込めるとしている。 ハフマン符号は、可変長符号を使って全体のデータ量を小さくするデータ圧縮アルゴリズム。より多く出現するデータ（バイト記号）に対して、より短いビット長の符号を割り当てる。「JPEG」や「ZIP」などの圧縮技術にも利用されている。 圧縮の並列化はできていたが、展開処理の並列化が困難だった プロセッサは単一コアの処理性能が頭打ちになっており、マルチコア化など並列化によって全体の処理性能を高める必要がある。だがハフマン符号には、圧縮処理時には並列化が比較的容易なのに対して、展開処理時の並列化が難しいと

[dekaino]

めちゃくちゃラッキーなケースで11000倍

[JULY]

あくまで、「ギャップ」を示すデータを付加すれば、GPU を使うような並列計算が可能になる、という話で、既存データの展開は対象外。ただ、動画ストリーミングとかで、受像装置側の負荷軽減に使われるかも。

[deep_one]

「データ圧縮時に、各セグメントに2つのセグメントにまたがったデータの次のデータが始まる位置（ギャップ）を記録する」新規プロトコル用か。