世界のスーパーコンピュータとそれを動かす人々


2月 16, 2015

コンパイラ、そして、もっと:アムダールの法則は健在か?

HPCwire Japan

Michael Wolfe

しばしば、新しいアーキテクチュアあるいは新しいプログラミング戦略によって、アムダールの法則による限界を超えられると主張している、ニュースを読んだりプレゼンテーションを聞いたりする。今こそアムダールの法則に関する議論を終わらせる時期であると、私は考えている。アムダールの法則の前提は、現在の並列計算の環境には適用されないと、ここで主張しよう。

法則

アムダールの法則は、P個のプロセッサーを使う並列プログラムの速度上昇の限界が、プログラムの並列化されている部分の割合をFとすると、残りの(1-F)を分母として制約されると述べている。その残りの部分は、1個のプロセッサーで処理されるか、複数のプロセッサーで冗長に処理されるかだからである。P個のプロセッサーによる処理速度をS(P)、1個のプロセッサーで処理する場合の経過時間をT(1)、P個のプロセッサーで処理する場合の経過時間をT(P)とすると、アムダールの法則は、次の不等式で表せる。

S(P) =

T(1)

1

1

(1)

T(P)

(1-F)+(F/P)

1-F

Fは、プログラムの並列に処理できる部分の割合で、それが100パーセント、即ちプログラム全体を並列処理できるならば、処理速度の向上に上限はない。プログラムの半分を逐次に実行する必要がある、即ちF=1/2の場合には、いくつのプロセッサーを投入しても、計算機資源の1/2が逐次実行に使われるために、速度向上の上限は2である。
Amdahl氏が1967年に発表したオリジナルの論文では、
当時の実際のプログラムで実行された命令の約40%が、データ管理の雑用に使われ、本質的に逐次実行すると主張された。彼は、2倍から3倍に速度向上できると示唆し、並列計算の速度向上の限界は5から7であると結論づけた。参考のために言及すると、Gene Amdahl氏が2013年12月 IEEE Computer magazineに回顧論文を書き、そこには元の論文が含まれる。

私は、アムダールの法則の大ファンである。私が計算機アーキテクチュアの教授だったときに、様々なアーキテクチュアの革新を評価するために、法則を使った。Amdahl氏が彼の古典的な論文で予見していたよりも、現在のプログラムは明らかに大きな速度向上を実現している。私の意見では、本質的に逐次実行であるプログラムの割合について、彼の断定は過大で、あまりにも保守的だった。我々は、非常に並列度が高いプログラムの書き方を学んだ。次の節で議論するように、我々が問題のサイズを大きくする際に、並列化可能な部分の割合は、ほとんど無制限に増加する。

しかし、法則は、現在のトレードオフを表しているだろうか。アムダールの不等式は、1960年代後半の技術を用いたマルチプロセッサーと速いユニプロセッサーの性能を比較するために開発された。比較の基準は、プロセッサーの数である。変化すると考慮された唯一の計算機資源がプロセッサーの数だった。現在考慮すべき他の機能はまだ発明されていなかった。

アムダールの不等式は、ときどき、性能限界ではなく、性能モデルとして扱われる。これは、多くの細かい事項を無視しているので、優れた性能モデルではない。しかし、ピーク性能と同じ制限を得られる。これは、超えることができない性能、あるいは速度向上である。我々は、性能を速度向上限界と比較し続けるべきだろうか。そこで私は、速度向上限界を上回ると主張する、4種類の方法を示す。そのうちの2つは、ストロング・スケーリングとウィーク・スケーリングとして20年間頻繁に議論されている問題であり、残りの2つは、オーバーヘッドとヘテロジニアスである。

ストロング・スケーリングとウィーク・スケーリング

法則のひとつの仮定は、逐次プログラムと並列プログラムによって、同じ問題を解決したいということである。これは、多くの場合に、たぶん真実であろう。あなたには、ひとつの仕事がある、そして、その仕事をなるべく速く処理したい。どれだけ速く仕事を完了できるか、これは、ストロング・スケーリングの測定方法である。

