«前の日記(2008年07月04日) 最新 次の日記(2008年07月06日)» 編集

ema log


2008年07月05日 [長年日記]

_ [最近]SSE4.1

intel よ、そんなに命令を増やしてどうするんだ。

そんな風に考えていたこともありました。

とりあえず、SSE3, SSE4 の命令よりも SSE4.1 の命令に魅力があります。そんな今日この頃。

# カタンに時間を吸い取られました。

_ [Programming]SSE2 で輝度変換

とりあえず、最近、SSE2で輝度変換するコード書いています。以下を読んで、もっと良い方法があれば、是非教えて下さい。

一応、書いておくとSSE2 っていうのは、intel とかのCPUで使える複数の数値の計算を1命令でできちゃう命令群で

for( int i=0; i<8; ++i ) { xmm0[i] *= xmm1[i]; }

みたいなことが可能です。

128bit のレジスタがあって、その中身は 8bit*16, 16bit*8, 32bit*4, 64bit*2, 128bit*1 の解釈が可能になっています。それぞれの命令には、まとめられた数値の演算ということで、packed hogehoge という名前がついています。

レジスタは 32bit 環境だと 8 本、x64だと 16 本利用可能です。面倒なので 64bit 環境決めうちで書いてます^^;

やっかいなのは、画素値は普通、一色を 8bit でもつのですが、RGB3色から輝度Yに変換する場合、8bit*16 だと、3*5 = 15 個となって、変なところでレジスタを跨いでしまいます。もちろん、この 5 個を対象にしても良いのですが、もう一つのレジスタに続きの 16 個を読み込んで 8 個をまとめて処理する方が都合がよいので、そのようにします。

後は、8bit * 8bit の packed multi は無いので、16bit に 0 拡張して 16bit * 16bit の packed multi で計算します。なお、

Y = (Y' + 0x0080) / 0x0100 + 0x0010
Y' = 0x0042 * R + 0x0081 * G + 0x0019 * B

と近似しています。 + 0x0080) / 0x0100 + 0x0010 の部分は両方で共通ですので、問題は Y' の 0x0042 * R + 0x0081 * G + 0x0019 * B をどう計算するかの工夫になります。

ここでは2つの作戦で実装してみました。後は16個単位にして動作速度を計測してみようと思います。Cで素直に書くのよりは少なくとも速くなっていて安心しました。

作戦1:並び替えてから計算

B0,B1,B2,B3,B4,B5,B6,B7 のようにメモリ/レジスタに格納されていれば計算が非常に楽です。そこで、↑のようにデータをバラバラにして再構成します。

左が下位ビット、右が上位ビットであることに注意。

以下、Blue について
load
B0G0R0,B1|G1R1,B2G2|R2,B3G3R3|B4G4R4,B5
G5R5,B6G6|R6,B7G7R7|B8G8R8,B9|G9R9,BaGa
unpack

16bit のpacked乗算しかないので、0 で埋めたレジスタと unpack して 0 拡張する(以下 0 を省略。16bit 幅)

B0 G0 R0 B1 G1 R1 B2 G2
R2 B3 G3 R3 B4 G4 R4 B5
G5 R5 B6 G6 R6 B7 G7 R7
mask

マスク保持するレジスタ数削減と、データを扱いやすくするためにシフトしてからマスクする

B0  0  0 B1  0  0 B2  0 // (1)
 0 B3  0  0 B4  0  0 B5 // (2)
 0  0  0  0 B6  0  0 B7 // (3)
shift + shuffle + or で並び替える
 0  0 B2  0  0  0  0  0 // (4) = (1) を 右シフト
B0  0 B2 B1  0  0 B2  0 // (5) = (1) or (4)
B0  0 B2 B1 B6  0 B2 B7 // (6) = (3) or (5)

上位64bitの16bitを並び替える(右が上位)。 例えば、B6 0 B2 B7 を元に 0 0 B6 B7 を作ります(B6 B6 B6 B6 のようなことも可能)。

B0  0 B2 B1  0  0 B6 B7 // (7) = pshufhw $197, (6), (7)
 0 B3  0  0 B4 B5  0  0 // (8) = pshufhw  $92, (2), (9)

後は、2つのレジスタを合わせて、下位を並び替えれば完了

B0 B3 B2 B1 B4 B5 B6 B7 // (9) = (7) + (8)
B0 B1 B2 B3 B4 B5 B6 B7 // (a) = pshuflw $108, (9), (a)
Green
元データ
xx G0 xx xx G1 xx xx G2
xx xx G3 xx xx G4 xx xx
G5 xx xx G6 xx xx G7 xx
2つめを左シフトしてマスク(マスク保持のレジスタ削減と、並び替えを考慮して)
00 G0 00 00 G1 00 00 G2
00 00 G3 00 00 G4 00 00
G5 00 00 G6 00 00 G7 00
shuffle, shift, shuffle

シャッフル命令を使って32bit単位でデータを近づけるために並び替える。

00 G0 00 G2 G1 00 00 00
00 00 00 G6 G5 00 G7 00
shift

上位内、下位内でしかシャッフルできないので、データ位置を調整

G0 00 G2 G1 00 00 00 00
00 G3 00 00 G4 00 00 00
00 00 00 00 G6 G5 00 G7
merge and shuffle

or と シャッフルを使ってデータを並び替える

