ひっくり返る常識。(アムダールの法則と問題規模)   

2005年12月18日



☆ひっくり返る常識。   
世の中いろいろと常識だと思っていたことが突如違った話になっていたりしてビックリすることがある。

例えば、先日知ってビックリしたことと言えば「銀河系はじつは棒渦巻き銀河だった。」 という話がある。(これは日経サイエンス2006年1月号「渦巻銀河のダイナミズム」に掲載されている。 興味のある方はご一読を...)

子供の頃、銀河系はアンドロメダ大星雲の腕をもう少し開き気味にした形のきれいな渦巻き銀河 と学校で習った記憶があり、それを常識として信じてきた。 しかし、最新の学説によれば銀河系は棒渦巻き銀河であるという説が有力であるそうだ。

もちろん、棒渦巻き銀河と言っても鎌を二つくっつけたような棒状構造が突出した典型的な棒状構造 (たとえばNGC1300等が有名。)を持つ訳ではなく、 渦巻き銀河のバルジ(中心部分の膨らんだ部分)が球状ではなくラグビーボール状に変形した程度で、あまり棒状構造が発達してないタイプだそうだ。 (M58星雲が近い形をしているらしい。)

だが、渦巻銀河か棒渦巻銀河かは大問題で、こんな基本的なことが今まで未解明(というか、誤った説のまま)でいたなんて少々信じられない気分である。

なぜ今まで見逃してきたかというと、実は太陽系がこのバルジに対し長手方向に沿った向きに位置しているからで、 この方向から見るとラグビーボールも真球に近い形に見える。だから、気づかなかったというわけだ。 ラグビーボール状構造を横から見る向きに太陽系があれば、もっと早い段階で気づいていたことだろう。

しかもそれだけではない。 さらにおもしろかったのは、「ある時は渦巻銀河、またある時は棒渦巻銀河。」と同じ銀河で棒状構造が 伸びたり縮んだりしているらしいことが分かったと言うことだ。(もちろん、この変化には何十億年という天文学的な時間がかかるが。)

今までの常識では、渦巻銀河はずっと渦巻銀河のまま、棒渦巻銀河は棒渦巻銀河のままであり、 他の銀河系と衝突して楕円銀河になってしまうまではそのままの形だというのが定説だった。 (少なくとも今まではそう習った。) しかし、コンピュータ・シミュレーションの結果、棒状構造の時間的変化が偶然発見されたんだそうだ。

当サイトの専門の化学と異なり、銀河進化の研究等は実験という研究手法が使えないという大きなハンデがある。 (試験管の中で銀河を振り回す訳にもいかない。) だから、これも地道な観測とコンピュータシミュレーション技術の進歩のおかげという訳だが、 こんな基本的な常識がひっくり返ってしまうことがあるから、これだから科学っておもしろい。1)

☆アムダールの法則の破綻?   
さて、PCネタで常識がひっくり返る話と言うと何かあるだろうか?

当サイトの場合、それは「アムダールの法則は問題規模が拡大する場合は制約事項にならない。」という話がある。 アムダールの法則は並列処理の性能向上限界を語るときによく引き合いに出される法則で、 当サイトではマルチコアの性能向上がクライアント用途では期待できないという話においてベース理論として使わせていただいたことがあるし、 シロウトの我々アマチュアにとっては常識では無いが、コンピュータの専門家にとっては初歩の知識だそうだ。

そして、これが並列化における基本法則であるため、AMDもクライアント用CPUにおけるマルチコアの限界について同じ根拠を用いており アムダールの法則を巡るIntelとAMDの戦いという記事において、AMDは 「デスクトップでは多くのエンタープライズコンピューティングジョブは、1個のハイパフォーマンスコアからしかほぼ恩恵を受けない状態が続く」 (同記事より引用)と主張している。

ところがintelはアムダールの法則は将来のアプリでは制約事項にならないとして反論しているのが面白い。

同記事によれば「並列化では、アムダールの法則が課題となる。しかし、将来のアプリケーションでは、 アムダールの法則が制約要素になるとは思わない。それは、プログラムサイズが大きくなると、逐次実行部分より、 並列化が可能な部分の方が急激に増えるからだ。そのため、大きなプログラムになればなるほど、 (並列性の)効率がアップする。だからこそ、大規模な並列スーパーコンピュータがこれだけ成功している。」(intelのJustin R. Rattner氏)とのことだ。

