コンテンツにスキップ

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
Cewbot (会話 | 投稿記録)
m Bot作業依頼: sourceタグをsyntaxhighlightタグに置換 (Category:非推奨のsourceタグを使用しているページ) - log
編集の要約なし
(同じ利用者による、間の3版が非表示)
1行目: 1行目:
[[ファイル:Bidirectional recurrent neural network.png|境界|右|フレームなし|160x160px]]
'''並行計算'''(へいこうけいさん、{{lang-en-short|concurrent computing}})とは、コンピュータプログラムにおいて複数の相互作用を及ぼす計算タスクの(同時)[[並行性|並行的]]実行を指す。'''並行コンピューティング'''あるいは'''並行処理''' (concurrent processing) とも呼ぶ。
{{プログラミング・パラダイム}}


'''並行計算'''または'''並行コンピューティング'''({{lang-en-short|''Concurrent computing''}})とは、一定のフェーズに集約される複数の計算を同時に実行し、相互作用が伴なう計算間の整合性を逐次取りながら各結果を導出して、その結果が反映された次の並行計算のフェーズへの移行を反復するといったコンピュータ処理を意味する。並行計算の計算は[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]とも読み替えられる。計算間の相互作用は[[メッセージパッシング]]や[[プロセス間通信]]などと呼ばれ、各計算過程の整合性維持手法は[[同期]](''synchronization'')と呼ばれる。
== 概要 ==
汎用的なコンピュータおよび[[オペレーティングシステム]]では、ごく短時間で実行タスクを切り替えて複数のタスクを疑似的に同時実行することのできる[[マルチタスク]]システムが採用されることが多い。そして個々のタスクは、通常別々の[[プログラム (コンピュータ)|プログラム]]として実装されるか、1つのプログラムから複数の[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]を生成する形で実装される。そのようなプログラムを作成することを'''並行プログラミング'''と呼ぶ。タスク群は1つのプロセッサ([[CPU]]における1つのコア)上で動作する場合、複数のプロセッサ([[マルチコア]]プロセッサもしくはマルチソケットプロセッサ)上で動作する場合 ([[マルチプロセッシング]])、あるいはネットワークを介した[[分散コンピューティング|分散システム]]で動作する場合が考えられる。並行コンピューティングは[[並列コンピューティング]]と近い概念だが、タスク間の相互作用を重視する点が後者とは異なる。また、並列処理はスループットの改善が目的だが、並行処理は主にシステムの応答性の改善が目的である。


対義語である順接計算(''sequential computing'')が各結果を順次待つための休止状態を必要とするのに対し、並行計算では同期が取られる範囲内での休止状態は排除される。類似語である[[並列計算]](''parallel computing'')が相互作用を伴わない計算単位への分割とそのコンピュータ資源の割り当てに焦点を当てているのに対し、並行計算では計算間の相互作用と同期に焦点を当てている。並列計算の計算は[[タスク]]や[[トランザクション]]とも読み替えられる。並行計算は[[レイテンシ|レイテンシー]]重視、並列計算は[[スループット]]重視とも認識されている。
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、[[エドガー・ダイクストラ]]、Per Brinch Hansen、[[アントニー・ホーア]]が挙げられる。

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


並行計算を行うシステムの開発ではスレッド間通信やプロセス間通信を意識して開発を行う必要がある。したがって、通信に用いるプロトコルの開発も必要となる。
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、[[エドガー・ダイクストラ]]、Per Brinch Hansen、[[アントニー・ホーア]]が挙げられる。並行計算を行うシステムの開発ではスレッド間通信やプロセス間通信を意識して開発を行う必要がある。したがって、通信に用いるプロトコルの開発も必要となる。


