Document

少しは組込み的な
アーキテクチャシミュレーション
―色々やってわかったこと―
中島浩
（京都大学）
目次


はじめに
忘れっぽくパターンにハマるパイプライン


割り込みは思ったほどは悪させず


リアルタイム業界の迷信と風説を打破
強力なパワーが潜む再利用


ハードウェアの性格を利用した最適化に挑戦
計算オーダ低減も可能な夢の最適化を探求
おわりに
はじめにが自慢話ですみません (1/6)

シミュレータ研究 @TUT の成果
対象／手法
MP
OoO 再利用
時分割並列
ISS 命令
キャッシュ
IDA キャッシュ
分岐予測
サイクル
論文
J2+C2
J1+C1
J1+C1+A1
J1+C1+A1
性能
当社x6.6@16p
SSx9.7
SSx9.4@16p
SSx34
SSx14
J1+C1
当社x1000000
J1+1stEMB 当社x173
J1+C1
当社x10000
MP: Multiprocessor Simulation, OoO: Out-of-Order Simulation
ISS: Instruction Set Simulation, IDA: Interruption Delay Analysis
はじめに

が自慢話ですみません
(2/6)
Multiprocessor シミュレータ Shaman
F/E Node
F/E Node
F/E Node
F/E Node
P
P
P
P
CCF
CCF
S/W
DSM
CCF
CCF
CT
CT
B/E Node
CT
CT
Network
Filtering Cache
 Cache/Memory 間の通信が
生じないアクセス(狭義の
ヒット)を除去
ノード間通信激減
Memory
はじめにが自慢話ですみません (3/6)

再利用による ooo-sim 高速化 BurstScalar
for (i=0;i<n;i++)
{ ... }
i=0
i=1
i=2
i=3
i=4
i=5
ループ先頭のパイプライン
状態を保存・比較
i=6
i=7
計算省略
状態・cacheアクセス・
分岐予測結果が一致
次状態へ直接遷移
i=8
i=9
はじめにが自慢話ですみません (4/6)

時間分割並列 ooo-sim
差分が ooo-sim に
影響なし整合
命令・cache・分岐予測
の in-order sim により
マシン状態を近似
warm-up
=?
はじめにが自慢話ですみません (5/6)

in-order sim のワークロード最適化
WL binary
自動変換
最適化コンパイル Optimized C function
...
BB_00001234() {
0x00001234:
cadr_t nPC; reg_t r3,r4;
add r3,r1,r2
r3=regs[2]+regs[1];
addi r3,r3,$5
r3=regs[3]=r3+5;
C function for BB
lw
r4,$8(r5) BB_00001234() {
r4=regs[4]=
bne r3,r4,$5
memw[regs[5]+8];
cadr_t PC,nPC;
0x00001244:
nPC=0x1244;
PC=0x1234; nPC=PC+4;
...
if (r3!=r4) nPC=0x1258;
regs[3]=regs[2]+regs[1];
return(nPC);
PC=0x1238; nPC=PC+4;
}
regs[3]=regs[3]+5;
PC=0x123C; nPC=PC+4;
regs[4]=memw[regs[5]+8];
PC=0x1240; nPC=PC+4;
if (regs[3]!=regs[4])
nPC=PC+4+(5<<2);
return(nPC);
}
はじめにが自慢話ですみません (6/6)

最悪割込み遅延解析

cache/予測ミス最悪値の解析 O(N2F)O(NF)
4 way set
a
b
c
d
2-bit counter
T
T N T N T
互いに干渉しない
T

割込み
c
b
b
実行サイクル最悪値の解析 O(N2)O(N logN)
=
計算省略
忘れっぽくパターンにハマる
パイプライン (1/5)

どれほど忘れっぽいか

時間分割並列 ooo-sim
<< 1000 inst

=
最悪割込み遅延解析
=
 10 inst
忘れっぽくパターンにハマる
パイプライン (2/5)

なぜ忘れっぽいか

長遅延命令 ( cache miss, etc.)
過去に依存しない
★

★
★
★
分岐予測ミス
過去に依存しない
★
★
★
忘れっぽくパターンにハマる
パイプライン (3/5)

どれほどハマるか

BurstScalar の再利用状況 @ SPEC CPU95



2.75
再利用率＝86.7%~99.99%
再利用回数／パターン＝48~273,000
最悪割込み遅延での pipeline パターン数
1
2.25
1.75
1.25
#active intervals/thread
2
3
4
5
[x 106inst]
忘れっぽくパターンにハマる
パイプライン (4/5)

なぜハマるか
パイプラインは忘れっぽい
過去への依存≪現在の入力への依存
現在の入力＝実行命令列＋cache 等の振舞
入力系列は繰り返す
入力系列はパターンにハマる
パイプラインがパターンにハマる
よって桶屋が儲かる

忘れっぽくパターンにハマる
パイプライン (5/5)

健忘性・偏執性につけこめるか



