並行計算

並行計算（へいこうけいさん、英: concurrent computing）とは、コンピュータプログラムにおいて複数の相互作用を及ぼす計算タスクの（同時）並行的実行を指す。並行コンピューティングあるいは並行処理 (concurrent processing) とも呼ぶ。

概要

汎用的なコンピュータおよびオペレーティングシステムでは、ごく短時間で実行タスクを切り替えて複数のタスクを疑似的に同時実行することのできるマルチタスクシステムが採用されることが多い。そして個々のタスクは、通常別々のプログラムとして実装されるか、1つのプログラムから複数のプロセスやスレッドを生成する形で実装される。そのようなプログラムを作成することを並行プログラミングと呼ぶ。タスク群は1つのプロセッサ（CPUにおける1つのコア）上で動作する場合、複数のプロセッサ（マルチコアプロセッサもしくはマルチソケットプロセッサ）上で動作する場合 (マルチプロセッシング)、あるいはネットワークを介した分散システムで動作する場合が考えられる。並行コンピューティングは並列コンピューティングと近い概念だが、タスク間の相互作用を重視する点が後者とは異なる。また、並列処理はスループットの改善が目的だが、並行処理は主にシステムの応答性の改善が目的である。

並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、エドガー・ダイクストラ、Per Brinch Hansen、アントニー・ホーアが挙げられる。

並行計算を行うシステムの開発ではスレッド間通信やプロセス間通信を意識して開発を行う必要がある。したがって、通信に用いるプロトコルの開発も必要となる。

並行的相互作用と通信

並行計算システムには、並行コンポーネント間の通信を抽象化してプログラマから隠蔽するものもある（Future パターンに基づいた言語機能あるいはライブラリなど）。一方、明示的に通信を行わなければならないものもある。明示的通信は次の2種類に分類される:

共有メモリ通信

並行コンポーネント群は共有メモリの内容を更新することで通信を行う（JavaやC#）。この並行プログラミング方式では、何らかのロックを必要とする（ミューテックス、セマフォ、モニタなど）。

メッセージパッシング通信

並行コンポーネント群はメッセージを交換することで通信を行う（Erlang、Occam）。メッセージの交換は非同期的に行われるか（「送って祈る」とも言われるが、一般にメッセージ受信が確認できないときはメッセージを再送する）、送信側がメッセージの受信を確認するまでブロック状態となって待つランデブー方式を使用する。メッセージパッシングによる並行性は共有メモリによる並行性よりも直感的に理解しやすい。また、一般にメッセージパッシングの方が頑健だが低速である。メッセージパッシングシステムを分析し理解するための数学的理論が数々存在する。例えば、アクターモデルや各種プロセス代数である。

リソースアクセス

並行計算の主要な課題の1つは、並行プロセスが互いの邪魔をしないようにすることである。共有リソースbalanceで表される預金口座からの引き落としを行う擬似コードを以下に例として挙げる。

boolean withdraw(int withdrawal) {
    if (balance > withdrawal) {
        balance = balance - withdrawal;
        return true;
    } else return false;
}

balance=500として、2つの並行プロセスがそれぞれwithdraw(300)とwithdraw(350)という引き落としを行ったとする。両方の処理の2行目が両方の3行目の処理の前に行われると、balance > withdrawalはどちらもtrueとなり、両方の処理で減算に進む。しかし、そうすると総引き落とし額は口座残高を超えてしまう。このような共有リソースにからむ問題は並行性制御を必要とするか、Lock-freeとWait-freeアルゴリズムのようなノンブロッキング・アルゴリズムを必要とする。

並行システムは共有リソース（通信媒体を含む）に依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの調停回路を実装する必要がある。これにより無制限の非決定性問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。

だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな並行性問題（デッドロックなど）を生じる。

並行プログラミング言語

並行プログラミング言語は、並行性のための構造を備えたプログラミング言語である。具体的には、マルチスレッド、分散コンピューティング、メッセージパッシング、共有リソース（共有メモリ）、Futureパターンのサポートなどである。

現在、並行性のための構造を備えた最も一般的な言語はJavaとC#である。これらの言語は共有メモリ型並行性モデルを基本とし、モニタによるロックを備えている（メッセージパッシングモデルを共有メモリモデル上に構築することも可能）。メッセージパッシング型並行性モデルの言語としては、Erlangが最もよく使われている。

研究目的で開発された並行プログラミング言語（Pictなど）は実用を目的としたものより多い。しかし、Erlang、Limbo、Occam といった言語は過去20年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:

• Ada
• Afnix – データへの並行アクセスは自動的に保護される（従来はAlephと呼ばれていたが、Alefとは無関係）。
• Alef – スレッドとメッセージパッシングを備えた言語。初期のPlan 9のシステム記述に使われた言語。
• Alice – Standard ML に Future による並行性サポート機能を追加したもの
• CDL (Concurrent Description Language) – machine translatable（機械的に変換可能）、構成可能、オブジェクト指向、ビジュアルプログラミング言語。
• ChucK – 音響関連専用のプログラミング言語
• Cilk – 並行版C言語
• Clojure – LISP系の言語、JVM上で動作する。
• Concurrent C
• Concurrent Clean – 関数型言語。Haskellに近い。
• Concurrent Pascal – by Per Brinch Hansen
• Corn
• Curry
• Cω – C オメガ。C#に非同期通信を追加した研究用言語。
• E – Future機能使用。デッドロックを発生させない。
• Eiffel – 契約プログラミングに基づいたSCOOP機構による。
• Erlang – 共有のない非同期メッセージパッシングを使用。
• Janus – 宣言型言語。論理変数などをaskerとtellerに明確に区別する。
• Join Java – Javaに基づいた並行プログラミング言語。
• Joule – データフロー言語。メッセージパッシングによって通信する。
• KL1 – Guarded Horn Clausesに基づく論理型言語。第五世代コンピュータプロジェクトの研究成果。KLICなどの実装が利用可能。
• Limbo – Alefからの派生。Plan 9の後継であるInfernoのシステム記述に使われた。
• Oz – マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
  • Mozart Programming System – マルチプラットフォーム版 Oz
• MultiLisp – Scheme に並列性サポート機能を追加した派生言語。
• Occam – Communicating Sequential Processes (CSP) の影響を強く受けている。
  • Occam-π – Occamの派生言語。ミルナーのπ計算の考え方を導入。
• Pict – ミルナーのπ計算の実装に基づいている。
• SALSA – インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
• SR – 研究用言語。

他の多くの言語でもライブラリの形で並行性をサポートしている（機能的にも上記リストに挙げたものと遜色ない）。

並行計算モデル

並行計算モデルはいくつか存在し、並行システムの分析と理解に使用される。以下に主なものを列挙する:

• アクターモデル
• ペトリネット
• プロセス代数
  • アンビエント計算
  • Calculus of Communicating Systems
  • Communicating Sequential Processes
  • π計算
• 並行論理プログラミング
• 並行制約プログラミング

関連項目

• 並列計算
• en:Message passing
• en:Ptolemy Project

参考文献

• Filman, Robert E.; Daniel P. Friedman (1984年). Coordinated Computing: Tools and Techniques for Distributed Software. New York: McGraw-Hill. pp. 370. ISBN 0-07-022439-0. http://ic.arc.nasa.gov/people/filman/text/dpl/dpl.html 

外部リンク

• Concurrent Systems Virtual Library