並列計算 並列計算の概要

並列計算

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2014/08/01 14:00 UTC 版)

関連する概念に並行計算(へいこうけいさん)があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。

特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータサーバスーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。

可能性と問題点

並列計算は、プロセッサ同士が独立して同時に仕事をするため、理想的な状況下ではプロセッサの回路規模を大きくすること無く、プロセッサの数に比例して性能が得られると考えられ、スーパーコンピュータなどで古くからとられた手法である。

しかし、問題点もある。並列計算を行う場合、もっともパフォーマンスを発揮するのはこれら複数のプロセッサが全て100%使い切られた時と考えられるが、従来のプログラムの多くは、複数のプロセッサを均等に全て使い切るようにはできておらず、また、そういったプログラミングは難しい。

買い物を例にとろう。まず買い物の前に、財布の中身を確かめなければならないし、足りなければ銀行で補充もしなければならない。その後はじめてお店にも行かなければならない。銀行に行くのと、お店に訪れるのは同時にできないし、財布の中身を確認してからでなければ、お店には行けない。プログラムもこれと似て、実行順番が変えられなかったり、同時に実行できなかったりする部分がどうしてもできてしまう。このため複数のプロセッサで同時に、かつ実行順番に依存しないようなプログラムのみでプログラムを構成することは難しい。

並列計算では、処理の"ある瞬間"ではそれぞれのプロセッサは実質まったく別に動作しており、そのため実行順番が全く問題にならないプログラムなら性能は引き出しやすい。しかし、先の例のように実行順番が強く束縛される場合は、あるプロセッサだけが働き、ほかのプロセッサはすることがなくなってしまうといった状態になり、性能が引き出しにくい。そのため,並列計算はそうでない場合と比べて性能を引き出すプログラミングが困難となる。

一般に、プログラムの処理が複数のプロセッサで均等に処理できる割合をプログラムの並列度と言うが、地球シミュレータの高い性能はこの並列度が他に比べて極めて高いことも重要な要因である。

以上のように、並列計算では高い性能を発揮する為にはソフトウェアの並列環境への最適化が重要な鍵となる(詳しくは並列化を参照)。

背景

従来、コンピュータソフトウェアは逐次的に計算されるものとして書かれてきた。問題を解くためにアルゴリズムが構築され、それによって逐次的に実行される命令列が生成される。その命令列は、コンピュータのCPU上で実行される。命令は一度に1つずつ実行される[1]

一方並列計算では、複数の計算ノードが同時並行的に動作して問題を解く。問題は独立した部分に分割され、各計算ノードがアルゴリズムの一部を同時並行的に実行する。計算ノードの実体は様々であり、マルチプロセッサ型のコンピュータの各CPUだったり、ネットワーク上のコンピュータだったり、専用ハードウェアだったり、それらの組合せだったりする[1]

1980年代から2004年まで、コンピュータの性能向上の主たる要因はクロック周波数の向上にあった。プログラムの実行時間は、命令数と1命令あたりの平均実行時間をかけたものに比例する。他の要因が全く変化しないと仮定すると、クロック周波数の向上によって1命令あたりの平均実行時間が減少する[2]

一方で、マイクロプロセッサ消費電力P = C \times V^2 \times F という式で与えられる。ここで、P は消費電力、C はクロックサイクル毎に切り替えられる静電容量(入力が変化するトランジスタの総数に比例)、V は電圧、F はプロセッサの周波数(正確には1秒あたりのサイクル数)である[3]。従って、クロック周波数が高くなると、プロセッサの消費電力も増大する。プロセッサの消費電力の増大は、インテルが2004年5月に開発中だったプロセッサをキャンセルした最大の理由であり、この時点がクロック周波数向上が性能向上の主たる要因となっていた時代の終焉であった[4]

ムーアの法則は、マイクロプロセッサでのトランジスタの実装密度が18カ月から24カ月毎に倍になるという経験則である。消費電力の問題は以前から指摘されていたが、ムーアの法則は未だに有効である。クロック周波数向上の時代が終わると共に、増大したトランジスタ数は周波数向上以外に利用されることになり、並列計算をマイクロプロセッサ上で実装する時代が到来した。

アムダールの法則とグスタフソンの法則

並列計算のプラットフォームにおけるアルゴリズムの性能は、そのアルゴリズムをどれだけ並列化できるかに依存する。そのため、1960年代にジーン・アムダールが定式化したアムダールの法則が重要となってくる[5]。それによると、プログラムの中の並列化できない部分が並列化による性能向上を制限する。大規模な工学的問題や数学問題には、一般に並列化可能な部分と並列化不可能な部分(逐次実行部分)がある。アムダールの法則によれば、以下のような関係が成り立つ。

S = \frac{1}{(1 - P)}

