PRAMシミュレータの構築情報論理工学研究室 01-1-26-037 橋本博之あらまし 背景 PRAM(Parallel Random Access Machine) PRAMシミュレータ PRAMシミュレータの実行例 結論背景 問題を高速に解く 複雑な問題を解きたい 高性能コンピュータを手軽に使いたい並列アルゴリズムが必要並列計算モデル上で設計・解析が行われる PRAM parallel random access machine 共有メモリ P１ P２ P３・・・・ Pｐ 共有メモリとそれに接続されたp個のプロセッサから成る PRAMアルゴリズムの実行 0 1 2 3 4 P1 P2 P3 5 演算命令メモリアクセス命令入出力命令同期 P4 メモリセルに対して 1単位時間でデータの読み書きができる 演算は1単位時間で行なうことができる PRAMの特徴  単純 同期や通信のコスト、データの局所性を無視  汎用 アーキテクチャに依存しないアルゴリズムの設計・解析がし易いしかし、PRAM自体の実現は困難である目的 PRAMアルゴリズムの評価を容易にする PRAMシミュレータの作成 PRAMアルゴリズムを記述できる言語を作成する PRAM用並列言語を作成 PRAMシミュレータとは  PRAM用並列言語  並列アセンブラ  PRAMコンパイラ  VPSM(Virtual Parallel Stack Machine)インタプリタ以上の4要素から成る PRAMシミュレータによる実行の流れ PRAM用並列言語プログラム VPSMインタプリタ PRAMコンパイラ並列アセンブラ PRAM用並列言語 C風手続き型言語 + Parallel命令＝ PRAM用並列言語 PRAMコンパイラの構造原始プログラム目的プログラム字句解析コード生成構文解析制約検査 PRAM用並列言語の文法 parallel文 parallel( i, j, k ) 命令文命令文命令文命令文実行実行実行実行プロセッサプロセッサプロセッサプロセッサ i i＋k i＋2k ・・・・・・・・・・・・・・命令文 j parallel文の例 PRAM用並列言語の例 main{ parallel(0,10,1) writeint($p); } 並列アセンブラで表す PUSHI 0 PUSHI 10 PUSHI 1 PARA PUSHP OUTPUT SYNC HALT PRAMシミュレータの実行例例: 2+3+5+7+1+8+5+4 プロセッサ4台時間 35 時刻3 17 プロセッサ1 時刻2 18 プロセッサ2 プロセッサ3 5 12 9 時刻1 9 プロセッサ4 2 3 5 7 1 8 5 4 時刻0 理論値 O(n/p+logp) 和計算プログラムの実行時間実行時間 t 100000 実行時間理論値 10000 1000 100 1 10 100 プロセッサ数　p (個) 1000 結果 和計算プログラムについて正しい解が出力された 実行時間は理論値とほぼ一致した正しい動作をしている結論 PRAM用並列言語の作成 PRAMシミュレータ（PRAMコンパイラ）の構築機能1 PRAM用並列言語を並列アセンブラに変換できる機能2 PRAM用並列言語のPRAM上での実行時間を計測できる