== 並行的相互作用と通信 ==
== 並行コミュニケーションモデル ==
並行計算システムには、並行コンポーネント間の通信を抽象化してプログラマから隠蔽するものもある([[Future パターン]]に基づいた言語機能あるいはライブラリなど。一方明示的に通信を行わなければならないものもある。明示的通信は次の2種類に分類される:
並行計算システムには、並行コンポーネント間の通信を抽象化してプログラマから隠蔽するものもあり、その代表例は[[Future パターン]]に基づいた言語機能あるいはライブラリなどである。一方明示的に通信を行わなければならないものもある。明示的通信は次の2種類に分類される


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


== リソースアクセス ==
== 共有リソースモデル ==
並行計算の主要な課題の1つは、並行プロセスが互いの邪魔をしないようにすることである。共有リソース<code>balance</code>で表される預金口座からの引き落としを行う擬似コードを以下に例として挙げる。
並行計算の主要な課題の1つは、並行プロセスが互いの邪魔をしないようにすることである。共有リソース<code>balance</code>で表される預金口座からの引き落としを行う擬似コードを以下に例として挙げる。
<syntaxhighlight lang="java" line start="1">
<syntaxhighlight lang="java" line start="1">
29行目: 32行目:
<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アルゴリズム]]のようなノンブロッキング・アルゴリズムを必要とする。
<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 π}}
* [[並行論理プログラミング]]
* [[並行制約プログラミング]]


