$30 off During Our Annual Pro Sale. View Details »

分子動力学法(3) 実装と高速化の詳細 / Simulation 07

分子動力学法(3) 実装と高速化の詳細 / Simulation 07

シミュレーション工学

kaityo256

May 22, 2023
Tweet

More Decks by kaityo256

Other Decks in Education

Transcript

  1. 2 71 分子動力学法の実装 • 分子動力学法には様々な種類がある • 短距離古典分子動力学法のコードは比較的単純 本講義の目的 • 効率の良いコードの実装には、ハードウェ

    アの理解が必須であることを知る • 単純なコードであっても、計算機の性能を 引き出すのは面倒であることを知る
  2. 4 71 𝑚𝑎 = 𝐹 物体の加速度は 物体に働く力に比例する 物体に働く力の分類 外力 原子間力

    重力 外場による振動など 多体力 二体力 ファンデルワールス力 バネなど 曲げ弾性など
  3. 9 71 粒子法 格子法 支配方程式を固定した格子上で 離散化して解く 支配方程式を流れに沿って動く参 照点上で離散化して解く SPH (Smoothed

    Particle Hydrodynamics) MPS (Moving Particle Semi-implicit) 粒子法と分子動力学法は扱う支配方程式が異なる
  4. 10 71 • 分子動力学法(Molecular Dynamics method, MD) は、原子に働く力を計算し、運動方程式を数値積 分することで時間発展させる手法 •

    原子の電子状態を真面目に解くのが第一原理MD、 経験ポテンシャルで代用するのが古典MD • 経験ポテンシャルを使う場合、力が遠距離まで届 く場合と近距離で減衰する場合で扱いが大きく異 る • 粒子法と分子動力学法は違う(数値計算手法とし ての性質は似ているが、解いている支配方程式が 異なる)
  5. 11 71 簡単のため、二体相互作用のみを考える 運動を支配するハミルトニアンは以下の通り 𝐻 = ෍ 𝑖 Ԧ 𝑝𝑖

    2 2𝑚 + ෍ 𝑖<𝑗 𝑉(𝑞𝑖𝑗 ) 𝑞𝑖𝑗 ≡ Ԧ 𝑞𝑖𝑗 = |Ԧ 𝑞𝑖 − Ԧ 𝑞𝑗 | 𝑞𝑖𝑗
  6. 12 71 位置の時間発展は簡単 𝐻 = ෍ 𝑖 Ԧ 𝑝𝑖 2

    2𝑚 + ෍ 𝑖<𝑗 𝑉(𝑞𝑖𝑗 ) 𝑑𝑞𝑖 𝑥 𝑑𝑡 = 𝜕𝐻 𝜕𝑝𝑖 𝑥 = 𝑝𝑖 𝑥 𝑚 𝑑 Ԧ 𝑞𝑖 𝑑𝑡 = 𝜕𝐻 𝜕 Ԧ 𝑝𝑖 = Ԧ 𝑝𝑖 𝑚 𝑑𝑞 𝑖 𝑦 𝑑𝑡 = 𝜕𝐻 𝜕𝑝 𝑖 𝑦 = 𝑝 𝑖 𝑦 𝑚 𝑑𝑞𝑖 𝑧 𝑑𝑡 = 𝜕𝐻 𝜕𝑝𝑖 𝑧 = 𝑝𝑖 𝑧 𝑚 まとめてベクトル形式で
  7. 13 71 運動量の時間発展はちょっと面倒 𝐻 = ෍ 𝑖 Ԧ 𝑝𝑖 2

    2𝑚 + ෍ 𝑖<𝑗 𝑉(𝑞𝑖𝑗 ) 𝑑𝑝𝑖 𝑥 𝑑𝑡 = − 𝜕𝐻 𝜕𝑞𝑖 𝑥 = − ෍ 𝑖<𝑗 𝜕𝑉 𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥 𝑞𝑖𝑗 ≡ Ԧ 𝑞𝑖𝑗 = |Ԧ 𝑞𝑖 − Ԧ 𝑞𝑗 |
  8. 14 71 𝑓𝑖𝑗 𝑥 = − 𝜕𝑉 𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥

    = − 𝑑𝑉 𝑞𝑖𝑗 𝑑𝑞𝑖𝑗 𝜕𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥 Ԧ 𝑞𝑖𝑗 Δ𝑥 𝑞𝑖𝑗 2 = 𝑞𝑖 𝑥 − 𝑞𝑗 𝑥 2 + 𝑞 𝑖 𝑦 − 𝑞 𝑗 𝑦 2 + 𝑞𝑖 𝑧 − 𝑞𝑗 𝑧 2 2𝑞𝑖𝑗 𝜕𝑞𝑖𝑗 𝜕𝑞𝑖 𝑥 = 2(𝑞𝑖 𝑥 − 𝑞𝑗 𝑥) ij原子間に働く力のx成分 距離の定義 両辺を𝑞𝑖 𝑥で偏微分 𝑓𝑖𝑗 𝑥 = − 𝑑𝑉 𝑞𝑖𝑗 𝑑𝑞𝑖𝑗 Δ𝑥 𝑞𝑖𝑗
  9. 15 71 𝑉 𝑟 = 4𝜀 𝜎 𝑟 12 −

    𝜎 𝑟 6 𝜀:相互作用エネルギー 𝜎:原子直径 貴ガスの相互作用をモデル化 • 近距離で斥力 • 中距離で引力 • 遠距離で相互作用無し
  10. 16 71 𝑉 𝑟 = 4 𝑟−12 − 𝑟−6 Ԧ

    𝑟 = (𝑑𝑥, 𝑑𝑦, 𝑑𝑧) 相対座標 ポテンシャル 力 𝑓 𝑟 = 48 𝑟13 − 24 𝑟7 𝐼𝑥 = 𝑓 × Δ𝑥 𝑟 × 𝑑𝑡 x方向の力積 = 48 𝑟14 − 24 𝑟8 Δ𝑥𝑑𝑡 𝑟 Δ𝑥 Δy 力積が距離の偶数次のみで記述できる
  11. 17 71 貴ガスの相互作用をモデル化 • 近距離で斥力 • 中距離で引力 • 遠距離で相互作用無し 原子は遠距離で相互作用しない

    カットオフ距離を設定し、それ以遠は無視 カットオフ距離内の原子ペアのみ力を計算する
  12. 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 原子数が大きい領域で使い物にならない
  13. 22 71 1. 初期状態を生成する 2. グリッド探索により相互作用ペアを作成する 3. それぞれのペアについて力積を計算し、運動量を更新する 4. 更新された運動量にもとづいて位置を更新する

    5. 3~5を繰り返す 分子動力学法の実装方法 力の計算 • ポテンシャルが距離の偶数次のみを含む場合、力積が距離の偶 数次のみで書ける • ポテンシャルが奇数次を含む場合は逆数平方根の計算が必要 相互作用ペアリスト • 相互作用距離にカットオフがある場合、相互作用する原子ペア を探索する必要がある • 全探索すると𝑂(𝑁2)だが、グリッド探索により𝑂(𝑁)となる
  14. 28 71 FLOPS (floating operations per second) 計算機の演算性能を表す指標 一秒間に浮動小数点演算を何回できるか Byte/s

    メモリの転送性能を表す指標 一秒間に何バイトを転送できるか Byte/Flop (B/F) メモリ転送性能と演算性能の比 1回演算する間に何バイト転送できるか
  15. 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までしか出せない
  16. 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を要求
  17. 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粒子のみ →ペア数が十分多ければメモリアクセスが半分に
  18. 34 71 0 1 2 3 4 5 6 7

    00 10 20 30 14番地のデータをください 連続する塊を まとめて取ってくる (ライン) キャッシュからあふれたラインは メモリに書き戻す
  19. 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 キャッシュ容量の一部しか活用してない キャッシュミスが多発 キャッシュ容量の大部分を活用 キャッシュヒット率が高い
  20. 38 71 探索範囲 相互作用範囲 マージン • ペアリスト構築時に、相互作用距離 より離れた距離にいるペアを探索、 リストに登録する •

    安全マージンを使い切るまで、同じ ペアリストを使いまわす • この手法をBookkeeping法と呼ぶ 重い処理であるペアリスト作成をサボることができる 相互作用ペアリストに相互作用していないペアを含む ため、力の計算前にチェックが必要 適切なマージンを取ると、全体で二倍以上早くなる
  21. 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 番号のふり直し
  22. 40 71 L2 Cache (256 KB) L3 Cache (8 MB)

    ソートあり ソートなし 粒子数 ソートなし:粒子数がキャッシュサイズをあふれる度に性能が劣化する ソートあり:性能が粒子数に依存しない Higher is Better
  23. 53 71 ※ Very Long Instruction Word ソフトウェアにがんばらせる コンパイラがデータと 命令を並べておく

    それをノーチェックで 演算機に流しこむ 依存関係チェックが不要→ハードウェアが簡単に 神のように賢いコンパイラが必要 後方互換性を失う 組み込み向けでは人気も HPC向けとしてはほぼ絶滅
  24. 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 +
  25. 59 71 3 8 2 5 1 3 4 8

    4 11 6 13 + 3 1 4 + 一つの計算をするのと同じ時間で 複数の計算を同時に実行できる CPUの理論ピーク性能は「SIMD幅を使い切った時」の値 SIMDが使えていなければ、数分の一の性能しか出せない
  26. 60 71 各位置ごとに異なる演算はできない 1 3 4 8 3 8 2

    5 4 11 6 13 + 複数のデータ(Multiple Data)に 単一の演算 (Single Instruction)を実行するから SIMD (Single Instruction Multiple Data)
  27. 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 メモリ レジスタ
  28. 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; 相対ベクトル 転置 自乗和
  29. 68 71 原子数: 12万, 数密度: 1.0, カットオフ: 3.0 100回の力の計算にかかった時間 [ms]

    ×1.44 ×1.07 ×2.31 ナイーブな実装 細かい最適化 SIMD化 i粒子でソート
  30. 69 71 • SIMDは1サイクルに複数の命令を実行す るための工夫の一つ • SIMDは幅広レジスタに複数のデータを載 せて同時に独立な計算を実行する • SIMD化の目的はSIMDレジスタを活用す

    ることで性能を向上させること • SIMD化は、コンパイラに任せる方法と、 自分で書く方法がある • SIMD化により数倍性能が変わるが、デー タ構造を変えたり、アセンブリを書いた りする必要がある
  31. 70 71 • 現代のCPUは、構造が複雑化、多階層化しており、性 能を出すのが困難 • 特にメモリアクセスがボトルネックになりやすいため、 性能を出すためにはキャッシュの有効活用が必要 • 現代CPUの性能はSIMD幅を使い切った場合の値であ

    り、SIMDレジスタを活用できないコードは性能が出 ない • 単純なコードであっても、高い計算効率を達成するに は、アルゴリズム(ソフトウェア)とハードウェアの両 方の知識が必要