Wikipedia

「並行計算」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
編集の要約なし
rvv
タグ: 手動差し戻し
1行目:
'''並行計算'''（へいこうけいさん、{{lang-en-short|concurrent computing}}）とは、コンピュータプログラムにおいて複数の相互作用を及ぼす計算タスクの（同時）[[並行性|並行的]]実行を指す。'''並行コンピューティング'''あるいは'''並行処理''' (concurrent processing) とも呼ぶ。
[[ファイル:Bidirectional recurrent neural network.png|境界|右|フレームなし|160x160px]]
{{プログラミング・パラダイム}}▼
 
== 概要 ==▼
'''並行計算'''または'''並行コンピューティング'''（{{lang-en-short|''Concurrent computing''}}）とは、一定のフェーズに集約される複数の計算を同時に実行し、相互作用が伴なう計算間の整合性を逐次取りながら各結果を導出して、その結果が反映された次の並行計算のフェーズへの移行を反復するといったコンピュータ処理を意味する。並行計算の計算は[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]とも読み替えられる。計算間の相互作用は[[メッセージパッシング]]や[[プロセス間通信]]などと呼ばれ、各計算過程の整合性維持手法は[[同期]]（''synchronization''）と呼ばれる。
汎用的なコンピュータおよび[[オペレーティングシステム]]では、ごく短時間で実行タスクを切り替えて複数のタスクを疑似的に同時実行することのできる[[マルチタスク]]システムが採用されることが多い。そして個々のタスクは、通常別々の[[プログラム (コンピュータ)|プログラム]]として実装されるか、1つのプログラムから複数の[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]を生成する形で実装される。そのようなプログラムを作成することを'''並行プログラミング'''と呼ぶ。タスク群は1つのプロセッサ（[[CPU]]における1つのコア）上で動作する場合、複数のプロセッサ（[[マルチコア]]プロセッサもしくはマルチソケットプロセッサ）上で動作する場合 ([[マルチプロセッシング]])、あるいはネットワークを介した[[分散コンピューティング|分散システム]]で動作する場合が考えられる。並行コンピューティングは[[並列コンピューティング]]と近い概念だが、タスク間の相互作用を重視する点が後者とは異なる。また、並列処理はスループットの改善が目的だが、並行処理は主にシステムの応答性の改善が目的である。▼
 
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、[[エドガー・ダイクストラ]]、Per Brinch Hansen、[[アントニー・ホーア]]が挙げられる。
対義語である順接計算（''sequential computing''）が各結果を順次待つための休止状態を必要とするのに対し、並行計算では同期が取られる範囲内での休止状態は排除される。類似語である[[並列計算]]（''parallel computing''）が相互作用を伴わない計算単位への分割とそのコンピュータ資源の割り当てに焦点を当てているのに対し、並行計算では計算間の相互作用と同期に焦点を当てている。並列計算の計算は[[タスク]]や[[トランザクション]]とも読み替えられる。並行計算は[[レイテンシ|レイテンシー]]重視、並列計算は[[スループット]]重視とも認識されている。
 
▲== 概要 ==
▲汎用的なコンピュータおよび[[オペレーティングシステム]]では、ごく短時間で実行タスクを切り替えて複数のタスクを疑似的に同時実行することのできる[[マルチタスク]]システムが採用されることが多い。そして個々のタスクは、通常別々の[[プログラム (コンピュータ)|プログラム]]として実装されるか、1つのプログラムから複数の[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]を生成する形で実装される。そのようなプログラムを作成することを並行プログラミングと呼ぶ。タスク群は1つのプロセッサ（[[CPU]]における1つのコア）上で動作する場合、複数のプロセッサ（[[マルチコア]]プロセッサもしくはマルチソケットプロセッサ）上で動作する場合 ([[マルチプロセッシング]])、あるいはネットワークを介した[[分散コンピューティング|分散システム]]で動作する場合が考えられる。並行コンピューティングは[[並列コンピューティング]]と近い概念だが、タスク間の相互作用を重視する点が後者とは異なる。また、並列処理はスループットの改善が目的だが、並行処理は主にシステムの応答性の改善が目的である。
 
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、[[エドガー・ダイクストラ]]、Per Brinch Hansen、[[アントニー・ホーア]]が挙げられる。並行計算を行うシステムの開発ではスレッド間通信やプロセス間通信を意識して開発を行う必要がある。したがって、通信に用いるプロトコルの開発も必要となる。
 
