Loop

コンピュータアーキテクチャ
高速化のヒント
天野 [email protected]
プログラムの高速化
• stallの割合が多い
– コードスケジューリング
– ループアンローリング
• ハードウェアの改造
– 複合命令
• 積和命令、LD-OR命令など
• MIPSのパイプラインはよく出来ているので下手な命令は性能を
低下させることになる
– SIMD演算命令
• メモリとレジスタの拡張がポイント
– スーパースカラ
• まともにやると大変なので注意
– VLIW
• メモリのバンド幅の制約で2命令が限度か？
– ベクトル演算命令
• 連続メモリ参照がうまく行くかどうかが設計上のポイント
コードスケジュール
• C=A+B, F=D+Eを実行する場合
lw $1,A($0)
lw $2,B($0)
add $3,$1,$2
sw $3,C($0)
lw $1,D($0)
lw $2,E($0)
add $3,$1,$2
sw $3,F($0)
ストール
2箇所ストールする
ストール
コードスケジュールでストールを減らす
• C=A+B, F=D+Eを実行する場合
lw $1,A($0)
lw $2,B($0)
lw $4,D($0)
add $3,$1,$2
lw $5,E($0)
sw $3,C($0)
add $6,$4,$5
sw $6,F($0)
lwの直後にその
結果を使わなけ
れば良い
C=A+B, F=D+E
で別々のレジスタ
を使う
かなりの割合でス
トール削減が可
能
遅延分岐
• 分岐命令の次の命令（遅延スロット）をパイプ
ラインに入れてしまう。
– 遅延スロットの命令は必ず実行される
→MIPSeの場合は遅延スロットは1
– つまり、遅延の効き目が遅い
– 有効な命令を入れてやる必要がある
→ パイプラインスケジューリング
• 今回のMIPSeはこの方法を採用している
遅延スロットのスケジュール
掛け算のプログラムの例： mult.asm
lw $1,0($0)
lw $2,4($0)
add $3,$0,$0
loop: add $3,$3,$2
addi $1,$1,-1 // ここはデータハザードでストールする
bne $1,$0,loop
add $0,$0,$0 // NOP ここを埋めてみるには？
sw $3,8($0)
end: beq $0,$0,end
add $0,$0,$0 // NOP ここはダイナミックストップなの
で気にしないでよい
コードスケジューリング後 mult2.asm
lw $1,0($0)
lw $2,4($0)
add $3,$0,$0
loop: addi $1,$1,-1 // ここはデータハザードでストールする
bne $1,$0,loop
add $3,$3,$2 // 遅延スロット
sw $3,8($0)
end: beq $0,$0,end
add $0,$0,$0 // NOP ここはダイナミックストップなの
で気にしないでよい
コードスケジューリング後:mult3.asm
lw $1,0($0)
lw $2,4($0)
add $3,$0,$0
addi $1,$1,-1 //あらかじめ引いておく
loop: add $3,$3,$2
bne $1,$0,loop
addi $1,$1,-1 //遅延スロット
sw $3,8($0)
end: beq $0,$0,end
add $0,$0,$0 // NOP ここはダイナミックストップなの
で気にしないでよい
配列にスカラを足す単純なループ
Loop： L.D F0,0(R1) ; 配列要素をF0にロード
ADD.D F4,F0,F2 ;スカラ値を加算
S.D F4,0(R1)
；結果をストア
DADDI R1,R1,#-8 ;ポインタをデクリメント（倍精度データを想定）
BNE R1,R2,Loop ；
ストールが生じる
Loop： L.D F0,0(R1) ; 配列要素をF0にロード
stall
ADD.D F4,F0,F2 ;スカラ値を加算
stall
stall
S.D F4,0(R1)
；結果をストア
DADDI R1,R1,#-8 ;ポインタをデクリメント（倍精度データを想定）
BNE R1,R2,Loop ；
NOP
スケジューリング
Loop： L.D F0,0(R1) ; 配列要素をF0にロード
stall
ADD.D F4,F0,F2 ;スカラ値を加算
stall
stall
S.D F4,0(R1)
；結果をストア
DADDI R1,R1,#-8 ;ポインタをデクリメント（倍精度データを想定）
BNE R1,R2,Loop ；
NOP
Loop： L.D F0,0(R1) ; 配列要素をF0にロード
DADDI R1,R1,#-8
ADD.D F4,F0,F2 ;スカラ値を加算
stall
stall
S.D F4,8(R1)
；結果をストア
BNE R1,R2,Loop ；
少しは良くなるが、限界が、、、
ループアンローリング
Loop： L.D F0,0(R1) ; 配列要素をF0にロード
ADD.D F4,F0,F2 ;スカラ値を加算
S.D F4,0(R1)
；結果をストア
L.D F6,-8(R1)
ADD.D F8,F6,F2
S.D F8,-8(R1)
L.D F10,-16(R1)
ADD.D F12,F10,F2
S.D F12,-16(R1)
L.D F14,-24(R1)
ADD.D F16,F14,F2
S.D F16,-24(R1)
DADDI R1,R1,#-32; ポインタを4回分デクリメン
BNE R1,R2,Loop ；
ループを4回分開いてやる
NOP
ループアンローリング
Loop： L.D F0,0(R1) ; 配列要素をF0にロード
L.D F6,-8(R1)
L.D F10,-16(R1)
L.D F14,-24(R1)
ADD.D F4,F0,F2 ;スカラ値を加算
ADD.D F8,F6,F2
ADD.D F12,F10,F2
ADD.D F16,F14,F2
S.D F4,0(R1)
；結果をストア
S.D F8,-8(R1)
S.D F12,-16(R1)
DADDI R1,R1,#-32; ポインタを4回分デクリメン
BNE R1,R2,Loop ；
S.D F16,8(R1)
ループを4回分開いてやる
スーパスカラ方式
２命令同時発行の例
（３，４命令同時発行も実現さ
れている）
WB
WB
EX
命令コードの互換性がある
命令実行制御がたいへん
EX
通常の命令
パイプライン
RF
RF
IF
IF
浮動小数点演算
パイプライン
キャッシュ
通常の命令
浮動小数点演算命令
メモリシステム
VLIW（Very Long Instruction
Word）方式
WB
EX
EX
EX
EX
RF
IF
４つの命令分の長い命令
実行の制御はコンパイラがあらかじめ行うので制御は簡単
コードの互換性がない
MIPSの5命令VLIW化の実行例
一人の命令で皆同じことをする
SIMD
命令メモリ
命令
演算装置
半導体チップ内でたくさんの
演算装置を動かすには良い
方法
アクセラレータ（普通のCPU
にくっつけて計算能力を加速
する加速装置）の多くは
この方式
安くて高いピーク性能が
得られる
Data memory
ベクタ命令
vector registers
a0a1a2…..
adder
Y=Y+X[i]
multiplier
X[i]=A[i]＊B[i]
一つの命令で連続したデータを一括して処理
ベクタレジスタが必要
b0b1b2….

Download Report