超並列システム向け可逆データ圧縮法の提案と実用化

点击翻译按钮获取中文摘要

現在幅広く利用されている可逆圧縮手法は，並列化による高速処理を前提に設計されておらず，本質的に逐次処理が必要なものが多い．そのため，GPUが身近にあるにもかかわらず，データの可逆圧縮の処理にその高い計算能力が活用されていない．本研究の目的は，GPUをターゲットに並列化による高速化が可能な効率良い可逆圧縮法を提案することである．本年度は，昨年度に開発したdeflateアルゴリズムの並列実行処理を，最新のGPU向けに最適化を行った． deflateアルゴリズムはgzip，zip等で幅広く用いられており，圧縮性能が高いため，もっともポピュラーな可逆のデータ圧縮方式である．deflate圧縮では，前方部分を辞書として用い，（オフセット，長さ）のペアの値に変換する．長さが長いほど，圧縮率が高くなる．さらに，オフセットと長さをハフマン符号により圧縮する．処理が逐次的なため，GPUによる並列化が困難であった．Deflateで用いる辞書をGPUにメモリ上に実装する際のデータ構造をGPUによる並列処理向けに改造した．また，理論的には，辞書のサイズを小さくしたり，ブロックサイズを小さくすると圧縮率が悪化するが，この悪化がほとんどおきないようにそれぞれのサイズを巧妙に設定する方法を開発した．また，CUDAブロックへのスレッドの分割サイズについてSKSS(Single Kernel Soft Synchronization)法が効率よく動作するよう最適化を行った．GPUの通常のプログラムは，バリア同期のために，複数のカーネルに分割し，このカーネルが逐次的に実行される．カーネル起動のオーバーヘッドは大きく，それが性能低下の大きな原因となる．SKSS法では，複数カーネルへの分割を避けて，１つのカーネルで切れ目なく並列処理を行うことができる．さらには，具体的なGPUによる並列処理への適用を試みた．