Microsoft PowerPoint - 講義1：離散化と並列化.pptx

講 義 1: 離 散 化 と 並 列 化 214 年 3 月 5 日 神 戸 大 学 大 学 院 システム 情 報 学 研 究 科 計 算 科 学 専 攻 横 川 三 津 夫

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 1 講 義 の 内 容 計 算 機 シミュレーション 非 定 常 問 題 の 時 間 微 分 項 の 離 散 化 定 常 問 題 線 型 方 程 式 の 反 復 解 法 実 行 時 間 の 評 価

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 2 計 算 機 シミュレーション 現 象 現 象 のモデル 化 数 理 モデル 偏 微 分 方 程 式 など 離 散 化, アルゴリズム 計 算 離 散 化 ( 計 算 格 子 も 選 択 ) 有 限 差 分 法, 有 限 要 素 法, スペクトル 法 など 足 し 算, 掛 け 算 だけの 式 で 記 述 プログラム,コンピュータ 結 果 の 検 証

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 3 熱 伝 導 問 題 ( 非 定 常 ) 2cm 長 さ2cmのアルミニウム 棒 の 左 端 を 温 めたとき,1 分 後 の 右 端 の 温 度 は 何 度 になっているのか? 棒 の 温 度 がどんな 風 に 変 化 するかを 知 りたい. 最 初 の 棒 の 温 度 は2 ( 初 期 状 態 ) 左 端 を 加 熱 し, 温 度 1 にする. 熱 伝 導 度 9.7x1-5 m 2 /s 長 さ 方 向 の 温 度 変 化 だけを 見 れば 良 い. 1 次 元 問 題

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 4 モデル 化 (1 次 元 非 定 常 熱 伝 導 問 題 ) 座 標 x 2cm 2 4 6 8 1 12 14 16 18 2 長 さ2cmのアルミニウム 棒 の 左 端 を 温 めたとき,1 分 後 の 右 端 の 温 度 は 何 度 になっているのか? 棒 の 温 度 がどんな 風 に 変 化 するかを 知 りたい. 最 初 の 棒 の 温 度 は2 ( 初 期 状 態 ) 左 端 を 加 熱 し, 温 度 1 にする. 熱 伝 導 度 9.7x1-5 m 2 /s 長 さ 方 向 の 温 度 変 化 だけを 見 れば 良 い. 1 次 元 問 題 1 次 元 の 数 理 モデル( 偏 微 分 方 程 式 )で 表 現 1 次 元 非 定 常 熱 伝 導 方 程 式 a 2 2 x

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 5 離 散 化 : 連 続 な 量 を 有 限 個 の 点 で 表 現 すること 2 2 x a 2 1 1 ) ( 2 x a ) 2 ( ) ( 1 1 2 Δ x a 時 間 微 分 : 前 進 オイラー 法 空 間 微 分 : 有 限 差 分 法 ) 2 ( 1 1 Δ r = 1 2 3 4 5 6 7 8 9 1 x x x 定 義 2 x 1 5 x =r 番 号 離 散 化

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 6 時 刻 の 温 度 から 経 過 した 後 の 温 度 を 求 める 式 Δ r( 1 2 1) 乗 算 : 2 回 加 減 算 : 3 回 時 刻 =3に 注 目 1 2 3 4 5 6 7 8 9 1 2 3 4 時 刻 + 3 Δ 1 2 3 4 5 6 7 8 9 1

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 7 プログラミング 言 語 FORTRAN77によるプログラム real*8 _new(:2), _old(:2) 格 子 分 割 数 2 n = 2 格 子 間 隔 x=1cm dx =.2/real(n) 時 間 間 隔 =.5 秒 d =.5 熱 伝 導 度 a=9.7x1 5 a = 9.7e 5 r = a*d/(dx*dx) do =, 2 初 期 温 度 を 設 定 する. _old() = 2. enddo 左 端 を1 度 にする. _old() = 1. r( 1 2 1) Δ 12x.5 秒 =6 秒 まで 繰 り 返 し do i = 1, 12 do = 1, 19 各 格 子 点 の 値 を 求 める. _new() = (1. 2.*r)*_old() + r*(_old( 1)+_old(+1)) enndo do = 1, 19 _old() = _new() enddo _old[2] = _old[19] 結 果 を 書 き 出 す. wrie(6,*) d*i, (_old(), =,2) enddo sop end

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 8 秒 から6 秒 までの 温 度 変 化 (1 秒 間 隔 ) 1 = 秒 =1 秒 8 =2 秒 =3 秒 温 度 ( ) 6 4 49 =4 秒 =5 秒 =6 秒 3 2. 5. 1. 15. 2. アルミ 棒 の 左 端 位 置 (cm) アルミ 棒 の 右 端

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 9 非 定 常 問 題 ( 時 間 発 展 方 程 式 )に 対 する 時 間 微 分 項 の 離 散 化 : は 空 間 の 微 分 演 算 子 を 含 む 項 初 期 条 件, 境 界 条 件 が 与 えられる. 境 界 条 件, 2 " 初 期 条 件,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 1 時 間 発 展 ( 非 定 常 ) 方 程 式 に 対 する 時 間 微 分 項 の 離 散 化,, は 時 間 刻 み 幅 ( 時 間 ステップ) 陽 解 法 過 去 の 情 報 だけで, 次 の 時 刻 の 値 を 求 める 方 法 陰 解 法 次 の 時 刻 の 値 を 求 めるために, 空 間 の 微 分 式 が 成 立 する として 求 める 方 法 単 段 法 時 刻 の 値 だけを 用 いて, 時 刻 の 値 を 求 める 方 法 前 進 オイラー 法 ルンゲ クッタ 法 など 後 退 オイラー 法 など 多 段 法 複 数 の 過 去 の 時 刻,, の 値 を 用 いて, 時 刻 の 値 を 求 める 方 法 アダムス-バッシュフォース 法 リープ-フロッグ 法 など 2 アダムス-モールトン 法 など

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 11 定 常 問 題 ( 熱 伝 導 方 程 式 を 例 として) 熱 伝 導 方 程 式, の 定 常 状 態 の 解 ( の 時 の 解 )はどうなるか? & 境 界 条 件 境 界 条 件 Dirichle(ディリクレ) 問 題 : 対 象 となる 領 域 の 境 界 上 で 解 の 値 が 指 定 さ れる 場 合 Nemann(ノイマン) 問 題 : 境 界 上 で 法 線 方 向 の 微 分 が 指 定 されている 場 合

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 12 2 次 元 定 常 熱 伝 導 問 題 2 次 元 正 方 形 領 域 [,1] [,1] での 熱 伝 導 問 題 境 界 条 件, 1 1, 1, 1,1 sin 1

差 分 式 のテイラー 級 数 展 開 からの 導 出 (2 変 数 ),,,, 2!,,,, 2! これらの 式 から...,,,,, 2,,,,,,, 2,, 214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 13

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 14 2 次 元 定 常 熱 伝 導 問 題 の 離 散 化 (その1) 方 向 を 1 等 分 : 1/1, 方 向 を 1 等 分 : 1/1,,, 境 界 条 件 として 既 知 の 値 内 部 の 格 子 点 ( 未 知 数 ) 内 部 の 格 子 点 での 関 係 式 を 作 る.,,,,,,,,,,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 15 離 散 化 偏 微 分 方 程 式 の 中 の 偏 導 関 数 をその 差 分 近 似 で 置 き 換 えることによ り, 偏 微 分 方 程 式 が 連 立 一 次 方 程 式 になる. を, 点,, で 離 散 化,,,,,, とすると,,,,,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 16, を 辞 書 式 順 序 で 並 べたベクトルをとすると, 点, に 関 する 離 散 式 は,,,,,,,,,,,,,,,,, 4,,, 1 1 4 1 1 離 れている 離 れている,,,,,,,,,,,,,,,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 17 行 列 表 現 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4,,,,,,,,,,,,,,,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 18 1 次 元 問 題 に 対 する 行 列, 次 連 立 一 次 方 程 式 が 導 かれる 行 列 形 式 :

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 19 線 形 方 程 式 とその 解 法 = : 正 方 行 列, 正 則 かつ =, = : 次 元 ベクトル 次 線 形 方 程 式 を 解 く. =,または 直 接 法 : 行 列 操 作 により 厳 密 解 を 求 める 方 法 ガウス 消 去 法 LU 分 解 法 ( 対 称 行 列 用 コレスキー 法 )など

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 2 連 立 一 次 方 程 式 の 反 復 解 法 反 復 法 を 真 の 解 の 近 似 値 とし, 反 復 ベクトルの 系 列 により, 真 の 解 に 近 づける 方 法 反 復 ベクトルの 系 列 の 作 り 方 によりいろいろな 解 法 がある. 定 常 反 復 法 ヤコビ 法 (Jacobi 法 ) ガウス ザイデル 法 (Gass-Seidel 法 ) 逐 次 過 大 緩 和 法 (Sccessive Over-Relaxaion:SOR) 法 交 互 方 向 法 (Alernaing-Direcion Implici Ieraive Mehod: ADI 法 )など クリロフ(Krylov) 空 間 法 共 役 勾 配 法 (Congae Gradien Mehod,CG 法 ) 講 義 4 双 共 役 勾 配 法 (Bi-CG 法 ) 一 般 化 最 小 残 差 法 (GMRES 法 )など

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 21 行 列 分 離 行 列 分 離 : = : 狭 義 下 三 角 行 列 : 対 角 行 列 : 狭 義 上 三 角 行 列

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 22 (1) ヤコビ 法 (Jacobi Mehod) ヤコビ 行 列 で, 反 復 ベクトル 系 列 を 生 成 する., / 1,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 23 (2) ガウス ザイデル 法 (Gass-Seidel Mehod) ガウス ザイデル 行 列 / 1,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 24 (3) SOR 法 (Sccessive Over-Relaxaion Mehod) 1, これらを 整 理 すると, 1 1 ω SOR 行 列

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 25 熱 伝 導 問 題 への 反 復 法 の 適 用 (ヤコビ 法 ) ヤコビ 法,,,,, 4 演 習 1 ガウス ザイデル 法,,,,, 4

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 26 ヤコビ 法, から, を 計 算 するので,どの 点 から 計 算 しても 同 じ 結 果 になる. 領 域 分 割 によって 並 列 化 が 可 能.

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 27 ヤコビ 法 プロセス1 プロセス

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 28 ガウス ザイデル 法, の 計 算 には, 更 新 された,,, が 必 要.このままでは 並 列 化 出 来 ない.

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 29 ガウス ザイデル 法 プロセス1 プロセス 計 算 の 順 番 に 着 目 して, 並 列 化 可 能 なプログラムを 見 つける. マルチカラー 法

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 3 ヤコビ 法 のMPI 並 列 化 の 方 針 (その1) 領 域 分 割 によりMPI 並 列 化 (プロセス 並 列 化 )を 行 う. 各 プロセスは, 部 分 の 計 算 を 担 当 する. 境 界 は 条 件 として 与 えられているの で, 計 算 しないこ とに 注 意

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 31 ヤコビ 法 のMPI 並 列 化 の 方 針 (その2) 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4,,,,,,,,,,,,,,,

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 32 ヤコビ 法 のMPI 並 列 化 の 方 針 (その3) 各 プロセスでの 計 算 には, 上 下 の 部 分 の 値 が 必 要 であることに 注 意.,, 4,,, スレッド 並 列 では, の 部 分 に 同 時 にアクセスしないようにする. プロセス 並 列 では, 上 下 部 分 の 値 を 転 送 する 必 要 がある.

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 33 実 行 時 間 の 評 価 並 列 実 行 数 とともに, 実 行 時 間 が 減 少 することが 期 待 される.ただし, 並 列 化 により, 計 算 結 果 が 異 ならないよう 注 意 する. 並 列 数 n に 対 し, 計 算 時 間 は 1/n になることが 期 待 実 行 時 間 を 計 測 して 確 認. スケーラビリティ 弱 スケーリング(weak scaling) 並 列 実 行 単 位 (スレッド,またはプロセス)あたりの 問 題 サイズを 一 定 に 保 ったまま(したがって 問 題 のサイズは 大 きくなる), 並 列 実 行 数 (ス レッド 数,プロセス 数 )を 増 加 させた 時 に, 実 行 時 間 がどのように 変 化 す るかをみる 性 能 評 価 指 標 強 スケーリング(srong scaling) 全 体 の 問 題 サイズを 固 定 したまま, 並 列 実 行 数 (スレッド 数,プロセス 数 )を 増 加 させた 時 に, 実 行 時 間 がどのように 変 化 するかをみる 性 能 評 価 指 標

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 34 弱 スケーリング 並 列 実 行 単 位 (スレッド,またはプロセス)あたりの 問 題 サイズを 一 定 に 保 っ たまま, 並 列 実 行 数 (スレッド 数,プロセス 数 )を 増 加 させた 時 に, 実 行 時 間 がどのように 変 化 するかをみる 性 能 評 価 指 標 1プロセス 2プロセス 4プロセス 8プロセス

214/3/5 RIKEN AICS HPC Spring School 214: 離 散 化 とその 周 辺 35 強 スケーリング 全 体 の 問 題 サイズを 固 定 したまま, 並 列 実 行 数 (スレッド 数,プロセス 数 )を 増 加 させた 時 に, 実 行 時 間 がどのように 変 化 するかをみる 性 能 評 価 指 標 2プロセス 4プロセス 8プロセス