PRAMシミュレータの構築 情報論理工学研究室 01-1-26-071 柳原 大志 あらまし 背景 PRAM C風並列言語 PRAMシミュレータ 実行結果 結論 背景 問題を高速に解きたい 複雑な問題を解きたい 高性能コンピュータを手軽に使いたい 並列アルゴリズムの必要性が高まっている PRAM(parallel random-access machine) P1 P2 共有メモリ （Shared Memory） ・ ・ ・ ・ PN PRAM上の実行時間 時刻 0 P1 P2 P3 P4 1 2 3 読み 書き 演算 読み 演算 書き 読み 書き 読み ・・・・・・・ ・ 読み ・・・・・・・ ・ ・・・・・・・ ・ 読み 演算 ・・・・・・・ ・ 並列アルゴリズムの評価 アルゴリズムの評価 正当性 計算量 目的 PRAMアルゴリズムの評価を容易にする PRAMシミュレータを作成 PRAMアルゴリズムを記述できる言語を作成する C風並列言語を作成 C風並列言語 C言語 + 命令（parallel） C風 並列言語 命令 parallel parallel(i,j) 命令文 命令文 命令文 命令文 実行 実行 実行 実行 プロセッサ プロセッサ プロセッサ プロセッサ i i＋1 i＋2 ・・・・・・・ ・ ・・・・・・・ ・ 命令文 j C風並列言語の実行の流れ C風 並列言語 C言語 PRAMシミュレータ Cコンパイラ （既存） 実行形式 PRAMシミュレータの構造 C風 並列言語 C言語 PRAMシミュレータ 字句解析 構文解析 コード出力 PRAMシミュレータの実行例 足し算プログラム n個のデータの和を求める 実行時間の理論値は logｎ PRAMシミュレータによる 足し算プログラムの実行時間 100 90 80 70 実 60 行 50 時 間 40 30 ｔ－3ｎ 7ｌｏｇｎ 20 10 0 64 128 256 512 1024 データ数 n（個） 2048 4096 結論 C風並列言語を作成 PRAMシミュレータを構築 機能1 C風並列言語をC言語に変換 機能2 C風並列言語のPRAM上の実行時間を計測 課題 ① 関数が使えないなど、文法制限が多い C風並列言語の適応範囲の拡張 ② 入出力ファイルが限定されている 実行の際に入出力ファイルを自由 に指定可能にする
© Copyright 2024 ExpyDoc