トランジスタ削減 ... ま、無理でしょう
実行サイクル削減 ... ま、無理でしょう
消費電力削減
... もしかしたらできるかも



パイプライン挙動は短期間の履歴で予測可能
(かもしれない)
予測に基づき投入資源量の調節 (電源 on/off 等)
が可能 (かもしれない)
ハードウェア機構での予測・調節が難しければ
詳細なシミュレーションで解析しておけばよい
(きっとそうに違いない！)
割り込みは思ったほどは悪させず
(1/4)

リアルタイム業界の迷信
cache/bpred/pipeline は性能予測性が悪い
 実行命令数で近似ってわけにはいかんわな
 これら定跡が役に立つのは局所性のおかげ
 確かにそうです、はい
 割込み/preemption は局所性を破壊
 まさに御意
 割込みで定跡機構の性能は致命的に悪化
定跡機構はリアルタイムシステムに不適
 おいおい、ほんとかぁ？

割り込みは思ったほどは悪させず
(2/4)

実際の最悪割込み遅延



cache miss ≦ 103 高々WSS/ライン長
分岐予測ミス ≦ 104 不幸な最悪値の存在
サイクル数 ≦ 105
10μsec @ 1GHz
80000
案外平気じゃん
60000
40000
20000
perl
vortex
compre
li
ijpeg
go
m88ksi
gcc
apsi
fpppp
wave5
applu
turb3d
su2cor
hydro2
mgrid
0
tomcatv
swim
delay in cycle
100000
割り込みは思ったほどは悪させず
(3/4)
リアルタイム業界の風説
cache/bpred/pipeline は性能予測性が悪い
 実行命令数で近似ってわけにはいかんわな
 特に割込み遅延の性能予測は難しい
 う～ん、確かにそうかもしんない

60000
[cycle]

こんなとんでもない
奴もあるしね
compress:
int. delay vs int. point
40000
20000
0
0
1
2
3
4
[x 106 inst]
割り込みは思ったほどは悪させず
(4/4)

リアルタイム業界の風説
cache/bpred/pipeline は性能予測性が悪い
 実行命令数で近似ってわけにはいかんわな
 特に割込み遅延の性能予測は難しい
 う～ん、確かにそうかもしんない
 性能予測ができないので定跡機構は使えない
 いやいや、難しいのとできないのとは違う




cache : 200K acc/sec @ F=2
1sec @ 1GIPS
 2day (seq)
分岐予測 : 5K branch/sec @ F=2
5h (par)
サイクル数 : 5K inst/sec @ F=1
 実用的
50K inst/sec @ F=1 & P=16
強力なパワーが潜む再利用 (1/3)

高速化の秘訣
＝やんなくてもいい (かもしれない)
計算 (通信) を省略して同一結果を得る
まさに
再利用

少し
再利用

まあ
再利用




Shaman
...
BurstScalar ...
並列 ooo-sim ...
WL 最適化 ...
C/B WCID ...
WCID
...
ヒット確定の cache access
一度やった inst sched
過去側の ooo-sim
命令フェッチ・デコード
因果地平越えのコスト計算
隣接割込み点の ooo-sim
適用性大
 効果大
(~数桁)
適用性小
 効果小
(~数倍)
強力なパワーが潜む再利用 (2/3)

再利用型プログラム vs 自動再利用
再利用型プログラム
比較対象
プログラムの意味で
定まるデータ集合
e.g. a[i] = a’[(i+c)%n]
比較方法
プログラムの意味で
定まる一致条件
e.g. x = x’ + c
再利用範囲プログラムの意味で
定まる実行区間
e.g.ループの途中まで
投機的に
自動再利用
参照する全レジスタと
(同じアドレスの) メモリ
e.g. a[i] = a’[i]
単純な一致
e.g. x = x’
特定の命令列
e.g. ループ全体
強力なパワーが潜む再利用 (3/3)

自動再利用の限界を打破するには...


そもそも自動は無理なのであきらめて...
再利用型プログラムのサポート役に徹する


計算状態の保存・比較 (・GC) が面倒
状態保存・比較機構／ライブラリ
再利用アルゴリズムの検証が困難
(効果がでかすぎると単純検証すらやってられない)
半自動検証・変換
c.f. 四半世紀前に聞いた話

N-queen 自動変換
N ! の解生成＆検証生成＆検証を融合普通の奴
おわりに

(1/2)
役に立つかどうかわかんない知見




が竜頭蛇尾ですみません
パイプライン：健忘性・偏執性
割込み遅延：正当な評価、予測可能性
再利用：潜在的有効性
きっと役に立つ知見



あなたのマシン/プログラムの挙動を詳細に
観測してみましょう
きっと「へぇ～」っと思うことがあるはず
「へぇ～」が「おぉ～」になるかも
おわりにが竜頭蛇尾ですみません (2/2)
へぇ～
ほぉ～

Download Report