同時実行コンピューティングとは、複数の計算を順番に実行するのではなく、重複する期間に同時に実行し、1 つの計算が完了してから次の計算を開始する コンピューティング形式です。

これは、プログラム、コンピュータ、ネットワークなど、各プロセスに個別の実行ポイント、つまり「制御スレッド」が存在するシステムの特性です。並行システムとは、他のすべての計算が完了するのを待たずに計算を進めることができるシステムのことです。[1]

並行コンピューティングはモジュールプログラミングの一形態です。そのパラダイムでは、全体的な計算が並行して実行可能なサブ計算に分割されます。並行コンピューティング分野の先駆者には、エドガー・ダイクストラ、ペル・ブリンチ・ハンセン、CAR・ホーアなどがいます。[2]

導入

同時計算の概念は、関連しているものの異なる概念である並列計算としばしば混同されます[ 3] [4]。ただし、どちらも「複数のプロセスが同時に実行される」と説明できます。並列計算では、実行は物理的に同じ瞬間に行われます。例えば、マルチプロセッサマシンの別々のプロセッサ上で、計算の高速化を目的として実行されます。並列計算は、（1コアの）単一プロセッサでは不可能です。なぜなら、どの瞬間（どのクロックサイクルでも）にも1つの計算しか実行できないからです。[a]一方、同時計算では、プロセスの存続期間が重なり合いますが、実行は同時には行われません。ここでの目標は、複数のクライアントが同時にサーバーにアクセスするように、同時に発生するプロセスをモデル化することです。ソフトウェアシステムを、複数の同時かつ通信する部分で構成されるものとして構造化することは、各部分が並列実行可能かどうかに関わらず、複雑さに対処するのに役立ちます。[5] : 1 

例えば、各プロセスの実行ステップをタイムシェアリングスライスでインターリーブすることで、1つのコアで複数のプロセスを並行して実行できます。つまり、一度に実行されるプロセスは1つだけで、そのタイムスライス内で完了しない場合は一時停止され、別のプロセスが開始または再開され、その後、元のプロセスが再開されます。このように、ある瞬間に複数のプロセスが実行の途中にある場合でも、その瞬間に実行されているのは1つのプロセスだけです。[要出典]

同時計算は、例えば各プロセスを別々のプロセッサまたはプロセッサコアに割り当てたり、計算をネットワーク全体に 分散したりすることによって並列に実行することができる[3] [6] 。

並行システムにおけるタスクの実行タイミングはスケジューリングに依存し、必ずしも同時に実行される必要はない。例えば、2つのタスクT1とT2があるとする。[要出典]

  • T1 は T2 より先に実行されて終了する可能性があり、その逆も成り立ちます(シリアルおよびシーケンシャル)
  • T1とT2は交互に実行される可能性がある（シリアルおよび同時）
  • T1とT2は、同じ瞬間に同時に実行される可能性がある（並列かつ同時実行）。

The word "sequential" is used as an antonym for both "concurrent" and "parallel"; when these are explicitly distinguished, concurrent/sequential and parallel/serial are used as opposing pairs.[7] A schedule in which tasks execute one at a time (serially, no parallelism), without interleaving (sequentially, no concurrency: no task begins until the prior task ends) is called a serial schedule. A set of tasks that can be scheduled serially is serializable, which simplifies concurrency control.[citation needed]

Coordinating access to shared resources

The main challenge in designing concurrent programs is concurrency control: ensuring the correct sequencing of the interactions or communications between different computational executions, and coordinating access to resources that are shared among executions.[6] Potential problems include race conditions, deadlocks, and resource starvation. For example, consider the following algorithm to make withdrawals from a checking account represented by the shared resource balance: 

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

Suppose balance = 500, and two concurrent threads make the calls withdraw(300) and withdraw(350). If line 3 in both operations executes before line 5 both operations will find that balance >= withdrawal evaluates to true, and execution will proceed to subtracting the withdrawal amount. However, since both processes perform their withdrawals, the total amount withdrawn will end up being more than the original balance. These sorts of problems with shared resources benefit from the use of concurrency control, or non-blocking algorithms.

Advantages

There are advantages of concurrent computing:

  • Increased program throughput—parallel execution of a concurrent algorithm allows the number of tasks completed in a given time to increase proportionally to the number of processors according to Gustafson's law.[8]
  • High responsiveness for input/output—input/output-intensive programs mostly wait for input or output operations to complete. Concurrent programming allows the time that would be spent waiting to be used for another task.[9]
  • より適切なプログラム構造 - 一部の問題や問題領域は、並行タスクまたはプロセスとして表現するのに適しています。例えば、MVCC などです。

