1 歴史と背景
並列計算の歴史は、計算機科学の黎明期にさかのぼる。初期の計算機は単一プロセッサが主流であったが、問題の大規模化とともに複数の処理装置を連携させる需要が生じた。1960年代から1970年代にかけて、ベクトルプロセッサやアレイプロセッサなどの並列アーキテクチャが研究され、後に商用システムへと発展した。1980年代には超並列計算機が登場し、1990年代以降のマルチコア技術の普及を経て、現代のクラウドコンピューティングに至るまで、並列計算は情報技術の中核を担っている。
1.1 初期の並列計算機
初期の並列計算機は、1970年代に登場したILLIAC IVやCDC STAR-100などのベクトルプロセッサに代表される。これらのシステムは、多数の演算ユニットを配列し、一つの命令で複数のデータを同時に処理するSIMD（Single Instruction, Multiple Data）方式を採用した。1980年代には、コネクションマシン（Connection Machine）のように、数千個のプロセッサを結合した超並列システムが研究され、並列アルゴリズムの基盤が築かれた。
1.2 マルチコア時代の到来
2000年代初頭、半導体プロセスの微細化によるクロック周波数の向上が物理的限界に達したため、プロセッサメーカーは一つのチップに複数のコアを搭載するマルチコアアーキテクチャへと転換した。これにより、汎用CPUにおいても並列実行が一般的となり、デスクトップからサーバーに至るまで、並列計算の基盤が広く普及した。
1.3 クラウドと大規模並列処理の台頭
2010年代以降、クラウドコンピューティングの普及により、数千台から数万台のサーバーを同時利用する大規模並列処理が実現した。GoogleのMapReduceやApache Hadoopなどのフレームワークは、分散環境でのデータ処理を標準化し、Amazon Web ServicesやMicrosoft Azureなどのプラットフォームが並列計算リソースをオンデマンドで提供するようになった。
2 基本概念
並列計算の基本概念には、問題を分割して並行処理するための原理と、それを抽象化するモデルが含まれる。これらは、効率的な並列プログラムの設計と性能評価の基盤となる。
2.1 並列性の種類
並列性は、データ、タスク、パイプラインの三つの主要な種類に分類される。それぞれ異なる問題構造に適しており、適切な並列化戦略の選択が重要となる。
2.1.1 データ並列
データ並列は、同一の処理を大規模なデータセットの各要素に同時に適用する方式である。典型的には、配列の各要素に対する演算や、画像の各ピクセルに対するフィルタリングなどが該当する。GPUコンピューティングの根幹をなす。
2.1.2 タスク並列
タスク並列は、互いに独立した異なる処理を複数のプロセッサで同時に実行する方式である。各タスクは異なる入力や異なる手順を持つことができ、例えば並列処理における異なるサブルーチンの同時実行などが該当する。
2.1.3 パイプラインモデル
パイプラインモデルは、一連の処理ステージを分割し、各ステージを異なるプロセッサが担当することで、全体のスループットを向上させる方式である。データがパイプラインを流れる間に、各ステージが並行して動作する。工場の組立ラインに類似する。
2.2 並列計算モデル
並列計算モデルは、並列システムの抽象化を提供し、アルゴリズムの設計と解析を容易にする。代表的なモデルとしてPRAM、BSP、LogPがある。
2.2.1 PRAMモデル
PRAM（Parallel Random Access Machine）モデルは、すべてのプロセッサが共通の共有メモリにアクセスできる理想的な並列計算モデルである。同期が無視され、メモリアクセス時間は均一と仮定する。理論的な並列アルゴリズムの解析に広く用いられるが、実際のハードウェア制約を反映していない。
2.2.2 BSPモデル
BSP（Bulk Synchronous Parallel）モデルは、プロセッサが局所計算、通信、同期のサイクルを繰り返す実用的なモデルである。各スーパーステップにおいて、プロセッサは個別に計算を行い、その後通信を実行し、バリア同期により次のステップへ移行する。通信コストを明示的に扱う点が特徴である。
2.2.3 LogPモデル
LogPモデルは、分散メモリシステムにおける通信コストを、レイテンシ（L）、オーバーヘッド（o）、帯域幅（g）、プロセッサ数（P）の四つのパラメータで表現する。通信の詳細な振る舞いを捉え、現実的な並列アルゴリズムの性能評価に役立つ。
3 ハードウェアアーキテクチャ
並列計算のハードウェアアーキテクチャは、メモリの共有方法とプロセッサの接続方式により分類される。主に共有メモリシステムと分散メモリシステムの二つに大別される。
3.1 共有メモリシステム
共有メモリシステムでは、複数のプロセッサが同一のメモリ空間を直接操作できる。これにより、データ共有が容易である一方、メモリアクセスの競合を管理する必要がある。
3.1.1 SMP（対称型マルチプロセッサ）
SMPは、すべてのプロセッサが対等な立場で共有バスを介してメモリにアクセスするアーキテクチャである。各プロセッサは同一のメモリアクセス特性を持ち、オペレーティングシステムがプロセッサ間の負荷を均等に割り振る。
3.1.1.1 UMA（均一メモリアクセス）
UMAは、SMPにおいてすべてのプロセッサがメモリ全体に対して均一なアクセス時間を持つ構成である。共有バスやクロスバースイッチを用いるため、プロセッサ数が増えると帯域幅がボトルネックとなる。小規模なマルチコアシステムで一般的である。
3.1.1.2 NUMA（不均一メモリアクセス）
NUMAは、メモリを各プロセッサに物理的に分散配置し、自ノードのメモリへのアクセスが他ノードよりも高速となる構成である。プロセッサ数が多くてもスケーラビリティを保ちやすいが、データの局所性を考慮したプログラミングが必要となる。
3.2 分散メモリシステム
分散メモリシステムでは、各プロセッサが独立したメモリを持ち、プロセッサ間の通信は明示的なメッセージパッシングにより行われる。大規模クラスタやスーパーコンピュータの基盤である。
3.2.1 メッセージパッシング方式
メッセージパッシング方式は、各プロセッサが排他的にローカルメモリを持ち、データ交換のために明示的な送信・受信操作をプログラムする。MPI（Message Passing Interface）が標準的なインターフェースとして広く利用される。
3.2.2 ハイブリッドシステム
ハイブリッドシステムは、共有メモリと分散メモリの両方の特性を組み合わせたアーキテクチャである。例えば、各ノード内では共有メモリ（SMP/NUMA）を利用し、ノード間ではメッセージパッシングを利用する。現代のスーパーコンピュータの多くがこの構成を採用する。
4 プログラミングモデルとツール
並列計算を実装するためのプログラミングモデルとツールは、ハードウェアアーキテクチャに応じて多様に存在する。これらは、開発者が効率的に並列処理を記述できるよう抽象化を提供する。
4.1 共有メモリ向け
共有メモリ向けのプログラミングモデルは、スレッドを用いてプロセッサ間でメモリを共有し、データ共有のオーバーヘッドを低減する。
4.1.1 OpenMP
OpenMPは、C/C++およびFortranに対応した共有メモリ並列プログラミングの標準APIである。プラグマディレクティブを用いてループやセクションを容易に並列化でき、自動スレッド管理を提供する。マルチコアCPUでの利用に適する。
4.1.2 Pthreads
Pthreads（POSIX threads）は、UNIX系OSで広く利用されるスレッドライブラリである。プログラマが明示的にスレッドの生成、同期、排他制御を管理する必要があるため、OpenMPよりも細かな制御が可能だが、複雑性は高い。
4.2 分散メモリ向け
分散メモリ向けのモデルは、プロセス間通信を明示的に記述し、大規模なクラスタ環境でのスケーラビリティを実現する。
4.2.1 MPI（Message Passing Interface）
MPIは、分散メモリシステムにおける事実上の標準であるメッセージパッシングインターフェースである。ポイントツーポイント通信と集団通信（ブロードキャスト、リダクションなど）の両方をサポートし、高効率な大規模並列アプリケーションの開発に不可欠である。
4.2.2 MapReduce
MapReduceは、Googleが開発した分散処理フレームワークで、MapフェーズとReduceフェーズからなる。データの分割、分散、並列処理、集約を自動化し、大規模データセットの処理を簡素化する。Apache Hadoopがそのオープンソース実装として広く使用される。
4.3 GPUコンピューティング
GPUコンピューティングは、多数のコアを持つグラフィックスプロセッサを汎用計算に利用する手法である。データ並列性の高い処理で高い性能を発揮する。
4.3.1 CUDA
CUDA（Compute Unified Device Architecture）は、NVIDIAが提供するGPUコンピューティングの並列プログラミングプラットフォームである。C/C++、Fortran、Pythonなどの言語からGPUカーネルを記述でき、ホストCPUとデバイスGPUのメモリ管理やスレッド制御を統合的に扱う。
4.3.2 OpenCL
OpenCL（Open Computing Language）は、異なるベンダーのGPU、CPU、FPGAなど、多様なアクセラレータをサポートするオープン標準の並列プログラミングフレームワークである。CUDAに比べ移植性が高いが、性能チューニングの複雑性は増す。
5 応用分野
並列計算は、科学技術計算から人工知能、ビッグデータ分析まで、幅広い分野で応用される。その高い計算能力は、現代のさまざまな課題解決に貢献している。
5.1 科学技術計算
科学技術計算において、並列計算は大規模な数値シミュレーションを可能とする。複雑な物理現象のモデル化や、膨大な計算資源を要する問題の解決に不可欠である。
5.1.1 気象予測
気象予測では、大気や海洋の状態を格子点で離散化し、時間発展をシミュレートする。全球規模の予測モデルには数万コアに及ぶ並列計算が用いられ、コンピュータの性能向上が予測精度の改善に直結する。
5.1.2 分子動力学シミュレーション
分子動力学シミュレーションは、原子や分子の相互作用を時間積分することで、材料や生体分子の振る舞いを解析する。多数の粒子の計算は並列化に適しており、大規模な系（数百万粒子規模）のシミュレーションが可能となっている。
5.2 人工知能と機械学習
人工知能と機械学習、特に深層学習においては、大規模なモデルの訓練と推論に莫大な計算資源が必要であり、並列計算が中核的な役割を果たす。
5.2.1 深層学習の分散訓練
深層学習モデルの訓練では、データ並列（複数のGPUで異なるミニバッチを処理）やモデル並列（モデルを複数のGPUに分割）が用いられる。通信効率を高めるための同期・非同期手法が研究され、大規模言語モデルの訓練などで実用化されている。
5.2.2 画像・音声認識
画像認識や音声認識では、畳み込みニューラルネットワーク（CNN）やTransformerなど、並列計算に適したモデルが採用される。特にGPUを用いた並列処理により、リアルタイムの推論が実現されている。
5.3 ビッグデータ分析
ビッグデータ分析では、ペタバイト級のデータを高速に処理するために、分散並列処理技術が不可欠である。データの分割と並行処理により、スケーラブルな分析基盤が構築される。
5.3.1 分散データベース処理
分散データベース処理では、データを複数のノードに分散して格納し、クエリを並列に処理することで応答時間を短縮する。Apache SparkやGoogle BigQueryなどのシステムが、SQLクエリを自動的に並列化する。
5.3.2 リアルタイムストリーム処理
リアルタイムストリーム処理は、センサーデータやログなどの連続的なデータストリームを、遅延を最小限に抑えて処理する技術である。Apache KafkaやApache Flinkなどの並列ストリーム処理エンジンが、イベント駆動型のアプリケーションで活用される。
6 性能評価と指標
並列計算の性能を評価するためには、スピードアップ、効率、そしてスケーラビリティを定量化する指標が用いられる。これらの指標は、システムの限界を理解し、最適なアルゴリズムを選択するために重要である。
6.1 スピードアップと効率
スピードアップは、逐次実行時間と並列実行時間の比で定義される。理想的なスピードアップはプロセッサ数に等しい線形スケーリングとなるが、実際には通信オーバーヘッドや負荷不均衡により低下する。効率は、スピードアップをプロセッサ数で割った値であり、資源の利用効率を示す。
6.2 アムダールの法則
アムダールの法則は、プログラムの逐次部分が並列性能の上限を規定することを示す。ある処理において、並列化可能な割合を \( p \) としたとき、最大スピードアップは \( 1/((1-p) + p/N) \)（\( N \) はプロセッサ数）で与えられる。逐次部分がわずかでも、プロセッサ数を増やしてもスピードアップは頭打ちとなる。
6.3 グスタフソンの法則
グスタフソンの法則は、アムダールの法則が固定問題サイズを前提としているのに対し、問題サイズをプロセッサ数に応じて拡大する場合のスケーラビリティを示す。並列部分の実行時間を一定に保ちながら問題規模を大きくできる場合、スピードアップはプロセッサ数に比例して増加することが可能である。大規模問題の解決において、より楽観的な見方を提供する。
7 課題と未来
並列計算は進化を続ける一方で、スケーラビリティ、プログラム複雑性、そして新たな計算パラダイムとの相互作用など、解決すべき課題も存在する。
7.1 スケーラビリティの限界
プロセッサ数が増大するにつれ、通信オーバーヘッドやメモリアクセスの競合が性能の頭打ちを引き起こす。また、電力消費や発熱の問題も深刻化しており、エネルギー効率の高いアーキテクチャが求められる。将来的には、特定の用途に特化したアクセラレータや、3次元積層などの新しい実装技術がスケーラビリティの限界を押し広げる可能性がある。
7.2 プログラムの複雑性とデバッグ
並列プログラムは、逐次プログラムに比べて設計、実装、デバッグが格段に難しい。競合状態、デッドロック、負荷不均衡などのバグは再現が困難であり、検出ツールや形式的検証技術の進展が必要とされる。また、異種混合システム（CPU+GPU+FPGAなど）の増加に伴い、プログラムの移植性と最適化の両立が課題である。
7.3 量子並列計算とのインタラクション
量子コンピュータは、量子ビットの重ね合わせや量子もつれを利用した固有の並列性を持つ。古典的な並列計算と量子計算は、ハイブリッドアーキテクチャとして統合される可能性が議論されている。古典並列計算機で量子アルゴリズムのシミュレーションを行ったり、量子処理ユニットを古典的な並列システムのアクセラレータとして利用する研究が進められている。しかし、量子誤り訂正やスケーラビリティの実現には依然として多くの課題が残る。