TOP MAP UP

並列化プログラミングについて



　最近のCPUは単一ダイに複数コアが載っており、プログラム自身がより並列化された書き方を求められるようになった。
　ここではレベルの高い物から低い物まで、色々手法を載せて行きたいと思う

並列化において注意すべき事


並列化手法

プログラム複数起動

　非常にローテクではあるが、なかなかバカに出来ない手法。単純に同一のプログラムを複数起動する。
　この際に、全体の演算範囲に対してそれぞれのそれをを指定する必要がある（でないとどのプログラムも同じ演算を行うので）この演算範囲の管理を手動で行う必要がある、というのがこの手法のデメリットと言えばデメリットなのだが、分割数と演算結果の返ってくる時間のオーダー次第では事実上大した問題ではなくなる（ゆっくりと結果が返ってくるのであれば、まったりと管理すれば良いので）
　演算時間が実用上問題無い範囲となるように、演算範囲を小さくして指定してやり、それぞれに結果を出力するようにしておけば、仮にハングアップしても結果は残る、という部分は割りと重要になる（演算時間と結果の取得性）
　また複数コアを同時に使うだけでなく、プログラムを他のマシンでも動かす事で分散コンピューティングも可能となる。分散化できれば、演算パワーが足りなければどんどんマシンを追加していけば良いので、コアを積極的に使うことに労力を割くよりも、もっと低い技術的コストで全体の演算速度を稼ぐ事が可能となる。
　参考までに自分で作った例としてAFSコンバータ（暗号化ADXの解析のビットサーチで使用）、PS2 ひぐらしのなく頃に 祭 カケラ遊び（暗号化セクタの解析で使用、現在解析プログラムその物はまだページには置いていない）等がある。

マルチスレッドプログラミング

　マルチスレッドプログラム自体は古いWindowsの頃から普通に出来ているが、それは基本的に「平行動作」に主眼を置かれたものであったが、マルチコア時代の現在、マルチスレッドプログラムは負荷に応じてそれぞれのコアで実行される事になる。
　プログラムのマルチスレッド化で注意して欲しいのは、Windowsにはプロセスやスレッドやファイバーの実行順序を決めるのに、それぞれに設定されたプライオリティの他に、負荷に応じた評価を行い実際の実行順序を決定する（これをboost機能という）
　昔からのプログラマであると、他のスレッドの動作によりフラグが立つまで、自分のスレッドを休ませる場合、ついついfor等で空ループを組んでしまうが、こういった組み方をすると、空ループがガンガン回るので、相対的にそのスレッドの負荷が上がってしまい、実行順序を決定する際に、更に優先的に実行機会を与えられてしまい、結果として本当に実行したいスレッドにさっぱり制御が渡らない、という現象が起こる（boost問題）ちなみにこの現象はSEGAのPSOBBでも起きていた（その後bugfixしたが）
　もちろん本来はmutex等を使ってコントロールすべきであるが、実際問題として（空ループで無いにせよ）こういった事は頻繁に起こるので、マルチスレッドを組む際にはスレッド毎の制御の渡り具合を把握しておく事が重要となる。
　ここでいうマルチスレッドプログラムは、そういったスレッドコントロールを自分で行えるので、非常に柔軟にやりたい事が出来る反面、コントロールの為のコストを払わなければならない。その辺りのノウハウがあるないで実行速度等の結果が大きく変わってくるのがデメリットと言えばデメリットである。

OpenMP

　OpenMPは「ソース自体はシングルスレッドで（マルチスレッドをコントロールするコードを書く事無しに）分散化したい部分のみ分散化を手軽に行える」のが特徴で、「もともとシングルスレッドの物で手軽にマルチコアの使用を行いたい」というのに最適である
　Windowsにおける実装としてはSide-by-SideにてOpenMPのコントロール部分が要求されるので、例えWin32APIのみ使っていたとしても、その分のランタイムが要求されるので注意。
　なお上記boost問題であるとか、そういった諸問題は現在の所確認されていない。非常に素直に並列化が可能である。
　参考までに自分で作った例としてAFSコンバータ（暗号化ADXの解析のビットサーチで使用）がある。

MPI

　MPIは自己と同一のプログラムが複数存在すると想定して、その自己達と通信（実態はTCP/IP等で）する事で、並列動作をコントロールする、という、主にクラスタリング（複数マシンでの分散処理）を念頭に置いた手法。
　最初からクラスタリングが前提な事と、MPIという専用のAPIを使う事などから、少々敷居が高い（なので飽くまで個人レベルを考える自分は採用を検討したことが無い）

GPGPU

　後日記述予定



プチノウハウ

実行条件の刈り込み

　並列化以前の話であるが、実際に演算を実行するかどうか？を事前に条件を使って刈り込みに行く。
　ただしこの刈り込みの判定が演算に対して非常に複雑になってしまう場合（あるいはearlyに判定できない場合）刈り込まない、という選択も重要

高速なデバイスを使う

　並列化以前の話であるが、例えばファイルを高速に読み出す場合、ファイルその物をRAMDISK等の非常に速いデバイスに置く等する