モデル

1962年に導入されたペトリネットは、並行実行のルールを体系化する初期の試みでした。後にデータフロー理論はペトリネットを基盤として発展し、データフロー理論の考え方を物理的に実装するためにデータフローアーキテクチャが開発されました。1970年代後半からは、相互作用するコンポーネントで構成されるシステムについて代数的推論を可能にするために、通信システム計算（CCS）や通信逐次プロセス（CSP）などのプロセス計算が開発されました。π計算は、動的なトポロジーに関する推論機能を追加しました。

入出力オートマトンが 1987 年に導入されました。

並行システムの動作を記述するために、 Lamport のTLA+などのロジックや、トレースやアクター イベント ダイアグラムなどの数学モデルも開発されてきました。

ソフトウェア トランザクショナル メモリは、データベース理論からアトミック トランザクションの概念を借用し、それをメモリ アクセスに適用します。

一貫性モデル

並行プログラミング言語とマルチプロセッサプログラムには、整合性モデル（メモリモデルとも呼ばれます）が必要です。整合性モデルは、コンピュータメモリ上での操作がどのように行われ、結果がどのように生成されるかについての規則を定義します。

最初の一貫性モデルの一つは、レスリー・ランポートの逐次一貫性モデルでした。逐次一貫性とは、プログラムの実行結果が逐次プログラムと同じ結果になるという性質です。具体的には、「すべてのプロセッサの処理が特定の順序で実行された場合と、各プロセッサの処理がプログラムで指定された順序で実行された場合とで、どの実行結果も同じになる」場合、プログラムは逐次一貫性があると言えます。[10]

実装

並行プログラムを実装するには、各計算実行をオペレーティング システム プロセスとして実装したり、計算プロセスを単一のオペレーティング システム プロセス内の 一連のスレッドとして実装するなど、さまざまな方法を使用できます。

交流とコミュニケーション

並行コンピューティングシステムの中には、並行コンポーネント間の通信がプログラマから隠蔽されているもの（例えば、futuresの使用など）もあれば、明示的に処理する必要があるものもあります。明示的な通信は、以下の2つのクラスに分けられます。

共有メモリ通信
並行コンポーネントは、共有メモリの内容を変更することで通信を行います（JavaやC#がその例です）。このスタイルの並行プログラミングでは、通常、スレッド間の連携のために何らかのロック機構（例：ミューテックス、セマフォ、モニター）を使用する必要があります。これらのいずれかを適切に実装したプログラムは、スレッドセーフであると言われています。
メッセージパッシング通信
並行コンポーネントは、メッセージ パッシング（メッセージの交換、MPI、Go、Scala、Erlang、occamに代表される）によって通信します。メッセージの交換は非同期的に実行される場合もあれば、送信側がメッセージを受信するまでブロックする同期的な「ランデブー」スタイルを使用する場合もあります。非同期メッセージ パッシングは、信頼できる場合もあれば、信頼できない場合もあります（「送信して祈る」と呼ばれることもあります）。メッセージ パッシングによる並行性は、共有メモリによる並行性よりもはるかに容易に理解できる傾向があり、通常、並行プログラミングのより堅牢な形式であると考えられています。[要出典]メッセージ パッシング システムを理解および分析するための多種多様な数学理論が利用可能であり、アクター モデルやさまざまなプロセス計算などがあります。メッセージ パッシングは、共有メモリキャッシュ コヒーレンスの有無にかかわらず、対称型マルチプロセッサによって効率的に実装できます。

共有メモリとメッセージパッシングの同時実行性には、異なるパフォーマンス特性があります。一般的に（常にそうとは限りませんが）、メッセージパッシングシステムではプロセスごとのメモリオーバーヘッドとタスクスイッチングオーバーヘッドは低くなりますが、メッセージパッシングのオーバーヘッドはプロシージャ呼び出しよりも大きくなります。これらの違いは、他のパフォーマンス要因によって打ち消されることがよくあります。

歴史

並行コンピューティングは、19世紀から20世紀初頭にかけての鉄道と電信に関する研究から発展しました。セマフォなど、この時代に遡る用語もいくつかあります。これらは、同じ鉄道システム上で複数の列車をどのように処理するか（衝突を回避し、効率を最大化すること）、そして時分割多重化（1870年代）などによって、与えられた一連の回線上で複数の伝送をどのように処理するか（効率を向上させること）という問題に対処するために生まれました。

