並行計算

並行計算とは、複数の計算あるいはアルゴリズムを、同一期間に同時実行させつつ相互に同調させて、次の期間開始までに互いに完遂させるという計算形態を意味している。非同期なメッセージパッシングではその完遂の抽象化も可能になる。対義語は順次計算である。並行コンピューティングとも邦訳される。並行プログラミングとも言われる。

並行計算は、コンピュータプログラムやコンピュータネットワークの重要な特性であり、各プロセスの各スレッド制御などがその要点になる。並行計算下の各スレッドは、一定の制約内で他のスレッドの完了を待つことなく同時にそれぞれ進行できる。非同期では他のスレッドの応答も一定の制約内で待たなくてよくなる。エドガー・ダイクストラやアントニー・ホーアが、並行計算のパイオニアとして名高い。

1. イントロダクション
------------

並行計算は、並列計算としばしば混同される。並列計算はマルチプロセッサ前提であり、独立した各プロセッサが割り振られた計算を同時実行することを指す。故にシングルプロセッサでは不可になる。分散システム内の各コンピュータが割り振られた計算を同時実行するのもそうである。並列計算はスループット・パフォーマンス向けとされる。並列計算の対義語はマルチプロセッサのシリアル計算でありPatterson、各プロセッサの排他的な計算順序配置が重視される。

並行計算は一つのプロセッサに複数のタスクを存在させて、各タスクに計算を割り振ることを指す。そこではタイムシェアリング技術などが使われる。マルチプロセッサならば、タスクを各プロセッサに分散できるのでより効率的になる。各タスクは協調する相手タスクが別プロセッサの並列性なのか、同プロセッサの並行性なのかを気にしない。いわゆるマルチタスクOSでは、カーネルとアプリケーションプログラムから複数のプロセスやスレッドが生成されて、それぞれがタスクの担い手になる。並行計算はレイテンシ・パフォーマンス向けとされる。並行計算の対義語はシーケンシャル計算でありPatterson、タスクが一つずつ実行される。

並列計算・シリアル計算・並行計算・シーケンシャル計算の適性は下のようになる。

スレッドAの完了後に、スレッドBが実行される
スレッドAと、スレッドBが交互に実行される
スレッドAと、スレッドBが同時に実行される並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。そこではスレッド間通信やプロセス間通信を意識して開発を行う必要があり、通信に用いるプロトコルの開発も必要となる。

1.1. リソース共有アクセス調整
-----------------

並行計算の最も身近な課題になるのは、複数のプロセス/スレッドで一つのリソース共有するためのアクセス調整をする並行性制御である。ここでよく取り沙汰されるのは競合状態、デッドロック、リソース欠乏などである。下は共有リソースのコード例である。 boolean withdraw { if  { balance = balance - withdrawal; return true; } return false; } ここでbalance=500としてプロセスAとプロセスBを走らせる。Aがwithdrawを、Bがwithdrawをコールする。Aが2行目をtrueで終えて3行目に入る前に、Bが2行目に入るとbalance > withdrawalはここでもtrueになってしまい、AとBの双方が減算してbalance=-150となり、口座残高以上の金額が引き落とされてしまうことになる。こうしたリソース共有問題の並行性制御では、クリティカルセクションのロック同期がよく使われる。

並行システムは共有リソースに依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの調停回路を実装する必要がある。これにより無制限の非決定性問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな並行性問題を生じる。非ブロックアルゴリズムはそれらに対応できる並行性制御とされる。

2. 並行計算のモデル
-----------

数々の並行計算モデルが提唱されている。

ペトリネット
データフローアーキテクチャ
プロセス代数
通信シーケンシャルプロセス
アクターモデル
ソフトウェアトランザクショナルメモリ
アトミックコミット

2.1. 一貫性モデル
-----------