ここで、S はプログラムの性能向上率(逐次実行版での実行時間を1としたときの倍率)、P は並列化可能な部分の比率である。逐次実行部分がプログラムの実行時間の10%を占めている場合、性能向上は10倍となり、それ以上の多くの計算ノードを追加しても意味はない。これにより、並列実行ユニットを追加して意味のある個数の上限が得られる。

アムダールの法則の概念を図示したもの。タスクが独立した二つの部分 A と B から構成されている。B は計算時間の約30%を占めている。がんばって B を改良して5倍の性能にしても、全体としての性能向上は少しでしかない。逆に A を2倍の性能に改良した方が全体性能はより向上する。

グスタフソンの法則は、アムダールの法則とも密接に関連する計算機工学における法則である。グスタフソンの法則は以下の式で表される。

\displaystyle S(P) = P - \alpha(P-1)

ここで、P はプロセッサ数、S は性能向上、\alpha は処理の並列化できない部分である[6]。アムダールの法則では問題のサイズが固定であり、逐次実行部分はプロセッサ数に依存しないと仮定されている。一方、グスタフソンの法則ではそのような仮定がない。

データ従属性

データ従属性(data dependency)を理解することが、並列アルゴリズムの実装法を知る基礎の一つとなる。計算と計算の間に従属関係があるということは実行の順序性が生じるということである。したがってプログラムは、従属性のある計算の連鎖のうちで最長のものより高速に実行することはできない(これをクリティカルパスと呼ぶ)。幸運なことに、多くのアルゴリズムにはそのような従属関係の長い連鎖は存在せず、計算のほとんどの部分は並列に実行できる。

Pi と Pj というプログラムの断片があるとする。Bernstein's conditions[7]は、2つの部分が独立していて並列に実行できる条件を示している。Pi への入力変数の集合を Ii で表し、Oi を出力変数の集合とする。Pj についても同様に表す。P i と Pj が独立であるための条件は以下の通りである。

  •  I_j \cap O_i  =  \emptyset
  •  I_i \cap O_j  =  \emptyset
  •  O_i \cap O_j  = \emptyset

最初の条件が成り立たない場合、フロー従属性(flow dependency)が存在し、最初の文の結果を次の文で使う場合などに相当する。第二の条件は反従属性(anti-dependency)を意味し、最初の文が書き換える変数の元の値を次の文の式で必要としている場合などに相当する。第三の条件は出力従属性(output dependency)を表す。2つの変数が同じメモリ上の位置にある場合、それぞれの更新は元のプログラムの順序関係通りに行われる(後から書き込んだ方が残る)必要がある[8]

例として以下の関数を考える。

1: function Dep(a, b)
2:    c := a·b
3:    d := 2·c
4: end function

Dep(a,b) の3行目は、2行目の前に実行できないし、並行して実行することもできない。何故なら3行目は2行目の結果を利用しているからである。これは上述の第一の条件に反しており、フロー従属性があると言える。

1: function NoDep(a, b)
2:      c := a·b
3:      d := 2·b
4:      e := a+b
5: end function

こちらの例では、各命令には従属関係はないので、並列に実行可能である。

Bernstein’s conditions では、異なるプロセス間でメモリは共有されないと仮定している。そのため、アクセスの順序性を確保する手段として、セマフォなどの同期機構が必要となる。

競合状態、相互排他、同期、並列スローダウン

並列プログラムにおけるサブタスクをスレッドと呼ぶ。システムによってはさらに小さく軽量なスレッドであるファイバーを使っており、もっと大きな単位であるプロセスを使っているシステムもある。いずれにしても、並列プログラムのサブタスクをここではスレッドと呼ぶ。

スレッドは、スレッド間で共有している何らかの変数を更新することがよくある。2つのスレッドの命令実行順序は一定ではない。例えば、次のようなプログラムを考える。

スレッド A スレッド B
1A: 変数 V を読む 1B: 変数 V を読む
2A: 変数 V の値に1を加算 2B: 変数 V の値に1を加算
3A 変数 V に値を書き戻す 3B: 変数 V に値を書き戻す

命令1Bが1Aと3Aの間に実行された場合、または命令1Aが1Bと3Bの間に実行された場合、このプログラムは間違ったデータを生成する。これを競合状態と呼ぶ。プログラマは相互排他のためにロックを使わなければならない。ロックとはプログラミング言語の構成要素であり、あるスレッドが変数の制御権を獲得すると、それがアンロックされるまで他のスレッドから読み書きできないようにする。ロックを獲得したスレッドはクリティカルセクション(プログラムの中で何らかの変数に排他的にアクセスする必要がある部分)を実行でき、それが完了したらそのデータをアンロックする。

従って、プログラムを正しく実行するには、上のプログラムを以下のようにロックを使って書き直す必要がある。