== 並行コミュニケーションモデル的相互作用と通信 ==
並行計算システムには、並行コンポーネント間の通信を抽象化してプログラマから隠蔽するものもあり、その代表例はる（[[Future パターン]]に基づいた言語機能あるいはライブラリなどである）。一方で、明示的に通信を行わなければならないものもある。明示的通信は次の2種類に分類される。:
 
; [[共有メモリ]]通信
20 ⟶ 17行目:
: 並行コンポーネント群はメッセージを交換することで通信を行う（[[Erlang]]、[[Occam]]）。メッセージの交換は非同期的に行われるか（「送って祈る」とも言われるが、一般にメッセージ受信が確認できないときはメッセージを再送する）、送信側がメッセージの受信を確認するまでブロック状態となって待つランデブー方式を使用する。メッセージパッシングによる並行性は共有メモリによる並行性よりも直感的に理解しやすい。また、一般にメッセージパッシングの方が頑健だが低速である。メッセージパッシングシステムを分析し理解するための数学的理論が数々存在する。例えば、[[アクターモデル]]や各種[[プロセス代数]]である。
 
== 共有リソースモデルアクセス ==
並行計算の主要な課題の1つは、並行プロセスが互いの邪魔をしないようにすることである。共有リソース<code>balance</code>で表される預金口座からの引き落としを行う擬似コードを以下に例として挙げる。
<syntaxhighlight lang="java" line start="1">
32 ⟶ 29行目:
<code>balance=500</code>として、2つの並行プロセスがそれぞれ<code>withdraw(300)</code>と<code>withdraw(350)</code>という引き落としを行ったとする。両方の処理の2行目が両方の3行目の処理の前に行われると、<code>balance > withdrawal</code>はどちらも<code>true</code>となり、両方の処理で減算に進む。しかし、そうすると総引き落とし額は口座残高を超えてしまう。このような共有リソースにからむ問題は[[並行性制御]]を必要とするか、[[Lock-freeとWait-freeアルゴリズム]]のようなノンブロッキング・アルゴリズムを必要とする。
 
並行システムは共有リソース（通信媒体を含む）に依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの[[調停回路]]を実装する必要がある。これにより[[無制限の非決定性]]問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな[[並行性]]問題（[[デッドロック]]など）を生じる。
 
だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな[[並行性]]問題（[[デッドロック]]など）を生じる。
== 並行計算モデル ==▼
並行計算モデルはいくつか存在し、並行システムの分析と理解に使用される。以下に主なものを列挙する:▼
* [[アクターモデル]]▼
* [[ペトリネット]]▼
* [[プロセス代数]]▼
** {{仮リンク|アンビエント計算|en|Ambient intelligence}}
** {{仮リンク|Calculus of communicating systems|en|Calculus of communicating systems}}
** [[Communicating Sequential Processes]]▼
** {{仮リンク|Π計算|en|Approximations of π}}
* [[並行論理プログラミング]]▼
* [[並行制約プログラミング]]▼
 