一貫性モデルはメモリモデルともよばれており、複数のプロセス/スレッドが同時にデータ領域に読み込み/書き込みを行っても、シーケンシャル計算と全く同じ結果が得られるようにするための計算モデルである。一貫性モデルの実装では、共有メモリ通信に分類されるクリティカルセクションのロック同期がよく使われる。

3. 並行計算の実装
----------

並行プログラムには数々の実装手法が存在する。大抵はオペレーティングシステムが提供するプロセスとスレッドの同時走行とその相互通信が実装の枠組みにされる。プロセス群とスレッド群の並行走行による複数作業の同時実行可能性はマルチタスクなどと言われる。

3.1. 相互作用と通信
------------

並行コンポーネント間の通信には、例えば以下の二通りがある。

ケース１：相互通信の明示的操作を要求する形式

同期傾向になる。明示的操作は特別なプログラム構文を必要にする。ソフトウェアトランザクショナルメモリ、クリティカルセクション同期などのモデルに従っての実装になる。共有メモリ通信並行コンポーネントたちは共有メモリの内容を更新することで通信を行う。JavaやC#が用いている。クリティカルセクションを定めてロックオブジェクトを用いての同期でその範囲を並行性制御する。ロック手法にはセマフォ、ミューテックス、モニタ、バリア、読み書きロックなどがある。スレッドセーフが重視されている。
ケース２：相互通信をプログラマから隠蔽する形式

非同期傾向になる。上の明示的操作をコード評価/呼出しやデータ参照/代入といった標準構文でまかなえる。プロセス計算、Futureパターンなどのモデルに従っての実装になる。メッセージパッシング通信並行コンポーネントたちはメッセージの交換で通信を行う。Erlang、Go、Scala、OpenMPI、Occamなどが用いている。メッセージ交換は通常非同期だが、チャネルという同期形式もあり、こちらでの送信側は受信側がメッセージに応答するまで待機する双方向通信になる。非同期なメッセージ交換での送信側は、受信側がいま応答できるかどうかに関係なくメッセージを送れる単方向通信になる。これは送って祈ると形容されている。ここでの送信型は、メッセージを送るとすぐにfutureやpromiseと呼ばれる抽象的な応答オブジェクトを受け取れるので基本的に待機することはない。メッセージパッシング通信は、共有メモリ通信よりも平易で堅牢であるが、オーバーヘッドが大きいとも考えられている。メッセージパッシングには数々の数学的理論があり、アクターモデルやプロセス計算などが有名である。

4. 並行プログラミング言語
--------------

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

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

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

Ada
Afnix – データへの並行アクセスは自動的に保護される。
Alef – スレッドとメッセージパッシングを備えた言語。初期のPlan 9のシステム記述に使われた言語。
Alice – Standard ML に Future による並行性サポート機能を追加したもの
[1] – 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に基づく論理型言語。第五世代コンピュータプロジェクトの研究成果。[2]などの実装が利用可能。
Limbo – Alefからの派生。Plan 9の後継であるInfernoのシステム記述に使われた。
Oz – マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
[3] – マルチプラットフォーム版 Oz
MultiLisp – Scheme に並列性サポート機能を追加した派生言語。
Occam – Communicating Sequential Processes  の影響を強く受けている。
Occam-π – Occamの派生言語。ミルナーのπ計算の考え方を導入。
Pict – ミルナーのπ計算の実装に基づいている。
SALSA – インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
SR – 研究用言語。他の多くの言語でもライブラリの形で並行性をサポートしている。

5. 関連項目
-------

並列計算
非同期IO
競合状態
トランザクション処理
ソフトウェアトランザクショナルメモリ
クリティカルセクション
不可分操作
排他制御
並行性制御
グローバル並行性制御
分散並行性制御
スケジューリング
マルチスレッド
マルチタスク
Ptolemy Project
メッセージパッシング
プロセス代数
アクターモデル
同期
ロック
セマフォ
ミューテックス
モニタ
バリア
非ブロックアルゴリズム

6. 脚注
-----

7. 参考文献
-------

8. 外部リンク
--------

[4]