しかし、より強力な並列システムの用途が、他にもある。計算において、何人かの利用者は、同じ時間内で最大規模の問題を解きたい。毎日の天気予報のための計算には、2時間から4時間の制限時間がある。より速い計算機は、天気予報を速く計算するためではなく、計算量を増やして予報の精度を上げるために使われる。この、一定の時間内にどれだけ大きな問題を解けるかは、ウィーク・スケーリングの測定方法である。Linpackベンチマークは、TOP500リストのために、同様の方法を使う。自分のシステムに合わせて問題の大きさを選べるからである。

一部分の利用者にとっては、ストロング・スケーリングだけが興味の対象である。問題の大きさはスケールしない。他の利用者にとっては、現在持っている計算機を使って、できる限り大きい問題を解きたい。法則の向きを変えてみよう。並列化の割合がFである問題をP個のプロセッサーで解く場合に、どれだけ速くなるかではなく、問題の大きさがP倍になったら、どれだけ遅くなるかである。プログラムの逐次実行の割合(1-F)の部分については、逐次実行が1回だけ起こり、残りの割合Fの部分については並列に動く。スケールされる速度向上の不等式は、次のようになる。

S(P) =

T(1)

(1-F)+FP

=

1+F(P-1)

(2)

T(P)

(1-F)+F

この不等式は、 Sandia National Laboratoriesの Edwin Barsis氏が書いた論文により、 Gustafsonの法則と呼ばれることがある。この不等式の重要な前提は、プログラムの逐次実行部分の割合は、問題の大きさによってスケールしないか、無視できるほどゆるやかにしかスケールしないことである。ありがたいことに、我々が高並列計算機を使う処理の際に、充分に真実である。例えば、90パーセント並列化された問題を考えよう。アムダールの法則によれば、速度向上の限界は10倍である。この問題を1000倍にスケール・アップし、プロセッサーの数を1000に増やすと、速度向上の限界は900倍になる。これは、我々が計算機資源のみによって、速度向上を制限されることを意味する。

キャッシュ・メモリーとスーパー・リニア速度向上

小規模な初期の並列計算機の利用者何人かは、P個のプロセッサーによってP倍以上の速度向上が起きる例を発見した。これは、アムダールの法則にも、より精密な分析にも反する結果である。2種類の単純な場合がある。一方は、並列サーチで、どれかひとつのプロセッサーが解を見つけると、全てのプロセッサーが作業を打ち切れる。サーチに成功した場合、どのプロセッサーも探索していない空間が存在する。

2人が電話帳の特定の番号を探している例を考えよう。1人目は先頭から、2人目は中央から探し始める。単純に考えると、これは完璧な並列問題であり、2倍の速度向上を得られるはずである。平均的な速度向上は2倍であるが、個々の場合を考えると、まったく向上しないこともあれば、大きな値になることもある。探している番号が電話帳の前半にあれば、2人目が電話帳の後半を探すことは無意味である。探している番号が後半の最初にあれば、2人目が即座に発見し、速度向上はほとんど無限になる。アムダールの法則は、処理すべき仕事の全体を複数のプロセッサーで分割すると仮定しているので、電話帳を探す例を説明できない。サーチだけでなく、多くの例題について、このようなことがある。

第二の場合は、キャッシュ・メモリーと仮想メモリーの登場によって発生した。アムダールの法則は、より多くの計算機資源が、より多くのプロセッサーであるという前提で、速度向上を計算する。しかし、プロセッサーには、性能を向上させる別の要素、特にキャッシュ・メモリーが存在する。特にストロング・スケーリングの場合において、より多くのプロセッサーを加えることは、個々のプロセッサーが担当する仕事が減ることでもある。仕事が少ないということは、しばしば、データが少ないということである。その少ないデータは、キャッシュ・メモリーに乗りやすくなる。ワーキング・セットをキャッシュ・メモリーに対応させるのは、ヒットかミスかの階段関数のようなものだ。ミスすれば、メモリーの通信速度でメイン・メモリーからデータを持ってくる。ヒットすれば、キャッシュ・メモリーの速度が出る。この速度の違いは10倍以上だ。したがって、ちょうどよい数のプロセッサーを追加して注目すべき速度向上があったときに、研究者らは驚いたわけだ。

