君たちの「並行」の理解は間違ってる

3 min read読了の目安(約3300字 8

TL;DR

  • 並行計算の理解を間違ってる人が多いので正したい
  • 並行計算=同時に実行すること
  • 並列計算≒同等のタスクを並行計算すること

もうちょっとちゃんと書いたフォローアップ記事も合わせて、お時間が許すようであればお読みください。

https://zenn.dev/koron/articles/05210473c8fc62f5e8fb

状況

並列と並行 / 多言語からみるマルチコアの活かし方に見られるように並行(concurrent)とは「複数の処理を順番に実行すること」とする誤った記述を、この記事に限らずチラホラ目にします。

大事になことなので繰り返しますが、間違った記述を含んでいるのはこの記事だけに限りません。

そのような誤った記述を見かけるたびに「ああこの人も間違ってるのか」と諦観を抱くだけというのもあまりに非生産的なので、間違ってますよとポインタとして示せるように簡単な読み物にしたものがこの記事です。

事実

計算=computingの分野においては並行=concurrentと並列=parallelの定義は実行方法を規定しません。

特に「並行」という翻訳が悪いのだと思いますがconcurrentは単に同時に以上の意味を持ちません。つまりconcurrent computingは「同時に計算する」という意味なのです。

そのため同時に計算しているように見えさえすれば、その実装方式がマルチコアであろうとシングルコアにおける時分割疑似マルチタスクであろうと、それらはすべて「並行計算」なのです。

並列計算と並行計算の関係

並列計算とは「特定の処理をいくつかの独立した小さな処理に細分化し~同時に実行させること」です。この説明を間違ってる記事はほぼ見かけません。多くの記事がforループの中身をスレッドに逃がすなど、正しい並列計算の例を挙げています。

しかし「同時に実行する」ということは、すなわち並列計算はほぼほぼ並行計算のサブセットと言えます。

そして並列計算とは細分化した処理を同時に計算することで、スループットなりレイテンシなりのパフォーマンスを向上させることを意図した技術です。本来その実行方法は問いませんが、仮にある処理を並列計算するように変更(=並列化)したものをシングルコアで実行した場合、諸々のオーバーヘッドにより並列化前よりパフォーマンスが悪化することが容易に想像できます。これでは並列計算の意味がないので、通常は「複数の処理装置(プロセッサ)上で」実行することでその性能を発揮します。

ただしSIMDのように1つのCPU=プロセッサで実行される並列計算もありますので、「並列計算」はやはりその実行方法を規定するものではありません。なおSIMDはCPU内に複数の実行ユニット=プロセッサが入ってるとも言えるのですが、実行方法=プロセッサの数とは見るレベルによって変わってくるので、この記事ではあまり重要とはしません。

並行と並列のおよそ正しい理解

さて以上を簡単にまとめると、並行と並列のおよそ正しい理解は以下のようになります。

  • 並行計算とはヘテロなタスクも同時に実行できること
  • 並列計算とはホモなタスクを同時に実行すること

以下蛇足

事例: Goにおける並行性と並列性の境界と関係性

Goのプログラムはgoroutineにより並行計算を記述します。たとえばHTTPサーバーとechoサーバーを同時に実行するようなものです。

もちろん並行計算は並列計算のスーパーセットであるため並列計算もgoroutineにより記述できます。たとえば個々のHTTPリクエストを実行するのもgoroutineですが、これは並列計算と言えます。

一方でgoroutineを実際に駆動させているGoのランタイムの視点から見ますと、すべてのgoroutineはruntime.gという構造体になっています。このgruntime.p(プロセッサ)に渡して実行する=計算することがgoroutineを実行するということに相当しています。この動作をランタイムの観点で見ると複数のg並列に計算されているといえます。

つまりgoroutineは並行計算を記述できますが、その実際の実行時には並列計算に落とし込んでいます。さらにいえばOSはGoで書かれたものも含めそういうプロセス群を並行計算していますし、CPUの命令レベルでは並列計算していると言えるのです。何が言いたいかというと「視点次第で並行性と並列性は入れ変わってしまう」ということです。

補足: 記事の裏側

並列計算についての説明は、簡単化のためにかなりぼやかしています。あくまでも本記事では「並行計算」についての誤解を正したかったので。

並列計算という語句はそのアルゴリズムについて論じるコンテキストのほうが強いので、本来なら並行計算と並べて語るべきものでもありません。ただ並行計算について間違った解釈をされる際に両単語が含まれることが多いので、それに倣ってこの記事では言及しています。

この記事はあえて「処理」という曖昧な語句を使わずに「計算」として統一しています。また一般的な意味での「並行」と「並列」について論じたものではありません。あくまでも「計算(機科学)」のコンテキストです。

なお「並行計算」についての厳密な定義に知りたい場合はこの記事(並行,並列,同時,および,分散)を読むと良いでしょう。なお他の語句についてはおざなりすぎてちょっと参考にならなそう。

補足その2: フォローアップ記事書きました

https://zenn.dev/koron/articles/05210473c8fc62f5e8fb

資料