並行アルゴリズムの学術的研究は1960年代に始まり、ダイクストラ（1965）が相互排除を特定して解決するこの分野で最初の論文を発表したとされています。[11]

有病率

同時実行性はコンピューティングのあらゆる分野に浸透しており、単一チップ上の低レベルハードウェアから世界規模のネットワークに至るまで、多岐にわたります。以下に例を挙げます。

プログラミング言語レベル:

オペレーティング システム レベル:

ネットワーク レベルでは、ネットワーク システムは個別のデバイスで構成されているため、通常はその性質上並行です。

並行プログラミングをサポートする言語

並行プログラミング言語とは、並行性のための言語構造を用いるプログラミング言語です。これらの構造には、マルチスレッド、分散コンピューティングのサポート、メッセージパッシング、共有リソース（共有メモリを含む）、FuturesとPromiseなどが含まれます。このような言語は、並行性指向言語または並行性指向プログラミング言語（COPL）と呼ばれることもあります。[12]

現在、並行処理に特化した構造を持つ最も一般的に使用されているプログラミング言語は、JavaとC#です。どちらの言語も基本的に共有メモリ型の並行処理モデルを採用しており、ロック機能はモニターによって提供されます（ただし、メッセージパッシングモデルは基盤となる共有メモリモデル上に実装可能であり、実際に実装されています）。メッセージパッシング型の並行処理モデルを使用する言語の中で、 2010年時点ではErlangがおそらく業界で最も広く使用されていました。[要出典]

