並列計算とベクトル化

複数の演算資源を用いて計算を高速化する手法群。スケーラビリティの法則、並列化モデル、データ並列(SIMD/ベクトル化)を含む。

スケーラビリティの法則

• アムダールの法則: 逐次部分(オーバーヘッド)があるため並列化の速度向上は飽和する。1コアで100秒(逐次1秒+並列99秒)の処理は1000コアでも約1.1秒で、上限は逐次部分に支配される。
• グスタフソンの法則: 「十分に大きな規模の問題は効率的に並列化できる」。問題規模を増やす立場。
• ストロングスケール: 問題サイズを固定してコア数を増やす(アムダール的)。
• ウィークスケーリング: プロセッサあたりの問題サイズを固定。スパコンでは95%以上が望ましい。

フリンの分類

命令ストリームとデータストリームの組で計算機を分類する。

• SISD: 単純な逐次。
• SIMD: 1命令で複数データ。ベクトル演算、GPUの行列演算。
• MISD: 冗長化・信頼性(原発・航空機・衛星など)。
• MIMD: 命令もデータも完全独立。

並列化モデル

• MPI: プロセス並列フレームワーク(SPMD)。各プロセスがランクを持ち、コミュニケータ(MPI_COMM_WORLD)単位で集団通信(Bcast/Gather/Scatter/Alltoall/Reduce)や1対1通信(ブロッキング/ノンブロッキング)、片方向通信(Get/Put)を行う。1つ落ちると全部落ちる。
• OpenMP: スレッド並列。#pragma でfork-joinし、共有変数/プライベート変数、reduction節、criticalによる排他制御を扱う。OpenACCはそのGPU版。
• ハイブリッドモデル: 1コア1プロセス(MPI)+プロセス内スレッド並列(OpenMP)。一般にオーバーヘッドが少なく効率的。
• ファーストタッチ: NUMA環境で、データを実際に使うスレッドが初期化することで近接メモリに物理配置する最適化。
• グリーンスレッド: OSのネイティブスレッドではなく言語/VM上の軽量スレッド。

ベクトル化(SIMD)

• AVX-512: x86_64 の512bit SIMD ISA拡張(double×8 / float×16)。masked load 等。
• インターリーブされたデータ(一定ストライド)のベクトル化、不規則な間接アクセス(グラフ・粒子シミュレーション・ハッシュ集約)の競合フリーベクトル化(in-vector reduction)など、データ再編成を避ける研究が盛ん。
• データ依存性: write→read(フロー依存)、read→write(反依存)、write→write(出力依存)。リダクションで解消できる場合がある。
• ループ並列化の自動化(TornadoVM + Soot + z3 による静的解析)も研究されている。

関連: _moc-systems / cuda / cpu-architecture-isa