並列計算
並列プログラミング言語と並列コンピュータには一貫性モデル(メモリモデルとも呼ぶ)が必須である。一貫性モデルとは、メモリ上の操作に関する規則を定義したものであり、どのように結果が生成されるかを定義したものである。
最初に定義された一貫性モデルは、レスリー・ランポートの逐次一貫性モデルである。逐次一貫性とは、並列プログラムを並列実行したときの結果と、それと等価な逐次プログラムの結果が同じという特性である。プログラムが逐次一貫性を持つとは、「...任意の実行の結果が、それを全プロセッサが逐次的順序で実行された場合と同じであり、その順序がプログラム内で指定された順序と同じである」ことを意味する。
ソフトウェアトランザクショナルメモリは、一貫性モデルの典型例である。ソフトウェアトランザクショナルメモリは、データベース理論から不可分操作の概念を借り、それをメモリアクセスに適用したものである。
数学的にこれらのモデルを表現する方法はいくつか存在する。プロセス計算は並行性を扱う数学の一分野である。プロセス計算はさらにアンビエント計算(英語版)、calculus of communicating systems、Communicating Sequential Processesなどに分類される。ペトリネットは一貫性モデルの定式化を試みた初期の例である。それに基づいて後にデータフロー理論が構築された。そして、データフローの考え方を物理的に実装したデータフロー・アーキテクチャが開発された。
複数の変数のロックには複数のロックが必要であり、それによってデッドロックが発生する可能性が生じる。不可分なロックは複数の変数を一度にロックするものである。その場合、対象変数群の一部がロックできなければ、全体のロックができないと見なされる。個別にロックされる2つの変数をロックする必要のあるスレッドが2つ存在したとして、一方のスレッドが一方の変数だけをロックし、もう一方のスレッドがもう一方の変数だけをロックするという状況が発生しうる。このような場合、双方のスレッドはロックできていない変数をロックしようとして待ち続け、結果としてデッドロックとなる。
多くの並列プログラムでは、サブタスク群が同期して動作することを要求する。この用途で使われるものとしてバリアがある。バリアは一般にソフトウェアロックを使って実装される。その種のアルゴリズムとしてLock-freeとWait-freeアルゴリズムがある。これはロックもバリアも使わずに全てを実現するものである。ただし、実装は難しく、データ構造の設計を慎重に行う必要がある。
並列化によって必ず性能が向上するとは限らない。一般にタスクを細分化してスレッド数を増やしていくと、スレッド間の通信に費やす時間が増大していく。すると、ある時点で通信オーバーヘッドが処理時間を支配するようになり、それ以上の並列化(スレッド数の増加)は単に処理時間の遅延を招くことになる。この現象を並列スローダウンと呼ぶ。