アルゴリズムやデータ構造への情熱について語ると、人々は困惑した顔をします。多くの人はプログラマーが何をしているのかは理解していますが、コンピュータサイエンスが何の役に立つのかは分かっていません。そして仮に分かったとしても、実生活とは無関係だと思っています。応用としてのコンピュータサイエンスは実はあらゆるところにあるのだということを、簡単な例でお見せしましょう。

整理しなければならない靴下の山を想像してみてください。決して楽しい暇つぶしとは言えません。あまりにも長い間この作業を先延ばしにしてきたので、どうしても1時間はかかってしまいそうです。

選択肢を考えた末、誰かに手伝ってもらうことにします。友人と一緒に作業に取りかかれば、だいたい半分の時間で終わります。

コンピュータ科学者なら、この靴下の山をリソースと呼ぶでしょう。あなたと友人はあっさりとワーカーへと格下げされます。二人とも同時に問題に取り組むことができます――つまり並列にです。これが並列コンピューティングの要点です。

さて、靴下の仕分けには、並列で行うのに適した性質がいくつかあります。

• 作業をきれいに分割できます。一人のワーカーが靴下のペアを見つけるのにかかる時間は、ほぼ同じです。
• 別のペアを見つけることは、同時に実行できる完全に独立したタスクです。

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

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

ではワーカーが3人ならどれくらいかかるでしょう？その通り！だいたい20分です。この関係を簡単な式で表すこともできます：

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

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

この場合、単純な解決策は、靴下を一旦置いて、しばらく待ってからまた新しい靴下を取ろうとすることです。別の解決策としては、仕分けのための何らかの「プロトコル」を設けることです。プロトコルは、共通の目標を達成するためにワーカー間で交わされる暗黙の了解だと考えてください。

たとえば今回のケースでは、各ワーカーが一色だけを担当するという方法があります。ワーカー1は緑の靴下を、ワーカー2は灰色の靴下を、といった具合です。この単純な工夫で、完全に別々のタスクに取り組むことになるので、デッドロックを回避できます。

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

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

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

このケースでは、各色の山の大きさがほぼ均等です。どのワーカーにとっても公平な作業量に見えます。

2つ目のケースでは、均等に分布していません。この例で灰色の靴下を仕分けたいとは思いません。もう少し真剣に考える必要があります。

では、どうすればいいのでしょうか？

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

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

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

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

もし小さな山がこんな風になっていたらどうでしょう？

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

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

ちなみに、プログラミングが大好きな理由についての関連記事もどうぞ。