アムダールの法則は並列化処理の限界を語る上での基本法則的側面があるので、 それが成り立たないというのは先の「銀河系は実は棒渦巻き銀河だった。」という話同様に、 当サイトには驚きを持って迎えられるのである。

というわけで、今回はこのアムダールの法則が継続して使える法則なのか、はたまた破綻をきたしているのか、シロウトなりに考えてみた。

☆スーパーコンピュータではどうなの?(問題規模一定の場合)   
さて、これが正しいかどうか調べるにはどうしたらいいのであろうか?

一つには、プロセッサ数を増やしていって、同時に問題規模も拡大してみて 効率がどのように変化するかを調べてみればいい事になる。 また、同様に同じ問題規模のアプリに対してプロセッサ数を拡大していって、 効率がどのように変化するかを調べてみる必要がある。

しかし、現時点ではパソコンの場合はプロセッサ数やコア数はせいぜい数個である。 なので、期待されるような違いが誤差に埋もれて得られない可能性があるし、 また、予算的にもそんなシステムを組める財布の余裕があるはずもない。

一番お金のかからないのは、資料を調べるかネットで情報を集めるかだが、 さすがにそこまでのハードな実験をしていらっしゃるご奇特&財布リッチな方は (ググった限りでは)いらっしゃらないようだ。

そこで考えてみたのが、前回のスパコンネタで調べた論文内容の活用である。 intelのJustin R. Rattner氏は先ほどの通りスーパーコンピュータを例に掲げている位だから十分参考になるだろう。

というわけで、趣味で調べているスパコンネタの論文をいくつか引っ張ってみたところ、面白いのを見つけた。 「Leading Computational Methods on Scalar and Vector HEC Platforms」と言う論文がそれである。

この論文の主旨は、スパコンにおける実効効率の違いとアーキテクチャとの因果関係を調査する事を目的としたものであり、 著者らはそれぞれスパコンのプロである。 論文は、各種の実アプリケーションをいろいろなアーキテクチャのスパコンで動かして、 性能を調査する内容となっている。

もちろん、この論文はコンピュータのプロが同じプロ向けに書いたものなので、 アマチュアの当サイトが完全に内容を理解するのはなかなか難しい。(しかも、英語が大の苦手だし...) だが、幸いにしてこの中に上記の検討の参考になりそうなデータが見つかったので、 これを引用しながらボチボチと考えてみたい。 (もちろん、シロウト解釈なので間違っている可能性も大いにある。眉につばして読んでいただきたい。)

まず最初に引用するのは、同論文からのPARATECのデータである。 PARATECというのは密度汎関数法によりターゲット物質の基底状態での電子密度を計算するアプリである。 ナノテクが重要視される現代では、この手のアプリの重要性は増している。

このベンチマークでは488原子で構成されるCdSeクラスタを量子ドットに見立てて、 その電子密度を計算している。 使用したコンピュータは下記の7機種である。 IBM pSeriesを除けばいずれの機種も現役バリバリの高性能機種で、TOP500でもそれぞれに名をはせている。

  1. IBM pSeries (Power3-380node-6080processors ローレンス・バークレイ国立研究所設置)
  2. Thunder (Itanium2-1024nodes-2048processors ローレンス・バークレイ国立研究所設置)
  3. Jacquard (Opteron-320dualnodes-1280processors ローレンス・リバモア国立研究所設置)
  4. CrayX1 (MSP-64nodes-512processors オークリッジ国立研究所設置)
  5. CrayX1E (MSP-96nodes-768processors オークリッジ国立研究所設置)
  6. 地球シミュレータ (640nodes-5120processors 地球シミュレータセンター設置)
  7. SX-8 (36nodes-288processors シュツッツガルト高性能計算機センター設置) 2)
今回はコンピュータ間のアーキテクチャの違いを見るのが目的ではないので、 これらのマシンについての詳細は省くが、CrayX1EはCrayX1の後継機であり、 SX-8は地球シミュレータのベースとなったSX-6の後継機である事だけは書いておいたほうが良いだろう。

では、下記に論文のデータを引用させていただく。(論文は表の形で掲載されているが、見にくいのでグラフ化させていただいた。) 注意していただきたいのは計算する物質は488原子で固定であり、プロセッサ数に限らず問題規模は固定である点だ。 ちなみに、PARATECでこの問題規模は論文著者の知る限りでは最大の問題規模だそうだ。

