アルゴリズムやデータ構造が好きだと話すと、よく怪訝な顔をされます。プログラマーが何をしているかはなんとなく想像がついても、コンピュータサイエンスが何の役に立つのかわからない、という人がほとんどです。仮に知っていたとしても、実生活とは無縁だと思われています。応用としてのコンピュータサイエンスが、実は身近なところにあふれていることを、シンプルな例でお見せしましょう。

靴下の山を整理しなければならないところを想像してみてください。決して楽しい作業ではありません。ずっと後回しにしてきたせいで、どう見積もっても1時間はかかりそうです。

選択肢を考えた末、誰かに手伝ってもらうことにします。友人と一緒に作業を始めれば、かかる時間はだいたい半分で済みます。

コンピュータ科学者なら、この靴下の山を「リソース」と呼ぶでしょう。あなたと友人は、そっけなく「ワーカー」と呼ばれることになります。二人で同時に、つまり「並列に」問題に取り組むわけです。これが並列コンピューティングの要点です。

靴下の仕分けには、並列作業に向いている性質がいくつかあります。

• 作業をきれいに分割できます。どのワーカーが靴下のペアを探すにも、かかる時間はだいたい同じです。
• 別のペアを探す作業は完全に独立しているので、同時に進めることができます。

この作業に割り当てるワーカーが多ければ多いほど、早く終わります。

• ワーカーが1人なら60分かかります。
• 2人なら30分です。

3人ならどれくらいでしょう？そう、約20分です。この関係はシンプルな式で表せます。

ただ、これは正確ではありません。オーバーヘッドのことを忘れていました。たとえばメアリーが靴下を取ろうとしたとき、スティーブンも同じ靴下に手を伸ばすかもしれません。二人はにっこり笑って、どちらかが別の靴下を取りに行きます。コンピューティングでもワーカーは同じことをします。もちろん微笑みはしませんが、別のタスクを取りに行きます。たくさんのワーカーがリソースを共有すると、このような状況は頻繁に起こります。そして、そのたびに解決に少し余分な時間がかかります。だからこそ、理想的な仕分け速度には少し届かないのです。

しかも、事態はさらに悪化します。100枚の靴下に対して100人のワーカーがいるとしましょう。最初に全員が1枚ずつ靴下を手に取り、ペアを探そうとします。ここで問題が起きます。各自が1枚取った時点で、山にはもう靴下が残っていません。すべてのワーカーが待ち状態になってしまいます。仕分けは永遠に終わりません。これがデッドロックです。並列コンピューティングで最も恐ろしい事態の一つです。

この場合、シンプルな解決策は、一度靴下を置いて、少し待ってからまた取りに行くことです。別の抜け出し方として、仕分けのための何らかの「プロトコル」を決める方法もあります。プロトコルとは、共通の目標を達成するためにワーカー間で交わされる暗黙の了解のようなものだと考えてください。

たとえば、各ワーカーが特定の色だけを担当するようにします。ワーカー1は緑、ワーカー2はグレー、といった具合です。このシンプルな工夫でデッドロックを避けられます。なぜなら、まったく別のタスクとして作業を分けることになるからです。

ただ、まだ落とし穴があります。もし緑の靴下が4枚しかなく、グレーが4000枚あったらどうでしょう。ワーカー1はすぐに暇になってしまいます。2組のペアなどあっという間に仕分けてしまい、あとはワーカー2が残りを仕分けるのを眺めるだけです。これではチームワークとは言えませんよね。

このように作業を分ける方法がうまくいくのは、各色の靴下の数がだいたい同じだと想定できる場合です。そうすれば、誰の作業量もほぼ均等になります。

次のヒストグラムを見れば、私が言いたいことがお分かりいただけるでしょう。

この場合は、色ごとにほぼ同じ大きさの山になっています。どのワーカーにとっても公平な作業量に見えます。

2つ目のケースでは、分布が均等ではありません。この例でグレーの山を担当したくはありませんよね。もう少し工夫が必要です。

どうすればよいでしょうか。

たいていの場合、作業の分割方法を別の角度から考えてみるのが役に立ちます。たとえば、大きなグレーの山を2人で一緒に仕分けることもできます。一方が大きな靴下、もう一方が小さな靴下を担当するのです。ただ、ここでまた別の問題が出てきます。この場合、「大きい」「小さい」を誰がどう決めるのでしょうか。

そこで、もっと賢い方法をあれこれ考えるよりも、ここは現実的にいくことにします。色やサイズに関係なく、誰もが同じ量の山を取って作業を始めるのです。

おそらく、各山にはペアが見つからない靴下が少し残るでしょう。それで構いません。残った靴下を全部集めて混ぜ合わせ、また新しい山を作って仕分け直せばよいのです。これを完了するまで繰り返します。これをタスクキューと呼びます。この方法には2つの利点があります。1つ目は、ワーカー間で余計な取り決めが不要なこと。2つ目は、問題領域について深く考え込まなくても、ワーカーの数に応じてそれなりにスケールすることです。

分散システムの厄介なところは、一見単純に見える解決策が、実際にはひどく失敗することがある点です。

たとえば、小分けにした山がこんな状態だったらどうでしょう。

各山の中にあるペアの数は……がっかりするほど少ないです。できることとしては、一致する数を増やすために、ごく簡単な事前仕分けを行う方法があります。あるいは、もっと良いアイデアを思いつくかもしれません。
素晴らしいのは、一度より速い方法を見つければ、それが似たようなタスクにも応用できるということです。

このような問題はコンピュータサイエンスに根ざしており、至るところで見つかります。個人的には、「Computer Science」という言葉はあまり好きではありません。ドイツ語の「Informatik」という言葉のほうが好みで、あえて訳せば「情報科学」といったところでしょうか。なぜなら、私たちがここで本当にやっていることの本質は、一つの問題だけでなく、ある種の問題群全体を解決する汎用的な方法を見つけることだからです。私たちはモノの本質やその性質について考えます。靴下を仕分けているのではなく、情報の根本的な問いに答えようとしているのです。なぜ私がこの分野に情熱を注いでいるのか、少しはお分かりいただけたでしょうか。

ちなみに、なぜ私がプログラミングを愛しているのかについては、こちらの関連記事なぜ私がプログラミングを愛するのかでも触れています。