アムダールの法則は、プロセッサーの計算能力のみが資源と仮定しているので、キャッシュを考慮していない。論文が発表された翌年の1968年にIBM System 360 Model 85に「buffer storage」と呼ばれた16KBから32KBのキャッシュが搭載されるまで、誰もキャッシュを考慮しなかったことは当然だろう。プロセッサーがP個あれば、キャッシュ・メモリーがP倍存在することを考えに入れる必要がある。これは学術的に興味深いが、価値はない。我々がとてつもなく大きなキャッシュ・メモリーを望んだとしても、現在のキャッシュ・メモリーはプロセッサー・チップに内蔵されており、キャッシュが大きいと応答速度が遅くなるので、キャッシュは2から3レベルに分かれており、1個のプロセッサーに巨大なキャッシュを持たせることは不可能である。ウィーク・スケーリングの場合には、プロセッサー当たりの仕事量はあまり変わらないので、前述のような簡単な考察はできず、あいまいな概念になるが、キャッシュの大きさは関係している。

アムダールの法則は、速度向上の限界がプロセッサー数の1次関数であることを前提としている。しかし、より多くのキャッシュを構築できるので、法則を超える速度向上を得られる例題が存在する。よりよい性能限界のひとつは、測定する資源の対象を変えることである。プロセッサー当たりの速度向上を測定する代わりに、トランジスターあるいは論理ゲート数当たりの速度向上を測定するのである。チップ内蔵のキャッシュは、計算するコアと同様に、トランジスターから作られる。10億個の論理ゲートからCPUを作るとして、16コアと16MBキャッシュの構成がよいか、32コアと2MBキャッシュの構成が良いか、考えてみよう。

これは、25年前からのRISC対SISC論争に似ている。単純な命令セットと単純な制御機構によって、より多くのレジスターとキャッシュを実装すべきだという主張だ。この競争については、命令セットと制御機構を単純にするRISCに対して、命令セット互換性とトランジスター数を味方にしたSISCが勝った。現在においては、GPUとメニー・コアCPUの設計において、同様のトレードオフが起きている。大きく、高性能で、deep (訳注:パイプラインが深いのでクロックを上げられるという意味だと思われる) 、コヒーレントなキャッシュを持つ少数のコアに対して、比較的性能が低く、キャッシュが小さな多数のコアから成るGPUあるいはメニー・コア・アクセラレーターが有利かどうか、トランジスターをどのように使うべきかのトレードオフがある。

オーバーヘッド

アムダールの法則は、オーバーヘッドを考慮していない。並列計算においては、並列処理の開始、並列タスク間の通信と同期に関するオーバーヘッドが常にある。一部分のマシンは、並列実行を支援するハードウェアを持っていた。例えば、Alliant FX/8システムは、最大8個のプロセッサー上で、1命令によって、逐次実行を並列実行へ切り替えられる機能があった。そこでは、オーバーヘッドはゼロではなかったが、かなり小さかった。そして、並列モードでは、別々のタスクの管理を必要とした。他のマシンでは、並列処理を実装するために、オペレーティングシステムを使っていて、現在も使われている。並列処理の開始と、プロセス間の同期の、オーバーヘッドが著しく高い。現在の共有メモリー・システムでは、オペレーティングシステムの1個のプログラム・カウンターを持つ1個のスレッド、単一の共有アドレス空間を使って、オーバーヘッドを削減する。大規模なMPIプログラムがメッセージを渡すには、オーバーヘッドが発生する。そして、アクセラレーターを使う現在のシステムでは、ホストCPUとアクセラレーター・デバイスの間のデータ転送に、オーバーヘッドが発生する。