スレッド A スレッド B
1A: 変数 V をロック 1B: 変数 V をロック
2A: 変数 V を読む 2B: 変数 V を読む
3A: 変数 V の値に1を加算 3B: 変数 V の値に1を加算
4A 変数 V に値を書き戻す 4B: 変数 V に値を書き戻す
5A: 変数 V をアンロック 5B: 変数 V をアンロック

一方のスレッドが変数 V をロックできた場合、もう一方は V がアンロックされるまで待たされることになる。これによってプログラムの正しい実行が保証される。ロックはプログラムの正しい実行の保証には必須だが、それによってプログラムの実行速度は大幅に低下する。

複数の変数のロックには複数のロックが必要であり、それによってデッドロックが発生する可能性が生じる。不可分なロックは複数の変数を一度にロックするものである。その場合、対象変数群の一部がロックできなければ、全体のロックができないと見なされる。個別にロックされる2つの変数をロックする必要のあるスレッドが2つ存在したとして、一方のスレッドが一方の変数だけをロックし、もう一方のスレッドがもう一方の変数だけをロックするという状況が発生しうる。このような場合、双方のスレッドはロックできていない変数をロックしようとして待ち続け、結果としてデッドロックとなる。

多くの並列プログラムでは、サブタスク群が同期して動作することを要求する。この用途で使われるものとしてバリアがある。バリアは一般にソフトウェアロックを使って実装される。その種のアルゴリズムとしてLock-freeとWait-freeアルゴリズムがある。これはロックもバリアも使わずに全てを実現するものである。ただし、実装は難しく、データ構造の設計を慎重に行う必要がある。

並列化によって必ず性能が向上するとは限らない。一般にタスクを細分化してスレッド数を増やしていくと、スレッド間の通信に費やす時間が増大していく。すると、ある時点で通信オーバーヘッドが処理時間を支配するようになり、それ以上の並列化(スレッド数の増加)は単に処理時間の遅延を招くことになる。この現象を並列スローダウンと呼ぶ。

細粒度並列性、粗粒度並列性、自明な並列性

アプリケーションは、スレッド間で同期や通信を必要とする頻度で分類できる。細粒度並列性(fine-graind parallelism)を持つものは、スレッド間で頻繁に通信する必要がある。粗粒度並列性(coarse-grained parallelism)を持つものはその逆である。自明な並列性を持つ(embarassingly parallel)ものは、ほとんど全くスレッド間の通信を必要とせず、したがって並列化も最も容易である。

一貫性モデル

レスリー・ランポートは初めて逐次一貫性の概念を定義した。また、LaTeXの開発でも知られている。

並列プログラミング言語と並列コンピュータには一貫性モデル英語版(メモリモデルとも呼ぶ)が必須である。一貫性モデルとは、メモリ上の操作に関する規則を定義したものであり、どのように結果が生成されるかを定義したものである。

最初に定義された一貫性モデルは、レスリー・ランポート逐次一貫性モデルである。逐次一貫性とは、並列プログラムを並列実行したときの結果と、それと等価な逐次プログラムの結果が同じという特性である。プログラムが逐次一貫性を持つとは、「…任意の実行の結果が、それを全プロセッサが逐次的順序で実行された場合と同じであり、その順序がプログラム内で指定された順序と同じである」ことを意味する[9]

ソフトウェアトランザクショナルメモリは、一貫性モデルの典型例である。ソフトウェアトランザクショナルメモリは、データベース理論から不可分操作の概念を借り、それをメモリアクセスに適用したものである。

数学的にこれらのモデルを表現する方法はいくつか存在する。プロセス計算は並行性を扱う数学の一分野である。プロセス計算はさらにアンビエント計算英語版calculus of communicating systemsCommunicating Sequential Processesなどに分類される。ペトリネットは一貫性モデルの定式化を試みた初期の例である。それに基づいて後にデータフロー理論が構築された。そして、データフローの考え方を物理的に実装したデータフロー・アーキテクチャが開発された。

フリンの分類

マイケル・J・フリンは、並列(および逐次)コンピュータ/プログラムの分類であるフリンの分類を提案した。フリンは命令列が単一か複数かという点と、その命令列(群)が扱うデータが単一か複数かによって4種類に分類した。

SISD(単一命令、単一データ)は、完全に逐次的なプログラムと等価である。SIMD(単一命令、複数データ)は同じ操作を多数のデータに対して行う場合を意味する。これは信号処理などで一般的である。MISD(複数命令、単一データ)はあまり使われない分類だが、フォールトトレラントシステムの冗長構成を指すことがある。シストリックアレイのようなアーキテクチャがこれに相当するが、実際の応用例は少ない。MIMD(複数命令、複数データ)は、ほとんどの並列プログラムに対応する。