G0 G3 G2 G1 G4 00 00 00
G0 G1 G2 G3 G4 00 00 00
00 00 00 00 00 G5 G6 G7
G0 G1 G2 G3 G4 G5 G6 G7
Red
元データ
xx xx R0 xx xx R1 xx xx
R2 xx xx R3 xx xx R4 xx
xx R5 xx xx R6 xx xx R7
シフトしてマスク
R0 00 00 R1 00 00 00 00
R2 00 00 R3 00 00 R4 00
00 R5 00 00 R6 00 00 R7
shuffle と or で並び替えていく

上位を並び替えて、合成

00 00 R5 00 00 00 R6 R7  // R6 00 00 R7 -> 00 00 R6 R7
R0 00 R5 R1 00 00 R6 R7

下位を並び替え

R0 R1 00 00 00 00 R6 R7  // R0 00 00 R1 -> R0 R1 00 00
00 00 R2 R3 00 00 R4 00  // R2 00 00 R3 -> 00 00 R2 R3

上位も並び替えて、合成

00 00 R2 R3 R4 00 00 00  // 00 00 R4 00 -> R4 00 00 00
R0 R1 R2 R3 R4 00 R6 R7
00 00 00 00 00 R5 00 00
R0 R1 R2 R3 R4 R5 R6 R7

以上で並び替えられたデータが得られるので、後は packed multi, packed add, packed shift で計算すればいい。

B0 B1 B2 B3 B4 B5 B6 B7
G0 G1 G2 G3 G4 G5 G6 G7
R0 R1 R2 R3 R4 R5 R6 R7

作戦2:並び替えずに計算して帳尻を合わせる

load
B0G0R0,B1|G1R1,B2G2|R2,B3G3R3|B4G4R4,B5
G5R5,B6G6|R6,B7G7R7|B8G8R8,B9|G9R9,BaGa
unpack

word の SIMD 乗算しかないので、0 で埋めたレジスタと unpack して 0 拡張する(以下 0 を省略。16bit 幅)

B0 G0 R0 B1 G1 R1 B2 G2
R2 B3 G3 R3 B4 G4 R4 B5
G5 R5 B6 G6 R6 B7 G7 R7
map

それぞれの色に係数をかける

B0' G0' R0' B1' G1' R1' B2' G2'
R2' B3' G3' R3' B4' G4' R4' B5'
G5' R5' B6' G6' R6' B7' G7' R7'
sum(右シフト/左シフトしながら加算していく)

直接 B0' + G0' + R0' を計算する命令は SSE2 にはないので、シフトして足し算する。xxx としているのは必要ではない足し算結果が入る部分(例えば G0' + R0' + B1 のような無意味な値)。

加算部分だけ見ると↓のようになる。Y6,'Y7'は下位64bitにいてほしいのでシフト方向が逆になっている

Y0' xxx     xxx Y1' xxx xxx B2'+G2' xxx // 右シフトしながら
xxx Y3'     xxx xxx Y4' xxx xxx     B5' // 右シフトしながら
xxx G5'+R5' xxx xxx Y6' xxx xxx     Y7' // 左シフトしながら

以下の値を作って加算する(あとで必要な部分だけマスクするので、それでOK)

  0   0   0   0   0   0   0     R2' B3'
  0   0   0   0   0   0   0     xxx G5'+R5'
mask

必要な部分のみ取り出す。(1)がこうなっているのは、実際にはマスクしてからシフトして加算しているので。後からshuffleでごまかせるからOK

Y0'   0   0 Y1'   0   0 Y2'   0 // (a)
  0   0 Y2'   0   0   0   0   0 // (b)
Y0'   0 Y2' Y1'   0   0 Y2'   0 // (1) = (a)+(b)
  0 Y3'   0   0 Y4'   0   0 Y5' // (2)
  0   0   0   0 Y6'   0   0 Y7' // (3)
merge and shuffle
Y0' Y3' Y2' Y1' Y4'   0 Y2' Y5' // (4) = (1) + (2)
Y0' Y1' Y2' Y3' Y4'   0 Y2' Y5' // (5) = pshuflw $108,(4),(5)
Y0' Y1' Y2' Y3' Y4' Y5'   0   0 // (6) = pshufhw  $92,(5),(6)
  0   0   0   0   0   0 Y6' Y7' // (7) = pshufhw $197,(6),(7)
Y0' Y1' Y2' Y3' Y4' Y5' Y6' Y7' // (8) = (6) + (7)
Refereces
IA-32 SIMDの扉
GCC x86 Inline Assembler
gccのx86インラインアセンブリに関して
gccで simd mmx sse sse2
本日のツッコミ(全4件) [ツッコミを入れる]
_ Hiroshi (2008年07月05日 15:57)

カタン買ったよ!うちの研究室にカタン部できたよ!

_ ema (2008年07月05日 22:06)

じゃあ、研究室間対抗戦しましょうか。ソフトボール大会よりは向いてると思うんだw<br># なんなら、サンクトペテルブルグとかプエルトリコでw

_ Hiroshi (2008年07月06日 01:41)

マリカーはいわいわ研,カタンはema研と対抗戦したいですw<br>というわけで,M1を鍛えておきますw

_ ema (2008年07月06日 14:58)

じゃあ、折を見て4人、4人ぐらいでトーナメントでもしましょうかw