== 並行プログラミング言語 ==
▲{{プログラミング・パラダイム言語|index=へいこうけいさん}}
並行プログラミング言語は、[[並行性]]のための構造を備えた[[プログラミング言語]]である。具体的には[[マルチスレッド]]、[[分散コンピューティング]]、{{仮リンク|メッセージパッシング|en|Message passing programming}}、[[並列ランダムアクセス機械|共有リソース方式]]、[[Future パターン|Futureパターン]]のサポートなどである。{{いつ範囲|date=2019年1月|現在}}、並行性のための構造を備えた最も一般的な言語は[[Java]]と[[C Sharp|C#]]である。これらの言語は共有メモリ型並行性モデルを基本とし、[[モニタ (同期)|モニタ]]によるロックを備えている（メッセージパッシングモデルを共有メモリモデル上に構築することも可能）。メッセージパッシング型並行性モデルの言語としては、[[Erlang]]が最もよく使われている。研究目的で開発された並行プログラミング言語（{{仮リンク|Pict|en|Pict (programming language)|label=Pict}}など）は実用を目的としたものより多い。しかし、Erlang、Limbo、Occam といった言語は過去20年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:
 
並行プログラミング言語は、[[並行性]]のための構造を備えた[[プログラミング言語]]である。具体的には、[[マルチスレッド]]、[[分散コンピューティング]]、{{仮リンク|メッセージパッシング型プログラミング|en|Message passing programming|label=メッセージパッシング}}、共有[[リソース]]（[[並列ランダムアクセス機械|共有メモリ]]）、[[Future パターン|Futureパターン]]のサポートなどである。
 
{{いつ範囲|date=2019年1月|現在}}、並行性のための構造を備えた最も一般的な言語は[[Java]]と[[C Sharp|C#]]である。これらの言語は共有メモリ型並行性モデルを基本とし、[[モニタ (同期)|モニタ]]によるロックを備えている（メッセージパッシングモデルを共有メモリモデル上に構築することも可能）。メッセージパッシング型並行性モデルの言語としては、[[Erlang]]が最もよく使われている。
 
研究目的で開発された並行プログラミング言語（[[Pict]]など）は実用を目的としたものより多い。しかし、Erlang、Limbo、Occam といった言語は過去20年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:
 
*[[Ada]]
73 ⟶ 66行目:
*[[Oz (プログラミング言語)|Oz]] &ndash; マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
**[http://www.mozart-oz.org/ Mozart Programming System] &ndash; [[クロスプラットフォーム|マルチプラットフォーム]]版 Oz
*{{仮リンク|MultLisp|en|MultiLisp}} &ndash; [[Scheme]] に並列性サポート機能を追加した派生言語。
*[[Occam]] &ndash; [[Communicating Sequential Processes]] (CSP) の影響を強く受けている。
**Occam-π &ndash; [[Occam]]の派生言語。[[ロビン・ミルナー|ミルナー]]のΠ[[π計算]]の考え方を導入。
*{{仮リンク|[[Pict|en|Pict (programming language)|label=Pict}}]] &ndash; ミルナーのΠ[[π計算]]の実装に基づいている。
*SALSA &ndash; インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
*SR &ndash; 研究用言語。
 
他の多くの言語でもライブラリの形で並行性をサポートしている（機能的にも上記リストに挙げたものと遜色ない）。
 
▲== 並行計算モデル ==
▲並行計算モデルはいくつか存在し、並行システムの分析と理解に使用される。以下に主なものを列挙する:
 
▲* [[アクターモデル]]
▲* [[ペトリネット]]
▲* [[プロセス代数]]
** [[アンビエント計算]]
** [[Calculus of Communicating Systems]]
▲** [[Communicating Sequential Processes]]
** [[π計算]]
▲* [[並行論理プログラミング]]
▲* [[並行制約プログラミング]]
 
== 関連項目 ==
* [[並列計算]]
* [[:en:Message passing]]
*[[プロセス代数]]
* [[:en:Ptolemy Project]]
*[[アクターモデル]]
* {{仮リンク|メッセージパッシング|en|Message passing}}
*{{仮リンク|Ptolemy Project|en|Ptolemy Project}}
 
==参考文献==
96 ⟶ 100行目:
 
{{デフォルトソート:へいこうけいさん}}
[[Category:並行計算|*へいこうけいさん]]▼
[[Category:オペレーティングシステムの仕組み]]
▲[[Category:並行計算|*へいこうけいさん]]
[[Category:エドガー・ダイクストラ]]
{{並列コンピューティング}}{{コンピュータ科学}}
{{コンピュータ科学}}
「https://ja.wikipedia.org/wiki/並行計算」から取得