プロセッサー数を倍増し、同時にオーバーヘッドを劇的に減らす、新しいシステムを作れると仮定しよう。そうすれば、クロックと計算速度が同じだとしても、古いシステムに比べて2倍を超える速度向上を得られるかもしれない。これは、アムダールの法則に反する。

我々は、オーバーヘッドを明示的に含むモデルを作れる。

S(P) = T(1)

1

1

1

(3)
T(P)

(1-F)+(F/P)+V

(1-F)+V

1-F

オーバーヘッド(V)はしばしば逐次実行で処理されるから、逐次実行の仕事に分類すべきだと、反論があるかもしれない。何十年も前に私が大学院生だった頃、逐次処理および並列処理によって、プログラムの実行をシミュレーションした。しばしば、逐次実行によるシミュレーションと比べて、並列実行によるシミュレーションは、しばしば低速だった。この原因の多くは、我々のシミュレーション方法の欠陥にあった。しかし、それによって、逐次実行のプログラムの計算時間を基準にするのではなく、並列プログラムを1個のプロセッサーで実行する際の計算時間を基準として、PP個のプロセッサーによる並列処理の速度向上を比較するという、華麗な並列高速化概念の発明をもたらした。逐次実行のプログラムにはオーバーヘッドがないので、古いモデルは実に愚かだった。

オーバーヘッドが並列処理の一部分として扱われるべきだという、もうひとつの主張があるかもしれない。オーバーヘッドは並列化の利益を受けないから不公平であり、並列化の利益を受ける部分の割合Fに含めるべきではないということだ。

オーバーヘッドが、無視できるほど小さな量ではないならば、別々に測定され同定される必要があると、私は主張する。並列部分の冗長性を減らすことが、アムダールの法則によって、あなたのプログラムの速度向上に重要でないならば、オーバーヘッドがゼロと近似してよいだろう。しかし、オーバーヘッドの削減は、並列性能全体を向上させるパズルの一片として、とても重要なことであり続けるだろう。

ヘテロジニアス

アムダールの法則は、明らかに、P個の全く同じ種類のプロセッサーを仮定している。過去のマルチプロセッサーと、現在のマルチコアは、この仮定を満たしているが、これは普遍的な真実ではない。現在のアクセラレーターには、同一アーキテクチュアの少数のコアを持つホストCPUと、しばしば異なる命令セットを持つ非常に並列度の高いアクセラレーターがある。我々は、1個あるいは複数のファット・プロセッサーと、多くのシン・プロセッサーから成る、高度な並列システムを容易に想像できる。ファット・プロセッサーは、より高いクロック速度、高い命令レベル並列性、アウト・オブ・オーダー命令スケジューリング、より多くの分枝予測を持っていて良い。これは、ARMのbig.LITTLEの考え方である。AMD APUのように、現在のアクセラレーター・ノードは、ファット・プロセッサー(CPU)と、多くのシン・コアまたはアクセラレーター上の処理要素を持ち、このモデルに適合する。1個または少数の伝統的な方法で最適化されたファット・コアと、スループットに最適化された多数のシン・コア、シン・コア同士では同じ命令セット、から成るプロセッサーをの設計を容易に想像できる。

このようなヘテロジニアス・システムにおいて、プログラムの並列化された部分は、シン・プロセッサーまたはコアで実行される。速度向上はどうなるだろうか。並列計算機の速度向と同様に、シン・コアがP個あるというモデルが、ひとつの方法だ。しかし、逐次実行の部分をファット・プロセッサーで実行でき、その速度はシン・プロセッサーのX倍であるとする。速度向上は次のようになる。

S(P) =

T(1)

1

(4)

T(P+1)

(1-F)/X+(F/P)+V/X

ここでは、ファット・プロセッサーの速度向上の因子により、逐次実行部分の割合(1-F)と、オーバーヘッドの割合(V)に、Xを掛ける。すると、アムダールの法則よりも大きな速度向上を予想できる。これは、多くの有能なマーケティング部門によって採用される方法である。

