パスワードを忘れた? アカウント作成
14292351 story
テクノロジー

広島大学、ハフマン符号の処理を高速化するデータ構造「ギャップ配列」を考案 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)で最優秀論文賞に選ばれたとのこと。
  • ついでに圧縮率もちょっと悪くなるけど、
    並列処理できる分、GPUで高速化できますよって話ですよね。

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

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

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

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

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

      • by Anonymous Coward

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

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

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

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

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

          • by Anonymous Coward

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

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

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

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

              • by Anonymous Coward

                そのツイートは「元コメ」(大量云々)とは無関係にコア数分割と言ってる様に見えます。
                レポートの内容を見れば主題は単一ソースのデコード時なのは明確です。
                これで、エンコード時の話や、複数ソースの同時デコードの話してるならかなり残念ですね。

              • by Anonymous Coward

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

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

      • by Anonymous Coward

        並列処理したらコア数倍速くなるというのなら並列度が桁違いのGPUで処理したほうが圧倒的に速くなるのでは。

      • by Anonymous Coward

        UtVideoで使うのは向かないでしょうが、これは肥大化するGPUのテクスチャ圧縮の分野では使えそうですね。
        最近のゲームは平気で数GB超えるテクスチャバッファ使いますし、GPU内で処理完結するならCPUとの転送も関係ないし。
        今でも圧縮は普通に使われてますが、圧縮展開の速度が上がれば使える範囲が増えて嬉しそう。

    • by Anonymous Coward

      性能を追求したファイル圧縮方式は複数のファイルを一個にまとめたうえで圧縮するからファイルの数は問題にならないと思う。

    • by Anonymous Coward

      「アルゴリズム単体で見ればちょっと遅くなるけど」というものではないでしょう。
      ギャップ配列という、本来デコードに必要ない(なくてもデコード可能な)ヒント情報を付け加えることによってデコードを高速化する、というものではないかと。

      ただ、「圧縮も高速化される」という点が分からないですね。
      (提示されているリリース文からは読み取れない)

  • by miyuri (33181) on 2020年09月07日 12時47分 (#3883952) 日記

    GPGPUでJPEGなエンコーダを作る時等で、誰でも行っていた手なので、何を今更感。

    ここに返信
    • Re:ふつーに (スコア:4, 参考になる)

      by Anonymous Coward on 2020年09月07日 13時32分 (#3883966)

      エンコーダではなくデコーダを高速化できるという技術ですね

      圧縮はそもそも今までも並列処理できる
      展開は符号長が可変なので頭から順に展開していかないとどこからどこまで符号かわからない=並列処理に向かない
      それなら事前にそれぞれの符号の目印を埋め込めば良いのでは?

      という理屈自体は割と単純なように思います
      動画圧縮でいえばずっとBフレームしか存在しなかったものにGOPという概念を追加するような

    • by Anonymous Coward

      圧縮の方はおまけみたいなもので、展開を高速化できたというのが核心じゃないの
      しかもGPUを使用する既知の最速デコーダと比較して

    • by Anonymous Coward

      誰でもやってるなら、おれおれライブラリなりRedditなりで公開してる人もいるよね?
      例えばどれ?

      • by Anonymous Coward

        おまえは本当に「Hello, world!」がほしいのか?

        • by Anonymous Coward

          うん欲しい。
          誰でもやってるハロワレベルの話なら腐るほど記事もあるよね、きっと。
          それならちょっと検索すりゃ一瞬で出せるっしょ?
          何で勿体ぶってるの?

          • by Anonymous Coward

            動画エンコーダの老舗、FFmpegのソースをgitから持ってくればよかろ?
            https://github.com/FFmpeg/FFmpeg [github.com]

            • by Anonymous Coward

              これデコーダの話なんですけど?(爆笑)

              • by Anonymous Coward

                「誰でも行っていた手」なのはエンコーダの話ですよ。
                文字は読めても意味は読めないんですね。

              • by Anonymous Coward

                > 「誰でも行っていた手」なのはエンコーダの話ですよ。
                はい、その通りだと思います。
                つまり、この論文はデコーダの話だと理解できずエンコーダの話ししちゃうくらい理解が及んでないと言うことです。(爆笑)
                一行コメントくらいはなんとか読めても前後を含めるとなると読めないんですね。

              • by Anonymous Coward

                > 「誰でも行っていた手」なのはエンコーダの話ですよ。
                それなら、エンコードする時にエンコードにはクソの役にも立たないギャップ配列みたいなのを一緒に作るのを、誰でも行っていた手だと思うくらい君は技術音痴と言うことになりますね。

    • by Anonymous Coward

      新規なのはデータ構造なわけだけど、このデータ構造を採用したものが既にあると言う話?

  • by miyuri (33181) on 2020年09月07日 18時22分 (#3884231) 日記

    ハフマン符号の圧縮処理では各バイト記号を可変長符号に変換し、連結すればよいだけなので並列化は容易です。

    符号の連結は、圧縮・伸長の双方で最も高速化が難しい処理なのに。

    ここに返信
    • by miyuri (33181) on 2020年09月07日 18時23分 (#3884233) 日記

      x 符号の連結
      o ビット列の連結

    • by miyuri (33181) on 2020年09月07日 18時36分 (#3884244) 日記

      あと、処理時間の記述は有るけど、圧縮率について書いてないのはなぜなのかなあにやにや。

      • by Anonymous Coward

        > 同様に、ギャップ配列の分だけ圧縮データのサイズも増加してしまうが、増加量は0.4~1.5%。デメリットと呼ぶほどでもない増加である。
        >にやにや。

    • by miyuri (33181) on 2020年09月08日 7時35分 (#3884521) 日記

      https://jnamaral.github.io/icpp20/slides/Yamamoto_Huffman.pdf [github.io]

      普通のハフマン符号のデータ量に、開始位置のズレを示すデータ(ギャップ配列)を加えただけに見える。
      各スレッド毎に伸長して、SM単位で合わせてデータ長を計算して、後のアドレスに書込むSMにデータ長を伝播する事になるけど、それでも良さげな性能が出るのか。

    • by Anonymous Coward on 2020年09月08日 0時04分 (#3884448)

      高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。

      だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。

      適応型には向かない(キリトリ線だけでなくその位置での辞書がないといけない)ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。

      ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。

    • by Anonymous Coward

      「圧縮処理では」、つまり限定することで何かと比較してる
      極普通のSEの常識で読めば展開と比べるだろうと容易に分かる
      で、まさに続く文章にそう書いてあるね

      > これが、ハフマン符号の展開処理が並列処理に向かない理由だ。

  • by uxi (5376) on 2020年09月10日 20時32分 (#3886664)

    新しいデータ構造「ギャップ配列」と言ってるんだけど、

    【今後の展開】処理の一部にハフマン符号を含んでいる圧縮方式(gzipなど)に今回開発したギャップ配列を組み込んで、
    https://www.hiroshima-u.ac.jp/system/files/148917/20200831_pr01.pdf [hiroshima-u.ac.jp]

    と書いてあるし、実際にどのようにして利用するつもりなのかがよく分からなかった。

    互換性と言う意味では gzip のデータ構造自体をいじるわけにも行かないだろうし、別ファイルとして添付するのだろうか?
    各ハフマン符号の先頭位置が分かればいいと言う話なので、圧縮済みのデータについても適当に同期位置を別ファイルで後付けすれば良いはずなんだけど、そういう意味では並列化を効率的に行うための一種のキャッシュかなという気もする。

    発表スライド
    https://jnamaral.github.io/icpp20/slides/Yamamoto_Huffman.pdf [github.io]

    --
    uxi
    ここに返信
  • by Anonymous Coward on 2020年09月07日 12時03分 (#3883937)

    10==様々 ってことですかね??

    ここに返信
    • by Anonymous Coward on 2020年09月07日 15時27分 (#3884065)

      論文は普通に 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 が勝つんじゃないかと思っていました

    • by Anonymous Coward

      広島大のPDFによると10個の様々なタイプのファイルとあるので、様々なフォーマットのファイル10個をまとめて圧縮したり解凍する性能比較を行ったように読めます。

  • by Anonymous Coward on 2020年09月07日 12時13分 (#3883938)

    1952年に開発されて半世紀以上使われている符号化に、今でもまだアルゴリズムの革新とかありえるんだ。
    超高速ソーティングとか研究している人もいるのかな。

    ここに返信
    • by Anonymous Coward

      ソートは下界があって、タイトバウンドかそれに近いアルゴリズムもあるから。

      • by Anonymous Coward

        ソートアルゴリズムも数学的なオーダーは変わらなくても並列化が可能かどうかで現実的な速度がまったく異なるものを開発する余地は十分にありそう

        • by Anonymous Coward

          そーとー余地があるのは素晴らしい

    • by Anonymous Coward

      並列化に向いてない処理というのは並列度が高くなればなるほど足を引っ張って全体を台無しにしてしまうのでチューニングが重要になります。

    • by Anonymous Coward

      アルゴリズムや基礎理論が面白いのは、文字通り世紀を越えたこういう発展があること
      機械学習なんかもライブラリをいじっているだけじゃ5年持たないけど
      学習アルゴリズムの理論である「計算論的学習」なんてのは数十年単位
      もちろん年単位でも発展しているから面白い

  • by Anonymous Coward on 2020年09月07日 12時17分 (#3883939)

    入力列に応じて辞書を更新するタイプの動的ハフマン符号でもうまく動くのかな?
    そもそもこの場合並列処理が無理な気がするけど、今の圧縮処理のトレンドでは使われてないのかな?

    ここに返信
    • by Anonymous Coward

      入力列に応じて辞書を更新するタイプの動的ハフマン符号でもうまく動くのかな?

      仕分けが必要な処理が入ると
      CPUの処理待ちでGPUが暇しちゃうかもね

    • by Anonymous Coward

      先行するデコード結果を参照することになるのでむりぽ。
      この発表、将来の展望でzipとかも入れてんだけど、そいつらのスライド辞書とかも同じく無理。
      並列化の分割点での辞書内容を独立に復元するないしはリセットする事ができればいいけど、
      数百バイト程度毎にそんなのやったら圧縮率が壊滅するので多分意味はない。

      これが成立するのは、
      入力の符号境界と出力のオフセットくらいしかシークで欠落する情報がないハフマン符号化で、
      出力のオフセットを後で適当にマージすることで省略し符号境界のビット表現を短縮できたから。
      より大量のデータを抱えた辞書が相手ではシークに必要なヒントが大きくなりすぎる。

      素直にGPGPUで扱うデータをハフマンのみで圧縮してオンメモリないしオンノードで扱うって方向のほうが使い勝手良いと思う。

  • by Anonymous Coward on 2020年09月07日 13時53分 (#3883983)

    リリースを読んだ感じでは、最大符号長によってギャップ配列のビット数が変わるよね。
    ハフマン木のバランスが悪い場合、ギャップ配列が相当おデブになるんじゃ……。
    まあ、「バランスが悪い=データが偏っている」ということなので、圧縮前のサイズを基準にすれば比較的軽微、ということかもしれないけど。
    ワーストケースを示してほしいところ。

    ここに返信
    • by Anonymous Coward

      ハフマン辞書のサイズなんてたかが知れているので、ワーストケースでもGPUの手に余るようなものになるとは思えないなぁ

      • by Anonymous Coward

        いや、処理速度とかではなく、圧縮率の方です。

        例えば、8ビットのデータをハフマン符号化したとき、ワーストケースでの最大符号長って256ビットになるんじゃなかったっけ。
        だとすると、1セグメントにつき8ビットのギャップ値が必要になるはずなので、そこそこ容量を取りそう。

typodupeerror

192.168.0.1は、私が使っている IPアドレスですので勝手に使わないでください --- ある通りすがり

読み込み中...