PARATECにおけるプロセッサ数と実効効率の関係
488個のCdSe原子からなる量子ドットの電子密度を計算している。

効率の絶対値は地球シミュレータが最高だが、今回はそのネタではないので 注目していただきたいのは別の点である。 見ていただくと分かるが、機種にかかわらず256ノード程度から急激に効率が低下している事が分かる。

この傾向には機種間の違いはあまり無く、ベクトル、スカラにかかわらず低下傾向が見られる。 つまり、効率の絶対値の違いはともかくとして、この低下傾向自体はCPUアーキテクチャに依存しないものであろう。 おそらく、効率低下の最大要因が並列化効率に起因するものだからだろう。

論文を読むと、この並列性を低下させ得ている最大の要因は3次元フーリエ変換における プロセッサ間の全域通信負荷であるとされていた。3) プロセッサ全体に対する通信はプロセッサ数に対して負荷が比例して増大する訳ではなく、 通常はかなり小さい依存性となる。

もしかりに、ここで全域通信負荷を負荷によらない一定値と近似してしまえば、 それはアムダールの法則において逐次部分が負荷に依存しない定数である事を意味する。

この近似が正しければこの効率低下の最大要因はおそらくアムダールの法則であり、 ベクトル機であろうがスカラ機であろうがノード数の物量作戦に訴えれば効率低下は免れがたい事を意味していると読める。

主な対策としては次のような感じではないだろうか?

  1. プロセッサ単体の性能を上げる。
  2. アルゴリズムを改良して非効率化が発生するプロセッサ数を先延ばしにする。
    (下図の通り、並列化率が上がれば性能低下が発生するプロセッサ数を先延ばしにできる。)
  3. 非効率化を甘んじて受け入れ、それを上回る物量を追求する。
    (このため、コスト対策・消費電力対策を優先する。)
本題からは逸れるが、この3つの方針は実は最近のスパコンの開発方針に通じている事は重要だと思う。 (当サイトはベクトル支持だが、最終的にどれが正しいかはプロでさえ見解が分かれる位だから「神のみぞ知る。」だ。)

たとえば、SX-8ではプロセッサの処理能力が地球シミュレータの2倍に強化され、なるべくノード数を増やすことなく 性能向上を図るためにプロセッサの性能を上げる方針を採用している。 また、最近のPCクラスタの躍進は二つめの方針+三つ目の方針であり、苦手な分野もアルゴリズムの改良でいずれはベクトル機と同等の効率に なるだろうという期待がある。BlueGene/Lはさらにそれを徹底して追求し、非効率化は承知の上でそれを上回る理論ピーク性能を備えるべく コストと消費電力の低減に力を入れている。このためには、単一CPU性能をあえて落とすことすら厭わない。

余談がすぎたので、本題に戻る。 では次に並列化率と並列化効率の関係をアムダールの法則通りに理論計算してみた。 それが、次の図である。

アムダールの法則から導き出される理論並列化効率
PARATECの結果は(値の絶対値こそ異なるものの)理論カーブに似ている。

PARATECの結果と比較すると数値の絶対値は異なるが、カーブの形が非常に似ている事が分かるだろう。 理論カーブを低効率側に圧縮したような形であり、 ゲタの量がシステムによって異なっているだけのようにも思える。

☆スーパーコンピュータではどうなの?(問題規模がプロセッサ数に比例拡大の場合)   
ではここで負荷がプロセッサ数に比例して増える場合を考えてみる。

同論文ではGTCの結果が掲載されていたが、これが参考になりそうだ。

GTCは磁気閉じこめ型核融合のシミュレーションをするアプリであり、 プラズマを構成する荷電粒子の動きを非常に強い磁場下で その電磁相互作用を考慮しながら自己無撞着に計算してゆく。 計算は粒子間の相互作用+外部磁場との相互作用をトレースする訳だが、 PIC(particle in cell)というアルゴリズムが使われているのが特徴らしい。

当サイトはプラズマ物理や核融合の専門家ではないし、 もちろんこんな専門性の高い話を解説できるだけの知識も持ち合わせていない。 ただし、今回の目的に対しては、幸いにして何を計算しているかは理解する必要がない。

