並行と並列について-並行コンピューティング技法-を読んで

コンピュータサイエンス的な「並行」と「並列」

「並行コンピューティング技法」の1.1.2「並行と並列：その違いは？」に以下のようにあった。

システムが複数の動作（処理の流れ）を同時に実行状態(in progress)に保てる機能を備えている場合を 並行(concurrent)と言い、複数の動作を同時に実行できる場合を並列(parallel)と言います。 重要な概念、違いは「実行状態」という点です。

重要なのは、

• 実行状態を複数保てるなら、並行(concurrent)
• 複数の動作を同時に出来るなら、並列(parallel)

です。

さらに、「「並行」は「並列」を包含します」との記載がありました。

つまり、並列も実行状態を複数保ててるわけですから、確かにそうです。

単純ではありますが、この後色々悩ましく思えてくるので、もう一度よく考えてみます。

システムが複数の動作を同時に実行状態に保てる

これを図にしてみました。書籍には、システムとはハードウェア、ソフトウェアが 含まれると記載があります。

システムは ハード、ソフト、つまりOSやミドルウェア、アプリケーションが含まれた 抽象的なものだと考えます。

とりあえず、何か逐次的な手続きの流れがあり、それが時間軸にそって一連の動作をするとし、それを処理と呼ぶことにします。

並行(concurrent)とは、システムが複数の動作を保てる機能を備えている場合とのことですので、 今回は、システムの中に手続きの流れである"処理"（矢印で表現）を２つ(１つ以上、複数）書いてみました。

並行ではない場合は、システムに複数の流れの動作を保てる機能を備えていないということで、 １つの"処理"（矢印で表現）しか、絶対に入りません。

つまり、複数の動作をシステム１つに入れれるか、入れれないかで「並行」という部分が 表現されると考えられます。

複数の動作を同時に実行できる

では、「並列」を見てみたいと思います。複数の動作を同時といって私たちが簡単に想像できるのは 複数のコアを持つCPUです。

各CPUコアが、それぞれが手続きの流れである処理を動作させることとなるわけですから、 下の図の「並列」と考えられます。

システムには、複数のコアがあり、それぞれが処理をしていることとなります。もし、システムには１つのＣＰＵコアしかなく １つだった場合にはどうなるかというと、隣の「並行」になり時分割で処理することになるでしょう。

つまり、「並行」と「並列」は対になる概念ではなく、並行の中に並列があることとなります。

まとめ

重要なのは、

• 実行状態を複数保てるなら、並行(concurrent)
• 複数の動作を同時に出来るなら、並列(parallel)

です。

また「並行」は「並列」を包含します。

FITEAの定期勉強会で議論になったポイント

• 「並行」は時分割でスレッドを処理、「並列」はマルチコアで処理
• 「並行」は概念的に違うものを同時に処理、「並列」は同じ処理を分割して処理

この１つ目は、上記のコンピュータサイエンス上の「並列」「並行」を 表現したものだったと考えられます。

では、「概念的に違うものを同時に処理」と「同じ処理を分割して処理」について 考えてみます。

今度は、「並列(parallel)」「並行(concurrent)」ではなく、 「並列プログラミング(parallel programing)」と「並行プログラミング(concurrent programing)」という 言葉でくくってみたいと思います。

並行プログラミング(concurrent programing)

ある問題を解く為に様々な解法で処理するかと思います。

２つほど、サンプル的な問題と解法を考えてみます。

• 巨大な行列の足し算を行う場合
  →各要素を足し合わせを繰り返し処理することとなります。
• ネットワークからPNG画像を大量に読込み、表示する
  →ネットワークから情報を逐次に読込み、デコードし表示します

これらを、普通に書くと、逐次的な処理になります。

for( i = 0; i<size; ++i )  a[i] = b[i] + c[i];
 
 

であったり

while( has_next )
  {
     buf = read_all_from_network();
     image = decode( buf );
     display( image );
  }
 
 

な形になるかと思います。これは逐次的な処理となります。

これを並行(concurrent)に処理する為に、a[i] = b[i] + c[i] をスレッド化したり 別の場合には、read_all_from_network() と decode() をスレッド化したりします。 （オーバヘッドとかあるので、単純ではありませんが、乱暴にスレッド化するとしました）

つまり、並行性(concurency)をスレッドという概念で作りだします。 この時、スレッドがCPUコアに個別に割り当てられることがあり、さらにハードウェアが 複数個のCPUコアを持っていると、並列(parallel)になるということです。

もちろん、並列の能力を持っていないと時分割で並行に動作します。

ここで、重要なのは、逐次的処理から並行性(concurency)を出すためにスレッドを 用いた点です。

私たちは、スレッドというものと時分割に慣れ親しみ、あるいは、スレッドは時分割である と思いこみ設計、あるいは教育されてきたために、このように感じるのだと分かりました。

並列プログラミング(parallel programing)

並列プログラミングは、並列化のための手段を先にイメージさせるモノとして扱われました。

例えば、MPIやPVMなどを用いたメッセージパッシングな手法です。

例えば、行列の演算等をする場合、同じような繰り返し処理等があるため、それを 別々に処理しようという考え方です。

つまり、逐次的な処理から並行性を作り出し、その並行性の実現にマルチスレッドとマルチコアCPU があるから、並列になるのではなく、最初から並列を考えるという事だと分かりました。

まとめ

つまり、並列プログラミングとは、並列化の手法を元にアルゴリズムを考える事をするのだと 考えると、

• 「並行」は概念的に違うものを同時に処理、「並列」は同じ処理を分割して処理

を

• 「並行プログラミング」は(スレッド等を用いて、大部分の場合)概念的に違うものを同時に処理、
  「並列プログラミング」は同じ処理を分割して（メッセージングパッシングする）処理

と読み解くとすっきりしたと感じました。

おまけ

【送料無料】並行コンピューティング技法 価格：3,360円（税込、送料別）

並列,並行についてしっかり書かれているので、お勧めの１品です。