Java による PRAM コンパイ ラの拡張
情報論理工学研究室
05-1-037-0138
藤枝正樹
PRAM ( Parallel Random Access Machine )
PRAM シミュレータ
目的
研究内容
動作確認と検証
結論と今後の課題
目次
共有メモリ型並列計算モデル
◦
全てのプロセッサが自由に読み書きを行うことができる。◦
仮定
全ての命令が種類に関係なく 1 単位時間で行われる。
1 命令毎に同期をとる。PRAM ( Parallel Random Access Machine )
共有メモリ
プロセッサ プロセッ
サ プロセッ
サ プロセッ サ
PRAM シミュレータ
PRAM 用並列言語プログラ ム
PRAM コンパイ ラ
並列アセンブ ラ
PVSM
( Parallel Virtual Stack Machine )
インタプリタ
既存の PRAM シミュレータは
1 段階の parallel 命令にしか対応していない
。
↓
parallel 命令の 2 重入れ子構造に対応する PRAM シミュレータの設計
目的
PRAM 用並列言語( K07 言語)
◦
parallel 文(並列処理命令)
文法 「 parallel( 式①,式② ) 文」 式①,② : int 型の評価値を持つ式(プロセッサ番号)
文 : 任意の文( parallel 文は 2 重入れ子構造まで 対応)
◦
特殊記号 $p
実行中のプロセッサ番号を表示する。 実行中のプロセッサ番号の値を持つ変数として処理。
parallel 文の 2 重入れ子構造で使用した場合、 2 桁の数として 表示。
研究内容
並列アセンブラ( VSM アセンブラ)
◦
PARA (並列処理の開始)
スタックで指定されたプロセッサ台数を使用して、並列状態へ と移行する。◦
SYNC (同期)
並列状態で処理中の各プロセッサが命令を読むまで動作を停止 し、全てのプロセッサが命令を読むと再び動作を開始する。◦
PUSHP (プロセッサ番号の挿入)
命令を実行しているプロセッサのプロセッサ番号をスタックトップに積む。(プロセッサ番号は 2 桁の数として表される。)
研究内容
PVSM インタプリタ
◦
VSM ( Virtual Stack Machine ) → 2 次元配列
VSM i,j ( 0 ≦ i,j < 10 )◦
プロセッサ番号 → 2 桁の 10 進数で表示
計算式( i*10 + j )研究内容
← j →
← →
i
main(){
parallel(0,5){
parallel(0,3){
writeint($p);
} }
}
動作確認と検証
PUSHI 0 PUSHI 5 PARA
PUSHI 0 PUSHI 3 PARA
PUSHP OUTPUT SYNC SYNC HALT
PRAM コンパイ ラ
0 1 2 3 10 11 12 13 20 21 22 23 30 31 32 33 40 41 42 43 50 51 52 53 Execution time : 11
Sequential time : 4 Parallel time : 7
Number of processors : 24
PVSM インタプ リタ
0 1 2 3 10 11 12 13 20 21 22 23 30 31 32 33 40 41 42 43 50 51 52 53 main(){
parallel(0,5){
parallel(0,3){
writeint($p);
} }
}
main(){
parallel(0,5){
parallel(0,3){
writeint($p);
} }
}
main(){
parallel(0,5){
parallel(0,3){
writeint($p);
} }
}
0~5番の 6 台を使
用 0~3 番の 4 台を使 用
←6×4 =
24合計24 台のプロセッサを 使用
i →
j →
(i *10 + j) →
←4+7 =
11実行にかかったステップ数が 11
結論
◦
parallel 命令の 2 重入れ子構造の対応を実現。◦
並列アルゴリズムの設計およびその計算量の解析の容易 化。