並列処理の話（その３）　並列処理の種類

今回の連載では、並列実行で処理を並列化させるためには、プログラムを同時に起動し、終了を同期して待つという一番オーソドックスな方法を紹介してきました。
並列処理の話（その２）　Windowsでコマンドを並列実行する（前編）

しかし、この方法はあくまで「異なった仕事を同時に実行する」ということす。
わかりやすく例にするなら、CPUコアが複数あるということは、作業員が複数いるということですが、2コア＝作業員が2人ということなら、2人が連携しなくてよい仕事は、同時に指示して実行すれば、速く終了しますね。
夏休みの宿題を、国語はAさん、算数はBさんとで手分けして行うようなものです。

しかし、宿題が1教科の場合に2人で行うことによって、宿題を早く終わらせる方法はあるのでしょうか。

■パーティション・パラレル

ひとつの方法として問題を分割して行う手法があります。
しかしこの方法では、問題集が一冊の場合は、2人で交互に参照する必要がありますし、回答を書き込むのも一人ずつになります。リソース競合ですね。
これでは2人で作業しても効率は2倍になりません。
これを解決するには、以下のような方法が考えられます。

入力を適切に分け、リソース競合が起こらないようにする。
- 各作業者にルールを与え、重ならないように処理する。（前半後半とか、一問おきとか）
- 問題集をコピーして、作業者に配ってしまう。
出力はそれぞれ行い、最後にマージしてソートし直す
- 終了した回答ページを並べ直す
- 回答転記用に第三者を用意する

入力ファイルの前半をスレッドA、後半をスレッドBのように分け、別々のファイルに出力した後で最後にひとつのファイルにまとめる、あるいは、作業スレッドのほかに管理スレッドを用意し、そこでデータを読み込んでレコードあるいは作業単位ごとに作業スレッドに渡して、処理が終わったら管理スレッドがレコードを統合して出力ファイルに書き出す、というような感じです。

プロセスグリッドであるHadoopはマシンをまたがってこのような並列処理を行うエンジンですが、MapとReduceがここで言う管理スレッドにあたります。

これらの手法ではデータを読んだり書いたりする部分は並列化されません。コンピューター上ではファイルの読み書きはCPU演算の数百～数千倍の時間がかかりますから、よほど並列化の数が多くないと、1プロセスで並列化せずに実行する時間より短縮できません。
Hadoopは、MapのためにHDFSにデータをロードしたり、ネットワーク経由でデータを読むことからも、同様の理由で数百台以上のマシンを並列化しないと効果が出ないとも言われます。もっとも、Hadoopはクラウドを利用し、数百台の稼働を自動化する仕組みで、トータルのコストと実行速度のバランスを取れるというメリットがあります。

また、この手法ではひとつ大きな問題があります。あるレコードが直前のレコードの値を参照したり、入力ファイルをソートして集計したりする場合には、入力ファイルを分割することができません。
例にした宿題の場合、前の問題の解答に対するさらなる問題が出されて、それが分割した問題集側にあったら、解答は書けませんね。

■パイプライン・パラレル

もう一つの並列手法として、パイプライン・パラレルというのがあります。
せっかく宿題を例にしたので、学校であれば給食の配膳みたいなものでしょうか。いわゆるバケツリレーです。

工場の流れ作業では、同じ作業だけを繰り返し行うので効率が上がる面があるのですが、コンピューター・ソフトウェアではあまり関係ありません。
トータルで考えると、バケツを渡す人の数だけ同時に作業が行われていることになりますから、作業時間は短縮されます。
この手法では、それぞれの作業時間が異なるとラインが詰まってしまうため、作業分担をどのように行うかというのがポイントになります。
データの順序等で処理が破綻することはありませんが、たとえば全ファイルを読んでソートをする処理が途中にあったとすると、そこでパイプラインは停止してしまいます。

どちらの手法も、並列処理に最適な作業分担を自動的に判断することは困難で、どのようなデータ加工を行うかも加味した上で、効率的な手法を選択できることが、コンピューターのパワーを最大限に生かした処理時間短縮のキモになります。

筆者が新人の頃、何も理由を知らされずにとにかく数日間ヘルプだと言われて炎上プロジェクトに投入されたことがありますが、何の指示もなくて1日中お茶飲んでいたことがあります。
炎上プロジェクトも、ただ人をつぎ込むだけじゃ火は消えないですよね。リソースを無駄なく有効にアサインできるプロマネがいてこそ納期通りに納品できるわけです。

あぁ、夏休みの宿題から炎上プロジェクトじゃ節操ないですねぇ。最初の頃に遊んでいると後半辛くなるってのは同じですけど。