では、ここでGTCにおけるプロセッサ数とセル中の粒子数の設定を下記に示してみよう。 論文ではアーキテクチャ間の違いを見るためにスケーラビリティーについても検討しているが、 GTCでは上記のようにプロセッサ数と共に、シミュレーションする粒子の数を単位セルあたり比例して増やしている。 (全セル数は固定)

注意して欲しいのは、先ほどのPARATECではプロセッサ数にかかわらず原子数が488個、つまり、 プロセッサ数にかかわらず問題規模が固定であること。逆にGTCではプロセッサ数の増加に伴って 問題規模も大きくなっている事である。 (本当は同じアプリでそれぞれデータがあればベストだが、都合良くは見つからなかったのでその点についてはご容赦ください。)

プロセッサ数 セル中の粒子数
64 100
128 200
256 400
512 800
1024 1600
2048 3200


問題は、表記のようにプロセッサ数とセル中の粒子数が増えた場合、 並列度と負荷の関係がどうなるかだ。 一次の比例関係なのか、二次の比例関係なのか、もっと別の関数なのか...

ここで普通に考えると、粒子間相互作用を中心に考えた場合は各粒子の組み合わせの数だけ、つまり 粒子数をnとした場合O(n)の演算量になるハズである。 しかし、PICというアルゴリズムを使用すると粒子間相互作用は粒子と場との相互作用に変換できるとある。 この場合の組み合わせ数は粒子と場との相互作用なのでO(n)となるハズである。

この「場」については、ウラソフ・ポアソン方程式を使って計算云々と書いてあって、 残念ながらタコ頭の当サイトにはまったく理解不能だったが、 今回の目的で一番肝心なことはGTCでは負荷が粒子数nに対しO(n)であることだ。 つまり、何を計算しているかがチンプンカンプン (^^;) でも、 プロセッサ数とセル中の粒子数が同一比率で増える上記の設定は、 問題規模とプロセッサ数が比例して増える状況である事は確かだと言える。

ではここで、論文に掲載されている結果を見てみよう。 GTCでは負荷が粒子数nに対してO(n)であるから、 この図はプロセッサ数と問題規模の比率を一定に保ったままの条件で行われている事に注意して欲しい。

GTCにおけるプロセッサ数と実効効率の関係
磁気閉じこめ型核融合をシミュレーションをしている。



見ていただくと分かるが、地球シミュレータの場合で何故か512プロセッサ→1024プロセッサで 数値がピョコンと上がっている。だが、その点を除けばPARATECと比べて効率低下傾向が非常に小さく、 プロセッサ数にかかわらずほぼ一定水準を維持している事がおわかりいただけると思う。 また、PARATEC同様に効率の絶対値こそ地球シミュレータが最大だが、その傾向には ベクトル、スカラの違いが見られない事も特徴である。

つまり、プロセッサ数が増えても問題規模もそれに比例して増えれば、 プロセッサ数増大によるアムダールの法則の制約はかなり緩和される事が分かる。 スーパーコンピュータの世界では10倍性能の高い機種が開発されれば 10倍演算量の大きい問題を解くことになる場合が多いので、実際の使用状況でも アムダール・リミットは緩和されているように思える。

ただし、地球シミュレータ以外ではわずかながらプロセッサ数増大に伴い効率が低下していく傾向が見られる。 逐次実行部分の依存性が並列実行部分に比べると非常に弱いため目立たないが、 依存性そのものはゼロではないようだ。(たとえばnに対して対数比例とか1/2乗で比例とか... ともかく相対的に低次元の依存性を持つと考えればつじつまが合う。)

このように、プロセッサ数の物量作戦が有効に機能するかどうかは、解くべき問題の規模や性質に大きく左右される。 この論文では物量作戦の典型例、BlueGene/Lについては記載が無いが、 当然のこととしてCdSe488原子の電子密度を解く問題規模のPARATECでは辛い状況が容易に想像できるし、 (図で131072コアレベルを推定していただくと分かる。) 逆にGTCで粒子数をプロセッサ数に比例して増やして測定すればきわめて高い性能を達成できると推定できる。

☆パソコンで問題規模が拡大する用途とは?   
というわけで、プロの世界で起こっている事を論文から読み解く限りにおいては、 確かに問題規模が拡大する用途ではアムダールの法則は制約事項になりにくそうだ。 当サイトの今までの考えにも少し修正が必要になりそうである。

