「広島大学、ハフマン符号の処理を高速化するデータ構造「ギャップ配列」を考案」記事へのコメント

アルゴリズム単体で見ればちょっと遅くなるけど

[Y.Tae (32469)]

ついでに圧縮率もちょっと悪くなるけど、
並列処理できる分、GPUで高速化できますよって話ですよね。

大量の画像を同時並列的に処理する場合でも高速化できるのでしょうか

Re:

[taka2 (14791)]

可逆圧縮動画コーデック UtVideo の作者の人 [twitter.com]が、

別にそんなことしなくても全体をコア数で分割して並列処理したらコア数倍速くなるという自明な高速化を昔から適用できている

GPUに投げるには処理が軽すぎるので、CPUメモリとGPUメモリの間で転送してGPUで処理するよりCPUで全部処理したほうが速い

と、GPUでハフマン展開を並列処理することそのものに否定的で一蹴してますね。

Re:

[Anonymous Coward]

その人が否定しているのは「UtVideoで使うには」という部分だけでは

Re:

[taka2 (14791)]

別にそんなことしなくても全体をコア数で分割して並列処理したらコア数倍速くなるという自明な高速化を昔から適用できている

こっちはたしかにUtVideo限定のものですが、元コメの質問「大量の画像を同時並列的に処理する場合」にも該当。

GPUに投げるには処理が軽すぎるので、CPUメモリとGPUメモリの間で転送してGPUで処理するよりCPUで全部処理したほうが速い

こっちは一般論としてハフマン復号をGPU処理することを否定しているかと。

Re:

[Anonymous Coward]

> 別にそんなことしなくても全体をコア数で分割して並列処理したらコア数倍速くなるという自明な高速化を昔から適用できている
展開時(ハフマン符号のデコード)にコア数分割するのがそもそも普通のデータ構造だと厳しいって論文だけど、昔から適用出来てるってほんと？

# 圧縮時(ハフマン符号のエンコード)ならそら昔からやってるよね

Re:

[taka2 (14791)]

元コメは、動画コーデックつまり独立した複数のハフマン符号列をデコードする場合の話で、
その場合は符号列ごとにコアを割り当てればいい、という話でしょ。

一つの長大なハフマン符号列をデコードする場合、つまり「すごくばかでかいgzipファイルを展開する」とかいった場合には
今まで並列化できなかったのが本手法で並列化できるようになるわけですし、
今後の展開としてgzipへの組み込みを挙げられてますね。

Re:

[Anonymous Coward]

これ語弊があると思うんだけど、gzipがストリームで頭から展開して中味が読めるってことは、ファイルがでかくても符号列がでかいわけじゃないんじゃないかな。実用上はどっかに仕切りを置いて切ってるんでしょ。

もちろん、大きく見た方が圧縮には有利なんだろうけど、巨大なメモリ展開まで含めて考えると実用的じゃないんでは。

Re:アルゴリズム単体で見ればちょっと遅くなるけど

[Anonymous Coward]

> どっかに仕切りを置いて切ってる

まさにそれが従来なかった点。

従来の問題は必ず頭から読まなきゃいけなかったけど、
今回のは途中から読めるようにしたので展開処理を並列化できるようになったと言う話。

予めデータ分割してから圧縮しておけば従来方式でも並列化可能と考えるとイマイチ萌えないけど、
何も考えなくてもgunzipが早く終わりますと言われれば悪くはない。