# 並列計算入門

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

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

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

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

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

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

:::{prf:definition} スレッドとプロセス
:label: def-thread-process

- **プロセス**は**自分専用のメモリ**を持つ独立した実行中のプログラムです。2 つのプロセスは互いのデータを直接
  見られず、共有するには**メッセージを送る**（データを間でコピーする）必要があります。
- **スレッド**はプロセスの*中*の 1 本の実行の流れです。1 プロセスの複数スレッドは**同じメモリを共有**するので、
  コピーなしに同じデータで作業できます。
:::

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

- **共有メモリ**（スレッド）:**1 台のマシン**の複数コアが RAM 上の 1 つのデータのコピーで作業します。速く
  （コピーなし）単純ですが、単一マシンのコアとメモリに限られます。→ [スレッドと BLAS](threads-and-blas.md)。
- **分散メモリ**（プロセス / **MPI**）:多数のプロセスが、場合により**異なるマシン**上で、各々データの*一部*を
  保持し、ネットワーク越しにメッセージを渡して片々を交換します。数千コアと巨大な問題までスケールしますが、
  プログラマが何がどこにあり、いつ通信するかを管理せねばなりません。→ [MPI と相互接続](mpi-and-interconnects.md)。

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

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

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

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

:::{prf:theorem} Amdahl の法則
:label: thm-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 のノブに対応づけます — 最も単純で最も有用な [スレッド](threads-and-blas.md) から。

:::{exercise}
:label: ex-primer

1. 同僚が「ジョブに 64 コア与えたのに 6 倍しか速くならなかった — ソフトが壊れている」と言います。Amdahl の
   法則で無害な説明をしなさい。6 倍の*天井*を与える並列割合 $p$ は？
2. 128 コアのマシン 1 台と、4 台のクラスタ（各 32 コア）があります。大きな配列を絶えず共有する必要があるジョブ
   では、どちらが良さそうで、なぜですか。
3. コアを足しても SCF の収束エネルギーが変わらず、時間だけが変わるのはなぜですか。
:::

:::{solution} ex-primer
:class: dropdown

1. 逐次割合が制限しています。6 倍の天井は $1/(1-p) = 6$、すなわち $p \approx 0.83$ — ジョブの約 17% が本質的に
   逐次（または通信律速）なので、64 コアでも ~6 倍を超えられません。壊れてはおらず、十分に並列でないだけです。
2. **128 コアのマシン 1 台** — **共有メモリ**（スレッド）を使うので、大きな配列を絶えず共有してもコストゼロ
   （コピーなし）。クラスタでは同じ共有が毎回配列をネットワークで送ることになり、通信律速のジョブでははるかに
   遅くなります。
3. エネルギーは物理（収束密度）で定まり、算術をコア間でどう分けるかでは定まりません。並列性は同じ演算の順序/
   配置を変えるだけなので、結果は（浮動小数点の簡約順序を除いて）同一です。
:::