しかし、我々パソコンマニアの場合は、このアムダール・リミットの緩和がCPUのマルチコア化の 制約事項になるかどうかは、もう一点別の要因を考えなくてはならない。 それは、はたしてCPU中のコア数に比例する形で問題規模が拡大する用途があるかどうかだ。

PARATECの結果を見れば分かるとおり、問題規模が一定の負荷をより速く処理したいという場合は、 逆にアムダールの法則が強烈な阻害要因になる事が分かる。 マルチコア化はポラックの法則を破るとされているが、 実は問題規模が一定の場合はアムダールの法則によりコア数の増大と共に マルチコアもどんどん非効率化していく。

つまり結局、性能阻害要因がポラックの法則からアムダールの法則に変わるだけで、 コア数に比例して処理能力が増える訳ではないのだ。

これが成り立たないためにはコア数増大に比例して問題規模が大きくならなければいけない。 intelではマルチコアを「将来のアプリのためのもの。」としているが、 この通り、問題規模が従来レベルのままで大きくならない従来アプリでは マルチコアも非効率なままなわけだから、このように主張されるのも無理からぬ話とは思う。

では、PCの世界では今後はどうなるのだろうか?

スーパーコンピュータの場合、人類には未解決の大問題がゴロゴロしているから、 問題規模拡大には問題がないだろう。 演算性能が不足している用途は、地球温暖化予測だろうと、タンパク質の立体構造予測だろうと、ナノテク材料の電子密度計算だろうと、 銀河形成だろうと、各分野それぞれにある。

しかし、我々のPCではどうだろうか?

もちろん、今回のケースではプロセッサ数が2〜3桁だ。 PCのマルチコアではコア数が2桁に届くのはだいぶ先だろうから、 今のところまだまだアムダールの法則による制約は少ないと見ることは可能だろう。

しかし、最近のPCは最上位機種を出しても注目されず、それなりの性能のお買い得機種に 注目が集まる事が指摘されている。PCの必要性能は飽和しつつあると言われている。

当サイトも、このWebサイトの記事はVIA-C3のマシンで書いている。 Webを見るのもC3だ。 ゲームをしたり、キャプチャしたTV番組を編集する時はさすがにPentium4マシンやSempronマシンでやっているが、 普段使いのマシンは性能よりもむしろ静音の方がメリットが大きいので、 そのような用途さえ除けばC3マシンで十分であるからだ。(実際、当サイトで一番稼働率の高いマシンはこのC3マシンだ。)

HDTVとかが負荷を増やす要因にはなるが、これはステップアップ的な一時的負荷増大であって、 時間に比例してHDTVの処理負荷が増えるわけではないだろう。

してみると、マルチコア最大の問題点は本当にその処理能力が必要な状況を生み出すことが出来るかという点にあると思われる。 スパコンとは異なり我々PCマニアは(ビデオ編集等を例外とすれば)最近のCPUパワーを持て余し気味であり、 最新高性能CPUを購入してもほとんどのマシンタイムでは省電力機能で低クロック動作モードで動いている。

将来、マルチコアで性能が10倍になったとき、10倍の問題規模の使途が主流になっているだろうか?  そして、コア数の増大に比例して、都合よくユーザーの問題規模も比例して大きくなるのだろうか?  もちろん、PCの使途が大きく変わる時代が来るのかもしれないが、 そんな世界は少なくとも現状の使途の延長線上にはありそうもない。

というわけで、当サイトの場合はビデオ編集系の趣味があまりないのでマルチコアは当分スルーで十分そうだ。 「アムダールの法則が成り立つのは問題規模一定の場合」というintelの主張には一定の理があると思われる というのが今回の結論だが、たとえ常識がひっくり返っても今しばらくはAMDの主張に近い状況であろう。 マルチコアがPC用途で引く手あまたとなるのはまだ先の出来事のようである。



1)
もっとも、棒状構造の存在だけなら数年前から知られていたらしい。 当サイトがPCマニアだから不勉強で知らなかっただけで、天文マニアには既に周知の事実のようだ。

2)
構成は当時のもの。現在は72nodes構成である。

3)
ただし、地球シミュレータの場合では、問題規模固定のままプロセッサ数を増やしたために ベクトル長が短くなってしまった事も効率低下の要因の一つと指摘されていた。

−参考文献−
本日のデータは Leading Computational Methods on Scalar and Vector HEC Platformsからの引用です。