圧縮ファイルの展開速度を最大1万倍超高速化するデータ構造を広島大が考案

広島大学は8月31日、富士通研究所と共同で、多くのデータ圧縮方式で採用されている「ハフマン符号」の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案したことを発表した。NVIDAのGPU「Tesla V100」を用いて実験した結果、従来の最速展開プログラムと比較して、2.5倍から1万1000倍の高速化を達成できたとしている。 同成果は、同大学大学院先進理工系科学研究科の中野浩嗣教授らの共同研究チームによるもの。詳細は、2020年8月に開催された国際会議「International Conference on Parallel Processing (ICPP)」において発表され、269件の投稿論文の中から最優秀論文賞に選ばれた。 インターネットを介して多数の画像ファイルや動画ファイルなどを転送したり、また記録メディアに保存したりする際、データの圧縮は誰でも日常的に行っている。そ

[mohno]

多少の無駄が生じるけど、高速化のために並列処理に向くような圧縮形式を考えた、ということか。既存の圧縮形式と互換があるなら役立ちそうではある（が、無駄が生じるなら使われる場面は限られるかもしれん）

[buhoho]

多くの処理が未だにシングルコア前提なんだなあ

[tripleshot]

ゲーム関係でロード＆展開の展開部分が圧倒的に早くなるとすればめっちゃ恩恵ありそう（テクスチャはjpegじゃないから関係ないだろうけど）

[nanakoso]

マルチコア向けの一工夫

[kkobayashi]

並列処理向けの最適化というの、今の時代でもまだ枯れてないのか

[tattyu]

"なぜ圧縮する際は容易なのかは、～略～最終的に連結すれば済むからだ。" 記号ごとにコア割り振って早くなる説明になってなくない？記号ごとだと連結する時ロックかけないとだめだしめっちゃ遅いと思うが。。。

[ROYGB]

説明を読むとそれほどたいしたことない感じもする。今でも音声や映像など部分解凍しながら再生できる圧縮方式はあるし、そういうものと比較して優位性がどの程度あるのか。

[miki3k]

並列処理向けの構造。データ量と計算量はトータルでは増えるはず。

[pmakino]

既存のアルゴリズムに応用できる汎用性があるようで面白そうだね。ギャップ配列の分圧縮率が悪くなるだろうけど、どの程度なのか。

[GARAPON]

なるほど、なるほど、 完全に理解したわ

[quabbin]

論文読んだ。1コードブロックあたり(例えば256bit)、4bitの冗長ビットを付け加えることで、ビット幅の確認を簡単にする機構。オーバーヘッドは0.5%～2%の間くらい。と。が、精査しないと使えるかすぐには判定がつかない。

[chimerast]

ファイルや通信の圧縮については、ストレージやネットワーク帯域の方がボトルネックになる気がするので、OSのメモリデータの圧縮とかで使われるようになるのかね。すでに別の形で並列化されているような気もするけど

[tetonamida]

わ

[rti7743]

データ構造を変えないといけないから普及するのには時間がかかりそうだ。使われるとしたら、新しいコーデックとかに使われるんかね。それに、一番時間かかるのは処理ではなくIOだしなあ。

[habarhaba]

難しい問題を簡単に解くのは良い研究だと思う

[orisaku]

ネットは広大だわ

[rryu]

ハフマン符号の複合処理をブロック単位で並列化しようとしてもブロック境界に符号の境界が来るとは限らないのでできないが、符号境界のヒントを付ければそれを使って並列化できると。

[zakkie]

“7.4倍”は分かるんだけど、"1万1000倍の高速化”ってなんだよ。いったい何と比較してるんだ。

[airj12]

よくわかんないけど展開結果を書き込まれるストレージ側が辛そう

[hidea]

コアどんどん増えてるから積もり積もるほどに効果は大きそう。

[ardarim]

圧縮率を多少犠牲にしてギャップ分をパディングにして完全にセグメントまたがりを無くした方が効率的だったりしないのかな

[sugawara1991]

経路を並列化できるとしてボトルネックは結果をシリアル化するための待ち合わせだったりするけど大丈夫なのかな。キューのロックフリー化でスケールするってレポート読んだこともあるけど

[nakag0711]

まあ理論上圧縮性能では算術圧縮に負けるから最近はハフマンはどうなんだろね

[Nyoho]

なるほど伸張時にも並列化できるように継ぎ目部分を工夫しただけなのに、今の時代には効果は絶大ですね。

[kazyee]

(圧縮)"処理時間の増加は4～18%程度であるという。(中略)同様に、ギャップ配列の分だけ圧縮データのサイズも増加してしまうが、増加量は0.4～1.5%。"

[tettekete37564]

最近のゲームのロード時間って圧縮ファイルの展開時間の気がしてならないので期待

[hanakoume302]

4コマ漫画にしてくれないと読めませんよ

[samu_i]

給料を１万倍にしてほしい。

[agricola]

ハフマン符号化にもまだまだ前人未踏の沃野があったのだなぁ。とりあえずは普通のマルチコアCPUで恩恵が享受できるようになると嬉しいかと。

[peketamin]

一万倍やぞ！

[technerd]

アツい展開だ

[z1h4784]

PS5もこういうの使ってるんじゃなかったっけ？超高速ロード技術の肝だったはず

[Fushihara]

圧縮率を1万倍にしろ

[tsubosuke]

“2.5～1万1000倍の高速化を達成” 差がありすぎるのなんでなんだ

[a8888]

GPUでの圧縮展開処理についてか。

[pendamadura]

並列処理するときにデータを区切りやすくしたってことかしら

[at_yasu]

なるほどなー（さっぱりわからん） / https://jnamaral.github.io/icpp20/slides/Yamamoto_Huffman.pdf これ読まんとわからんかった…

[mangakoji]

再読可能化符号の1%増が許される時代が来るとは…そっちのほうが驚きだわ。