CPU実験D班
最終発表会
2017/2/21
minrt.mlの全体図（コア係より）
minrt.mlの全体図（コア係より）
並列化判定をした関数
iter_trace_diffuse_rays
・関数間でグローバル配列を読み書き
・グローバル配列は多層
（配列の,組の,配列の...)
・トリッキーなループ内WAR依存（後述）
for構文に変換(Knormal.t)
let f a b i =
....
if(i<j) then
…
f c d (i+d)
else
...
let f a b i =
let index = ref i in
let a' = ref a in
let b' = ref b in
for( ; !index<j ; index:=!index+d){
.....
a' := c;
b' := d
}
各for構文を並列化判定
・配列の読み書きに関するフローグラフ
・ループ越えWAR依存がないか
・IO命令がないか
...などを調べる
A'
a4
a3
a2
a1
A
Array_treeの作成
変数の（配列、組の）親子関係を表す
A'
a4
a3
a2
a1
A
・・・
Let b =A.(2) in
・・・
Array_treeの作成
A'
a4
a3
a2
a1
A
・・・
Let b =A.(2) in
・・・
Let c = A.(2) in
b
Array_treeの作成
A'
a4
a3
a2
a1
A
・・・
Let b =A.(2) in
・・・
Let c = A.(2) in
b
変数bとcが同じ領域を示すことを、記憶
Array_treeの作成
Rw_graphの作成
・配列読み書きに関するフローグラフ
・関数呼び出し内の動作も追う
・Array_treeの作成と同時に行う
Rw_graphの作成
L1:read a.(1)
L2:write b.(unknown)
L4:read a.(1)
L3:read a.(1)
・・・
Get(c, unkown)
・・・
Array_treeに
「cはbと同じ領域を示している」
という情報がある時…
Rw_graphの作成
L1:read a.(1)
L2:write b.(unknown)
L4:read a.(1)
L3:read a.(1)
・・・
Get(c, unkown)
・・・
Array_treeに
「cはbと同じ領域を示している」
という情報がある時…
bの名前でグラグに登録！
L5:read b.(unkown)
トリッキーなループ内WAR依存（例）
Let t = f …. In
If t <> 0 then
…
a.(0)….
else
(*a.(0)はreadしない*)
関数fは、、、
・内部の条件分岐でa.(0)にwriteしている
・a.(0)に書きこまなかった場合は必ず返り値が0になる
素朴に判定するとループ越え依存の可能性があるが…
トリッキーなループ内WAR依存（例）
Let t = f …. In
If t <> 0 then
…
a.(0)….
else
(*a.(0)はreadしない*)
関数fは、、、
・内部の条件分岐でa.(0)にwriteしている
・a.(0)に書きこまなかった場合は必ず返り値が0になる
左のa.(0)への参照は、fの返り値が0以外の時のみ起こるので、
直前の関数f内での書き込みに依存！
トリッキーなループ内WAR依存
「a.(n)がL(rw_graphのラベル）以降writeされていない」という仮定の元での、変数の環境を保持
（putされた配列ごとに複数持つ)
L:write( a.(n)<-10)
Let x=a.(n) in…
If a.(n) unwritten until L then…
{・・・
x=10
・・・}
トリッキーなループ内WAR依存
If (t<>0) then
e1
else
e2
If a.(n) unwritten until L then…
{・・・
x=10
t=0
・・・}
上のような仮定を保持していた時…
トリッキーなループ内WAR依存
If (t<>0) then
e1
else
e2
If a.(n) unwritten until L then…
{・・・
x=10
t=0
・・・}
この仮定の元では、e2に分岐することが分かる!
待遇を取れば、
「e1に分岐するなら、L以降a.(n)にwriteされた」
e1のrw_graphを成長させる過程で、「L以降a.(n)にwriteされる経路を通った」
という情報も含ませる
iter_trace_diffuse_raysの並列化判定結果
判定後...
ハードウェアの構造上、並列化できる処理は１つだけなので、ユーザに並列化する関数を選んでもらう。
並列計算のための命令セット
forkは単一モードの命令
next, acc, endは並列モードの命令
f29
f30
f31
gc
gd
parent
child1
child2
child3
child5
child4
child6
gcの初期値: 118
gdの初期値: -2
fork
working
working
working
working
working
working
working
118
-2
next
next
next
118
116
114
112
acc
acc
mode:
single
parallel
end
end
end
end
end
end
end
all_end
add_sub
命令
mov
fadd_fsub
fmul
fdiv_fsqrt
fmov
lw
sw
agu
ftoi
itof
cmp
b
fpr_arch
gpr_arch
gpr_rob
fpr_rob
命令メモリ
リターン
アドレス
スタック
データメモリ
PC
gpr_cdb
fpr_cdb
out
並列実行関係以外の命令
FPGAのリソース使用量
さらに高速化できそうな点