• 多くのデータ圧縮方式で用いられているハフマン符号の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案しました。
• 圧縮処理時にこのギャップ配列を付加することにより、ハフマン符号の並列展開処理を大幅に高速化することが可能になります。
• GPU向けに「ギャップ配列」を含めたさまざまな高速化手法を開発・適用した結果、同じGPUを用いた従来の最速展開手法より、2.5倍から11000倍の高速化が達成できました。

広島大学大学院先進理工系科学研究科の中野浩嗣教授らの研究チームは、株式会社富士通研究所と共同で、 GPUによるハフマン符号の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案しました。さまざまなファイルに対してNVIDIA社のTesla V100 GPUを用いて実験した結果、従来の最速展開プログラムに比べ、2.5倍から11000倍の高速化が達成できました。

本研究成果は2020年8月開催の国際会議International Conference on Parallel Processing (ICPP)において発表し、その結果269件の投稿論文の中から最優秀論文賞(Best Paper Award)に選ばれました。

(1) GPU
Graphics Processing Unitの略で、本来はグラフィックス専用処理のための集積回路ですが、グラフィックス以外の汎用計算用を行えるよう拡張されており、計算処理能力の高さから、多くのスーパーコンピュータに搭載されています。

(2) ハフマン符号
1バイト(8ビット)の記号を可変長のビット列の符号に置き換える変換表(コードテーブル)を用いて、バイト記号列をビット列(可変長符号列)に変換するデータの符号化方法。頻出するバイトに対して短いビット列を割り当てることにより変換後のビット列の長さを短くすることができる。もっとも基本的なデータ圧縮手法であり、多くのデータ圧縮方式(gzip, zip, png, jpg等)に組み込まれている。

• 国際会議名: International Conference on Parallel Processing (ICPP) 2020
• 論文タイトル: Huffman Coding with Gap Arrays for GPU Acceleration
• 著者名: Naoya Yamamoto, Koji Nakano, Yasuaki Ito, and Daisuke Takafuji (Hiroshima University)
             and Akihiko Kasagi and Tsuguchika Tabaru (Fujitsu Laboratories Ltd.)
• DOI: 10.1145/3404397.3404429
• 受賞: ICPP 2020 Best Paper Award (269件投稿中1位)