広島大学、ハフマン符号の処理を高速化するデータ構造「ギャップ配列」を考案 66
ストーリー by nagazou
デジカメ写真とかによさげ 部門より
デジカメ写真とかによさげ 部門より
広島大学の中野浩嗣教授らの研究チームは8月31日、GPUによる「ハフマン符号」の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案したそうだ（広島大学リリース[PDF]、マイナビ）。
ハフマン符号はJPEGやZIPなど多くのデータ圧縮で使われている符号化方式。NVIDAのGPU「Tesla V100」を用いた実験では、10種類の様々な種類のファイルを用意し、既知の最速プログラムとギャップ配列用に構築したプログラムを用いて比較したという。その結果、従来の展開プログラムと比較した場合、圧縮処理で2.5～7.4倍、また展開処理については、2.5倍から最大1万1000倍もの高速化が達成できたとしている。
ちなみにこの論文は、8月に開催された第49回並列処理に関する国際会議（ICPP）で最優秀論文賞に選ばれたとのこと。
ハフマン符号はJPEGやZIPなど多くのデータ圧縮で使われている符号化方式。NVIDAのGPU「Tesla V100」を用いた実験では、10種類の様々な種類のファイルを用意し、既知の最速プログラムとギャップ配列用に構築したプログラムを用いて比較したという。その結果、従来の展開プログラムと比較した場合、圧縮処理で2.5～7.4倍、また展開処理については、2.5倍から最大1万1000倍もの高速化が達成できたとしている。
ちなみにこの論文は、8月に開催された第49回並列処理に関する国際会議（ICPP）で最優秀論文賞に選ばれたとのこと。
アルゴリズム単体で見ればちょっと遅くなるけど (スコア:2)
ついでに圧縮率もちょっと悪くなるけど、
並列処理できる分、GPUで高速化できますよって話ですよね。
大量の画像を同時並列的に処理する場合でも高速化できるのでしょうか
Re:アルゴリズム単体で見ればちょっと遅くなるけど (スコア:1)
可逆圧縮動画コーデック UtVideo の作者の人 [twitter.com]が、
と、GPUでハフマン展開を並列処理することそのものに否定的で一蹴してますね。
Re: (スコア:0)
その人が否定しているのは「UtVideoで使うには」という部分だけでは
Re:アルゴリズム単体で見ればちょっと遅くなるけど (スコア:1)
こっちはたしかにUtVideo限定のものですが、元コメの質問「大量の画像を同時並列的に処理する場合」にも該当。
こっちは一般論としてハフマン復号をGPU処理することを否定しているかと。
Re: (スコア:0)
> 別にそんなことしなくても全体をコア数で分割して並列処理したらコア数倍速くなるという自明な高速化を昔から適用できている
展開時(ハフマン符号のデコード)にコア数分割するのがそもそも普通のデータ構造だと厳しいって論文だけど、昔から適用出来てるってほんと？
# 圧縮時(ハフマン符号のエンコード)ならそら昔からやってるよね
Re:アルゴリズム単体で見ればちょっと遅くなるけど (スコア:2)
元コメは、動画コーデックつまり独立した複数のハフマン符号列をデコードする場合の話で、
その場合は符号列ごとにコアを割り当てればいい、という話でしょ。
一つの長大なハフマン符号列をデコードする場合、つまり「すごくばかでかいgzipファイルを展開する」とかいった場合には
今まで並列化できなかったのが本手法で並列化できるようになるわけですし、
今後の展開としてgzipへの組み込みを挙げられてますね。
Re: (スコア:0)
そのツイートは「元コメ」(大量云々)とは無関係にコア数分割と言ってる様に見えます。
レポートの内容を見れば主題は単一ソースのデコード時なのは明確です。
これで、エンコード時の話や、複数ソースの同時デコードの話してるならかなり残念ですね。
Re: (スコア:0)
これ語弊があると思うんだけど、gzipがストリームで頭から展開して中味が読めるってことは、ファイルがでかくても符号列がでかいわけじゃないんじゃないかな。実用上はどっかに仕切りを置いて切ってるんでしょ。
もちろん、大きく見た方が圧縮には有利なんだろうけど、巨大なメモリ展開まで含めて考えると実用的じゃないんでは。
Re: (スコア:0)
並列処理したらコア数倍速くなるというのなら並列度が桁違いのGPUで処理したほうが圧倒的に速くなるのでは。
Re: (スコア:0)
UtVideoで使うのは向かないでしょうが、これは肥大化するGPUのテクスチャ圧縮の分野では使えそうですね。
最近のゲームは平気で数GB超えるテクスチャバッファ使いますし、GPU内で処理完結するならCPUとの転送も関係ないし。
今でも圧縮は普通に使われてますが、圧縮展開の速度が上がれば使える範囲が増えて嬉しそう。
Re: (スコア:0)
性能を追求したファイル圧縮方式は複数のファイルを一個にまとめたうえで圧縮するからファイルの数は問題にならないと思う。
Re: (スコア:0)
「アルゴリズム単体で見ればちょっと遅くなるけど」というものではないでしょう。
ギャップ配列という、本来デコードに必要ない（なくてもデコード可能な）ヒント情報を付け加えることによってデコードを高速化する、というものではないかと。
ただ、「圧縮も高速化される」という点が分からないですね。
（提示されているリリース文からは読み取れない）
ふつーに (スコア:2)
GPGPUでJPEGなエンコーダを作る時等で、誰でも行っていた手なので、何を今更感。
Re:ふつーに (スコア:4, 参考になる)
エンコーダではなくデコーダを高速化できるという技術ですね
圧縮はそもそも今までも並列処理できる
展開は符号長が可変なので頭から順に展開していかないとどこからどこまで符号かわからない＝並列処理に向かない
それなら事前にそれぞれの符号の目印を埋め込めば良いのでは？
という理屈自体は割と単純なように思います
動画圧縮でいえばずっとBフレームしか存在しなかったものにGOPという概念を追加するような
Re: (スコア:0)
圧縮の方はおまけみたいなもので、展開を高速化できたというのが核心じゃないの
しかもGPUを使用する既知の最速デコーダと比較して
Re: (スコア:0)
誰でもやってるなら、おれおれライブラリなりRedditなりで公開してる人もいるよね？
例えばどれ？
Re: (スコア:0)
おまえは本当に「Hello, world!」がほしいのか？
Re: (スコア:0)
うん欲しい。
誰でもやってるハロワレベルの話なら腐るほど記事もあるよね、きっと。
それならちょっと検索すりゃ一瞬で出せるっしょ？
何で勿体ぶってるの？
Re: (スコア:0)
動画エンコーダの老舗、FFmpegのソースをgitから持ってくればよかろ？
っ https://github.com/FFmpeg/FFmpeg [github.com]
Re: (スコア:0)
これデコーダの話なんですけど？(爆笑)
Re: (スコア:0)
「誰でも行っていた手」なのはエンコーダの話ですよ。
文字は読めても意味は読めないんですね。
Re: (スコア:0)
> 「誰でも行っていた手」なのはエンコーダの話ですよ。
はい、その通りだと思います。
つまり、この論文はデコーダの話だと理解できずエンコーダの話ししちゃうくらい理解が及んでないと言うことです。(爆笑)
一行コメントくらいはなんとか読めても前後を含めるとなると読めないんですね。
Re: (スコア:0)
> 「誰でも行っていた手」なのはエンコーダの話ですよ。
それなら、エンコードする時にエンコードにはクソの役にも立たないギャップ配列みたいなのを一緒に作るのを、誰でも行っていた手だと思うくらい君は技術音痴と言うことになりますね。
Re: (スコア:0)
新規なのはデータ構造なわけだけど、このデータ構造を採用したものが既にあると言う話？
なにかがおかしい (スコア:2)
符号の連結は、圧縮・伸長の双方で最も高速化が難しい処理なのに。
Re:なにかがおかしい (スコア:2)
x 符号の連結
o ビット列の連結
Re:なにかがおかしい (スコア:2)
あと、処理時間の記述は有るけど、圧縮率について書いてないのはなぜなのかなあにやにや。
Re: (スコア:0)
> 同様に、ギャップ配列の分だけ圧縮データのサイズも増加してしまうが、増加量は0.4～1.5%。デメリットと呼ぶほどでもない増加である。
>にやにや。
Re:なにかがおかしい (スコア:2)
https://jnamaral.github.io/icpp20/slides/Yamamoto_Huffman.pdf [github.io]
普通のハフマン符号のデータ量に、開始位置のズレを示すデータ(ギャップ配列)を加えただけに見える。
各スレッド毎に伸長して、SM単位で合わせてデータ長を計算して、後のアドレスに書込むSMにデータ長を伝播する事になるけど、それでも良さげな性能が出るのか。
Re:なにかがおかしい (スコア:1)
高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。
だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。
適応型には向かない（キリトリ線だけでなくその位置での辞書がないといけない）ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。
ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。
Re:なにかがおかしい (スコア:2)
メモリには32bit単位で書き込みたいのに、伸長後の断片は8bit単位なので、連結する必要が有るが、その処理が重そう。
そこを圧縮率を犠牲にして伸長後の断片を32bit単位にしていると思ったけど、そうでもなかったという。
Re:なにかがおかしい (スコア:2)
伝播とは言うものの、個別に足し込むだけだから問題無いのか。
Re: (スコア:0)
「圧縮処理では」、つまり限定することで何かと比較してる
極普通のSEの常識で読めば展開と比べるだろうと容易に分かる
で、まさに続く文章にそう書いてあるね
> これが、ハフマン符号の展開処理が並列処理に向かない理由だ。
コンセプトの段階？ (スコア:2)
新しいデータ構造「ギャップ配列」と言ってるんだけど、
と書いてあるし、実際にどのようにして利用するつもりなのかがよく分からなかった。
互換性と言う意味では gzip のデータ構造自体をいじるわけにも行かないだろうし、別ファイルとして添付するのだろうか？
各ハフマン符号の先頭位置が分かればいいと言う話なので、圧縮済みのデータについても適当に同期位置を別ファイルで後付けすれば良いはずなんだけど、そういう意味では並列化を効率的に行うための一種のキャッシュかなという気もする。
発表スライド
https://jnamaral.github.io/icpp20/slides/Yamamoto_Huffman.pdf [github.io]
uxi
Re:コンセプトの段階？ (スコア:2)
その意味で
・別ファイルで後付け
・一種のキャッシュ
って書いてるんだけど伝わらなかったんですね。
uxi
10種類の様々な種類のファイル (スコア:0)
10==様々 ってことですかね？？
Re:10種類の様々な種類のファイル (スコア:3, 参考になる)
論文は普通に Web で公開 [acm.org]されており、そこに細かい記載がありますよ
・text（Collection of sacred text）
・xml（Wikipedia dump file）
・exe（Tarred executables of Mozilla）
・image（Medical magnetic resonance image）
・database（Chemical database of structures）
・text（50th Mersenne number）
・bin（ The SAO star catalog）
・html（The 1913 Webster Dictionary）
・src（Linux kernel 5.2.4）
・text（Never self-synchronizes）
聖書のように容量の軽いものから、Linux ソースのような重い物まで効果が出ていて凄いですね
軽い場合なんかは、GPU へのデータ転送や初期化のコストが結構重くて、CPU が勝つんじゃないかと思っていました
Re: (スコア:0)
広島大のPDFによると10個の様々なタイプのファイルとあるので、様々なフォーマットのファイル10個をまとめて圧縮したり解凍する性能比較を行ったように読めます。
結構いまさら感 (スコア:0)
1952年に開発されて半世紀以上使われている符号化に、今でもまだアルゴリズムの革新とかありえるんだ。
超高速ソーティングとか研究している人もいるのかな。
Re: (スコア:0)
ソートは下界があって、タイトバウンドかそれに近いアルゴリズムもあるから。
Re: (スコア:0)
ソートアルゴリズムも数学的なオーダーは変わらなくても並列化が可能かどうかで現実的な速度がまったく異なるものを開発する余地は十分にありそう
Re: (スコア:0)
そーとー余地があるのは素晴らしい
Re: (スコア:0)
並列化に向いてない処理というのは並列度が高くなればなるほど足を引っ張って全体を台無しにしてしまうのでチューニングが重要になります。
Re: (スコア:0)
アルゴリズムや基礎理論が面白いのは、文字通り世紀を越えたこういう発展があること
機械学習なんかもライブラリをいじっているだけじゃ5年持たないけど
学習アルゴリズムの理論である「計算論的学習」なんてのは数十年単位
もちろん年単位でも発展しているから面白い
動的ハフマンコード (スコア:0)
入力列に応じて辞書を更新するタイプの動的ハフマン符号でもうまく動くのかな？
そもそもこの場合並列処理が無理な気がするけど、今の圧縮処理のトレンドでは使われてないのかな？
Re: (スコア:0)
入力列に応じて辞書を更新するタイプの動的ハフマン符号でもうまく動くのかな？
仕分けが必要な処理が入ると
CPUの処理待ちでGPUが暇しちゃうかもね
Re: (スコア:0)
先行するデコード結果を参照することになるのでむりぽ。
この発表、将来の展望でzipとかも入れてんだけど、そいつらのスライド辞書とかも同じく無理。
並列化の分割点での辞書内容を独立に復元するないしはリセットする事ができればいいけど、
数百バイト程度毎にそんなのやったら圧縮率が壊滅するので多分意味はない。
これが成立するのは、
入力の符号境界と出力のオフセットくらいしかシークで欠落する情報がないハフマン符号化で、
出力のオフセットを後で適当にマージすることで省略し符号境界のビット表現を短縮できたから。
より大量のデータを抱えた辞書が相手ではシークに必要なヒントが大きくなりすぎる。
素直にGPGPUで扱うデータをハフマンのみで圧縮してオンメモリないしオンノードで扱うって方向のほうが使い勝手良いと思う。
ワーストケース (スコア:0)
リリースを読んだ感じでは、最大符号長によってギャップ配列のビット数が変わるよね。
ハフマン木のバランスが悪い場合、ギャップ配列が相当おデブになるんじゃ……。
まあ、「バランスが悪い＝データが偏っている」ということなので、圧縮前のサイズを基準にすれば比較的軽微、ということかもしれないけど。
ワーストケースを示してほしいところ。
Re: (スコア:0)
ハフマン辞書のサイズなんてたかが知れているので、ワーストケースでもGPUの手に余るようなものになるとは思えないなぁ
Re: (スコア:0)
いや、処理速度とかではなく、圧縮率の方です。
例えば、8ビットのデータをハフマン符号化したとき、ワーストケースでの最大符号長って256ビットになるんじゃなかったっけ。
だとすると、1セグメントにつき8ビットのギャップ値が必要になるはずなので、そこそこ容量を取りそう。