並列計算入門

並列計算入門#

qc-rs 固有の話に入る前に、本章は Part IV の残りが使う語彙を — HPC の予備知識を前提とせず — 築きます。 並列性とは何か、スレッドとプロセスとは何か、なぜクラスタは大きなノート PC と違うのか、実際どれだけの高速化が 期待できるのか。

なぜ並列性か:同時に仕事をする#

1 つの CPU コアは 1 本の命令列を実行します。量子化学計算は数十億の算術演算で、1 コアでは次々と行われます。 現代のハードウェアは多数のコア（ノート PC で 4〜16、サーバで 64〜256）を持ち、クラスタは多数のマシンを 持ちます。並列性とは、仕事を分割して、異なるコアやマシンで同時に片々を走らせることで、総仕事量は変わらなく ても実時間（実際に待つ時間）を削ることです。

落とし穴は、すべての仕事がきれいに分割できるわけではないこと:一部のステップは以前の結果に依存し、片々の調整も 時間を食います。どれだけ得するかは、問題がどれだけ並列化可能かに依存します — 下で定量します。

スレッド 対 プロセス:共有メモリ 対 分散メモリ#

片々を並列に走らせるには根本的に異なる 2 つの方法があり、その違い — どうデータを共有するか — が Part IV の すべてを駆動します。

定義 5 (スレッドとプロセス)

  • プロセスは自分専用のメモリを持つ独立した実行中のプログラムです。2 つのプロセスは互いのデータを直接 見られず、共有するにはメッセージを送る（データを間でコピーする）必要があります。

  • スレッドはプロセスの中の 1 本の実行の流れです。1 プロセスの複数スレッドは同じメモリを共有するので、 コピーなしに同じデータで作業できます。

これが 2 つの古典的な並列モデルを与えます:

  • 共有メモリ（スレッド）:1 台のマシンの複数コアが RAM 上の 1 つのデータのコピーで作業します。速く （コピーなし）単純ですが、単一マシンのコアとメモリに限られます。→ スレッドと BLAS。

  • 分散メモリ（プロセス / MPI）:多数のプロセスが、場合により異なるマシン上で、各々データの一部を 保持し、ネットワーク越しにメッセージを渡して片々を交換します。数千コアと巨大な問題までスケールしますが、 プログラマが何がどこにあり、いつ通信するかを管理せねばなりません。→ MPI と相互接続。

GPU は第 3 のモデル — 自分のメモリを持つ数千の小さなコアで、巨大な配列に同じ演算を適用するのに理想的です。 → GPU / CUDA。

実際の HPC 実行はしばしば 3 つすべてを入れ子にします:マシン間で MPI、各マシン内でスレッド、各々に付いた GPU。

どれだけ速くなるか:Amdahl の法則#

並列性には厳しい天井があります:並列化できない部分が、いくらコアを投入しても総高速化を制限します。

定理 3 (Amdahl の法則)

プログラムの実行時間の割合 \(p\) が並列化可能（\(1-p\) が本質的に逐次）なら、\(N\) コアでの高速化は

\[ S(N) = \frac{1}{(1-p) + \dfrac{p}{N}} \;\xrightarrow{N\to\infty}\; \frac{1}{1-p}. \]

なので 90% が並列なら（\(p=0.9\)）、最大高速化は \(1/(1-0.9) = 10\times\) — 無限のコアがあってもです。逐次の 10% が規模で支配します。

実践的な教訓:(1) 逐次部分が効き始めると、コアを 2 倍にしても時間は半分にならない;(2) 収穫逓減点を超えて コアを足すのは無駄;(3) 逐次割合（や通信オーバーヘッド）を減らす方が、ハードウェアを足すより価値があることが 多い。だから qc-rs は高価なステップ（積分組み立て、XC グリッド、J/K 構築）を並列化し、小さな分子は 16 コア でも 4 コアと変わらないかもしれません — 仕事が小さすぎて調整コストを上回れないのです。

Tip

仮定せず測る 大きなジョブに踏み切る前に、必ず 2〜3 のコア数で実際の実時間を確認してください — 小さすぎる、または逐次 ステップに支配される計算は速くならず、他の人が使えるコアを占有するだけです。「比だけでなく絶対時間を報告する」は 自分の実行にも当てはまります。

ハードウェアの地形#

  • マルチコア CPU（ノート PC や 1 サーバノード）:共有メモリ、スレッドで駆動。最初で最も易しい高速化。

  • クラスタ（ネットワークで結ばれた多数のノード）:分散メモリ、MPI で駆動。ノードは相互接続で 通信 — 通常の Ethernet/TCP（遅い）か InfiniBand（速い、帯域 ~35 倍）で、通信の多いステップ（次章以降）に 非常に効きます。

  • GPU:配列の多いカーネル用の超並列アクセラレータ、ノードごとの任意の追加。

ここまでで得たもの#

概念が揃いました:コアと実時間、スレッド（共有メモリ）対 プロセス/MPI（分散メモリ）対 GPU、そして Amdahl の 天井。次の 3 章が各々を qc-rs のノブに対応づけます — 最も単純で最も有用な スレッド から。

練習 16

  1. 同僚が「ジョブに 64 コア与えたのに 6 倍しか速くならなかった — ソフトが壊れている」と言います。Amdahl の 法則で無害な説明をしなさい。6 倍の天井を与える並列割合 \(p\) は？

  2. 128 コアのマシン 1 台と、4 台のクラスタ（各 32 コア）があります。大きな配列を絶えず共有する必要があるジョブ では、どちらが良さそうで、なぜですか。

  3. コアを足しても SCF の収束エネルギーが変わらず、時間だけが変わるのはなぜですか。