並列処理について

並列処理と言葉の意味

コンピュータインフラストラクチャや計算処理では、並列化した複数のタスクを実行して計算処理を行うことができます。

アーキテクチャからの視点

SMP(Symmetric Multiprocessing/Shared Memory Processing)

メモリ共有型並列コンピューティングと言われるもので、計算処理は１つのノード内だけで複数のCPUを使って実行されます。

既存コードをほとんどそのままで実行することができます。しかし、メモリやストレージなどリソースに限界があります。特にメモリが不足する場合ではアウトオブコア処理(Out-Of-Core)に対応するための修正が必要になります。これは、メモリ上のデータを外部装置に書き出しておき、都度部分的に読み出しながら全体を処理する方法で、処理性能は大幅に低下してしまいます。

DMP (Distributed Multiprocessing/Distributed Memory Processing)

分散メモリ型並列コンピューティングと言われるもので、

ネットワークに結合された複数のコンピュータを利用して計算処理を分散して実行します。

HPC Cluster あるいは Beowulf Cluster と呼ばれることもあります。

使用するミドルウェアによっては既存コードを大幅に修正する必要があります。しかし、それを克服することができればシステムのリソースの限界を超えることができます。

運用コストからの視点

Webサービスを提供するようなときは、サービスを止めないことがとても重要になりますが、通常は、こうしたサービス維持をハードウェアで担保すると、そのコストは非常に大きくなります。

そもそも、ソフトウェアが実行されるコンピュータは、本来個別に運用されるものです。障害や運営側の都合で、処理途中にシャットダウンや停止される場合があります。

クラウドであれば、GCP Preemtible や AWS Spot のようにコストが安いけどクラウド運営側の都合でシャットダウンされてしまう可能性があるインスタンスもあります。

また、AWS Lambda や Azure Functions のように構築や運用面を考えなくてよくコストも安いけれど、短い時間しか使えないインスタンスもあります。

ソフトウエア側でこうした特性を充分に考慮して設計すれば、運用コストを大幅に抑えることができます。

処理パフォーマンスからの視点

アプリケーションのリソース要求とスケーリング

アプリケーションやサービスが動作するインフラストラクチャのスケーラビリティは、リソースを静的に追加/削除してアプリケーションの変化するニーズに対応します。これには、アプリケーションが処理を行うためのパフォーマンスとコストとのバランスで変化させたいという場合もあります。

ほとんどの場合、こうした問題には、スケールアップ（垂直スケーリング）やスケールアウト（水平スケーリング）によって処理されます。

スケールアップとスケールアウトの違い

スケールアップとスケールアウトの違いは図でみると理解が簡単です。

https://gyazo.com/7a9ca3ef3e8d778db05a76363b907076

スケールアップ(Scale Up) / 垂直スケーリング (Vertical Scaling)

スケールアップは、既存のシステムにリソースを追加することでパフォーマンスを得ようとします。このときのリソースは、メモリ、CPU（処理速度やコア数）、ストレージ、ネットワークインタフェースやネットワーク速度などになります。

特定のシステムをスケールアップする場合、オンプレミスで追加リソースを調達して運用開始するためには、通常は数週間または数か月かかりますが、クラウドでは数分程度ですみます。

クラウドでのスケールアップでは、アプリケーションはより強力なインスタンスへ移動することが多く、別のホストに移行して、元のサーバーを廃止することもあります。

スケールアップで留意するべきことは次のようになります。

物理的な限界

システムに静的にリソースを追加もしくは増強をしようとしても物理的な限界があり、スケールできる上限があります。また、多くの場合でシステムのコストが跳ね上がることになります。

サービスやアプリケーションの継続性と透過性の維持

スケールアップによりシステムの変更をユーザに意識させずに、アプリケーションを動作し続けるためには、それに応じた手続きや処理、運用方法などを設計段階から考慮する必要があります。

スケールアウト(Scale Out) / 水平スケーリング(Horizontal Scaling)

スケールアウトは分散アーキテクチャに分類されます。スケールアウトには2つの基本的なパターンがあります。

ハイパーコンバージドインフラストラクチャ(HCI: Hyper Converged Infrastructure)

あらかじめパッケージ化されたインフラストラクチャやノードをアプリケーションのインフラストラクチャに追加する方法

分散サービス

アプリケーションに依存しない分散リソースをサービスとして提供する方法。

リソース個々のコンポーネント（コンピューティング、メモリ、ネットワーク、ストレージ）のコストは垂直スケーリングに依存します。

