キャッシュの理想と限界(シロウトの考え方では)   

2007年7月26日



☆追加コメントに関する簡単な感想。   
さて、今回のネタは数回前のキャッシュネタの続きだが、 本題に入る前に、前回の件で当サイトからの疑問点に対する回答が追加掲載されたので簡単な感想を書いてみる事にした。

この件は当サイトの側から始めたものではないので議論の深入りはここで止めにしておくが、 追加掲載された論理を一言で言うと「論理自体は強固だが、論理のカバー範囲は狭い。」という印象だ。 双方の実力差を考えれば当サイトが疑問点を掲載しても鎧袖一触の形で簡単に論破されるのでは?と当サイトとしては 正直内心ビクビクでの掲載だったのだが、追加掲載された内容は積極的に当サイトの論理を論破して完全勝利を目指すという方針ではなく、 守らなければならない重要ポイントを確実に守り切るという方針であり、意外にも守備的な論理構築であるように思った。1)

と言うわけで、正直ちょっとホッとしてるところだ。 (アマチュア相手に本気出すのも大人げないと緩めていただいた可能性はありますけど...)

☆キャッシュネタの続き   
と言うわけで、本題に戻ってキャッシュネタの続き。

最近、CPU単一コアの性能向上が限界に達しているのではないかという主張が 多く見られる。マルチコア化へ進む理由の一つである。

当サイトでは特にCPUを中心としてこの辺りの状況をワッチしてきた。 確かにILPを中心に据えた今までの手法が壁に突き当たりつつあるのは 事実のようにも思える。

キャッシュというのは言うまでもなくデータや命令が繰り返し再利用されることで 効力を発揮する。オンダイのメモリアクセスはチップ外のメモリアクセスよりも 非常に高速である事を利用している。 このため、データや命令に局所性が無いと無意味になる。

典型例は科学技術計算だ。 膨大なデータを扱うスーパーコンピューティングの世界では、アプリの種類によっては あまりにデータ量が多いためキャッシュ内のデータが再利用される頃には 肝心のデータがキャッシュから追い出されている場合が多い。

実際ある資料では、CPU中の浮動小数点ユニット面積とキャッシュ面積を 比較して、キャッシュ面積ばかり大きくて浮動小数点ユニット面積が相対的に かなり小さいことがキャッシュベース・アーキテクチャが科学技術計算に弱い 理由である事を示唆していた。

では、PCではどうなのであろうか?

スパコンと異なり、(マルチメディア系を除けば)データ量が小さいPC用途では キャッシュの恩恵は絶大である。 一度BIOSでキャッシュを切ってマシンを動かしてみればその効力が 如何に大きいかは実感していただけると思う。

PC用CPUはキャッシュオフにしてしまうと、intel、AMD、Transmeta、VIA、等々 メーカーによらず一様にすべてお話にならない性能になってしまう。

intelとAMDでは、キャッシュに対する考え方は異なっている。 Coreマイクロアーキテクチャ系では高帯域1次キャッシュと 2コア共有だが通常型2次キャッシュの組み合わせ。 Net-Burst系では超高速・高機能だが実質的に低容量の1次キャッシュ (トレースキャッシュ)と通常型2次キャッシュの組み合わせ。 AMDは速度や機能ではトレースキャッシュに負けるが 相対的に容量の大きな通常型1次キャッシュと レイテンシ大だが容量面で効率的な排他的2次キャッシュの組み合わせ。

しかし、これほどの設計思想の違いがありながら、 命令やデータの局所性が無いアプリに対して無力なのはいずれも同様。 また、一長一短ありながら総合的には両者の実際の効力に思ったほど大きな違いがないのも 不思議なくらいである。(AMDの場合はオンチップのメモリコントローラに助けられている面はあるにせよ。)

ともあれ、PC用CPUはキャッシュ無しでは10年前のCPUにも負けてしまうような 性能にしかならないわけで、 キャッシュベースアーキテクチャはキャッシュが効く範囲のデータ数を扱う場合は 非常に効果的なアーキテクチャなのであろう。

☆もしも理想のキャッシュがあったとしても...   
ではCPUの能力向上にキャッシュの増強がどれほど効くのであろうか?

皆様の中に、もし100%ヒットする理想のキャッシュがあったら CPUの性能は2倍にも3倍にもなるとお考えの方はいらっしゃるだろうか?  実はキャッシュの性能余力はアプリのヒット率により大きく変わるが、 現状でよく効いているアプリでは性能向上の余地は驚くほど小さい というのが当サイトの以前の結論である。

まず、現状のアプリでのヒット率はどれくらいであろう?