皮肉なことに、P個のシン・コアの速度と、プログラムの残りの部分を処理する1個のファット・コアの速度を、比較するべきだと言われるかもしれない。X因子は、現在、並列数と比較されるので、あまり印象的には見えない。

S(P) =

T(1)

1

(5)

T(P+1)

(1-F)+(F/P)X+V

これは、現在のアクセラレーター(GPUまたはXeon Phi)システムにおいて、アクセラレーターのコア数による速度向上に対して、ホスト・コアによる速度向上が小さいことに一致する。

しかし、どちらの計算式も正しい物ではない。我々が本当に知りたいのは、特定の技術やトランジスターを作るコストを元にして、P個の標準的なコアを使うべきか、Pf個のファット・コアとPt個のシン・コアを使うべきかである。ここまでの比較では、ファット・コアは多かれ少なかれ伝統的なコアと同様であるから、Pf+Pt>Pである。これは、検討的すべきリソースが、トランジスター数あるいは論理ゲート数とする議論とは別である。

結論

アムダールの法則は、45年以上前の AFIPS Spring Joint Computer Conference において、 Gene Amdahl博士によって提案された。その論文の最初の節は、先駆者による並列計算への挑戦と約束について思い出す場合にのみ、現在でも魅力的である。「10年間以上にわたって、1台のコンピューターによる性能が限界に達し、複数のコンピューターの結合が協調して問題を解決する方法によってのみ、進歩が可能であると、予言者が言った。」

その法則の仮定が有効である場合には、並列処理による速度向上の限界が、不等式によって与えられる。そのために、しばしば、誤って引用され、多くの設計上の決断を攻撃するために誤って使われている。法則の本来の意義は、プロセッサーの数が速度向上に重要なのではなく、より速いプロセッサーの開発が重要だということである。これは、現在においても真実である。

しかし、アムダールの法則の仮定は、もはや有効ではない。仮定のいくつかは、問題のサイズが固定されているために、性能の曲線に不連続がなく、計算機資源はプロセッサーの数だけであり、並列化のオーバーヘッドは最小で、全てのプロセッサーが同質(ホモジニアス)ということである。これらの仮定を超えようとするシステムの性能については、法則は関与しない。現在のHPCについて、法則は単純には適用できない。我々は、プロセッサーあるいはコアの数よりも、他の計算機資源を考慮すべきである。チップ設計者は、キャッシュ容量とコアの数、少数のファット・コアか多数のシン・コアかというトレードオフにおいて、論理ゲートの数を考えることができる。

ある固定された大きさの22nm技術で作られたチップによって、いくつかのアプリケーション・セットがどのくらいの性能を得られるだろうか。顧客は、コストを度外視できず、コストは市場の大きさから利益を得られるコモディティーな部品に有利である。

ある固定された費用で、自分のアプリケーションのために、どのくらいの性能を得られるだろうか。自分のマシン・ルームは、発電所にどのくらい近いだろうか。顧客は、プログラミングの容易さを考慮するかもしれない。新しいシステムで自分のプログラムを最大限の性能で動かすために、どのくらいのリファクタリングが必要だろうか。

我々は、HPCシステムの設計について、高性能なプロセッサー・ノードから至る所のクラスターについて、多様性を見ている。低消費電力のIBM Blue Geneシステム、組み込みPowerPCノード、NVIDIA GPUあるいはXeon Phiコプロセッサーによって加速されたノードなどである。最近の発表と合理的な予測によると、将来において、並列プログラミングはますます多様になるであろう。

しかし、アムダールの法則に未来はない。法則は目的を終えており、現在優雅に引退する必要がある。次に法則を見聞する際には、Gene Amdahl博士による、単純かつエレガントだが時代遅れな性能限界について、誤用を戒め、法則を引用した者が何をトレードオフしたか明らかにさせるように、お勧めする。

筆者について

Michael Wolf博士は、学界と産業界において、35年間以上コンパイラーを開発し、現在はNVIDIA社でPGIコンパイラーの技術者である。本記事は、筆者個人の見解であり、NVIDIA社の見解ではない。