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

広島大学の教授である中野浩嗣氏らの研究チームは、GPUによるハフマン符号の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案した。従来の最速展開手法に比べて、最大1万1000倍高速化できるという。

[＠IT]

　広島大学大学院先進理工系科学研究科の教授である中野浩嗣氏らの研究チームは2020年8月31日、富士通研究所と共同で、GPUによる「ハフマン符号」の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案したと発表した。従来の最速展開手法に比べて2.5〜1万1000倍の高速化が見込めるとしている。

　ハフマン符号は、可変長符号を使って全体のデータ量を小さくするデータ圧縮アルゴリズム。より多く出現するデータ（バイト記号）に対して、より短いビット長の符号を割り当てる。「JPEG」や「ZIP」などの圧縮技術にも利用されている。

圧縮の並列化はできていたが、展開処理の並列化が困難だった

　プロセッサは単一コアの処理性能が頭打ちになっており、マルチコア化など並列化によって全体の処理性能を高める必要がある。だがハフマン符号には、圧縮処理時には並列化が比較的容易なのに対して、展開処理時の並列化が難しいという課題があった。

　元データをハフマン符号化（圧縮）するには、バイト記号と可変長符号の対応表（コードブック）に従ってバイト記号を可変長符号に変換し、変換した可変長符号を連結する。そのため、元データを複数部分に区切ってそれらを複数のプロセッサコアを使って同時に変換処理し、最終的に連結することで比較的容易に並列化できる。

ハフマン符号の圧縮と展開の処理

　これに対して圧縮データは可変長符号からなっているため、データの途中からではデータ区切りが分からず、展開時には先頭から逐次的に変換する必要がある。展開時に並列化が困難なのは、このためだ。

「セグメント」と「ギャップ」を使って並列化を実現