並列プログラミング
目的
もうすぐ、SuperConでスーパーコンピュータで競技するので、すこしでも並列処理について詳しくなって、何が必要かまとめます。ROP chalやりたいんですけど、解法もわかってもう少しっていうところで出来なくて泣きそうなので、少し別のことをしたいと思いました。以前、Geventについても調べていて、それをブログにうｐしてたのですが、当時は並列プログラミングにしか興味なくて実際どのような動きをコンピュータの中で動いているかわからなかったため、もう少し調べようと思いました。
内容
1.MPIについて
1-1.並列処理の種類
・単一命令・単一データ流（SISD)
・単一命令・複数データ流（SIMD)
・複数命令・単一データ流（MISD)
・複数命令・複数データ流（MIMD)
種類はたくさんあるが、有名なのは「単一命令・複数データ流（SIMD)である。SIMDとは、一つの命令で同時に複数のデータを処理する概念であります。MPIに基づく並列計算は広い意味でSIMDと…。メモリの使い方でも呼び方に種類があります。共有メモリ型と分散メモリ型。分散メモリ型では各CPUのメモリの中身を参照するために、メッセージを交換する（メッセージ・パッシング）必要があります。それをMPI(Message Passing Inferface)という。
1-2.並列プログラミングのモデル
実際どのような実行方式が行われているかわからないと、誤動作になる可能性が有る。SPMDモデルと、Master/Workerモデルがある。SPMDは、一つの並列プログラムしか存在せず、並列開始したときの並列プログラムがp個分コピーされて実行されます。MPI.ver1というわけです。Makster/Workerモデルは、一般的なモデルです。MasterはWorkerの生成と消去を管理することで、進めます。つまり、Master用とWorker用にプログラムが別れることがあります。
1-3.プログラムの種類
大きく分けて、マルチプロセス(HPF)とマルチスレッドがあります。Pythonでいうmultiprocessingモジュールが前者で、後者はthreadingモジュールが後者です。C言語で後者をPthreadというのをよく使います。僕が以前読んだ LinuxNetworkProgrammingに載っていたはずですプロセスとスレッドの概念について話します。プロセスとは、ソフトウェア上の概念で、CPUはハードウェア上での概念。ハードウェアの機能として１つのOSで1CPUに複数のスレッドを割り当てることを保証する場合、必ず１プロセスだけが１CPUに割り当てられるわけではないということです。すると、複数のMPIプロセスを1CPUに割り当てることができるという認識になります。スレッドとプロセスを混同して使うことでハイブリットMPI実行が可能となります。最近では、GPUも含めて使うことでMPI+X実行状態を可能にしています。GPGPUのことかな…。
1-4. 性能評価指標
並列化効率で、並列効率Ep[%] = Sp/P * 100 (0 <= Ep)となります。100台使って、効果が50倍のときは、並列化効率は50%となります。
アムダールの法則とは、並列処理でとても重要な法則となる。あるプログラムの実行時間をK秒とする。そのうち並列化が可能な割合をα%とする。その結果が図です。
無限大の数のCPUを使っても(p → ∞ )、代数効果はたかだか1/(1-α)ということを示した式です。
1-5.MPI functionの種類
・システム関数
MPIを利用に必須な関数。MPI_Init,MPI_Comm_rank,MPI_Comm_size,MPI_Finalizeなど…。
１対１通信関数
あるプロセスからプロセスへデータを転送する関数。MPIではP2P的関数が基本で非常に重要です。
- ブロッキング型
関数を止めたり、動かしたりする。MPI_Send,MPI_Recvです。
- ノンブロッキング型
通信データの送受信が各々待たずにおやく終わらせて、呼び出し箇所まで戻る方式。通信終了の状態判断は, MPI_Waitが使われます。該当関数に MPI_Isend, MPI_Irecvなどがあります。
この２つはC言語で言うselect.hのことかと思います。
1-6.データ分散方式
並列計算では、配列データをどのように分散メモリに分散させるかというデータ分散が重要になります。1次元データ分散で、行列データの分散と配列データの分散は同じことです。ここから、難しいのですが、MPIの数値計算では、大域的な配列のインデックスから、各ランクが持つ局所的なインデックスを計算して、処理を進める必要があります、また、大域インデックスから、データを所有しているランク番号を知る必要があります。そこで、それらの計算方式をデータ分割方式で表します。
元の配列サイズを N, 元の配列の行インデックス（大域インデックス）を i(global) , MPI実行時の最大ランク数を p とします。データ分割により分散された行列のインデックス（局所インデックス）をj(local)とします。 i(global)を所有しているランク番号を P(iglobal)とします。自分のランク番号を myidとします。
1-7.逐次プログラム→並列プログラム
1.正しく動く逐次プログラムを作る。
2. (1.)のプログラムで、適正なテスト判定をする
3. (2.)のテスト問題の実行について、
適切な処理の単位ごとに、正常動作する計算結果を確認する
4. (1.)を並列化する
5. (2.)のテスト問題をつかって動作検証する
6. (3.)と同じだったかを判定する。
1. 全てのプロセスで、配列サイズは逐次プログラムと同じサイズで良い
2. 各プロセスは、データ分散に基づいく配列の担当範囲のみ計算し、
ループの開始値と終了値を変更する。
3. (2.)の動作を確認する
4. 各プロセスで、データ分散に基づき、
担当するデータ範囲しか配列を確保しないようにする
配列確保に基づき、計算ループの範囲と配列の参照の仕方を変更する
1次元ブロック分散を採用するとしますと、
ib = N / p for j in range(myid*ib, (myid+1)*ib): [ 逐次プログラムと同じ計算式 ]
を、手順4の処理をすると、
for j in range(ib): #jj = j を用いた式 A[jj][...] = ... #データ分散に基づく局所インデックスの参照
1-8. ベクトル計算
y = Ax.という式が行列-ベクトル積であります。
for i in range(n): y[i] = 0.0 for j in n: y[i] += A[i][j]*x[j]
が、ベクトル積となる。
2.Pythonモジュールについて
Pythonには、いくつか並列処理をさせるためのモジュールがあります。今回ボクが使って説明するのは、multiprocessing/Gevent/asyncioの３つなのですが、各々の違いを言いたいと思います。あと、自分の見解だと限界があるので、サイトからの引用と、僕の見解で言及していきたいと思います。間違ってたら怖いので、あとで師匠にも合ってるか聞いてみたいと思います。
multiprocessing
要はプロセス間通信を行うときに便利なパッケージで，threadingと似たようなAPIなのでGILが回避できてマルチプロセッサとかマルチコアの性能を有効に使える...multiprocessingパッケージはローカルとリモートマシンのプロセス並行制御をサポートしています。スレッドの代わりにプロセスを使うことで，GIL(Global Interpreter Lock)が起こす問題を効果的に避けることができます。
Gevent
並行プログラムのコアとなる考え方は、大きいタスクは小さいサブタスクに分割して、 それらを1つずつ、あるいは 同期的に 動かす代わりに、同時に、あるいは 非同期に 動かすことです。 2つのサブタスク間の切り替えは コンテキストスイッチ と呼ばれます。
asyncio
This module provides infrastructure for writing single-threaded concurrent code using coroutines, multiplexing I/O access over sockets and other resources, running network clients and servers, and other related primitives.
どれも同じような関数ばっかりで、わかりやすいといえばわかりやすいのかもしれないです。
もう少し、Pythonモジュールについて書こうかと思ったんですが、
少し知識不足がすぎるので、もう少し蓄えてから、Part2を書きたいと思います。
考察
詰まるところ、並列処理には割りと種類があるが、厳選？された中でMPIが強いと。そのMPIのプログラミングを学ぼうという感じです。ここまでは理論が割りと簡単。難しいというのは別に、関数の多さとその概念を理解するのに時間がかかるということです。言ってしまえば、時間さえ多少取れれば、MPIにしてもPythonのモジュールの理解にしてもわかると思います。「効率の良いメッセージパッシング」というのが、並列プログラミングの課題だと思うのですが、実のところそこはまだ理解が浅いので、「並行コンピューティング技法」など読んで、バブルソートなどの、一般的に使われているアルゴリズムから勉強しようかと思います。。
感想
〇〇に精通した人、というのは大抵低レイヤを専攻しているというのが私のイメージで、僕もいつかはそういう人になりたいなと思っていたのですが、どのようにしたら成れるのかもわからないですし、とりあえず、並列処理から始めるのもいいかなと思いました。楽しかったです。Part2もがんばって書きます。
