アカウント名:
パスワード:
ハフマン符号の圧縮処理では各バイト記号を可変長符号に変換し、連結すればよいだけなので並列化は容易です。
符号の連結は、圧縮・伸長の双方で最も高速化が難しい処理なのに。
x 符号の連結o ビット列の連結
あと、処理時間の記述は有るけど、圧縮率について書いてないのはなぜなのかなあにやにや。
> 同様に、ギャップ配列の分だけ圧縮データのサイズも増加してしまうが、増加量は0.4~1.5%。デメリットと呼ぶほどでもない増加である。>にやにや。
https://jnamaral.github.io/icpp20/slides/Yamamoto_Huffman.pdf [github.io]
普通のハフマン符号のデータ量に、開始位置のズレを示すデータ(ギャップ配列)を加えただけに見える。各スレッド毎に伸長して、SM単位で合わせてデータ長を計算して、後のアドレスに書込むSMにデータ長を伝播する事になるけど、それでも良さげな性能が出るのか。
> GPGPUでJPEGなエンコーダを作る時等で、誰でも行っていた手なので、何を今更感。
高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。
だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。
適応型には向かない(キリトリ線だけでなくその位置での辞書がないといけない)ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。
ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。
メモリには32bit単位で書き込みたいのに、伸長後の断片は8bit単位なので、連結する必要が有るが、その処理が重そう。そこを圧縮率を犠牲にして伸長後の断片を32bit単位にしていると思ったけど、そうでもなかったという。
伝播とは言うものの、個別に足し込むだけだから問題無いのか。
圧縮時に個々に並列処理されるデータの長さを32bitの倍数にしておけば伸長後もそうなるはずなのでビット単位の操作とか必要ないはず。むしろ圧縮時に並列処理されたデータが可変長ビットになるのでそれらを繋げるときにビット操作が必要になるかも知れないが、繋げる箇所の数はデータ量に対して少ないし、そもそも連結処理にはひたすらシフトする必要があるけどハッシュなんかに比べると重くはない(おそらくCPUよりメモリアクセスがボトルネックになる)。
あるいはデータフォーマットを工夫することでそれも避けられる。というか並列処理単位ごとにヘッダとデータという構造にして、ヘッダにビット長を入れておいて末尾のキリの悪い半端bitを捨てることにすれば、ギャップ配列もいらなくなるかもね。この場合は既存のデータフォーマットの拡張ではできないけれども。
「圧縮処理では」、つまり限定することで何かと比較してる極普通のSEの常識で読めば展開と比べるだろうと容易に分かるで、まさに続く文章にそう書いてあるね
> これが、ハフマン符号の展開処理が並列処理に向かない理由だ。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
日本発のオープンソースソフトウェアは42件 -- ある官僚
なにかがおかしい (スコア: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: (スコア:0)
> GPGPUでJPEGなエンコーダを作る時等で、誰でも行っていた手なので、何を今更感。
Re:なにかがおかしい (スコア:1)
高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。
だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。
適応型には向かない(キリトリ線だけでなくその位置での辞書がないといけない)ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。
ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。
Re:なにかがおかしい (スコア:2)
メモリには32bit単位で書き込みたいのに、伸長後の断片は8bit単位なので、連結する必要が有るが、その処理が重そう。
そこを圧縮率を犠牲にして伸長後の断片を32bit単位にしていると思ったけど、そうでもなかったという。
Re:なにかがおかしい (スコア:2)
伝播とは言うものの、個別に足し込むだけだから問題無いのか。
Re: (スコア:0)
圧縮時に個々に並列処理されるデータの長さを32bitの倍数にしておけば伸長後もそうなるはずなのでビット単位の操作とか必要ないはず。むしろ圧縮時に並列処理されたデータが可変長ビットになるのでそれらを繋げるときにビット操作が必要になるかも知れないが、繋げる箇所の数はデータ量に対して少ないし、そもそも連結処理にはひたすらシフトする必要があるけどハッシュなんかに比べると重くはない(おそらくCPUよりメモリアクセスがボトルネックになる)。
あるいはデータフォーマットを工夫することでそれも避けられる。というか並列処理単位ごとにヘッダとデータという構造にして、ヘッダにビット長を入れておいて末尾のキリの悪い半端bitを捨てることにすれば、ギャップ配列もいらなくなるかもね。この場合は既存のデータフォーマットの拡張ではできないけれども。
Re: (スコア:0)
「圧縮処理では」、つまり限定することで何かと比較してる
極普通のSEの常識で読めば展開と比べるだろうと容易に分かる
で、まさに続く文章にそう書いてあるね
> これが、ハフマン符号の展開処理が並列処理に向かない理由だ。