君たちの「並行」の理解は間違ってる
TL;DR
- 並行計算の理解を間違ってる人が多いので正したい
- 並行計算=同時に実行すること
- 並列計算≒同等のタスクを並行計算すること
もうちょっとちゃんと書いたフォローアップ記事も合わせて、お時間が許すようであればお読みください。
状況
並列と並行 / 多言語からみるマルチコアの活かし方に見られるように並行(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という構造体になっています。このgをruntime.p(プロセッサ)に渡して実行する=計算することがgoroutineを実行するということに相当しています。この動作をランタイムの観点で見ると複数のgが並列に計算されているといえます。
つまりgoroutineは並行計算を記述できますが、その実際の実行時には並列計算に落とし込んでいます。さらにいえばOSはGoで書かれたものも含めそういうプロセス群を並行計算していますし、CPUの命令レベルでは並列計算していると言えるのです。何が言いたいかというと「視点次第で並行性と並列性は入れ変わってしまう」ということです。
補足: 記事の裏側
並列計算についての説明は、簡単化のためにかなりぼやかしています。あくまでも本記事では「並行計算」についての誤解を正したかったので。
並列計算という語句はそのアルゴリズムについて論じるコンテキストのほうが強いので、本来なら並行計算と並べて語るべきものでもありません。ただ並行計算について間違った解釈をされる際に両単語が含まれることが多いので、それに倣ってこの記事では言及しています。
この記事はあえて「処理」という曖昧な語句を使わずに「計算」として統一しています。また一般的な意味での「並行」と「並列」について論じたものではありません。あくまでも「計算(機科学)」のコンテキストです。
なお「並行計算」についての厳密な定義に知りたい場合はこの記事(並行，並列，同時，および，分散)を読むと良いでしょう。なお他の語句についてはおざなりすぎてちょっと参考にならなそう。
補足その2: フォローアップ記事書きました
Discussion
とても勉強になりました。
ご指摘の通りの勘違いをしており、私も現在執筆中のオンラインブックでも誤った説明をしてしまっていましたので、修正いたします。
修正のご機会をいただけてとても感謝しています。
一点、この表現についてはやはり理解が難しく自分で調べてみたのですが、理解に間違いがないか確認させてください。
自分で調べてみたところ、
cuncurrentな処理というのは、結果的に「単に同時である」というのはその通りなのですが、どちらかというと「逐次的でない」という意味に近いように理解しました。プログラミング言語の通常の計算は上から下へ順序を守って逐次的に実行される、つまり「上の計算が終わるまで下の計算を行ってはならない」というルールを（暗黙的に）指示するのに対し、並行計算は「Aの計算が終わっていなくてもBの計算を実行してもよい」という指示を行うことを意味します。
逐次的 でなくてよい 複数の計算があった時に、具体的にそれをどう扱うかはプロセッサ、あるいはむしろOSの問題であり、複数プロセッサによる並列実行を行っ てもよい し、いわゆる疑似並列実行を行っ てもよい という言葉で捉えると、実態に合っておりかつ（私にとって）理解が容易でした。
（プログラムが並行計算を指示したとき、賢いOSであればCPUをうまく使って素早く実行するし、賢くないOSであればCPUをうまく使えず却って遅く実行してしまう）
あるいは言い換えると、「並行計算」は計算の 順序 を規定する言葉であり同時性には言及しておらず、「並列計算」は計算の 同時性 を規定する言葉であり逆にタスクの関係性（もとが同じ種類のタスクであったかどうか、逐次的に行われてようとしていたかなど）については言及していない、と言ってしまったほうが分かりやすいように感じました。
（
同時性という言葉には解釈の幅があり、どれぐらいの時間幅の中で複数のタスクが実行されていればよいと認めるかによって、並列計算と呼ばれたり疑似並列計算と呼び分けたりする）上記の理解には概ね間違いがないでしょうか？
ありがとうございます～
興味深い解釈です。ただちょっとその考えに至った参考資料や例に乏しいので、concurrentとparallelというシンプルな概念の対比を踏まえての定義としては若干不向きかなという感想です。
あっているような間違っているようなという感じです。
なによりも「言及していない」ということを定義に用いるのは明確に誤りです。
また並列計算はタスクの関係性については「タスク(=処理)間の関係性が無い」と並列計算 / Wikipediaでは以下のように言及しているため、誤りと言って差し支えないでしょう。
「同時性」についてはすでにお気づきだと思いますが、定義次第でいくらでも同時なのか逐次なのかいじれてしまうので論じる意味がない=定義の差として利用するのはイマイチかなと。その点Wikipediaのほうは「複数のプロセッサ」と記述していて「上手いな」と思いました。
最後に並行計算の「計算の順序を規定する」ですが、これは表現として惜しい感じです。というのは並列計算 / Wikipediaを読むと、並行計算のタスクは基本的に依存性がない=同時に実行できるところから出発していて、必要であれば依存性(≒相互作用)を記述できることに特徴があると解釈できます。
逆に並列計算においてはタスク間の相互作用は基本的には導入できません。ゆえにホモ=同質なタスク群を実行するとしました。すると並行計算は相互作用があったりなかったりできるのでヘテロ=異質なタスク群を実行するとしました。
とはいえ本来であればこの2つは観点が異なるので、まじめに比較して定義するには値しないって話なんですけどね。
回答ありがとうございます。
失礼しました！
参考にした資料は、
になります。
（英語版のWikipediaと日本語版のWikipediaを比較すると、随分内容が不足していたので英語版を参照しました）
Concurrent computing / Wikipedia では、冒頭で
とされており、McGraw-Hill Concise Encyclopedia でも
と書き出されており、
sequantialと並べて概説されていました。そこで、「逐次的であること」の対比で理解した次第です。
（ただし、McGraw-Hill Concise Encyclopediaは2002年のものなので参考にしないほうが良いのかもしれません）
表現が紛らわしく申し訳ありません。
「言及しないと定義されている」わけではなく、「定義の中で言及されていない」ということが言いたかったことです。
（定義の中で言及されていない、ということが直ちに定義を誤りとさせることはない認識です）
ですが、改めて上記資料を見ると、
during overlapping time periodsやThe simultaneous executionなどの表現が必ず添えられていることから、同時性（定義が曖昧なことを承知でここでは敢えて使っています）について言及されていない、という私の意見は誤りでした。こちらのタスクの関係性（＝依存性）については、ご指摘の通りで、誤った（不要な）注釈でした。
考えてみると、「プログラムの依存性」という言葉も「同時性」と同じく定義によっていじれるなと思い、並列/並行の概念を理解する際には持ち出すべきではありませんでした。
（仮にプログラム同士が依存性があるとして、具体的に依存関係をもつ処理は全体の一部分であり（クリティカルセクションなど）、依存性の程度の扱いが難しそう）
いずれにせよ、Muraokaさんの本記事の指摘どおり、
「1つのCPUがタスクAをやったりタスクBをやったりするのが並行計算（であり並列計算ではない）」
「複数のCPUが複数のタスクを行うのが並列計算（であり、並行計算ではない）」
という（今朝までの私の）理解は明らかに間違いであり、大変勉強になりました・・・
私も同じようにもやもやしておりましたので、こういった記事を執筆いただき大変ありがたく思います。
並行＝同時と断言してしまうと角が立ちますので、「同期間に開始、実行、完了する」と言い換えるのが、誤解も少なくてよいのではないかと思います。
以下、私が最も腑に落ちたstack overflowの回答の引用です。
ありがとうございます～
ただ本記事はタイトルの語調からもわかるようにかなりキャッチーに主張するようにしています。多少「角が立つ」のと「誤解が残りうる」のは記事の個性と考えて、言い換えない方針です。
本当はもっと説明したいけど、それはそれで本文では論点がボヤけてしまいますので
もしもより誤解の少ない記述が必要だとお考えなら、ご自身で記事を書いてお知らせください。喜んでリンクさせていただきます。
お返事ありがとうございます。
左様でございましたか、差し出がましい真似をしてしまい申し訳ございません。
続編に期待しております笑
さまざまな考察とても良いと思います!
お時間ありましたら考え・主張をまとめて「より正確にはこう解釈すると良い」的な記事に仕立ててみたらどうでしょう? その際はぜひお知らせいただければ、喜んでリンクさせていただきます。