茂木 和洋 @ まるも製作所

 今回は省略
 初めての方は、#1 の資料を参照

 適応フィルタとは 適応フィルタの問題点（速度面で）
 SIMD比較命令でマスク処理
 ベンチマーク 固定のフィルタではなく、入力値によって処理を変更し、最適な結果を求める
例• 基準値との差異を閾値と比較して、参照画素として使うか使わないかを切り替える• 最小自乗法でフィッティングしてフィルタ係数自体を動的に作成する• 他いろいろ 次のスライドから実際の例で紹介 lennaを素材に使う

 今回はグレースケールで扱います 8bitグレイスケールに、±12のランダムノイズが加算されている場
合について考える

0111012221124211222

101110 左のガウスフィルタをノイズ加算済み画像に適用すると

 ノイズはある程度消えるものの、絵がぼけてしまう
 次のスライドで並べて比較 絵がボケるのは、エッジ部分の輝度値に差が大きいところも考慮せずに畳み込んでいるため
 ノイズは±12なので、一定の閾値を設定し、中央画素との差が閾値を超えた場合は畳み込みに使わなければボケない 前のスライドのアルゴリズムで処理した場合
 次のスライドで並べて表示 判りにくかったかもしれないので
 前スライドは単純な5x5ガウシアンフィル

タ [左] とエッジ考慮5x5ガウシアン [右] 次スライドはノイズ画像 [左] とエッジ考慮5x5ガウシアン [右] を並べて表示 主に、処理負荷に関して
 実際のコードで単純な5x5ガウシアンとエッジ考慮5x5ガウシアンで比較すると




















for (y=0;y<height;y++) {for (x=0;x<width;x++) {w =pr2[x-1]+ pr2[x]+ pr2[x+1];w += pre[x-2] + pre[x-1]*2 + pre[x]*2 + pre[x+1]*2 + pre[x+2];
w += src[x-2] + src[x-1]*2 + src[x]*4 + src[x+1]*2 + src[x+2];
w += nxt[x-2] + nxt[x-1]*2 + nxt[x]*2 + nxt[x+1]*2 + nxt[x+2];
w +=nx2[x-1]+ nx2[x]+ nx2[x+1];
dst[x] = clip_u8((w+16)/32);}
dst += width;
src += src_pitch;pr2 += src_pitch;
pre += src_pitch;
nxt += src_pitch;nx2 += src_pitch;}

単純な5x5ガウシアンの場合






static int thresholding(int val, int center, int threshold) {if (abs(val-center) > threshold) { return center; }return val;}<途中省略>for (y=0;y<height;y++) {for (x=0;x<width;x++) {int center = src[x];w = thresholding(pr2[x-1], center, threshold);w += thresholding(pr2[x],center, threshold);w += thresholding(pr2[x+1], center, threshold);<以降省略>



エッジ考慮ガウシアンの場合

 ループの一番奥に分岐が入る 参照画素毎に処理が切り替わるので、SIMDに向かない 最適化原則

1. ディスクを読むな2. [キャッシュよりも大きな] メモリを読むな
3. 分岐するな
4. 除算するな
5. 乗算するな 最適化原則

1. ディスクを読むな

2. [キャッシュよりも大きな] メモリを読むな
3. 分岐するな
4. 除算するな
5. 乗算するな 今回の適応フィルタならばSIMD化可能

 SIMD比較命令でビットマスクを作り、参照画素を選択すればよい
 制御構造の分岐を除去でき、SIMDで並列処理できるので高速化する

PCMPGTW mm0, mm1 の例
mm00x1000

0x07650x05730x3276mm10x0100

0x04000x10000x4000mm00xFFFF

0xFFFF

0x00000x0000 PCMPGTx, PCMPEQx

は比較を行い、対応レジスタのビットを全て立てたり、全て落としたりする命令







static int thresholding(int val, int center, int threshold) {if (abs(val-center) > threshold) { return center; }return val;}<途中省略>for (y=0;y<height;y++) {for (x=0;x<width;x++) {int center = src[x];w = thresholding(pr2[x-1], center, threshold);w += thresholding(pr2[x],center, threshold);w += thresholding(pr2[x+1], center, threshold);<以降省略>



この処理をSIMD比較命令で8並列処理すると
















;// xmm0 に threshold 設定済み;// xmm1 に 全て 0xffff 設定済み;// xmm2 に center 設定済み;// esi が参照画素アドレス
PMOVZXBW xmm4, [esi]; // WORD変換
MOVDQA
xmm6, xmm4;
PSUBW
xmm4, xmm2; // val-center
PABSW
xmm4, xmm4; // 絶対値に変換
PCMPGTW xmm4, xmm0; // 閾値と比較
MOVDQA
xmm5, xmm4;
PXOR
xmm4, xmm1; // mask 反転
PAND
xmm5, xmm2;
PAND
xmm4, xmm6;
POR
xmm4, xmm5;

 左のコード断片で、centerとvalの選択処
理を8画素並列に実行可能 xmm4に選択後画素が入る 注意事項• PMOVZXBW (BYTE 配列をゼロ拡張してPACKED WORD読み込み) は SSE4.1 の命令• PABSW (PACKED WORD を絶対値変換) は
SSSE3 の命令 VisualStudio 2010 (cl 16.00.30319) の場合 (SandyBridge Core i5 2500K)• C実装 :• SSE4.1 実装 :13.587 sec
1.186 sec

 512x512画像1024回実行の消費時間
 /Ox/Oi /arch:SSE2 /MT を指定

 Intel Compiler XE (icl 12.0.3.175)• C実装 :• SSE4.1 実装 :
 環境は同一

 /fast /MT を指定

2.278 sec
1.186 sec
















$LN1004:
pmovzxbd xmm3, DWORD PTR [eax+edi]$LN1005:
psubdxmm6, xmm3
$LN1006:
movdqaXMMWORD PTR [80+esp], xmm0
$LN1007:pabsd
xmm0, xmm6
$LN1008:
movdqaxmm6, XMMWORD PTR [32+esp]$LN1009:
pcmpgtd xmm0, xmm6
$LN1010:pblendvb xmm5, xmm3, xmm0
$LN1011:
movdqaXMMWORD PTR [96+esp], xmm5

 左は /Fa で確認した

ASM出力の一部
 この程度のコードであれば自動でSIMD化してくれる模様
 DWORDで計算しているので、並列度は手で書いた場合の半分

 Intel Compiler は結構がんばってくれる それでもまだ人間の方が賢い ループの奥の分岐を潰してSIMD化できれば、やらない場合よりも10倍程度速くなる (こともある)

 今回のコード等は次のURIに置いてます。
• http://www.marumo.ne.jp/junk/x86opti/2011_0

1_2nd/x86opti_02_kzmogi.zip

 会場で指摘してもらった以下二点の追加実験結果を記載します• PBLENDVB [SSE4.1] を使った方が、選択処理は楽なのでは• Intel Compiler が WORD 処理をしてくれないのは、stdlib.h の abs() が原因ではないか

CL

ICL

C [OLD]13.5872.278

C [NEW]

29.3912.044

SSE4.1 [OLD]

1.186

1.186

SSE4.1 [NEW]

0.983

0.998

 PBLENDVB でかなりの高速化 abs() 排除でIntel CもWORD処理をしてくれるようになったが、VCがさらに遅くなる やっぱり手で書いた方が速い