スケールアウトで留意するべきことは次のようになります。

ソフトウェアが分散処理を意識する必要がある

プロセスとスレッドの違い

プロセスはそれぞれのメモリ空間は独立している

スレッドはプロセスのメモリ空間を共有している

https://gyazo.com/a0dd337530b58735f8a7c21b6073c9fa

スレッドについて

スレッドは "thread of execution（実行の脈絡）” に由来している言葉で、プログラム処理の実行単位です。プロセスに比べて、プログラムを実行するときのコンテキスト情報が最小で済むので切り替えが速くなります。コンテキストは、タスクが中断されるときは再開時のために実行中のタスクの内容を保存しておく必要があります。このプログラムの実行中の内容を保存するために使用されるのがコンテキストで、コンテキスト情報を切り替えることをコンテキストスイッチと言います。

ほとんどのPython 3実装では、実際には異なるスレッドが同時に実行されるわけではなく、中断されながら同時に実行されているように見えているだけです。

また、コンテキストスイッチはOS側で行われ、プログラムからは制御できません。

GIL(Global Interpriter Lock)

https://gyazo.com/40e72fc93e571620a5d172458bc38610

マルチプロセスで並列処理

複数のプロセスで並列処理を行うことで、GIL を回避することができます。

ただし、ロックを使ってしまうと状況は変わらないことに注意が必要です。

代表的なモジュール

マルチプロセスの注意点

マルチプロセスでプログラミングをするときに注意点には次のものがあります。

プロセスは独立したメモリ領域で動作している

変数へのアクセスには注意が必要

同じ変数やオブジェクトが同じ値を保持しているとは限らない

プロセス生成やデータ/オブジェクトをコピーするオーバヘッドを意識する

闇雲に並列化せずに、もっとも効果のある部分を並列化

物理コア数以上のプロセスで実行しない

並列数の上限が外部に依存していることに注意

並列処理が向いている問題

並列処理向いている問題には次のようなものがあります。

いずれも、大量の処理を、なんども繰り返す必要があるものです。

進化的アルゴリズム(Evolutional Algorithm)

モンテカルロ・シミュレーション (Monte Carlo Simulation)

データマイニング (Data Minning)

データ処理 (Data Processing)

グラフ分析 (Graph Traversal)

機械学習 (Machine Learning)

Amdahlの法則

具体的に説明してみましょう。

全体の性能向上率は次式で表されます。

$ \dfrac {1}{1-P+\dfrac {P}{S}}

$ \dfrac {1}{1-P}

この法則の意味は、並列化することによる性能向上は並列化できる処理の割合に依存するということです。

例えば、プログラムの12％を並列化できる（残り88%は並列化できないシリアル処理)とき、

https://gyazo.com/887eb2c95fc958c322724ed7c427eb78

Gustafsonの法則

$ S = s + p × N

https://gyazo.com/88ef002d2d22f4a0b6b03fd5a26f91a8

ただし、Gustafsonが指摘したように、実際には、問題のサイズは利用可能なリソースの量に比例します。 問題に必要なリソースが少ない場合、計算を実行するために大量のリソースを使用することは有益ではありません。 つまり、小さな問題には少量のリソースを使用し、大きな問題には大量のリソースを使用するということになります。

HPCクラスターを使用する場合、ほとんどの場合、ジョブの並列スケーリングを測定する価値があります。

強いスケーリングの計測：ジョブの全体的な計算時間が処理要素（スレッドまたはマルチプロセスのいずれか）の数を増やすことでテスト

弱いスケーリングの計測：ジョブサイズと処理要素の数の両方を増やすことによってテスト。

並列スケーリングの計測テストの結果は、特定のジョブのサイズを要求するリソースの量を適切に示すことになります。

並列プログラムを実行や開発をする上で重要なポイントを次にまとめます。

並列コンピューティングを効率化するには、スケーラビリティが重要

強いスケーリングは、プロセッサの数に関して固定された問題サイズの高速化に関係し、アムダールの法則に従う

弱いスケーリングは、プロセッサの数に関してスケーリングされた問題サイズの高速化に関係し、グスタフソンの法則に従う

HPCクラスターを使用する場合、ほとんどの場合、ジョブのスケーリングを測定する価値がある

強いスケーリングテストと弱いスケーリングテストの結果は、ジョブのサイズと特定のジョブに要求する必要のあるリソースの量との間で、最適なバランスを示す良い指標となる

参考