intelの公開資料によると、マルチメディア系では 命令キャッシュは98%程度ヒットしているという。 (マルチメディア系ではループ処理の比率が大きいから、通常のアプリではもう少し低い値だろうと思われる。) ただし、マルチメディア系ではPC用途では例外的にデータサイズが 非常に大きいためデータキャッシュヒット率は90%程度に低迷している。 (非マルチメディアでのデータキャッシュヒット率の資料はないが、 おそらく命令キャッシュと同程度であろう。)

近代CPUは大容量キャッシュ装備だが...
左はCoreマイクロアーキテクチャ、右はNet-Burstアーキテクチャ。
近いうちにWindows3.1時代のメインメモリと同程度の2次キャッシュが搭載されるだろう。

次に、PentiumM発表時に使われた公開資料を見てみよう。 この資料によると、CPUの動作時間の内データミスで約20%のマシンタイムが奪われている。

これは、逆に言うと100%ヒットする理想のデータキャッシュがもし仮に この世にあったとしても、1/(1-0.2)=1.25だから 25%しか性能が向上しない事を示している。

この中には命令キャッシュミス分が含まれていないから、 命令キャッシュも理想キャッシュであれば実際はもう少し速くなるわけだが、 命令キャッシュ分で75%分もミスっているとは思えないから、 キャッシュ単独で2倍にも3倍にもなるというのは夢物語であることがよくわかる。

もう一つ例を挙げておこう。 RISCアーキテクチャの開祖・パターソン先生の名著 「コンピュータの構成と設計」の中に練習問題としてこんな問題がある。 本をお手持ちの方は下巻の525ページをご覧頂きたい。 ここに掲載されているのは、100%ヒットする魔法のキャッシュが仮にあったとしたらどの程度性能が向上するか 計算してみなさい、という練習問題だ。

これは、情報処理の試験に出てくるヒット率とレイテンシから計算する問題 よりずっと高度な設問(命令の出現頻度まで考慮しなければならない。)だが、 実はこの問題は単なる練習問題としての架空の問題設定ではなく、 R3000をベースにしたアーキテクチャでの シミュレーション結果に基づいている。

で、結果を見てみよう。パターソン先生の模範解答は 100%ヒットする魔法のキャッシュがあったとしても 性能向上は68%でしか無いというものである。 ここでも2倍3倍という性能向上はあり得ない。

また、著書の中でパターソン先生はこう述べている。 キャッシュ容量を増大させるとキャッシュアクセスに時間がかかるようになるが、 キャッシュ容量が一定値を超えるとアクセスタイム増大によるデメリットが ヒット率改善による性能向上を上回るようになるとのことだ。

つまり、キャッシュ容量増大は無限に行える訳ではない。 無理矢理増量しようと思ったらキャッシュ階層を深めるしかなく、 その結果、増やした容量の割に改善効果がさらに薄まる事になる。

最後にパターソン先生の回答とは違って信用性に問題ありだが、 当サイト的超簡略概算計算も述べておこう。

キャッシュがデータや命令を再利用していると言うことは、 メインメモリ容量とキャッシュ容量が同一になったときの 性能向上がキャッシュの性能向上の限界であることが容易にわかる。

つまり、メインメモリ容量が例えば256MBだったとすると、 キャッシュ容量が256MBになったときの性能を予想すれば、 それがキャッシュによる性能向上の限界値という事になるだろう。

ここで、この性能向上の予想に役立ちそうな情報がある。 それは以前AMD64系で2次キャッシュ容量が2倍になったCPUとクロックを10%向上した CPUは同じ性能のプロセッサナンバーとして扱われていたという点だ。 つまり、2次キャッシュ容量が2倍になると、性能はクロック10%分向上する事になる。

では、クロックと性能は正比例ではないのでその分について考えてみよう。 ベンチマークから見るとクロック10%の向上は性能8%程度の向上に相当 するだろう。

このCPUが売られていた頃のメインメモリ容量は256MB程度が標準だったから、 この性能向上比率で1MBの2次キャッシュ容量を256MBまで増大させてみよう。 すると、2=256だから、そのときの推定性能は 1.08=1.85となる。

実際には単一のアプリがメインメモリの端から端まで使い切るわけではないし、 メインメモリ容量の1/3程度はディスクキャッシュに使われている。 また、キャッシュの効果が飽和するという当サイトの主張をも無視した単純計算である。 だから、1.85倍というのはあまりにも理想すぎる値であるわけだが、 仮に理想的に1.85倍のままだとしてもやはり2倍にも至らないことがわかる。

☆実は低いキャッシュの効率   
Net-Burstが消費電力過多でコケた事から、 キャッシュ容量増大に期待する声はPCマニアに多い。 なぜかはわからないがPCマニアは高クロック主義が嫌いだし、 かといってILPを高めるのは限界に近づいているからだ。 しかし、以前も書いたとおり当サイトはキャッシュ容量増大には過大な期待をかけられないと考えている。 それは、キャッシュの面積効率の低さが原因である。

