読者です 読者をやめる 読者になる 読者になる

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

parallel と concurrent、並列と並行の違い

2014/11/07 内容を修正しました
2010/09/17 文章を修正しました

一般的に、parallelは並列、concurrentは並行と訳されます。検索してもずばり書かれた物がなかったので、僕なりの理解を書いてみます。
(注:言葉の定義の問題なので、複数の流儀があり得ます。端的に言えば、いわゆるCPUのSIMD命令を「並行」と見なすかどうかに違いが現れます)

参考リンク:

一番妥当(だと思う)定義

一言で言えば、

  • Concurrent(並行)は「複数の動作が、順不同もしくは同時に起こりうる」こと
  • Parallel(並列)は、「複数の動作が、同時に起こること

です。普通は「並列 ⊂ 並行」です(稀に、並列と並行は違う概念であって「並列 ⊂ 並行」ではないという定義もあります)。

この2つは、そもそも目的が違う概念です。並行というのは、世の中一般、同時進行するものごとをプログラムとして表現する際に用いる広い概念です。一方で並列というのは、主に計算速度を稼ぐために計算を同時に進めることを言います。

「論理的に順不同に起こりうる」とはどういうことでしょうか。CPUが1コアだった時代、よく「ひとつのパソコンで、ネットサーフィン(死語)をしながらメールを読めるのはどうしてでしょうか」という質問がありました。これに対する答えは、「CPUが仕事を細切れにして交互に処理しているからです」というものです。これが「並行 concurrent」です。CPUがシングルコアであった時代は、ミクロなレベルで見れば計算処理は同時実行されていません。ある瞬間を切り取ってみれば、CPUは1つの仕事しかしていないわけです。人間が認知できる時間間隔で見れば十分に「同時っぽい」というだけです。

違う言い方をすると、

  • 並行 = 複数の処理の実行順が不定であるという論理的な概念
  • 並列 = 複数の処理が同時に走るという物理的な概念

ということもできますね。

「並行処理」とは

並行処理は、複数の処理が(論理的には)同時に走っていて、処理やイベントが起きるタイミングが任意である、という場合に使います。分散処理の文脈で使われる場合が多いですが、必ずしも分散とは限りません。

上記の例で挙げたように、CPUがシングルコアであるような計算機上でマルチタスクOSを走らせる場合を考えてみます。この計算機上でプログラムAとプログラムBが「同時に」走っていて、処理A1, A2, ... と、処理B1, B2, ... を実行している場合を考えます。それぞれのプロセスの中で、A1, A2, ... の処理の流れと B1, B2, ... の処理の流れは確実に順番通りに起こります。

しかしこの時、OSは非常に細かい時間間隔で2つのプロセスを切り替えて交互に実行しています。ですから、Aが実行している処理とBが実行している処理の互いの順番は不定となります。A1, B1, A2, B2, ... という順番で処理が起こるかもしれないし、A1, A2, ..., An, B1, B2, ..., Bn という順番で起こるかもしれません。プログラムが同期を取らない限り、その順番には何の保証もありません。

これは、計算機が複数(あるいはマルチコア)のような場合でも全く同じ話ですね。

「並列処理」とは

並列処理とは、実際に処理が同時に起こっていることを指します。目的は主に計算速度の向上です。

ですから、仮に1コアのCPUが1つしかない場合、並行処理には何の意味もないことがわかります(SIMD命令を除く)。そのCPUの上で複数プロセスを走らせて計算を分担したとしても、CPUは1つしかないわけですから何の意味もありません。並列とは、計算速度を向上させるために同時に行うという物理的な概念です。

※ 厳密に言うと、仮にCPUが1コアしかなくても、並列処理によって速度が向上する場合があります(計算とメモリアクセスがオーバーラップできて、CPUストールを防げるようなケース)

微妙な定義:「仕事の種類」に基づくもの

他に微妙な理解として、「並列は同じ仕事を分担して同時にする、並行は違う仕事を同時にする」というのがあります。しかし、これは上記の定義から派生した内容だと思われます。専門的な事を言うと、これはフリンの分類におけるSIMDとMIMDの違いに近いです。別々のタスクを細切れにして順繰りに処理していくという場合には、結果的に互いに違う種類の仕事をするというシチュエーションで使われることが多いだけです。他所での説明だとこちらの方が強調されて、理解を妨げているような気がします。

具体例

例を挙げてみましょう。

Concurrent GCというものがあります。いわゆる「Stop the world」現象を防ぐために、GC処理と本来の処理を細切れにして互い違いに実行することを意味しています。こうすることによって、見た目にはプログラムの処理がStopすることを防ぐことができます。合計の処理時間が変わらないとしても、サーバーなどのインタラクティブ性を確保するために、本来のプログラムの処理と同時に実行することに意義があります。だから、バッチ処理の場合はConcurrent GCはあまり意味がありません。

一方、Parallel GCは、処理を「真に並列に」実行します。必然的に、同じ処理(例えば、collect処理)を並列に実行することになります。これは、複数の物理プロセッサを同時に使うことによって処理時間の短縮を狙っているわけです。


というわけで、並行と並列の違いについてまとめてみました。

【広告】