並行コンピューティング

並行コンピューティングとは、複数の計算を順次実行するのではなく、重複する時間帯に同時に実行するコンピューティングの一形態である。つまり、ある計算が完了する前に次の計算が開始されるという従来の方式とは異なる。

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

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

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

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

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

並行システムにおけるタスクの実行タイミングはスケジューリングに依存し、タスクは必ずしも並行して実行されるとは限りません。例えば、2つのタスクT1とT2があるとします。

• T1はT2より先に実行され完了することもあれば、その逆もあり得る（逐次実行と逐次実行の両方）。
• T1とT2は交互に実行される（直列実行と並列実行の両方が可能）。
• T1とT2は、同じ瞬間に同時に実行される可能性がある（並列および同時実行）。

「シーケンシャル」という言葉は、「同時実行」と「並列実行」の両方の反意語として使われます。これらが明確に区別される場合、同時実行/シーケンシャル、並列実行/シリアルが反対のペアとして使われます。^{[ 7 ]}タスクがインターリーブなしで（逐次的に、並列性なし、前のタスクが終了するまでタスクが開始されない）一度に 1 つずつ実行されるスケジュールは、シリアル スケジュールと呼ばれます。シリアルにスケジュールできるタスクのセットはシリアル化可能であり、これにより同時実行制御が簡素化されます。

bool withdraw ( int withdrawal ){if (残高>=引き出し額){残高-=引き出し;return true ;}falseを返します。}

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

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

並行システムの挙動を記述するために、ランポートのTLA+のような論理体系や、トレースやアクターイベント図のような数学モデルも開発されてきた。

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

並行プログラムを実装するには、さまざまな方法が利用できます。例えば、各計算処理をオペレーティングシステムのプロセスとして実装する方法や、単一のオペレーティングシステムのプロセス内で計算処理をスレッドの集合として実装する方法などがあります。

Concurrent computing developed out of earlier work on railroads and telegraphy, from the 19th and early 20th century, and some terms date to this period, such as semaphores. These arose to address the question of how to handle multiple trains on the same railroad system (avoiding collisions and maximizing efficiency) and how to handle multiple transmissions over a given set of wires (improving efficiency), such as via time-division multiplexing (1870s).

The academic study of concurrent algorithms started in the 1960s, with Dijkstra (1965) credited with being the first paper in this field, identifying and solving mutual exclusion.^[12]

Concurrency is pervasive in computing, occurring from low-level hardware on a single chip to worldwide networks. Examples follow.

At the programming language level:

• Channel
• Coroutine
• Futures and promises

At the operating system level:

• Computer multitasking, including both cooperative multitasking and preemptive multitasking
  • Time-sharing, which replaced sequential batch processing of jobs with concurrent use of a system
• Process
• Thread

At the network level, networked systems are generally concurrent by their nature, as they consist of separate devices.

Concurrent programming languages are programming languages that use language constructs for concurrency. These constructs may involve multi-threading, support for distributed computing, message passing, shared resources (including shared memory) or futures and promises. Such languages are sometimes described as concurrency-oriented languages or concurrency-oriented programming languages (COPL).^[13]

Today, the most commonly used programming languages that have specific constructs for concurrency are Java and C#. Both of these languages fundamentally use a shared-memory concurrency model, with locking provided by monitors (although message-passing models can and have been implemented on top of the underlying shared-memory model). Of the languages that use a message-passing concurrency model, Erlang was probably the most widely used in industry as of 2010.

多くの並行プログラミング言語は、実運用向けというよりは研究用言語（例： Pict ）として開発されてきました。しかし、 Erlang、Limbo、Occamといった言語は、過去20年間で様々な時期に産業界で利用されてきました。並行プログラミング機能を利用する、あるいは提供する言語の例を以下に挙げます（ただし、これらに限定されません）。

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

他の多くのプログラミング言語も、ライブラリの形で並行処理をサポートしており、そのレベルは上記のリストとほぼ同等である。

• 非同期I/O
• チュスペース
• フローベースプログラミング
• Java ConcurrentMap
• プトレマイオス・プロジェクト
• 競合状態 § コンピューティング
• 構造化された並行処理
• トランザクション処理

• 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-52016年3月4日にオリジナル（PDF）からアーカイブされました。2009年11月21日に取得。
• フィルマン、ロバート・E.、ダニエル・P・フリードマン（1984）。『協調コンピューティング：分散ソフトウェアのためのツールとテクニック』ニューヨーク：マグロウヒル。370ページ。ISBN  978-0-07-022439-1。
• Leppäjärvi, Jouni (2008).同期プリミティブの普遍性に関する実用的かつ歴史的視点からの調査(PDF) . オウル大学。2017年8月30日にオリジナル(PDF)からアーカイブ済み。 2012年9月13日取得。
• タウベンフェルド、ガディ（2006）。同期アルゴリズムと並行プログラミング。ピアソン／プレンティスホール。p.  433。ISBN 978-0-13-197259-9。

• ウィキメディア・コモンズにある同時プログラミング関連のメディア
• 並行システム仮想ライブラリ