ポラックの法則ではトランジスタ数の0.5乗で性能が向上するとされている。 だから、ILP増強の設計思想は非効率だと...

だが、キャッシュによる性能向上をポラックの法則と比較してみよう。 キャッシュ容量を2倍にしてクロック10%向上と同じ効果ということが、 如何に非効率的かを考えてみて欲しい。

ポラックの法則はトランジスタ数に対して性能向上が O(n0.5)である。 しかし、キャッシュ増強は「キャッシュ容量を2倍にして...」と言うことは、 トランジスタ数に対して指数関数的に増強しなければならない事を示しており、 性能向上としては指数の逆関数で対数関数的にしか性能が向上しない 事を示している。

つまり、オーダーとしてはO(logn)だ。

高校レベルの数学知識があれば簡単にわかることであるが、 対数関数の値の増加ぶりが如何に非効率的かはn0.5の比ではない。 例えば、対数関数Y=logXで1目盛り1cmとしてみよう。 X軸を宇宙の直径程度まで増大しても、Yの値は家の2階に届かないのだ。

つまり、非効率、非効率と叩かれるポラックの法則だが、 キャッシュ容量増強による性能向上はポラックの法則をも越えて超非効率 というのが、当サイト的推論である。 PC用CPUの性能向上に欠かせないキャッシュではあるが、 キャッシュ単独の場合はすでに現段階でその性能向上余地は開拓しつくされており、 今後の性能向上という意味ではキャッシュ単体ではそれほど余力は残されていないと考えるのが妥当だろう。 キャッシュを生かすためにはキャッシュ以外の性能向上手法と組み合わせて相乗効果を狙うしかないと思う。

☆クロック増強とソフトウエアの肥大化とともに...   
さて、ここで今回のコラムを考える上で資料集めをしていたら、 おもしろい雑誌記事が目に付いた。 今は休刊になってしまったが、当時当サイトが最も信頼できるPC雑誌として よく購読していたPC-WAVE誌である。 この1994年3月号にキャッシュについて考える上でおもしろい記事が載っていた。

この記事はCPUが386時代から486時代へと切り替わる頃のもので、 386ピン互換で内部キャッシュを持ち486相当の性能を示すという IBMのBlueLightningについての解説である。 (それにしてもIBMってBlue〜ってネーミング好きですね。)

この当時、同様のコンセプトのCPUとしてCyrixのCx486SLCというCPUがあった。 しかし、Cyrixのチップがキャッシュ容量1KBだったのに対して、 IBMのBlueLightningは16KBと16倍もあり、その分性能が高いのが売りだった。

この記事ではIBMの発表として、この16KBのキャッシュで 典型的アプリでのヒット率は97%であるとされていた。 16KBは当時としては大容量ではあるが、2次キャッシュとはいえMB級キャッシュが ザラの現代CPUから見ればゴミみたいな容量である。 しかし、この程度の容量でも当時は97%もの高ヒット率を達成できていたわけである。

では、この比率から言えば現代CPUはとてつもなく高いヒット率でないと いけないわけだが、命令キャッシュで98%程度とは腑に落ちない。

おそらく、これは当時と今とではソフトの肥大の程度が全然違うためであろう。 PC用CPUのキャッシュヒット率の歴史は、 「キャッシュ容量の増大によってヒット率がどんどん高まっていく歴史」ではなくて、 「キャッシュ容量増大によるヒット率向上とソフトの肥大によるヒット率低下の イタチごっこの歴史」であると言えると思う。

当サイトでの経験を例にしてみよう。くだんのIBM製BlueLightningであるが当サイトでは 386との交換用CPUアクセラレータとして使用したことがある。 そのとき、DOSアプリでは今までに経験したことのない衝撃的な高速性を示し、 「おぉぉ、凄い!」とIBMの技術力に驚嘆した記憶がある。 このとき体感した高速感は実は当サイトのCPU交換において最も衝撃的な 体感速度の向上だったことを言い添えておきたいと思う。 (ちなみに、DOSアプリならCyrixのCx486SLCの1KBキャッシュでも結構速くなった。)

しかし、直後にWindows3.1での運用テストとなり、このときDOSでの高速性を 期待していただけに、Windows3.1での速度には少々 失望させられたことを覚えている。

BlueLightningはコードサイズの小さいDOS時代のソフトでは爆速だったが、 Wiondows3.1ではそれなりの高速性に効果が縮小してしまった。 これは、おそらくDOSとWindows3.1では扱うコードサイズが異なるために、 キャッシュの効力に大きな違いが出てしまったためと考えられる。