デイビッド・パターソンジョン・ヘネシーの著書には「もちろん一部のマシンはこれらの混成であるが、単純で分かりやすく、とりあえずの近似としては最適であるが故にこの分類が今も使われている」とある[10]




  1. ^ a b Blaise Barney. “Introduction to Parallel Computing”. Lawrence Livermore National Laboratory. 2007年11月9日閲覧。
  2. ^ John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. 3rd edition, 2002. Morgan Kaufmann, ISBN 1558607242. Page 43.
  3. ^ J. M. Rabaey. Digital Integrated Circuits. Prentice Hall, 1996.
  4. ^ Laurie J. Flynn. Intel Halts Development of 2 New Microprocessors. New York Times, 2004年5月8日
  5. ^ G. Amdahl. The validity of the single processor approach to achieving large-scale computing capabilities. In Proceedings of AFIPS Spring Joint Computer Conference, pages 483–485, Atlantic City, N.J., April 1967. AFIPS Press.
  6. ^ Reevaluating Amdahl's Law Communications of the ACM 31(5), 1988. pp. 532-533
  7. ^ A. J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, Oct 66, 757-762.
  8. ^ K. Hwang and F. A. Briggs. Computer architecture and parallel processing. McGraw-Hill, 1984.
  9. ^ Leslie Lamport. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9 (September 1979), 690–691.
  10. ^ Patterson and Hennessy, pg 748
  11. ^ David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, 1999. ISBN 1558603433, pg 15
  12. ^ Culler et al, pg 15
  13. ^ Yale Patt. "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). カーネギーメロン大学での講義(2004年4月)、2007年11月7日閲覧
  14. ^ a b Culler et al, pg 124
  15. ^ a b Culler et al, pg 125
  16. ^ a b Patterson and Hennessy, pg 713
  17. ^ a b Hennessy and Patterson, pg 549
  18. ^ Patterson and Hennessy, pg 714
  19. ^ What is clustering? Webopedia computer dictionary. 2007年11月7日閲覧
  20. ^ Beowulf definition. PC Magazine. 2007年11月7日閲覧
  21. ^ Architecture share for 06/2007. TOP500 Supercomputing Sites. ここでは、74.60%のマシンがクラスターとされている。2007年11月7日閲覧
  22. ^ Hennessy and Patterson, pg 537
  23. ^ MPP Definition. PC Magazine. 2007年11月7日閲覧
  24. ^ SIGGRAPH 2005 - GPUをCPU的に活用するGPGPUの可能性 マイコミジャーナル、2005年9月6日。2008年4月5日閲覧
  25. ^ Oleg Maslennikov (2002). Systematic Generation of Executing Programs for Processor Elements in Parallel ASIC or FPGA-Based Systems and Their Transformation into VHDL-Descriptions of Processor Element Control Units. Lecture Notes in Computer Science, 2328/2002:272.
  26. ^ Y. Shimokawa, Y. Fuwa, N. Aramaki. A parallel ASIC VLSI neurocomputer for a large number of neurons and billion connections per second speed. IEEE International Joint Conference on Neural Networks, 1991年11月18日-11月21日. 3: 2162–2167.
  27. ^ K.P. Acken, M.J. Irwin, R.M. Owens. A Parallel ASIC Architecture for Efficient Fractal Image Coding. The Journal of VLSI Signal Processing, July 1998, 19(2):97–113(17)
  28. ^ Andrew B. Kahng. "Scoping the Problem of DFM in the Semiconductor Industry." University of California, San Diego. 2004年6月21日
  29. ^ a b Patterson and Hennessy, pg 751
  30. ^ L.F. Menabrea, Sketch of the Analytic Engine Invented by Charles Babbage. Bibliothèque Universelle de Genève, 1842. 2007年11月7日閲覧
  31. ^ a b c Patterson and Hennessy, pg 753
  32. ^ da Cruz, Frank (2003年). “Columbia University Computing History: The IBM 704”. Columbia University. 2008年1月8日閲覧。
  33. ^ a b c d e Wilson, Gregory V. (1994年). “The History of the Development of Parallel Computing”. 2008年1月8日閲覧。
  34. ^ Anthes, Gary (2001年11月19日). “The Power of Parallelism”. Computerworld. 2008年1月8日閲覧。
  35. ^ Patterson and Hennessy, pg 749
  36. ^ Patterson and Hennessy, pgs 749–750: 「いくつかの有益な技術を生み出したが、ILLIAC IV はコンピュータとしては失敗であった。当初計画した規模の4分の1しか構築できなかったにも関わらず、1966年に800万ドルと見積もられていた費用は1972年には3100万ドルにまで膨れ上がった。(中略)おそらく最も悪名高いスーパーコンピュータであろう。プロジェクトは1965年に開始され、実際のアプリケーションが実行可能になったのは1976年だった」






英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

並列計算に関連した本

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「並列計算」の関連用語

並列計算のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す




並列計算のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの並列計算 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2014 Weblio RSS