多くの並行プログラミング言語は、実稼働用言語というよりも、研究用言語（例：Pict ）として開発されてきました。しかしながら、 Erlang、Limbo、occamといった言語は、過去20年間で様々な時期に産業用途で利用されてきました。並行プログラミング機能を使用または提供する言語の一覧（網羅的ではありません）は以下のとおりです。

  • Ada —汎用、メッセージパッシングとモニターベースの同時実行をネイティブサポート
  • Alef —ベル研究所の Plan 9の初期バージョンにおけるシステムプログラミング用の、スレッドとメッセージパッシングを備えた並行処理
  • Alice —Standard MLの拡張で、futuresによる並行性のサポートを追加
  • Ateji PX —π計算からヒントを得た並列プリミティブを備えたJavaの拡張
  • Axum —ドメイン固有、並行、アクターモデルとCのような構文を使用した.NET共通言語ランタイムに基づく
  • BMDFM —バイナリモジュラーデータフローマシン
  • C++ —スレッドとコルーチンのサポートライブラリ[13] [14]
  • Cω (C オメガ) - 研究用、C# を拡張、非同期通信を使用
  • C# — lock、yieldを使用した並行コンピューティングをサポートし、バージョン5.0以降ではasyncおよびawaitキーワードも導入されました。
  • Clojure —Javaプラットフォーム上のLispの現代的な関数型プログラミング方言
  • Concurrent Clean —Haskellに似た関数型プログラミング
  • 並行コレクション（CnC）—データと制御のフローを明示的に定義することで、メモリモデルに依存しない暗黙的な並列性を実現します。
  • Concurrent Haskell —共有メモリ上で並行プロセスを操作する遅延型の純粋関数型言語
  • 並行ML —標準MLの並行拡張
  • 並行パスカル—Per Brinch Hansen著
  • カレー
  • D —並行プログラミング（アクターモデル）を明示的にサポートするマルチパラダイム システムプログラミング言語
  • E —デッドロックを防ぐためにPromiseを使用する
  • ECMAScript —非同期操作にPromiseを使用する
  • エッフェル—契約による設計の概念に基づくSCOOPメカニズムを通じて
  • Elixir — Erlang VM 上で実行される動的かつ関数型のメタプログラミング対応言語。
  • Erlang —共有メモリなしで同期または非同期のメッセージパッシングを使用する
  • FAUST —リアルタイム機能、信号処理用。コンパイラはOpenMPまたは特定のワークスティーリングスケジューラを介して自動並列化を提供します。
  • Fortran —共配列と同時実行はFortran 2008標準の一部です
  • Go —CSPに基づく並行プログラミングモデルを使用したシステムプログラミング用
  • Haskell —並行・並列関数型プログラミング言語[15]
  • ヒューム- 機能的、並行的、同期チャネルパターンとメッセージパッシングによってオートマトンプロセスが記述される、制限された空間と時間の環境向け
  • Io —アクターベースの並行性
  • ヤヌス-論理変数、バッグチャネルに対する明確な質問者と発言者を特徴とする。純粋に宣言的である。
  • Java —スレッドクラスまたはRunnableインターフェース
  • Julia —「並行プログラミングの基本要素：タスク、async-wait、チャネル」[16]
  • JavaScript — Web ワーカー、ブラウザー環境、Promise、およびコールバック経由。
  • JoCaml —並行および分散チャネルベースのOCamlの拡張で、プロセスの結合計算を実装します。
  • Join Java —Java言語に基づく並行処理
  • Joule —データフローベース、メッセージパッシングで通信
  • Joyce —並行、教育、Concurrent Pascal上にPer Brinch HansenのCSPの機能を搭載して構築
  • LabVIEW —グラフィカル、データフロー、関数はグラフ内のノード、データはノード間のワイヤ、オブジェクト指向言語を含む
  • Limbo — Alefの親戚、 Inferno (オペレーティングシステム)のシステムプログラミング用
  • Locomotive BASIC —BASICのAmstrad版には、並行サブルーチン用のEVERYコマンドとAFTERコマンドが含まれています。
  • MultiLisp —並列処理をサポートするために拡張されたSchemeバリアント
  • Modula-2 —システムプログラミング用。N. Wirth による、コルーチンをネイティブにサポートした Pascal の後継。
  • Modula-3 —スレッド、ミューテックス、条件変数を幅広くサポートするAlgolファミリーの最新メンバー
  • Newsqueak — チャネルを第一級の価値として扱うリサーチ向け。Alefの前身。
  • オッカム—通信順次プロセス（CSP） の影響を強く受けている
  • ooRexx —通信と同期のためのオブジェクトベースのメッセージ交換
  • Orc —クリーネ代数に基づく、高度に並行、非決定性
  • Oz-Mozart —マルチパラダイム、共有状態とメッセージパッシングの並行性、および未来をサポート
  • ParaSail —オブジェクト指向、並列、ポインタや競合状態がない
  • PHP —Goからヒントを得たメッセージパッシングを実装した並列拡張によるマルチスレッドサポート[17]
  • Pict —本質的にはミルナーのπ計算の実行可能な実装
  • Python — スレッドベースの並列処理とプロセスベースの並列処理を使用[18]
  • Rakuはデフォルトでスレッド、プロミス、チャネルのクラスを含んでいます[19]
  • Reia —共有なしオブジェクト間で非同期メッセージパッシングを使用する
  • Red/System —Rebolに基づくシステムプログラミング用
  • Rust —システムプログラミング用。移動セマンティクスによるメッセージパッシング、共有不変メモリ、共有可変メモリを使用。[20]
  • Scala — 一般的なプログラミングパターンを簡潔かつエレガントで型安全に表現できるように設計された汎用言語
  • SequenceL —汎用機能。主な設計目標は、プログラミングの容易さ、コードの明瞭性と可読性、マルチコアハードウェアでのパフォーマンスのための自動並列化、競合状態がないことが証明されていることです。
  • SR —研究用
  • SuperPascal —教育用の並行処理ライブラリ。Per Brinch HansenによるConcurrent PascalとJoyce をベースに構築。
  • Swift —構造化された方法で非同期および並列コードを記述するための組み込みサポート[21]
  • ユニコン—研究用
  • TNSDL —通信交換を開発するためのもので、非同期メッセージパッシングを使用します。
  • VHSICハードウェア記述言語（VHDL）—IEEE STD-1076
  • XC — XMOSが開発した C 言語の並行性拡張サブセット。通信する順次プロセスと、プログラム可能な I/O の組み込み構造に基づいています。

他の多くの言語では、上記のリストとほぼ同等のレベルで、ライブラリの形で並行性のサポートを提供しています。

参照

注記

  1. ^ これは、パイプラインやベクトル化された命令といったプロセッサコア内部の並列処理を考慮に入れていない。1コア1プロセッサのマシンは、コプロセッサなどを使用することである程度並列処理が可能であるかもしれないが、プロセッサ単体では並列処理は不可能である。

