Chienomi

並列化は、すれば良いというものではない

プログラミング::beginners

序

時折、「並列化しました！」という成果報告を目にする。

が、同時にそれがwinではないケースというのもよく見る。

これは、「並列化できた=高速化できた=良くなった」という考えに基づいているためだろう。

だが、パフォーマンス向上というのは難しい命題であり、見識の不足によって問題を引き起こすことも多々あるのだ。

もし単純なロジックの改善による高速化を果たしたなら、それは良いことである可能性はそれなりに高いが、必ずしも良いことであるとは限らない。 高速化に伴ってメモリやCPUなどの計算資源の使用量が増えたのならば、その高速化は一長一短であり、実際のニーズによって評価されることとなる。

また、高速化がライブラリの導入や変更によって実現された場合、メンテナンス面から問題を生じる必要があり、別視点からの評価も必要となる。

だが並列化の場合、これらとはそもそも違い、並列化が「望ましくないケース」というのが山ほどあるのだ。 本稿ではこれについて話していこう。

並列化すべきところとそうでないところ

まずバックグラウンドで動かすようなスクリプトを考えてみよう。

これを仮に10ジョブ動かすものとして、並列すれば完了時間が短縮されるとする。 まぁ、これはよくあることだ。

では、これは並列化すべきだろうか? 答えはおよそ否である。

まず単純なケースでは、スクリプトが独立して動作するようになっていれば、単純に並列化したい数だけ起動すれば良い。

$ foo 1 &
$ foo 2 &
$ foo 3 &
$ foo 4 &
$ foo 5 &

これであれば、いくつ並列で動作させたいかをユーザーは完全に自由にコントロールできる。 並列化の処理がスクリプト自体に組み込まれていたら、その挙動を調整する余地が大幅に減る。

それはキッチンシンクアプローチであり、Windows的でもある。 よくない手法だ。

また、並列化を外部に委ねることで何並列にするかだけでなく、何を並列実行するかに対しても自由を与えることができる。 ユーザーがfooに多くのリソースを占有してほしくないからfooは逐次実行でいいのでbarを同時に動かしたい、と考えているならば、そのようにできるのだ。

$ for i in {1..5}; do foo $i; done &
$ bar & bar & bar &

このような柔軟な扱いを可能にするために、必要なのは並列化することではなく、独立であるようにすることである。 fooをどのタイミングで、いくつ、どの順番で動かそうが支障なく動作するようにするのだ。

フォアグラウンドで動作させるものであれば並列化させれば良いかというとそうでもない。 取り扱いを考えればまず並列化は組み込みでない方が良いというのは同じだし、ユーザーは他のジョブを考えればバックグラウンドで実行している可能性がある。 そのプロセスが重くなり、並列動作によってより多くのCPUを使おうという動作の並列化をするのであれば、そのプロセスはより排他的に動作するようになる。 ユーザーから見れば扱いにくいソフトウェアだ。

では並列化したほうが良いものはなにか。

一番シンプルには、「ユーザーを待たせるもの」だ。

対話的なプログラムで、基本的にユーザーは実行を完了するために待つというものであれば、その待たせている処理そのものを短縮したほうが良い。 ユーザーから見て放置しづらい(頻繁に対話的操作が必要であるなど)ものであり、なおかつCPU時間を多く必要とするせいでユーザーを待たせやすいものであれば、並列化によって待ち時間を短縮したほうが良いからだ。

必要のないIOによって実行時間が伸びてしまうケースも、並列化によって改善できる。 IOはCPUをほとんど使わないが、実行の継続がIOの完了を待つ場合時間だけはかかる。 IOの完了を待たなくても実行が継続できるのであれば、その処理をバックグラウンドで行うように並列化を行うと良い。 最終的にはそのIOが完了していなければ継続できない場合でも、進められるだけ進めて待ち合わせすれば良い。

膨大な計算によって実行時間が非常に長くなるものも並列化させる候補ではある。 膨大な計算を行う処理は、基本的には他のことを同時にはしない(コンピュータにそのタスクだけを走らせて放置する)からだ。 別に並列化したからといって計算量が減るわけではないのだが、実時間として途方もなく長くなることを防ぐ意味で(なるべく早く成果を得たいために)並列化によってさらなる実時間短縮が求められることはある。

だが、そもそも何日もかかるような計算を書くことはあまり一般的ではないし、家庭用PCではせいぜい16並列とかそんなものなので、一般用途のプログラミングにおいて求められることでもない。 また、こうしたプログラムにおいてはまず計算量の削減が第一であり、それだけ高速に実行できる言語で書くといったことが先にある。その上でさらなる時間短縮のために並列化を行うわけである。 だから、この理由で並列化を行うことは、大部分の人はない。

また、そのようなプログラムであったとしても、必ずしも並列化処理を組み込むことが正解であるとは限らない。 それぞれの処理を独立させ、任意箇所を任意数の並列実行可能なようにしたほうが良い可能性も高い。

基本的かつ重要なこと

システムはマルチスレッドで動作するようになっており、OSに優れたスケジューリング機能を備えた並列実行の機構が用意されている。

なので、もっとも素直なのはこのOSの機能を活用すること――つまりはプロセスを使うことだ。

なおかつ、OSには複数のプロセスを任意に起動する機構がある。 Windowsはワイルドカードの展開など基本的な機能がシェルにないためその展開機能を内蔵する必要があるが、Unixコマンドであればワイルドカードの展開はシェルが行うものであるからプログラムに組み込むことはあまりない。 同じように、OSやシェルによってプロセスを任意の起動できる以上は並列化もプログラムに組み込むよりは、標準の機能からコントロールしやすいようにプログラムを作るほうが望ましい。

可能なら、プログラムはひとつのことを確実に行うようにすべきであり、それらのプログラムは互いの状態に干渉しないようにすべきである。

そうすれば、並列化は並列化したい箇所に任意数で並列化できるようになる。 それぞれの処理が独立していれば状態に干渉して停止してしまうこともなく、効率の良い並列化にもつながる。

実際にプログラムに並列化処理を組み込む必要があることは稀であり、特に対称並列化(同じ処理を分割して並列で行うための並列化)を組み込む必要があるケースは非常に限られており、非対称並列化(異なる処理を同時に行うための並列化)を限られた典型的ケースにおいておこなうことがほとんどである。

並列化に適したプログラムの構築については、Orbital design デザインパターンを参照してほしい。

まず認識しておくべきこととして、並列化はプログラムを改善する手法の中でかなり限られたケースで有効なものであるが、並列実行するかどうかによらずプログラムを小さくひとつのことを実行するものにしておくことは利益をもたらす可能性が高いということである。

並列化プログラミングに囚われてはならない。 その威力を発揮するところで使うのだ。