並行計算

並行計算（へいこうけいさん、）とは、複数の計算あるいはアルゴリズムを、同一期間に同時実行させつつ相互に同調（コンカレント）させて、次の期間開始までに互いに完遂させるという計算形態を意味している。非同期なメッセージパッシングではその完遂の抽象化も可能になる。対義語は順次計算（シーケンシャル）である。並行コンピューティングとも邦訳される。並行プログラミング（Concurrent programming）とも言われる。
並行計算は、コンピュータプログラムやコンピュータネットワークの重要な特性であり、各プロセスの各スレッド制御などがその要点になる。並行計算下の各スレッドは、一定の制約内で他のスレッドの完了を待つことなく同時にそれぞれ進行できる。非同期では他のスレッドの応答も一定の制約内で待たなくてよくなる。エドガー・ダイクストラやアントニー・ホーアが、並行計算のパイオニアとして名高い。
イントロダクション.
並行計算は、並列計算（parallel computing）としばしば混同される。並列計算はマルチプロセッサ前提であり、独立した各プロセッサが割り振られた計算を同時実行することを指す。故にシングルプロセッサでは不可になる。分散システム内の各コンピュータが割り振られた計算を同時実行するのもそうである。並列計算はスループット・パフォーマンス向けとされる。並列計算の対義語はマルチプロセッサのシリアル計算（serial computing）であり、各プロセッサの排他的な計算順序配置が重視される。
並行計算は一つのプロセッサに複数のタスクを存在させて、各タスクに計算を割り振ることを指す。そこではタイムシェアリング技術などが使われる。マルチプロセッサならば、タスクを各プロセッサに分散できるのでより効率的になる。各タスクは協調する相手タスクが別プロセッサの並列性なのか、同プロセッサの並行性なのかを気にしない。いわゆるマルチタスクOSでは、カーネルとアプリケーションプログラムから複数のプロセスやスレッドが生成されて、それぞれがタスクの担い手になる。並行計算はレイテンシ・パフォーマンス向けとされる。並行計算の対義語はシーケンシャル計算（sequential computing）であり、タスクが一つずつ実行される。
並列計算・シリアル計算・並行計算・シーケンシャル計算の適性は下のようになる。
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。そこではスレッド間通信やプロセス間通信を意識して開発を行う必要があり、通信に用いるプロトコルの開発も必要となる。
リソース共有アクセス調整.
並行計算の最も身近な課題になるのは、複数のプロセス/スレッドで一つのリソース共有するためのアクセス調整をする並行性制御である。ここでよく取り沙汰されるのは競合状態、デッドロック、リソース欠乏などである。下は共有リソースのコード例である。
boolean withdraw(int withdrawal) {
 if (balance > withdrawal) {
 balance = balance - withdrawal;
 return true;
 return false;
ここでcodice_1としてプロセスAとプロセスBを走らせる。Aがcodice_2を、Bがcodice_3をコールする。Aが2行目をcodice_4で終えて3行目に入る前に、Bが2行目に入るとcodice_5はここでもcodice_4になってしまい、AとBの双方が減算してcodice_7となり、口座残高以上の金額が引き落とされてしまうことになる。こうしたリソース共有問題の並行性制御では、クリティカルセクションのロック（セマフォ・ミューテックス・モニタなど）同期がよく使われる。
並行システムは共有リソース（通信媒体を含む）に依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの調停回路を実装する必要がある。これにより無制限の非決定性問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな並行性問題（同期のデッドロックなど）を生じる。非ブロックアルゴリズムはそれらに対応できる並行性制御とされる。
並行計算のモデル.
数々の並行計算モデルが提唱されている。
一貫性モデル.
一貫性モデル（consistency models）はメモリモデルともよばれており、複数のプロセス/スレッドが同時にデータ領域に読み込み/書き込みを行っても、シーケンシャル計算と全く同じ結果が得られるようにするための計算モデルである。一貫性モデルの実装では、共有メモリ通信に分類されるクリティカルセクションのロック同期がよく使われる。
並行計算の実装.
並行プログラムには数々の実装手法が存在する。大抵はオペレーティングシステムが提供するプロセスとスレッドの同時走行とその相互通信が実装の枠組みにされる。プロセス群とスレッド群の並行走行による複数作業の同時実行可能性はマルチタスクなどと言われる。
相互作用と通信.
並行コンポーネント間の通信には、例えば以下の二通りがある。
ケース１：相互通信の明示的操作を要求する形式
ケース２：相互通信をプログラマから隠蔽する形式
並行プログラミング言語.
並行プログラミング言語は、並行性のための構造を備えたプログラミング言語である。具体的には、マルチスレッド、分散コンピューティング、、共有リソース（共有メモリ）、Futureパターンのサポートなどである。
、並行性のための構造を備えた最も一般的な言語はJavaとC#である。これらの言語は共有メモリ型並行性モデルを基本とし、モニタによるロックを備えている（メッセージパッシングモデルを共有メモリモデル上に構築することも可能）。メッセージパッシング型並行性モデルの言語としては、Erlangが最もよく使われている。
研究目的で開発された並行プログラミング言語（Pictなど）は実用を目的としたものより多い。しかし、Erlang、Limbo、Occam といった言語は過去20年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:
他の多くの言語でもライブラリの形で並行性をサポートしている（機能的にも上記リストに挙げたものと遜色ない）。