並列計算
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2018年10月) |
並列計算（へいれつけいさん、英語: parallel computing）は、コンピュータにおいて特定の処理をいくつかの独立した小さな処理に細分化し、複数の処理装置（プロセッサ）上でそれぞれの処理を同時に実行させることである[1]。並列コンピューティングや並列処理ともいう。
概要
大きな問題を解いたり、大量のデータを処理したりする過程は、より小さなサブタスクやサブデータグループの処理に分割できることが多い、という事実を利用して単位時間あたりの処理効率（スループット）の向上を図る手法である。
並列処理（並列計算）はスーパーコンピュータでは以前から採られている手法である。スーパーコンピュータの高い性能は、プロセッサ数やノード数がパーソナルコンピュータに比べて極めて多く、並列処理性能が高いことで実現している。
並列計算のために設計されたコンピュータは並列コンピュータという。並列コンピュータは当初スーパーコンピュータなどの高価で大規模なシステムのみに見られる設計だったが、パーソナルコンピュータや携帯機器でもCPUをマルチコア化し並列処理をさせることが当たり前になってきた。CPUのクロック周波数を上げることで処理性能向上させることには限界や問題が見えてきたからこの手法が採用されるようになった。
また並列処理に特化したコプロセッサであるGPUも、個人が（比較的気軽に）購入できる価格帯で販売されるようになってきており、PCに後付で搭載する形での使用も広まっている。GPUは当初は主に、コンピュータゲームの3DCGレンダリングなどの画像処理に使われていたので「GPU」と呼ばれることになったが、実際には並列処理全般に使うことができるものであり、こうした使用法をGPGPUといい、今ではディープラーニングや暗号資産のマイニングなど、現実的な時間内に処理しようとすると並列処理が必要となるさまざまな用途で使われるようになっている。
並列処理の歴史を遡ると、1958年にIBMの研究者ジョン・コックと Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている[2]。1962年には、バロース社が4プロセッサのコンピュータ D825 を発表した。→#歴史
関連する概念に並行計算（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクを、プロセスやスレッドなどをもちいて単一または複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。並列計算は物理的に計算資源が複数なければ効果が得られないが、並行計算はたとえ計算資源が1つだけだったとしても、マルチタスクに対応したオペレーティングシステムがプロセッサ時間をスライスして各タスクの処理に割り当てることで効果が得られる。
特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。
背景
従来、コンピュータソフトウェアは逐次的に計算されるものとして書かれてきた。問題を解くためにアルゴリズムが構築され、それによって逐次的に実行される命令列が生成される。その命令列は、コンピュータのCPU上で実行される。命令は一度に1つずつ実行される[3]。
一方並列計算では、複数の計算ノードが同時並列的に動作して問題を解く。問題は独立した部分に分割され、各計算ノードがアルゴリズムの一部を同時並列的に実行する。計算ノードの実体は様々であり、マルチプロセッサ型のコンピュータの各CPUだったり、ネットワーク上のコンピュータだったり、専用ハードウェアだったり、それらの組合せだったりする[3]。
1980年代から2004年まで、コンピュータの性能向上の主たる要因はクロック周波数の向上にあった。プログラムの実行時間は、命令数と1命令あたりの平均実行時間をかけたものに比例する。他の要因が全く変化しないと仮定すると、クロック周波数の向上によって1命令あたりの平均実行時間が減少する[4]。
一方で、マイクロプロセッサの消費電力は グスタフソンの法則は、アムダールの法則とも密接に関連する計算機工学における法則である。グスタフソンの法則は以下の式で表される。
並列プログラミング言語と並列コンピュータには一貫性モデル（メモリモデルとも呼ぶ）が必須である。一貫性モデルとは、メモリ上の操作に関する規則を定義したものであり、どのように結果が生成されるかを定義したものである。
最初に定義された一貫性モデルは、レスリー・ランポートの逐次一貫性モデルである。逐次一貫性とは、並列プログラムを並列実行したときの結果と、それと等価な逐次プログラムの結果が同じという特性である。プログラムが逐次一貫性を持つとは、「…任意の実行の結果が、それを全プロセッサが逐次的順序で実行された場合と同じであり、その順序がプログラム内で指定された順序と同じである」ことを意味する[11]。
ソフトウェアトランザクショナルメモリは、一貫性モデルの典型例である。ソフトウェアトランザクショナルメモリは、データベース理論から不可分操作の概念を借り、それをメモリアクセスに適用したものである。
数学的にこれらのモデルを表現する方法はいくつか存在する。プロセス計算は並行性を扱う数学の一分野である。プロセス計算はさらにアンビエント計算、calculus of communicating systems、Communicating Sequential Processesなどに分類される。ペトリネットは一貫性モデルの定式化を試みた初期の例である。それに基づいて後にデータフロー理論が構築された。そして、データフローの考え方を物理的に実装したデータフロー・アーキテクチャが開発された。
マイケル・J・フリンは、並列（および逐次）コンピュータ/プログラムの分類であるフリンの分類を提案した。フリンは命令列が単一か複数かという点と、その命令列（群）が扱うデータが単一か複数かによって4種類に分類した。
SISD（単一命令・単一データ）は、完全に逐次的なプログラムと等価である。SIMD（単一命令・複数データ）は同じ操作を多数のデータに対して行う場合を意味する。これは信号処理などで一般的である。MISD（複数命令・単一データ）はあまり使われない分類だが、フォールトトレラントシステムの冗長構成を指すことがある。シストリックアレイのようなアーキテクチャがこれに相当するが、実際の応用例は少ない。MIMD（複数命令・複数データ）は、ほとんどの並列プログラムに対応する。
デイビッド・パターソンとジョン・ヘネシーの著書には「もちろん一部のマシンはこれらの混成であるが、単純で分かりやすく、とりあえずの近似としては最適であるが故にこの分類が今も使われている」とある[12]。
1970年代のマイクロプロセッサの開発以来、コンピュータの主なアーキテクチャ上の進化はワードサイズ（プロセッサが一度に処理できるビット幅）を倍々にしていくことで成されてきた[13]。ワードを大きくすることで、従来のワードサイズでは多数の命令を必要としていた大きな変数の処理が、より少ない命令数で実行可能となる。例えば、8ビットのプロセッサで2つの16ビットの整数を加算する場合を考える。まず、2つのデータの下位8ビットを通常の加算命令で加算し、その後上位8ビットをキャリー付き加算命令で加算することで、下位8ビットで発生したキャリーを考慮する。つまり、8ビットプロセッサでは1つの演算に2つの命令を必要とし、16ビットプロセッサならそれを1命令で実行できる。
マイクロプロセッサの歴史を見れば、8ビット、16ビット、32ビットとワードサイズは大きくなっていった。32ビットとなった段階で汎用コンピュータのワードサイズの大型化は約20年間止まり、32ビットが標準的とされる時代が続いた。そして近年になってx86-64アーキテクチャが登場し、64ビットプロセッサが一般化した。
コンピュータプログラムは、基本的にプロセッサが実行すべき命令の列である。この命令列はプログラムの結果に影響を与えない形で並べ替え可能であり、同時並列的に実行できる命令毎にグループ化することができる。これを命令レベルの並列性と呼ぶ。命令レベルの並列性によるアーキテクチャの改良は1980年代中ごろから1990年代中ごろに盛んに行われた[14]。
最近のプロセッサは多段命令パイプラインを備えている。パイプラインの各ステージは、命令に対して行うべき異なる処理に対応している。N段のパイプラインを持つプロセッサでは、N個の命令について同時にそれぞれ異なる段階の処理をしていることになる。典型的なパイプラインの例としてRISCプロセッサの5段のパイプラインがある（各段は命令フェッチ、命令デコード、実行、メモリアクセス、ライトバック）。Pentium 4 は35段のパイプラインを持つ[15]。
パイプライン化による命令レベルの並列性だけでなく、同時に複数の命令を処理できるプロセッサもある。これをスーパースケーラプロセッサという。命令はデータ従属性がない場合にのみ、同時に実行可能なものとしてグループ化できる。
アウト・オブ・オーダー実行と命令レベルの並列性を実装する技法としては、スコアボードやトマスロのアルゴリズム（スコアボードと似ているがレジスタ・リネーミングを利用）が一般的である。
データ並列性はプログラムのループが本質的に備えている並列性であり、ループの各周回が各ノードで並列に処理されるようデータを配布する部分が中心となる。並列化されるループは、大きなデータ構造の各要素について似たような処理を行うものである[16]。科学技術計算にはデータ並列性があることが多い。
ループ伝搬依存（loop-carried dependency）とは、ループにおいて以前の周回の結果に依存して新たな周回の計算が行われる性質をいう。ループ伝搬依存があると、ループの並列化はできない。例えば、以下のフィボナッチ数の一部を計算する擬似コードを考えてみよう。
このループでは、CUR が以前の CUR の値と PREV に依存しており、その値は周回ごとに再計算されるため、並列化できない。つまり、ある周回での計算は、それ以前の周回の計算結果に依存しているため、周回ごとに並列化することはできないのである。
問題が大きくなるほど、可能なデータ並列性も多くなる傾向がある[17]。
タスク並列性は、「同じまたは異なるデータ群に関する全く異なる計算は並列に実行可能である」という並列プログラムの特性である[16]。データ並列性がほぼ同じ計算を並列に実行するのとは対照的である。問題が大きくなっても、それに比例してタスク並列性が高くなることはない[17]。
並列コンピュータの主記憶は、共有メモリ型（全プロセッサが単一の物理アドレス空間を共有する）と分散メモリ型（各プロセッサがローカルな独自の物理アドレス空間を持つ）に分けられる[18]。分散メモリは、メモリが論理的に分散しているためにそのように呼ばれるが、実際には物理的にも分散していることが多い。分散共有メモリはこの2つの方式を組み合わせたものであり、各プロセッサはローカルなメモリとローカルでないメモリの両方にアクセスできる。この場合、ローカルなメモリへのアクセスはローカルでないメモリへのアクセスよりも一般に高速である。
全主記憶に同じレイテンシおよび帯域幅でアクセスできるコンピュータアーキテクチャを UMA (Uniform Memory Access) と呼ぶ。これは共有メモリシステム（メモリが物理的に分散していない場合）しか実現できない。それ以外のアーキテクチャはNUMA (Non-Uniform Memory Access) と呼ぶ。分散メモリシステムはNUMAである。
コンピュータにはキャッシュメモリが使われていることが多く、（物理的にも論理的にも）プロセッサの近くに高速かつ小容量のメモリを配置し、主記憶の内容のコピーを一時的に保持する。共有メモリ型の並列コンピュータでは、主記憶上の同じアドレスの内容のコピーが複数のキャッシュメモリ上に存在する可能性があり、その内容が食い違うとプログラムの実行に支障が発生する。そのような問題への対処としてキャッシュコヒーレンシシステムがあり、プロセッサが常に最新の内容を得られるようキャッシュの内容を制御する。よく使われる方式としては、バススヌーピングがある。大型かつ高性能のキャッシュコヒーレンシシステムの設計は、コンピュータアーキテクチャの中でも非常に難しい問題である。そのため、共有メモリ型のシステムは分散メモリ型ほどスケーラブルではない[18]。
プロセッサ同士またはプロセッサとメモリの通信のハードウェア実装方式は様々であり、マルチポート型の共有メモリ、クロスバースイッチ、共有バス、スター型、リング型、ツリー型、ハイパーキューブ型、ファット・ハイパーキューブ型（ハイパーキューブの頂点に複数のノードが接続される形態）、メッシュ型などの様々なネットワーク構成のインターコネクト・ネットワークがある。
インターコネクト・ネットワークを使った並列コンピュータは、直接接続されていないノード間でメッセージパッシングできるように何らかのルーティング機構が必要となる。大規模なマルチプロセッサ機では、プロセッサ間の通信媒体は複数の階層を構成することもある。
並列コンピュータは、ハードウェアのどのレベルで並列性をサポートするかによって大まかに分類できる。これは、基本計算ノード間の距離とも大まかに対応している。
なお、以下の分類は相互排他的ではない。例えば、対称型マルチプロセッサを複数束ねたクラスターというのもよくある構成である。
マルチコアプロセッサは、複数の実行ユニット（コア）を持つプロセッサである。マルチコアとスーパースケーラは異なる概念である。どちらも複数の命令を同時並列的に実行可能だが、スーパースケーラが1つの命令ストリーム（スレッド）から複数の命令を取り出して実行するのに対して、マルチコアでは複数の命令ストリームから複数の命令を取り出して実行する。マルチコアの個々のコアがスーパースケーラになっていることもある。
初期の擬似マルチコア方式として同時マルチスレッディングがあった。この場合のプロセッサにはコア（実行ユニット）は1つしかないが、キャッシュミス時などコアが待ち状態になったときに、別のスレッドを実行できる。
インテルのマルチコアアーキテクチャは Core と Core 2 プロセッサから始まった。別の有名なマルチコアプロセッサとしては、ソニー・コンピュータエンタテインメントのPlayStation 3用に設計されたIBMのCellがある。
対称型マルチプロセッサ（SMP）は、複数個のプロセッサがメモリを共有し、バスで相互接続された形態のコンピュータである[19]。バスがボトルネックとなるため、スケーラビリティは制限される。そのため、SMPは一般に32プロセッサを越えることはない[20]。大型のキャッシュメモリを使って必要なバス帯域幅を低減して十分なメモリ帯域幅が確保できるなら、対称型マルチプロセッサは極めて費用対効果が高い[19]。
分散（メモリ）コンピュータは、処理ノード間をネットワークで相互接続した分散メモリ型のコンピュータシステムである。分散コンピュータはスケーラビリティが良い。
クラスターは複数のコンピュータをネットワークで相互接続して、全体として1つのシステムとして機能させるものであり、多くの面で単一のコンピュータであるかのように見ることができる[21]。クラスターの構成は対称的である必要はないが、対称性がないと負荷分散が難しくなる。クラスター方式においても、システムリソースを共有する密結合型とリソースを共有しない疎結合型が存在する。
典型的なクラスター方式として Beowulf がある。これはTCP/IPイーサネットLANで普通のコンピュータ群を相互接続してクラスターを構成できる[22]。Beowulf の当初の開発者は Thomas Sterling と Donald Becker であった。
TOP500に掲載されているスーパーコンピュータの多くはクラスターである[23]。
超並列プロセッサ（MPP）は、非常に多数のプロセッサで構成される単一のコンピュータである。MPP はクラスターと多くの面で共通する特性を示すが、より大規模であり、100プロセッサよりずっと多数のプロセッサを装備していることが多い[24]。各CPUにはメモリがあり、オペレーティングシステムとアプリケーションのコピーがそこに格納される。CPU間の通信は非常に高速なインターコネクトで行われる[25]。
TOP500で2007年まで世界最高速のスーパーコンピュータとされていた Blue Gene/L はMPPである。
グリッド・コンピューティングは、並列計算の中でも最も分散された形態である。遠隔にあるコンピュータをインターネットで相互接続して構成され、1つの問題を共同して解く。インターネットは利用可能な帯域幅が低く、レイテンシが大きいため、自明な並列性を持つ問題に使われることが多い。グリッド・コンピューティングを利用した分散コンピューティングプロジェクトが数多くあり、SETI@homeやFolding@homeがよく知られている。
多くのグリッド・コンピューティングは、オペレーティングシステムとアプリケーションの間に特有のミドルウェアを置き、ネットワークリソースの管理やアプリケーション向けのインタフェースの標準化を行っている。よく知られたグリッド・コンピューティング用ミドルウェアとして、Berkeley Open Infrastructure for Network Computing (BOINC) がある。グリッド・コンピューティング用ソフトウェアでは、コンピュータが何もしていない時間を使うため、その時間を「スペアサイクル（spare cycles）」と呼ぶことが多い。
並列処理専用のマシンには、利用分野が限定されているものや、特定の並列問題のクラスしか解けないものもある。
真の並列性 (MIMD) という概念の起源は、イタリア人数学者ルイジ・メナブレアの "Sketch of the Analytic Engine Invented by Charles Babbage" に遡る[33][34]。 1958年、IBMの研究者ジョン・コックと Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている[2]。1962年、バロース社は4プロセッサのコンピュータ D825 を発表した。これは、クロスバースイッチ経由で最大16個のメモリモジュールにアクセス可能であった[35]。1967年、アムダールと Slotnick は、アメリカ情報処理学会連合会の会議で並列処理の可能性について公開討論を行った[2]。アムダールはこのとき、後に「アムダールの法則」と呼ばれる考え方に基づいて、並列性の限界について述べた。
1969年、ハネウェルが最初の Multics システムを発表した。これは、最大8プロセッサまでが並列に動作可能な対称型マルチプロセッサシステムであった[2]。カーネギーメロン大学では1970年代に C.mmp というマルチプロセッサ開発プロジェクトが行われ、大規模と言える初のマルチプロセッサであった[34]。同期機能を持ったキャッシュ（MESIプロトコル参照）を持ったプロセッサ群をバスで接続する形態のマルチプロセッサ機としては、1984年の Synapse N+1 が最初である[34]。
SIMD型並列コンピュータの起源は1970年代に遡る。初期のSIMD型コンピュータは、命令列を実行するときのプロセッサの制御装置におけるゲート遅延への対策という意味合いが強かった[36]。1964年、Slotnick はローレンス・リバモア国立研究所向けの超並列コンピュータ構築を提案している[2]。その提案に対してアメリカ空軍が資金を提供し、それが最初のSIMD並列マシン ILLIAC IV となった[2]。設計の鍵となったのは、最大256プロセッサによる高い並列性であり、それらプロセッサが後にベクトル計算機と呼ばれる方式で大きなデータを処理するものであった。しかし、プロジェクトは11年もかけて当初の4分の1の規模までしか構築できず、事前の見積もりの4倍の費用がかかってしまった[37]。1976年に実際のアプリケーションが実行可能になったが、その性能は当時既に発売されていた商用のスーパーコンピュータ Cray-1 に劣っていた。
並列計算を行う場合、もっともパフォーマンスを発揮するのはこれら複数のプロセッサが全て100%使い切られた時と考えられるが、従来のプログラムの多くは、複数のプロセッサを均等に全て使い切るようにはできておらず、また、そういったプログラミングは難しい[要出典]。
一般に、プログラムの処理全体のうち、複数のプロセッサで均等に処理できる部分の割合をプログラムの並列度と言う。並列コンピュータの処理性能を活かすには、プログラムの並列度が高くなければならない[要出典]。
買い物を例にとろう。まず買い物の前に、財布の中身を確かめなければならないし、足りなければ銀行で補充もしなければならない。その後はじめてお店にも行かなければならない。銀行に行くのと、お店に訪れるのは同時にできないし、財布の中身を確認してからでなければ、お店には行けない。プログラムもこれと似て、実行順番が変えられなかったり、同時に実行できなかったりする部分がどうしてもできてしまう。このため複数のプロセッサで同時に、かつ実行順番に依存しないようなプログラムのみでプログラムを構成することは難しい[要出典]。
並列計算では、処理の「ある瞬間」ではそれぞれのプロセッサは実質まったく別に動作しており、そのため実行順番が全く問題にならないプログラムなら性能は引き出しやすい。しかし、先の例のように実行順番が強く束縛される場合は、あるプロセッサだけが働き、ほかのプロセッサはすることがなくなってしまうといった状態になり、性能が引き出しにくい。そのため，並列計算はそうでない場合と比べて性能を引き出すプログラミングが困難となる[要出典]。
また、並列化のためのオーバーヘッドが、並列化によって得られる性能向上の恩恵を上回ってしまうこともありえる。例えば複数のプロセスやスレッド上で並列処理しようとする場合、各プロセスやスレッドの起動／終了処理およびデータ分割／統合処理などにかかる時間の合計が、並列化によって短縮された時間の合計を上回ってしまうと、並列化することで逆に処理性能が低下してしまうことになる。そのほか、物理的なプロセッサコアの数を上回るプロセスやスレッドを起動して並列処理をしても、コンテキスト切り替えのオーバーヘッドなどがかさむことで、かえって性能が低下してしまう[要出典]。
以上のように、並列計算によって高い性能を発揮するためには、ソフトウェア側の並列コンピューティング環境への最適化が重要な鍵となる[要出典]（詳しくは並列化を参照）。
フリンの分類
並列性の分類
ビットレベルの並列性
命令レベルの並列性
データ並列性
1: prev := 0
2: cur := 1
3: do:
4: PREV := CUR
5: CUR := CUR + PREV
6: while (CUR < 10)
タスク並列性
ハードウェア
メモリと通信
並列コンピュータの分類
マルチコア・コンピューティング
対称型マルチプロセッシング
分散コンピューティング
クラスターコンピューティング
超並列プロセッサ
グリッド・コンピューティング
専用並列コンピュータ
課題
関連項目
脚注
外部リンク
典拠管理データベース: 国立図書館 ハードウェア コンピュータシステムの構造 ネットワーク ソフトウェアの構造 ソフトウェア記法
とツールソフトウェア開発 計算理論 アルゴリズム コンピューティングの数学 情報システム セキュリティ ヒューマンコンピュータ
インタラクション並行性 人工知能 機械学習 グラフィックス 応用コンピューティング
並列コンピュータ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/03 07:32 UTC 版)
「セル・オートマトン」の記事における「並列コンピュータ」の解説
離散的(非連続的)時間で記述され、時刻t+1における1つのセルの内部状態は、時刻tにおける状態によって決定されるといった点で、セル・オートマトンはチューリングマシンとよく似ている。実際、万能チューリングマシンと等価な動作をするセル・オートマトンが存在することが知られている。しかし、チューリングマシンは「逐次的な処理を行うデジタルコンピュータ」のモデルであるのに対し、セル・オートマトンは各セルが並列に演算処理を実現しており、いわば "並列コンピュータ" であるという点で大きく異なる。 セル・オートマトンの概念をハードウェアで実装して情報処理を行おうとする試みも行われている。処理要素は格子状に配置され、2次元か3次元の平面充填構造とされる。それ以外の並べ方も可能だが、まだ試されたことはない。各処理要素（すなわちセル）は隣接する少数のセルだけとやり取りする。遠いセルとの直接通信手段は存在しない。セルの相互作用には、電荷、磁化、振動などの物理的な手段を使う。いずれにしても各処理要素間を結線する必要はない。これは、今日のノイマン型コンピュータのプロセッサとはかなり違う。 例えばシストリックアレイ（英語版）はCAプロセッサアレイの一例である。
※この「並列コンピュータ」の解説は、「セル・オートマトン」の解説の一部です。
「並列コンピュータ」を含む「セル・オートマトン」の記事については、「セル・オートマトン」の概要を参照ください。
- 並列コンピュータのページへのリンク
