Share
Embed
Transcript
71 slides
-
2 71 分子動力学法の実装 • 分子動力学法には様々な種類がある • 短距離古典分子動力学法のコードは比較的単純 本講義の目的 • 効率の良いコードの実装には、ハードウェ
アの理解が必須であることを知る • 単純なコードであっても、計算機の性能を 引き出すのは面倒であることを知る -
4 71 𝑚𝑎 = 𝐹 物体の加速度は 物体に働く力に比例する 物体に働く力の分類 外力 原子間力
重力 外場による振動など 多体力 二体力 ファンデルワールス力 バネなど 曲げ弾性など -
5 71 原子間力の起源:原子や電子の量子力学的な相互作用 電子状態を真面目に計算する →第一原理計算(ab initio calculation) 第一原理計算で力を計算して原子を動かす →第一原理MD (ab
initio MD, Car-Parrinello method) ※ 電子状態は密度汎関数理論(Density Functional Theory, DFT)で計算する -
6 71 毎回電子状態を解くのは大変なのでモデル化 距離だけの関数で表現 多体力 二体力 𝜃 𝑟 原子の位置関係で表現 電子状態を解かず、原子の位置関係による経験的な
ポテンシャルで計算する方法を古典分子動力学法と呼ぶ -
7 71 短距離力 距離が離れると急速に弱くなる力 ファンデルワールス力など 一定距離(カットオフ距離)で力の計算を打ち切る Bookkeeping法などで計算コストを落とす(後述) 長距離力 離れた距離でも力が及ぶ クーロン力や重力など
周期的境界条件の扱いに工夫が必要(Ewald和等) 多重極展開などで計算コストを落とす ※本講義では紹介しません -
9 71 粒子法 格子法 支配方程式を固定した格子上で 離散化して解く 支配方程式を流れに沿って動く参 照点上で離散化して解く SPH (Smoothed
Particle Hydrodynamics) MPS (Moving Particle Semi-implicit) 粒子法と分子動力学法は扱う支配方程式が異なる -
10 71 • 分子動力学法(Molecular Dynamics method, MD) は、原子に働く力を計算し、運動方程式を数値積 分することで時間発展させる手法 •
原子の電子状態を真面目に解くのが第一原理MD、 経験ポテンシャルで代用するのが古典MD • 経験ポテンシャルを使う場合、力が遠距離まで届 く場合と近距離で減衰する場合で扱いが大きく異 る • 粒子法と分子動力学法は違う(数値計算手法とし ての性質は似ているが、解いている支配方程式が 異なる) -
11 71 簡単のため、二体相互作用のみを考える 運動を支配するハミルトニアンは以下の通り 𝐻 = 𝑖 Ԧ 𝑝𝑖
2 2𝑚 + 𝑖<𝑗 𝑉(𝑞𝑖𝑗 ) 𝑞𝑖𝑗 ≡ Ԧ 𝑞𝑖𝑗 = |Ԧ 𝑞𝑖 − Ԧ 𝑞𝑗 | 𝑞𝑖𝑗 -
12 71 位置の時間発展は簡単 𝐻 = 𝑖 Ԧ 𝑝𝑖 2
2𝑚 + 𝑖<𝑗 𝑉(𝑞𝑖𝑗 ) 𝑑𝑞𝑖 𝑥 𝑑𝑡 = 𝜕𝐻 𝜕𝑝𝑖 𝑥 = 𝑝𝑖 𝑥 𝑚 𝑑 Ԧ 𝑞𝑖 𝑑𝑡 = 𝜕𝐻 𝜕 Ԧ 𝑝𝑖 = Ԧ 𝑝𝑖 𝑚 𝑑𝑞 𝑖 𝑦 𝑑𝑡 = 𝜕𝐻 𝜕𝑝 𝑖 𝑦 = 𝑝 𝑖 𝑦 𝑚 𝑑𝑞𝑖 𝑧 𝑑𝑡 = 𝜕𝐻 𝜕𝑝𝑖 𝑧 = 𝑝𝑖 𝑧 𝑚 まとめてベクトル形式で -
13 71 運動量の時間発展はちょっと面倒 𝐻 = 𝑖 Ԧ 𝑝𝑖 2
2𝑚 + 𝑖<𝑗 𝑉(𝑞𝑖𝑗 ) 𝑑𝑝𝑖 𝑥 𝑑𝑡 = − 𝜕𝐻 𝜕𝑞𝑖 𝑥 = − 𝑖<𝑗 𝜕𝑉 𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥 𝑞𝑖𝑗 ≡ Ԧ 𝑞𝑖𝑗 = |Ԧ 𝑞𝑖 − Ԧ 𝑞𝑗 | -
14 71 𝑓𝑖𝑗 𝑥 = − 𝜕𝑉 𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥
= − 𝑑𝑉 𝑞𝑖𝑗 𝑑𝑞𝑖𝑗 𝜕𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥 Ԧ 𝑞𝑖𝑗 Δ𝑥 𝑞𝑖𝑗 2 = 𝑞𝑖 𝑥 − 𝑞𝑗 𝑥 2 + 𝑞 𝑖 𝑦 − 𝑞 𝑗 𝑦 2 + 𝑞𝑖 𝑧 − 𝑞𝑗 𝑧 2 2𝑞𝑖𝑗 𝜕𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥 = 2(𝑞𝑖 𝑥 − 𝑞𝑗 𝑥) ij原子間に働く力のx成分 距離の定義 両辺を𝑞𝑖 𝑥で偏微分 𝑓𝑖𝑗 𝑥 = − 𝑑𝑉 𝑞𝑖𝑗 𝑑𝑞𝑖𝑗 Δ𝑥 𝑞𝑖𝑗 -
15 71 𝑉 𝑟 = 4𝜀 𝜎 𝑟 12 −
𝜎 𝑟 6 𝜀:相互作用エネルギー 𝜎:原子直径 貴ガスの相互作用をモデル化 • 近距離で斥力 • 中距離で引力 • 遠距離で相互作用無し -
16 71 𝑉 𝑟 = 4 𝑟−12 − 𝑟−6 Ԧ
𝑟 = (𝑑𝑥, 𝑑𝑦, 𝑑𝑧) 相対座標 ポテンシャル 力 𝑓 𝑟 = 48 𝑟13 − 24 𝑟7 𝐼𝑥 = 𝑓 × Δ𝑥 𝑟 × 𝑑𝑡 x方向の力積 = 48 𝑟14 − 24 𝑟8 Δ𝑥𝑑𝑡 𝑟 Δ𝑥 Δy 力積が距離の偶数次のみで記述できる -
17 71 貴ガスの相互作用をモデル化 • 近距離で斥力 • 中距離で引力 • 遠距離で相互作用無し 原子は遠距離で相互作用しない
カットオフ距離を設定し、それ以遠は無視 カットオフ距離内の原子ペアのみ力を計算する -
19 71 for i in range(N-1): for j in range(i+1,N):
dx = qx[i] - qx[j] dy = qy[i] - qy[j] dz = qz[i] - qz[j] r2 = dx**2 + dy**2 + dz**2 if r2 < cutoff**2: add_pair(i, j) 単純な実装 計算量=ループの回転数 全てのペアについて距離をチェックする = 𝑁 𝑁 − 1 2 = 𝑂 𝑁2 原子数が大きい領域で使い物にならない -
22 71 1. 初期状態を生成する 2. グリッド探索により相互作用ペアを作成する 3. それぞれのペアについて力積を計算し、運動量を更新する 4. 更新された運動量にもとづいて位置を更新する
5. 3~5を繰り返す 分子動力学法の実装方法 力の計算 • ポテンシャルが距離の偶数次のみを含む場合、力積が距離の偶 数次のみで書ける • ポテンシャルが奇数次を含む場合は逆数平方根の計算が必要 相互作用ペアリスト • 相互作用距離にカットオフがある場合、相互作用する原子ペア を探索する必要がある • 全探索すると𝑂(𝑁2)だが、グリッド探索により𝑂(𝑁)となる -
23 71 1. 初期状態を生成する 2. グリッド探索により相互作用ペアを作成する 3. それぞれのペアについて力積を計算し、運動量を更新する 4. 更新された運動量にもとづいて位置を更新する
5. 3~5を繰り返す 分子動力学法の実装(再掲) 上記の単純な実装では まったく 性能が出ない -
28 71 FLOPS (floating operations per second) 計算機の演算性能を表す指標 一秒間に浮動小数点演算を何回できるか Byte/s
メモリの転送性能を表す指標 一秒間に何バイトを転送できるか Byte/Flop (B/F) メモリ転送性能と演算性能の比 1回演算する間に何バイト転送できるか -
29 71 for i in range(N): r[i] = r[i] +
v[i] * dt 一次元の運動方程式で位置を更新するコード ループ内のメモリ転送と計算量 1. r[i]とv[i]をロードする (16 Bytes) 2. 加算と乗算を実行する(2 FLOPS) 3. r[i]をストアする (8 Bytes) このコードでCPUが遊ばないためには、B/Fが12必要 現代のCPUの典型的なB/F値は0.5程度 ピーク性能の1/24までしか出せない -
30 71 力の計算はペアごとに行う 相互作用範囲内にあるペアは配列に格納 ペアの番号の若い方をi粒子、相手をj粒子と呼ぶ 相互作用ペア 1 9 0 2
0 1 2 7 3 9 3 5 1 2 1 4 2 8 3 4 0 5 2 6 i粒子 j粒子 2個の粒子の座標を取得 (48 Bytes) 力積を計算し、運動量を更新 (約50 FLOP) 運動量の書き戻し (48 Bytes) B/F=2.0を要求 -
31 71 0 1 2 5 1 2 4 9
2 6 7 8 3 4 5 9 i粒子 j粒子 i粒子をキーとしてソート 1 2 5 2 4 9 6 7 8 4 5 9 0 1 2 3 メモリ表現 i粒子の情報がレジスタに乗る →読み込み、書き込みがj粒子のみ →ペア数が十分多ければメモリアクセスが半分に -
32 71 メモリは大容量だが遠くてデータ転送が間に合わない →演算器の近くに小容量高速なメモリを置く(キャッシュ) CPU 演算器 演算器 キャッシュ メモリ 一度使ったデータは再利用する可能性が高いため、演算器
の近くにデータを残しておく(時間局所性) 使ったデータの周辺のデータは今後使われる可能性が高い ため、一緒に持ってくる(空間局所性) -
34 71 0 1 2 3 4 5 6 7
00 10 20 30 14番地のデータをください 連続する塊を まとめて取ってくる (ライン) キャッシュからあふれたラインは メモリに書き戻す -
36 71 メモリの連続アクセス 0 1 2 3 4 5 6
7 00 10 20 30 ここへのアクセスでキャッシュミス 残りのデータは続けてキャッシュヒット メモリのランダムアクセス 0 1 2 3 4 5 6 7 00 10 20 30 キャッシュ容量の一部しか活用してない キャッシュミスが多発 キャッシュ容量の大部分を活用 キャッシュヒット率が高い -
38 71 探索範囲 相互作用範囲 マージン • ペアリスト構築時に、相互作用距離 より離れた距離にいるペアを探索、 リストに登録する •
安全マージンを使い切るまで、同じ ペアリストを使いまわす • この手法をBookkeeping法と呼ぶ 重い処理であるペアリスト作成をサボることができる 相互作用ペアリストに相互作用していないペアを含む ため、力の計算前にチェックが必要 適切なマージンを取ると、全体で二倍以上早くなる -
39 71 時間発展を続けると、空間的には近い粒子が、メモリ上 では遠くに保存されている状態になる→ソート 0 1 2 3 1 4
9 7 8 5 12 6 11 10 0 2 3 13 0 1 2 3 0 2 1 4 5 3 6 7 8 12 9 13 10 11 0 1 2 3 0 1 2 3 10 13 4 9 5 7 8 12 6 11 9 0 10 11 12 13 1 2 3 4 5 6 7 8 番号のふり直し -
40 71 L2 Cache (256 KB) L3 Cache (8 MB)
ソートあり ソートなし 粒子数 ソートなし:粒子数がキャッシュサイズをあふれる度に性能が劣化する ソートあり:性能が粒子数に依存しない Higher is Better -
41 71 • 現代のCPUはメモリアクセスがボトルネックに なっており、高い計算性能を活かすのが困難 • 高速小容量メモリであるキャッシュの活用が性 能向上のカギ • 使うデータがなるべくメモリ上で連続している
方が性能が良い→ソートが有効 余計に計算してでもメモリアクセスを減らし たほうがトータルで高速になることが多い -
45 71 整数と浮動小数点数は異なるレジスタ、異なる演算器を使う 整数レジスタ 浮動小数点レジスタ 整数演算器 浮動小数演算器 整数レジスタ しか受け付けない 浮動小数点レジスタ
しか受け付けない ※SIMDレジスタは異なるデータ型で共有することが多い -
46 71 レジスタには長さがある レジスタの長さはビット数(bit)で表す 32ビットレジスタ 64ビットレジスタ ハードウェアやソフトウェアの「ビット数」は 対応する整数レジスタのビット数で決まる ファミコン 8ビット
スーファミ 16ビット プレステ 32ビット NINTENDO64 64ビット ・・・ -
47 71 数値計算では、主に倍精度実数を用いる 倍精度実数は64ビットで表現される 64ビット浮動小数点レジスタ 倍精度実数 (64ビット) ひとつ乗る 数値計算に用いるCPUの多くは64ビット整数レジスタと 64ビット浮動小数点レジスタを持つ
ただし、x86系のCPUは歴史的事情により64ビット浮動小数 点レジスタを持たず、128ビットSIMDレジスタを使う -
53 71 ※ Very Long Instruction Word ソフトウェアにがんばらせる コンパイラがデータと 命令を並べておく
それをノーチェックで 演算機に流しこむ 依存関係チェックが不要→ハードウェアが簡単に 神のように賢いコンパイラが必要 後方互換性を失う 組み込み向けでは人気も HPC向けとしてはほぼ絶滅 -
57 71 • 64ビットレジスタは倍精度実数を1つ載せることができる • 128ビットレジスタなら、2つ載せることができる • 256ビットレジスタなら、4つ載せることができる 128ビット 64ビット
256ビット ビット幅が広く、データを一度に複数載せることが できるレジスタをSIMDレジスタと呼ぶ -
58 71 1 3 4 8 2つのレジスタに4つずつ値を載せる(256ビットの場合) 3 8 2
5 「同じ位置」同士で同時に独立な演算をする 1 3 4 8 3 8 2 5 4 11 6 13 + -
59 71 3 8 2 5 1 3 4 8
4 11 6 13 + 3 1 4 + 一つの計算をするのと同じ時間で 複数の計算を同時に実行できる CPUの理論ピーク性能は「SIMD幅を使い切った時」の値 SIMDが使えていなければ、数分の一の性能しか出せない -
60 71 各位置ごとに異なる演算はできない 1 3 4 8 3 8 2
5 4 11 6 13 + 複数のデータ(Multiple Data)に 単一の演算 (Single Instruction)を実行するから SIMD (Single Instruction Multiple Data) -
66 71 Z Y X Z Y X Z Y
X Z Y X メモリ上にデータを以下のように並べる (パディング付きArray of Structure, AoS) 3成分のデータを256bitレジスタに一発ロードできる ただし1成分(64bit) は無駄になる Z Y X Z Y X Z Y X Z Y X メモリ レジスタ -
67 71 Z Y X i粒子 Z Y X -
j粒子 dz dy dx 相対座標 dz 1 dy 1 dx 1 dz 2 dy 2 dx 2 dz 3 dy 3 dx 3 dz 4 dy 4 dx 4 4ペア分計算 dx 1 dx 2 dx 3 dx 4 dy 1 dy 2 dy 3 dy 4 dz 1 dz 2 dz 3 dz 4 転置 r4 r3 r2 r1 自乗和 4ペア分の距離 v4df vdq_1 = vq_j1 - vq_i; v4df vdq_2 = vq_j2 - vq_i; v4df vdq_3 = vq_j3 - vq_i; v4df vdq_4 = vq_j4 - vq_i; v4df tmp0 = _mm256_unpacklo_pd(vdq_1, vdq_2); v4df tmp1 = _mm256_unpackhi_pd(vdq_1, vdq_2); v4df tmp2 = _mm256_unpacklo_pd(vdq_3, vdq_4); v4df tmp3 = _mm256_unpackhi_pd(vdq_3, vdq_4); v4df vdx = _mm256_permute2f128_pd(tmp0, tmp2, 0x20); v4df vdy = _mm256_permute2f128_pd(tmp1, tmp3, 0x20); v4df vdz = _mm256_permute2f128_pd(tmp0, tmp2, 0x31); v4df vr2 = vdx * vdx + vdy * vdy + vdz * vdz; 相対ベクトル 転置 自乗和 -
68 71 原子数: 12万, 数密度: 1.0, カットオフ: 3.0 100回の力の計算にかかった時間 [ms]
×1.44 ×1.07 ×2.31 ナイーブな実装 細かい最適化 SIMD化 i粒子でソート -
69 71 • SIMDは1サイクルに複数の命令を実行す るための工夫の一つ • SIMDは幅広レジスタに複数のデータを載 せて同時に独立な計算を実行する • SIMD化の目的はSIMDレジスタを活用す
ることで性能を向上させること • SIMD化は、コンパイラに任せる方法と、 自分で書く方法がある • SIMD化により数倍性能が変わるが、デー タ構造を変えたり、アセンブリを書いた りする必要がある -
70 71 • 現代のCPUは、構造が複雑化、多階層化しており、性 能を出すのが困難 • 特にメモリアクセスがボトルネックになりやすいため、 性能を出すためにはキャッシュの有効活用が必要 • 現代CPUの性能はSIMD幅を使い切った場合の値であ
り、SIMDレジスタを活用できないコードは性能が出 ない • 単純なコードであっても、高い計算効率を達成するに は、アルゴリズム(ソフトウェア)とハードウェアの両 方の知識が必要