だいぶ前、
バンディング低減フィルタをSIMDを使って高速化した。だいぶんと速くなったのでもういいかなと思っていたのだけど、さらに速くするネタを思いついたので更新。
だいたい1.3～1.8倍ぐらい速い。
画像処理系のフィルタは1要素のサイズが小さいのもあって、整数SIMD化するとだいぶ速くなる。そうすると、だんだん相対的に演算よりメモリアクセスのほうが重い、という感じになってきて、速度があげにくくなってしまう。下手をすると演算を増やしてでもメモリアクセスを減らしたほうがいいなどという、なにをやっているのか意味の分からない状態になってしまう。(実際バンディング低減の高速化はそんな感じ)
こういう状態の中でさらに高速化しようとすると、もはや演算の中身はどうでもよくて、処理中のメモリアクセスのパターンを把握して、なんとかそれを減らせないか、もしくはキャッシュヒットさせるかということが大切になる。
バンディング低減フィルタのsample=1の時、あるピクセルの処理に必要なデータは下の図のような感じで、自分のピクセル(オレンジ)と、rangeの範囲内でランダムに決まる2ピクセル(ピンク)となっている。
フレームのピクセルデータのメモリ上の並びは、横方向にまずは並べていく方式なので、縦方向にずれているピクセルはメモリ上では非常に遠い。このため、参照範囲が縦方向にかなり広い可能性がある(ここでは上下にそれぞれrange分だけ離れている可能性がある)というのはかなり厄介になる。
これまでのバンディング低減フィルタの処理は、フレームを下の図のように分割したうえで各スレッドに割り当て、各スレッドはフレームデータのメモリ上の並びに沿って、まずフレームを横方向に処理していって、1行終了したらもとに戻って次の行の処理を始めるというものだった。
この処理の順序では、横方向に広い範囲のデータを一気に処理するため、キャッシュにも横方向に広い範囲のデータを取り込んでしまう。AviutlのYC48はわりかし重めのフォーマットなので、fullHDだと1行が約12KBにもなる。HyperThreadだとすると1スレッドが使えるのは半分だとして、L1キャッシュ(32KB)には1行分程度しか乗らないのでまあ期待しないとしても、L2(256KB)にも10行程度しか乗らない。一方、rangeは30などに設定することが多いので、上下の全60ライン分の範囲が参照される可能性があり、これに対してL2のキャッシュ量256KB/2=10行分というのはけっこう足りないことが分かる。このため、range内のピクセルをランダムに参照するとき、L2キャッシュミスしてしまう確率がかなり高いんじゃないかなあ、ということになる。
そこで、処理順を変更することを考える。
フレームを処理する際に、一気に横方向に処理してしまうのではなく、フレームをいくつかのブロックに分解し、ブロックごとに処理していくことを考える。こうすると、キャッシュに取り込む横方向のデータ量を抑えられ、縦(行)方向のデータもある程度キャッシュに載せておけるようになるかもしれない。ブロック処理中にはブロック周辺のデータがキャッシュにあるので、L2あたりのキャッシュヒット率が上がるかなあ、と期待できる。L1はちょっと少なすぎるので、ここではまあ、L3ヒットになってしまっていたものがL2ヒットになればいいかなあ、ぐらいのイメージ。
横を8分割、縦を5分割する例。
このとき、実際にどのくらいのブロックサイズが良いかはよくわからないので、実際にブロックサイズを変えて、fullHDのフレームの平均処理時間を計ってみた。CPUによって効果が変わる可能性があるので、いくつかのCPUで測定してみた。
比較した環境はこんな感じ。
| CPU | i7 5960X | i7 6700K | i7 4770K | i7 4610Y | N3150 |
| コア数 | 8C/16T | 4C/8T | 4C/8T | 2C/4T | 4C/4T |
| CPU世代 | Haswell | Skylake | Haswell | Haswell | Airmont |
| Coreクロック | 4.2GHz | 4.3GHz | 3.8GHz | 1.2-2.9GHz | 2.08GHz |
| Uncoreクロック | 3.6GHz | 4.1GHz | 3.8GHz | ? | - |
| L1キャッシュ | 32KBx8 | 32KBx4 | 32KBx4 | 32KBx2 | 24KBx4 |
| L2キャッシュ | 256KBx8 | 256KBx4 | 256KBx4 | 256KBx2 | 1MBx2 |
| L3キャッシュ | 20MB | 8MB | 8MB | 4MB | - |
| メモリ | DDR4-2400 | DDR4-2933 | DDR3-2400 | DDR3-1600 | DDR3-1600 |
| OS | Win10 x64 | Win10 x64 | Win10 x64 | Win10 x64 | Win10 x64 |
この環境で、縦横それぞれのブロックの数を変えながら、fullHD (1920x1080)のフレームを処理したときの平均処理時間(単位:ms)を図って、エクセルで表にしてみた。
まず i7 5960X。赤枠のところが従来のバージョンで、横方向にはブロック分割せず、縦方向にはスレッド数分分割するというもの。横方向の分割数を増やしていくと、あるところまでは高速化していくことが分かる。縦方向の分割数はスレッド数以上には増やさないほうがいいみたい。
i7 5960X 1080p 1フレームの平均処理速度 (単位:ms)
次に6700K。赤枠のところが従来のバージョン。やはり、横方向の分割数を増やしていくと、あるところまでは高速化する。従来(赤枠)と比べると、高速化率はかなり大きい。
i7 6700K 1080p 1フレームの平均処理速度 (単位:ms)
次に4770K。やはり、横方向の分割数を増やしていくと、あるところまでは高速化する。これも従来(赤枠)と比べると高速化率はかなり大きい。
i7 4770K 1080p 1フレームの平均処理速度 (単位:ms)
デュアルコアもちょっと試そうということで4710Y。ところが、やっぱりタブレットなので、どうしても熱の制約にひっかるらしく、結構測定が不安定な様子。それでもなんとなく傾向は見える。
i7 4710Y 1080p 1フレームの平均処理速度 (単位:ms)
最後にCeleron N3150。横方向の分割数を増やしていくと、高速化していくのだが、これまでとはだいぶグラフの傾向が異なっている。というかものすごく遅い…。
Celeron N3150 1080p 1フレームの平均処理速度 (単位:ms)
というわけで、あまり分割数を増やしすぎてもよくないが、横方向の分割数を16ぐらいまで上げるとだいたいどのCPUでもいい感じかな、ということが分かる。縦方向の分割数は並列スレッド数分だけあるといいようだ。
最終的には、解像度がfullHD以外でもうまくいくように、横方向のブロック分割は128ピクセルの大きさ(fullHDだと15分割)、縦方向のブロック分割数はスレッド数分、という風にした。
最後に今回のfullHDでの処理時間(単位:ms)と高速化率をまとめるとこんな感じ。
| i7 5960X | i7 6700K | i7 4770K | i7 4610Y | N3150 |
|---|
| 高速化版+6 | 1.91 | 3.43 | 4.15 | 30.03 | 61.63 |
| 高速化版+7 | 1.51 | 1.90 | 2.53 | 24.60 | 24.48 |
| 高速化率 | x 1.27 | x 1.80 | x 1.64 | x 1.22 | x 2.52 |
6700Kだと1.8倍とかになっていて、それなりに高速化できている。ただ、fullHDより小さい解像度では、ここまで大きな効果は出ない。
というわけで、メモリアクセスのパターンを考慮して、すこし処理順を変えてあげると、キャッシュミスが減ったりで結構速度が変わったりすることがわかった。たぶんL3ヒットがL2ヒットになっただけだと思うんだけど、それでもそれなりに効果はあるようだ。
と、ここまで、高速化した過程を書いてきたのだけど、読み返すと、なんか延々とキャッシュがどうのこうのという話をするという、異常にマニアックな記事になってしまった。申し訳ない…。
バンディング低減 ダウンロード>>ダウンロード (ミラー) >>OneDriveの調子がいまいちの時はミラー(GDrive)からどうぞ。同じものです。ソースはこちら