== 並行プログラミング言語 ==
== 並行プログラミング言語 ==
並行プログラミング言語は、[[並行性]]のための構造を備えた[[プログラミング言語]]である。具体的には[[マルチスレッド]]、[[分散コンピューティング]]、{{仮リンク|メッセージパッシング|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年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:
{{プログラミング言語|index=へいこうけいさん}}

並行プログラミング言語は、[[並行性]]のための構造を備えた[[プログラミング言語]]である。具体的には、[[マルチスレッド]]、[[分散コンピューティング]]、{{仮リンク|メッセージパッシング型プログラミング|en|Message passing programming|label=メッセージパッシング}}、共有[[リソース]]([[並列ランダムアクセス機械|共有メモリ]])、[[Future パターン|Futureパターン]]のサポートなどである。

{{いつ範囲|date=2019年1月|現在}}、並行性のための構造を備えた最も一般的な言語は[[Java]]と[[C Sharp|C#]]である。これらの言語は共有メモリ型並行性モデルを基本とし、[[モニタ (同期)|モニタ]]によるロックを備えている(メッセージパッシングモデルを共有メモリモデル上に構築することも可能)。メッセージパッシング型並行性モデルの言語としては、[[Erlang]]が最もよく使われている。

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


*[[Ada]]
*[[Ada]]
66行目: 73行目:
*[[Oz (プログラミング言語)|Oz]] &ndash; マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
*[[Oz (プログラミング言語)|Oz]] &ndash; マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
**[http://www.mozart-oz.org/ Mozart Programming System] &ndash; [[クロスプラットフォーム|マルチプラットフォーム]]版 Oz
**[http://www.mozart-oz.org/ Mozart Programming System] &ndash; [[クロスプラットフォーム|マルチプラットフォーム]]版 Oz
*MultiLisp &ndash; [[Scheme]] に並列性サポート機能を追加した派生言語。
*{{仮リンク|MultLisp|en|MultiLisp}} &ndash; [[Scheme]] に並列性サポート機能を追加した派生言語。
*[[Occam]] &ndash; [[Communicating Sequential Processes]] (CSP) の影響を強く受けている。
*[[Occam]] &ndash; [[Communicating Sequential Processes]] (CSP) の影響を強く受けている。
**Occam-π &ndash; [[Occam]]の派生言語。[[ロビン・ミルナー|ミルナー]]の[[π計算]]の考え方を導入。
**Occam-π &ndash; [[Occam]]の派生言語。[[ロビン・ミルナー|ミルナー]]のΠ計算の考え方を導入。
*[[Pict]] &ndash; ミルナーの[[π計算]]の実装に基づいている。
*{{仮リンク|Pict|en|Pict (programming language)|label=Pict}} &ndash; ミルナーのΠ計算の実装に基づいている。
*SALSA &ndash; インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
*SALSA &ndash; インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
*SR &ndash; 研究用言語。
*SR &ndash; 研究用言語。


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

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

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


== 関連項目 ==
== 関連項目 ==
* [[並列計算]]
* [[並列計算]]
*[[プロセス代数]]
* [[:en:Message passing]]
*[[アクターモデル]]
* [[:en:Ptolemy Project]]
* {{仮リンク|メッセージパッシング|en|Message passing}}
*{{仮リンク|Ptolemy Project|en|Ptolemy Project}}


==参考文献==
==参考文献==
100行目: 96行目:


{{デフォルトソート:へいこうけいさん}}
{{デフォルトソート:へいこうけいさん}}
[[Category:オペレーティングシステムの仕組み]]
[[Category:並行計算|*へいこうけいさん]]
[[Category:並行計算|*へいこうけいさん]]
[[Category:オペレーティングシステムの仕組み]]
[[Category:エドガー・ダイクストラ]]
[[Category:エドガー・ダイクストラ]]
{{並列コンピューティング}}{{コンピュータ科学}}
{{並列コンピューティング}}
{{コンピュータ科学}}

2021年2月22日 (月) 09:24時点における版

並行計算または並行コンピューティング: Concurrent computing)とは、一定のフェーズに集約される複数の計算を同時に実行し、相互作用が伴なう計算間の整合性を逐次取りながら各結果を導出して、その結果が反映された次の並行計算のフェーズへの移行を反復するといったコンピュータ処理を意味する。並行計算の計算はプロセススレッドとも読み替えられる。計算間の相互作用はメッセージパッシングプロセス間通信などと呼ばれ、各計算過程の整合性維持手法は同期synchronization)と呼ばれる。

対義語である順接計算(sequential computing)が各結果を順次待つための休止状態を必要とするのに対し、並行計算では同期が取られる範囲内での休止状態は排除される。類似語である並列計算parallel computing)が相互作用を伴わない計算単位への分割とそのコンピュータ資源の割り当てに焦点を当てているのに対し、並行計算では計算間の相互作用と同期に焦点を当てている。並列計算の計算はタスクトランザクションとも読み替えられる。並行計算はレイテンシー重視、並列計算はスループット重視とも認識されている。

概要

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

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

並行コミュニケーションモデル

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

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

共有リソースモデル

並行計算の主要な課題の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パターンのサポートなどである。現在[いつ?]、並行性のための構造を備えた最も一般的な言語はJavaC#である。これらの言語は共有メモリ型並行性モデルを基本とし、モニタによるロックを備えている(メッセージパッシングモデルを共有メモリモデル上に構築することも可能)。メッセージパッシング型並行性モデルの言語としては、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#に非同期通信を追加した研究用言語。
  • E – Future機能使用。デッドロックを発生させない。
  • Eiffel契約プログラミングに基づいたSCOOP機構による。
  • Erlang – 共有のない非同期メッセージパッシングを使用。
  • Janus – 宣言型言語。論理変数などをaskerとtellerに明確に区別する。
  • Join Java – Javaに基づいた並行プログラミング言語。
  • Joule – データフロー言語。メッセージパッシングによって通信する。
  • KL1Guarded Horn Clausesに基づく論理型言語。第五世代コンピュータプロジェクトの研究成果。KLICなどの実装が利用可能。
  • Limbo – Alefからの派生。Plan 9の後継であるInfernoのシステム記述に使われた。
  • Oz – マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
  • MultLisp英語版Scheme に並列性サポート機能を追加した派生言語。
  • OccamCommunicating Sequential Processes (CSP) の影響を強く受けている。
  • Pict英語版 – ミルナーのΠ計算の実装に基づいている。
  • SALSA – インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
  • SR – 研究用言語。

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

関連項目

参考文献

外部リンク