SIMD化
手作業によるSIMD化はなかなか時間がかかっています。個人的な目標はCPIを1.0以下にすることですが、思った以上にCPIが減らないので取り合えず現状のパッチをアップします。SIMD化した部分は#ifdef __SIMD__で囲っています。
パッチはこちら。
個人的にはMMXやSSEなどを直接使ったことはないので、SIMDプログラミングの経験値は低いです。その点はご容赦願います。
SIMD化の例
前回のプロファイリングで上位に挙がっていたix_max関数が割と簡単なので例にあげてみます。ix_max関数のCのコードは以下の通りです。配列の最大値を求めています。
int
ix_max(const int *ix, const int *end)
{
int max1 = 0, max2 = 0;
do {
int x1 = *ix++;
int x2 = *ix++;
if (max1 < x1)
max1 = x1;
if (max2 < x2)
max2 = x2;
} while (ix < end);
if (max1 < max2)
max1 = max2;
return max1;
}これのアセンブラソースをspu-gcc_timingというツールにかけると静的解析を見ることができます。これで各命令がストールなく動作するか、並列実行できるかなどを見ることができます。静的解析結果は以下の通り。
.type ix_max, @function
ix_max:
0D 01 ori $7,$3,0
1D 012345 hbra .L48,.L40
0D 12 ori $10,$4,0
1D 1234 fsmbi $9,0
0D 23 il $8,0
1D 2 lnop
.L40:
0D 34 ai $12,$7,4
1D 345678 lqd $13,0($7)
1 -567890 lqd $11,0($12)
1 ---9012 rotqby $2,$13,$7
0d 01 ai $7,$7,8
1d -1234 rotqby $3,$11,$12
0 23 clgt $6,$10,$7
0 34 cgt $4,$2,$9
0 -56 cgt $5,$3,$8
0 67 selb $9,$9,$2,$4
0D 78 selb $8,$8,$3,$5
.L48:
1D 7890 brnz $6,.L40
0 -90 cgt $7,$8,$9
0 -12 selb $3,$9,$8,$7
0D 2 nop $127
1D 2345 bi $lr最初の0とか1とかがどのパイプラインで実行しているか、次の数字や-が実行状態です。-はストール状態です。右側はアセンブラコード。メインループは.L40から.L48の間です。あまり並列動作できず、1ループで6回ストールしています。
これを見て初めて気がついたのですが（よく読むとチュートリアルにちゃんと書いてありますが）、SPUは実はクワッドワード単位のロードとストアしかできないのです。そのため、通常のコード（上記例だとintの配列操作）だとクワッドワード単位でロードしてシフトすることで必要なワードデータのロードが完了します。ストアはもっと最悪で書き込む値をシフトして、書き込み先の値をロードして合成してから書きこみます。以前、なんでSHUFのストールが多いかわからなかったのですが、SPUの作りを知って理解しました。こりゃーたぶん通常のコードのままだとPPUに負けます。
これを以下のコードに直してみました。
int
ix_max(const int *ix, const int *end)
{
vec_int4 *v_ix;
vec_int4 max1 = (vec_int4)(0),max2,max3,max4;
vec_int4 data1,data2,data3,data4;
vec_uint4 result1,result2,result3,result4;
int i,j,k;
max4 = max3 = max2 = max1;
if((int)ix & 0x0000000F){
max1 = spu_splats(*ix++);
max2 = spu_splats(*ix++);
}
v_ix = (vec_int4*)ix;
i = (int)end - (int)ix;
k = i & 0x0000000F;
i >>= 4;
j = i & 3;
i >>= 2;
for(;i > 0;i--){
data1 = *v_ix++;
result1 = spu_cmpgt(data1,max1);
max1 = spu_sel(max1,data1,result1);
data2 = *v_ix++;
result2 = spu_cmpgt(data2,max2);
max2 = spu_sel(max2,data2,result2);
data3 = *v_ix++;
result3 = spu_cmpgt(data3,max3);
max3 = spu_sel(max3,data3,result3);
data4 = *v_ix++;
result4 = spu_cmpgt(data4,max4);
max4 = spu_sel(max4,data4,result4);
}
for(;j > 0;j--){
data1 = *v_ix++;
result1 = spu_cmpgt(data1,max1);
max1 = spu_sel(max1,data1,result1);
}
if(k){
ix = (const int *)v_ix;
data1 = spu_splats(*ix++);
data1 = spu_insert(*ix++,data1,0);
result1 = spu_cmpgt(data1,max1);
max1 = spu_sel(max1,data1,result1);
}
result2 = spu_cmpgt(max2,max1);
max2 = spu_sel(max1,max2,result2);
result4 = spu_cmpgt(max4,max3);
max4 = spu_sel(max3,max4,result4);
result1 = spu_cmpgt(max2,max4);
max1 = spu_sel(max4,max2,result1);
max2 = spu_rlqwbyte(max1,4);
max3 = spu_rlqwbyte(max1,8);
max4 = spu_rlqwbyte(max1,12);
result2 = spu_cmpgt(max2,max1);
max2 = spu_sel(max1,max2,result2);
result4 = spu_cmpgt(max4,max3);
max4 = spu_sel(max3,max4,result4);
result1 = spu_cmpgt(max2,max4);
max1 = spu_sel(max4,max2,result1);
return si_to_int((qword)max1);
}結構でかくなりました。このコードの静的解析結果は以下の通りです。
.type ix_max, @function
ix_max:
0D 01 il $14,0
1D 0123 shlqbyi $8,$3,0
0D 12 andi $2,$3,15
1D 1234 shlqbyi $6,$4,0
0D 23 ori $17,$14,0
1D 2345 shlqbyi $15,$14,0
0D 34 ori $16,$14,0
1D 3456 brz $2,.L47
0D 45 ai $10,$3,4
1D 456789 lqd $11,0($3)
0D 56 ai $8,$3,8
1D 5 lnop
0D 67 ila $5,66051
1D 678901 lqd $9,0($10)
0d 78 ila $4,66051
1d ---0123 rotqby $7,$11,$3
1 -2345 rotqby $3,$9,$10
1 -4567 shufb $14,$7,$7,$5
0d 5 nop $127
1d -6789 shufb $15,$3,$3,$4
.L47:
0D 78 sf $13,$8,$6
1D 789012 hbra .L67,.L61
0 89 ori $11,$8,0
0 9012 rotmai $12,$13,-6
0 0123 rotmai $8,$13,-4
0 12 andi $18,$13,15
0 -34 cgti $6,$12,0
0 45 andi $13,$8,3
0D 5 nop $127
1D 5678 brz $6,.L58
.L61:
0D 67 ai $12,$12,-1
1D 678901 lqd $27,0($11)
0D 7 nop $127
1D 789012 lqd $25,16($11)
0D 89 cgti $19,$12,0
1D 890123 lqd $23,32($11)
1 901234 lqd $21,48($11)
0 01 ai $11,$11,64
0 -23 cgt $26,$27,$14
0 34 cgt $24,$25,$15
0 45 cgt $22,$23,$17
0 56 cgt $20,$21,$16
0 67 selb $14,$14,$27,$26
0 78 selb $15,$15,$25,$24
0D 89 selb $17,$17,$23,$22
1D 8 lnop
0D 90 selb $16,$16,$21,$20
.L67:
1D 9012 brnz $19,.L61
.L58:
0D 01 cgti $12,$13,0
1D 012345 hbra .L66,.L62
0d 1 nop $127
1d -2345 brz $12,.L60
.L62:
0D 34 ai $13,$13,-1
1D 345678 lqd $30,0($11)
0 45 ai $11,$11,16
0 56 cgti $28,$13,0
0D 0 ---9 cgt $29,$30,$14
1D 9 lnop
0D -12 selb $14,$14,$30,$29
.L66:
1D 1234 brnz $28,.L62
.L60:
0D 2 nop $127
1D 2345 brz $18,.L56
0D 34 ai $36,$11,4
1D 345678 lqd $37,0($11)
0D 45 ila $38,66051
1D 4567 cwd $34,0($sp)
1 567890 lqd $35,0($36)
1 -----1234 rotqby $32,$35,$36
1 2345 shufb $33,$37,$37,$38
1 ---6789 shufb $31,$32,$33,$34
0 ---01 cgt $18,$31,$14
0 -23 selb $14,$14,$31,$18
.L56:
0D -45 cgt $48,$15,$14
1D 456789 hbr .L65,$lr
0 56 cgt $47,$16,$17
0 67 selb $46,$14,$15,$48
0 78 selb $44,$17,$16,$47
0 -90 cgt $45,$46,$44
0d -12 selb $41,$44,$46,$45
1d --3456 rotqbyi $43,$41,4
1 4567 rotqbyi $17,$41,8
1 5678 rotqbyi $40,$41,12
0 -78 cgt $42,$43,$41
0 -90 cgt $39,$40,$17
0 01 selb $16,$41,$43,$42
0 12 selb $14,$17,$40,$39
0 -34 cgt $15,$16,$14
0 -56 selb $3,$14,$16,$15
0D 6 nop $127
.L65:
1D 6789 bi $lrコードが増えていますが、メインループは.L61から.L67の間です。相変わらずあまり並列動作はできていませんが、ストールは一つしかしていません。オリジナルコードと比べて1ループで8倍の処理を行うので実行コード自体も減ってストールも減っています。
今回はこのようなSIMD化をいくつかの関数で行ってみました。詳しくはパッチを見てください。
結果
今回の結果は以下の通りです。パフォーマンス解析（動的解析）の方がたぶん現実に近いと思うのでこちらの結果のみです。恒例の3秒WAVファイルのエンコード結果です。
systemsim % mysim spu 5 display statistics SPU DD3.0 *** Total Cycle count 1164904915 Total Instruction count 643 Total CPI 1811671.59 *** Performance Cycle count 1164904915 Performance Instruction count 685337277 (629133623) Performance CPI 1.70 (1.85) Branch instructions 36201307 Branch taken 26165073 Branch not taken 10036234 Hint instructions 10594989 Hint hit 17663931 Contention at LS between Load/Store and Prefetch 17830093 Single cycle 389671183 ( 33.5%) Dual cycle 119731220 ( 10.3%) Nop cycle 19247350 ( 1.7%) Stall due to branch miss 189334053 ( 16.3%) Stall due to prefetch miss 25488 ( 0.0%) Stall due to dependency 376267721 ( 32.3%) Stall due to fp resource conflict 910 ( 0.0%) Stall due to waiting for hint target 26889219 ( 2.3%) Stall due to dp pipeline 6 ( 0.0%) Channel stall cycle 43737756 ( 3.8%) SPU Initialization cycle 9 ( 0.0%) ----------------------------------------------------------------------- Total cycle 1164904915 (100.0%) Stall cycles due to dependency on each pipelines FX2 28476210 ( 7.6% of all dependency stalls) SHUF 122265468 ( 32.5% of all dependency stalls) FX3 10339489 ( 2.7% of all dependency stalls) LS 117697723 ( 31.3% of all dependency stalls) BR 256232 ( 0.1% of all dependency stalls) SPR 379 ( 0.0% of all dependency stalls) LNOP 0 ( 0.0% of all dependency stalls) NOP 0 ( 0.0% of all dependency stalls) FXB 0 ( 0.0% of all dependency stalls) FP6 78549863 ( 20.9% of all dependency stalls) FP7 18682351 ( 5.0% of all dependency stalls) FPD 6 ( 0.0% of all dependency stalls) The number of used registers are 128, the used ratio is 100.00 dumped pipeline stats systemsim %
1164904915/3000000000=0.39 [sec]
約7.7倍速です。5月19日のSIMD前のパフォーマンス解析のサイクル数が1545099715なので、そのときの75%のサイクル数となり、そこそこ速くなっています。
0.5秒のWAVで実行した結果も貼ります。Athlonで速くなったとは言っても3秒のWAVのパフォーマンス解析はやっぱり遅いです。約1時間コース。0.5秒ならその1/6の時間ですむので。
systemsim % mysim spu 6 display statistics SPU DD3.0 *** Total Cycle count 186784983 Total Instruction count 643 Total CPI 290489.85 *** Performance Cycle count 186784983 Performance Instruction count 107788871 (98916031) Performance CPI 1.73 (1.89) Branch instructions 5791247 Branch taken 4229544 Branch not taken 1561703 Hint instructions 1697612 Hint hit 2805465 Contention at LS between Load/Store and Prefetch 2928000 Single cycle 60407925 ( 32.3%) Dual cycle 19254053 ( 10.3%) Nop cycle 2998968 ( 1.6%) Stall due to branch miss 31490654 ( 16.9%) Stall due to prefetch miss 4968 ( 0.0%) Stall due to dependency 59804649 ( 32.0%) Stall due to fp resource conflict 150 ( 0.0%) Stall due to waiting for hint target 4098273 ( 2.2%) Stall due to dp pipeline 6 ( 0.0%) Channel stall cycle 8725328 ( 4.7%) SPU Initialization cycle 9 ( 0.0%) ----------------------------------------------------------------------- Total cycle 186784983 (100.0%) Stall cycles due to dependency on each pipelines FX2 4238984 ( 7.1% of all dependency stalls) SHUF 18879227 ( 31.6% of all dependency stalls) FX3 1615677 ( 2.7% of all dependency stalls) LS 18772810 ( 31.4% of all dependency stalls) BR 37078 ( 0.1% of all dependency stalls) SPR 94 ( 0.0% of all dependency stalls) LNOP 0 ( 0.0% of all dependency stalls) NOP 0 ( 0.0% of all dependency stalls) FXB 0 ( 0.0% of all dependency stalls) FP6 13518721 ( 22.6% of all dependency stalls) FP7 2742052 ( 4.6% of all dependency stalls) FPD 6 ( 0.0% of all dependency stalls) The number of used registers are 128, the used ratio is 100.00 dumped pipeline stats systemsim %
考察
速度はまだまだですが、それ以上にCPIがあまり改善していないのがうれしくないです。どうもストール数も減ったけど実行コードも減ったのでCPIがあまり変わっていないようです。パフォーマンス解析を見ると依存関係によるストールは大幅に減っていますが、ブランチミスがむしろ増えています。ブランチミスの対策はブランチをやめるか__builtin_expect関数を使うことのようですが、うまくブランチミスを減らせてないです。今後はさらなるSIMD化とともにブランチミスを減らす方法を模索する必要がありそうです。