つまり、キャッシュの効力がコードサイズに依存する以上、今後の キャッシュ容量増大が効果的かどうかはアプリの肥大の程度にもよる と言うのが当サイトの予想である。 キャッシュ増強による性能向上が大きくなるためには、 今後アプリがどんどん肥大化していく状況になる必要がある。 そうでなければ、キャッシュによる性能向上は早晩壁に突き当たると いうのが結論だ。

キャッシュは的確に効果を出す渋い縁の下の力持ちである。 しかし、それによる性能向上は開拓しつくされており、 今後のアプリが大きく肥大していかない限り 性能向上は微々たるものになるというのが今回の結論だ。 (その意味ではメモリ喰いのVistaが出たことはCPUベンダーにとっては福音なのかもね!?)

マルチコアにおいては、コア数が2倍になると(2次キャッシュの場合)キャッシュ容量が 半分になったのと同様な事情となるわけで、この意味ではキャッシュ容量増大には まだ期待が抱けるかと思う。しかし、 単一コア換算に補正した容量値で考えた場合は 大容量キャッシュCPUに過大な期待は禁物であろう。

ILP水準の向上も限界、マルチコア化もソフトの対応が完了するまでは効果おあずけ、 キャッシュ増量も数世代後には効果が飽和...とすれば、intel、AMDがCPUコアに対して 打つ手は何なのか? Fusionの様にCPUコア以外の相乗効果を狙う以外に方法は残されていないのか?

ソフトの肥大化に期待するというのも妙な話だし、 技術的な打開策は何になるのか当サイト的には非常に興味がある。



1)
どういう事かというと...

まず、図の黒実線が「PC を1ノード100万で買った時」から「Cray XT4 等のそこそこ高いスカラ並列機」となった。 当サイトの論理は、「PCではスケーラビリティーが成り立たないから、京速計算機レベルではその効果を補正する必要性がある。」 というものである。しかし、XT4はHPC界の老舗Crayの製品だから立派な「餅屋」の製品である。もちろんスケーラビリティーに問題はないだろう。 (実際、同社のサイトにアクセスしてみたら、WRFという気象コードで10400CPUまでスケールする例が掲載されていた。)

つまり、最初の図では価格がいくらかには関わらずPCである限りは当サイトの論理が当てはまるわけだが、 確かに追加された図ではその点が回避できている。 スカラ機であるXT4がB/F比が高い領域でもコストパフォーマンスでベクトル機に勝るという論理はかなり強固に守られていると言える。 (バンド幅は理論値ではなく実効値である必要があるため、STREAMバンド幅で近似した場合は差がかなり縮まると思われる。だが、 さすがにコスト比を覆すまでには至らないと思われる。)

しかし一方で、最初の図はPCの場合を直接書き込んだものではない事をご本人が認めてしまったために、 論理的にカバー出来ない範囲が生じてしまっているように思う。

例えば、「ベクトル機のほうが価格性能比が良い領域がある、と思っている、ということは、ベクトル機は図の赤線のように振る舞う、 つまりはメモリバンド幅当りの価格が PC より安い、と思っている、ということです。 これは15年前にはそうだったかもしれませんが、今はそうではなくなっています。」 と書いてあるが、PCではスケーラビリティーが成り立たない事を認めてしまったために、 この話には「ノード数が少ない場合には」という枕詞が付くのでは?という当サイト流の反論を許してしまっている。

当サイトの考えはと言うと、ノード数が1台の場合は確かに15年前に負けていたのかもしれないが、 ノード数が京速計算機レベルの場合は今でもベクトル機のコストパフォーマンスはPCより良いと考えているわけである。 その理由は、PCはスケ−ラビリティーが極端に悪いので、京速計算機レベルでは実はコストパフォーマンスが 極端に低下してしまうからである。 (当サイトの論理を完膚無きまでに叩きのめす方針ならば、PCでもスケーラビリティーが成り立つという論理を構築する必要性がある。 そうでない論理構築と言うことは、つまり守備的ということだろう。)

具体的に言うと、当サイトが引用した図から見て、PCクラスタはそもそもノード数を無限大にしてさえ性能が京速計算機レベルに到達しないと考えられる。 京速計算機の目標性能が一台のSX6+より低いという事はあり得ないし、Dual Xeon, GBit, Speed-upの漸近線はSX6+に届かないからである。 ノード数が無限大でも性能が有限値までしか漸近しないということはコストパフォーマンスはノード数が増えるに従ってゼロに収束していくわけだし、 京速計算機レベルが性能目標の場合、PCクラスタでは性能が目標値に届かないのでそもそも比較評価の土俵に上がれない。 つまり、PCの価格が100万か20万かは結論には無関係な話となる。

今回のご指摘だが...これが情報関係の学会でオーサライズされた結論なら単に誤りの指摘ということだが、 プロ間でも論争中の命題の場合はご指摘の前にまず学会での定説を定めていただけるとありがたい...というのがアマチュアとしての第一感である。