参考文献

  1. ^ オペレーティングシステムコンセプト第9版、Abraham Silberschatz著、「第4章 スレッド」
  2. ^ ハンセン、パー・ブリンチ編。 （2002年）。同時プログラミングの起源。土井：10.1007/978-1-4757-3472-0。ISBN 978-1-4419-2986-0. S2CID  44909506。
  3. ^ ab Pike, Rob (2012-01-11). 「並行性は並列性ではない」Wazaカンファレンス、2012年1月11日。http://talks.golang.org/2012/waza.slide (スライド) および http://vimeo.com/49718712 (ビデオ) より取得。
  4. ^ 「並列処理と並行処理」Haskell Wiki。
  5. ^ Schneider, Fred B. (1997-05-06).並行プログラミングについて. Springer. ISBN 9780387949420。
  6. ^ ab ベン・アリ、モルデカイ (2006). 『並行・分散プログラミングの原則（第2版）』アディソン・ウェズレー. ISBN 978-0-321-31283-9。
  7. ^ パターソン＆ヘネシー 2013、503ページ。
  8. ^ パドヴァ、デイヴィッド (2011).並列コンピューティングの百科事典。 Springer New York、ニューヨーク州 (2011 年 9 月 8 日発行)。ページ 819–825。ISBN​​ 978-0-387-09765-7。
  9. ^ 「非同期I/O」、Wikipedia、2024年12月20日、 2024年12月27日閲覧
  10. ^ ランポート、レスリー（1979年9月1日）「マルチプロセスプログラムを正しく実行するマルチプロセッサコンピュータの作り方」IEEE Transactions on Computers . C-28 (9): 690– 691. doi :10.1109/TC.1979.1675439. S2CID  5679366.
  11. ^ PODC Influential Paper Award: 2002. ACM Symposium on Principles of Distributed Computing (Report) . 2009年8月24日閲覧。
  12. ^ Armstrong, Joe (2003). 「ソフトウェアエラー発生時における信頼性の高い分散システムの構築」(PDF) . 2016年4月15日時点のオリジナル(PDF)からアーカイブ。
  13. ^ 「標準ライブラリヘッダー <thread> (C++11)」. en.cppreference.com . 2024年10月3日閲覧。
  14. ^ 「標準ライブラリヘッダー <coroutine> (C++20)」. en.cppreference.com . 2024年10月3日閲覧。
  15. ^ Marlow, Simon (2013) Haskellによる並列・並行プログラミング：マルチコア・マルチスレッドプログラミングのテクニックISBN 9781449335946
  16. ^ 「Juliaでの並行プログラミングと並列プログラミング — JuliaCon India 2015 — HasGeek Talkfunnel」juliacon.talkfunnel.com。2016年10月18日時点のオリジナルよりアーカイブ。
  17. ^ 「PHP: parallel - マニュアル」www.php.net . 2024年10月3日閲覧。
  18. ^ ドキュメント » Python 標準ライブラリ » 並行実行
  19. ^ 「並行性」. docs.perl6.org . 2017年12月24日閲覧。
  20. ^ Blum, Ben (2012). 「型安全な共有可変状態」 . 2012年11月14日閲覧。
  21. ^ “Concurrency”. 2022年. 2022年12月15日閲覧。

出典

  • パターソン、デイビッド・A、ヘネシー、ジョン・L (2013) 『コンピュータの構成と設計：ハードウェア／ソフトウェア・インターフェース』 モルガン・カウフマン著『コンピュータ・アーキテクチャと設計シリーズ（第5版）』 モルガン・カウフマンISBN 978-0-12407886-4。

さらに読む

  • Dijkstra, EW (1965). 「並行プログラミング制御における問題の解決」Communications of the ACM . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID  19357737.
  • ハーリヒー、モーリス (2008) [2008]. 『マルチプロセッサプログラミングの技法』 モーガン・カウフマン. ISBN 978-0123705914。
  • ダウニー、アレン・B. (2005) [2005]. セマフォの小さな本(PDF) . グリーンティー・プレス. ISBN 978-1-4414-1868-5. 2016年3月4日にオリジナル（PDF）からアーカイブ。 2009年11月21日閲覧。
  • フィルマン、ロバート・E.、ダニエル・P・フリードマン (1984). 『コーディネイテッド・コンピューティング：分散ソフトウェアのためのツールとテクニック』 ニューヨーク：マグロウヒル. p. 370. ISBN 978-0-07-022439-1。
  • Leppäjärvi, Jouni (2008). 同期プリミティブの普遍性に関する実用的かつ歴史的視点からの概説(PDF) . オウル大学. オリジナル(PDF)から2017年8月30日にアーカイブ. 2012年9月13日閲覧.
  • タウベンフェルド、ガディ (2006). 同期アルゴリズムと並行プログラミング. ピアソン/プレンティス・ホール. p. 433. ISBN 978-0-13-197259-9。
  • ウィキメディア・コモンズにおける並行プログラミングに関連するメディア
  • コンカレントシステム仮想ライブラリ