Cache Memories

Topics
・Generic cache memory organization
・Direct mapped caches
・Set associative caches
・Impact of caches on performance

Resource:class12.ppt, class14.ppt

northbrigde
southbrigde

【General Caching Concepts】
２つのことを考える

・Placement policy
→もってきた値をどこにおくか

・Replacement policy
→誰かを追い出さないと、他の値は入れない→つまり、誰を追い出すか


-Types cache misses-

・Cold(compulsary) miss
→最初は失敗する(キャッシュが溜まるまでの間)→cf.冬の朝の車

・Conflict miss(よく起こるので、なるべく避けるようにする)
→メモリの値は入れる場所が分かれている。
→キャッシュがたくさんあるのに3号車しか使わない(結構よく起きる)
→キャッシュは十分大きくても、各データ同士の関連性が高いと、
同じキャッシュブロックに入ろうとする。よって、効率的にキャッシュが使えなくなる。
→つまり、キリのいい数では悪くなり、キリの悪い数だと良くなる場合がある。

・Capacity miss
→ランダムにたくさんのメモリを触りまくると、うまくいかなくなる。
→そもそもキャッシュが小さすぎた？


Lecture14　-Cache Memories Oct. 10, 2002-
【Inserting an L1 cache Between the CPU and main memory】
キャッシュの階層↓
・一番上にはCPUのレジスターファイル
・レベル１キャッシュ
・レベル２キャッシュ

一般には、一バイトごとに関するのではなくて、
16,32,64byte単位でキャッシュとメモリの間を行き来する。

Line size→行き来するデータの単位

FeaturedとActualの結果は微妙にずれている→理由は後で話す

L1だと　Latency　3cycle　⇔　L2だとLatency　10cycle

このぐらい変わる！

それぞれのcache blockには管理情報(validとtag)が付いている
→どこのメモリから持ってきたのか(tag)
→意味がある情報なのか(valid)→1 or 0?

このまとまりをキャッシュラインと呼ぶ
キャッシュラインのまとまりをキャッシュセットという
キャッシュセットの集まりをキャッシュという
B*E*S=Cとなる


【Addressing Caches】
1回に動かせるデータ単位を、大体三つぐらいにぶった切って
真ん中のbitsを「どの部屋に入っているか」に使う(=set index)

一番上のbitsをtagに使う(=tag)
そこがvalidだったら、下位bitsで読めばよい。(=block offset)

The word at address A is in the cache ifthe tag bits in one of
the lines inset match .
The word contents begin at offset bytes from the beginningof the block.

→上位ビットが色んなところにバラけるのが良いところ


【Direct-Mapped Cache】
Simplest kind of cacheCharacterized by exactly one line per set.

一号室の店員一つ、自分の入れる号室は決まっている
→そうすると、柔軟性が無くなってしまう→だから真ん中のビットを使う。

Set selectionn
→Use the set index bits to determine the set of interest.

Line matching and word selectionn
・Line matching: Find a valid line in the selected set with amatching tag
・Word selection: Then extract the word

Line matching→validであってindexがあって、blockの中のしかるべきワードを使うこと？
Word selection→省略

【Why use Middle Bits as Index?】
High-Order Bit Indexing
・Adjacent memory lines wouldmap to same cache entryn
・Poor use of spatial locality

Middle-Order Bit Indexing
・Consecutive memory lines mapto different cache lines
・Can hold C-byte region ofaddress space in cache at onetime

キャッシュが小さくて4色しかなかった場合。右側がメモリだとする。
同じ色のところに入れる→キャッシュがぶつかりまくる(左側)
→真ん中を使えばうまくバラける→よって、昨今のCPUの大原則となっている

最初のラインに入っても二つ目のラインに入っても良い実際のCPUでは18ways
真ん中を使って部屋を選ぶ

上位の0110ってタグを見て、タグと一致するかどうか調べて、
有効かどうか調べて有効だったらブロックを調べる。validタグが2つあるときは、両方調べる？

最後は一番下を調べて、そこのワードをCPUに読んだり書き込んだりする。
→柔軟性がある変わりに、個々の部屋が大きければ大きいほどタグを比較する回数が増える。
→データと命令は異なるので多くのCPUではデータキャッシュとインストラクションキャッシュにかわる。
→memoryに入らなければ仮想メモリを使ってdiskに入る

Pentium3ぐらいだと、associativityは4-way

(基本情報でやったやつ)※要意味確認！！間違ってるかも。
write-through方式→CPUが計算した結果は、L1 dataに書くだけで終わらせる。
→毎回書いてると大変だから、MainMemoryに書かないこと
→忙しいときは、キャッシュだけを使ってやる→L1とL2にだけ書く。

write-back方式→CPUに書くのはL2がいっぱいになったときだけ、そういう方針のこと

write allocate→ライトアルケイトしない場合、書いたデータはまた読む確立が高いから、Main Memoryまで書かなくても良い？
→キャッシュに書く必要がない場合、キャッシュに書く動作を省略して、直接Main memoriesに書く。→L2には書く、メインメモリーに書かない。

プログラムの中で、ポインターとか使わないプログラムだったら配列が一番問題になる。
典型的ないい確率だったら、L1は3-10%。L2は 99%はあたるのが良いプログラム
→L2からもれるのは相当悪いプログラム

【Cache performance Metrics】
Miss Raten
Fraction of memory references not found in cache(misses/references)
Typical numbers:
3-10% for L1
can be quite small (e.g., <>Hit Time
Time to deliver a line in the cache to the processor (includestime to determine whether the line is in the cache)
Typical numbers:
1 clock cycle for L1
3-8 clock cycles for L2

Miss Penalty
Additional time required because of a miss
Typically 25-100 cycles for main memory

hit time1 clock cycle for L13-8 clock cycles for L2

Miss PenaltyTypically 25-100cycle
→キャッシュを外れると一桁以上遅くなる→桁違いに遅くなる

ではどういうプログラムを書けばよいのか？

【Writing Cache Friendly Code】
・Repeated references to variables are good (temporallocality)
・Stride-1 reference patterns are good (spatial locality)

キャッシュにやさしいプログラムの書き方→temporal locality

配列を書くときはstride-1で書くのは悪くない→spatial locality

アドレスは行順で繋がっている。

例えばキャッシュブロックが16byteだと4回に一回は外れる。

だから、一回外れると、3回当たる。

64byteだと1回外れると、15回当たる。

配列の場合は列順にアクセスされるから、毎回キャッシュから外れてしまう。
→横並びに読み込めば、キャッシュに当たっていたのに。。。

【The memory mountain】
Read throughput (read bandwidth)
Number of bytes read from memory per second (MB/s)

Memory mountain
Measured read throughput as a function of spatial andtemporal locality.
Compact way to characterize memory system performance.

教科書の表紙→先生のお気に入り。ただし、今は飛ばす？

・大事なこと配列をたくさんアクセスしたときに、飛び飛びにアクセスするのは大損する

・世の中でとってもよくやる計算行列の掛け算。

どれだけよくなるのかを話す。普通の行列の掛け算のプログラム→3重ループ

普通に3重ループで書くとあまり良いことにはならない
→全体のキャッシュサイズとキャッシュブロックのサイズを考えてプログラムを書く。

O(N^3)で我慢する

N reads per source element　ココはN回読まれる

・Bの各要素もN回読まれる。
・Bの各要素もN回読まれる。
・Cは内積だから、N回の足し算はためておいて、最後に計算する。

→AやBに頻繁にアクセスするので、そこをうまくやらなくてはいけない。

【Concluding Obsercations】
Programmer can optimize for cache performance
How data structures are organized
How data are accessed
Nested loop structure
Blocking is a general technique

All systems favor “cache friendly code”
Getting absolute optimum performance is very platform specific
Cache sizes, line sizes, associativities, etc.
Can get most of the advantage with generic code
Keep working set reasonably small (temporal locality)
Use small strides (spatial locality)

【仮定】
Line size = 32B (big enough for 4 64-bit wordsN)はとてもでかい。
よって、個々の配列のごく一部しか、L1やL2には乗っからない。
そのときどうすればよいか？

→配列のプログラムを良く見て、for文一番内側のプログラムに注目する。
→添え字に注目→アクセスパターンを見る
→工夫をすれば添え字kを一番外側に持っていくことが出来る。

前提として持っているべき知識
・addressは横に続いていること→row-major order
・Stepping through columns in one row
・ブロックサイズが十分大きかったら、compulsory miss rate = 4 bytes/BB = ブロックの大きさ→あんまり高くない
・配列を縦にアクセスすると、空間的局所性がいかせない→miss rate 100%
添え字が外からijk,kij,jkiなどがある一番内側のイテレーション一回分でどのぐらい
ijk→misses/iter = 1.25
kij→misses/iter = 0.5
詳しくは言わないが工夫のしがいがある。

添え字の順番→3の階乗個ある

一番内側のループを図ってみた→何故かijkの方が早い
→キャッシュミスレートだけでは分からない。
→理由は、コードのスケジューリング、レジスターなども絡んでくるから

配列が小さいと数Bで済む！

【！！課題の重要なヒント！！】
行列の掛け算をやるときどういうやりかたがいいか？→ブロッキング

小行列
4つの小行列。線形台数を復習
小行列ごとで計算した方が嬉しい。
→AやBが小さいとキャッシュに載りやすいから。
大きな配列ではまずい。小行列でやっては差し込む、これを繰り返す。

ただし、プログラムがややこしくなる50loopぐらいになる。
→一見難しいように見えるが、小行列の掛け算だからキャッシュにあたる。

キャッシュの升目はかなりでかい！下に行きまくると外れまくるが、
4×4とか小さいレベルなら外れない→だから小行列を使う。これがアイデア。


結果他のアルゴリズムは、キャッシュから外れまくるが、小行列のアルゴリズムは、
10[cycle per elements]以下で収まっている。
→割といい性能が維持されている→2倍ぐらい早い。

メモリマウンテンは来年のお楽しみ。

Programer can optimize for cache performance
→ループしているところが一番→ループの入れ異なっているところに注目する

All systems favor "cache friendly code"個々のコンピュータシステムは、
個々の性能に非常に依存する。

一般的な原則としては、working set→アクセスするメモリの総量を小さくする左側をアクセスするのはlarge stride→ストライドがでかい！

【課題説明】
やること：画像処理
期限：年明け

→2次元配列をひっくり返す。それだけ。でもバカにはできない。90℃回転するプログラム。

要素の数は4MB
→つまり、そこらへんのPCではキャッシュに載らない→如何にうまくキャッシュに載せるかを考える。


結果よりも工夫と考察を評価する。キャッシュに関しては出来るだけ記載する。
勿論プログラムのソースも出す。

行列の転置＋行列の逆転この画像は壊さないで、別のものに入れてよい。画像を壊して、そこに置くとなると、ちょっと大変だから。

matrix_t[N][N]を2次元配列方とする。
・src=source
・dst=destination
このプログラムは難しい。
ソースに対しては気持ちがいいプログラムだと、デスティネーションに対して悪くなる
デスティネーションに対して気持ちがいいプログラムを作ると、ソースに対して気持ち悪くなる。


さらにがんばって見たい人
【発展課題】
・今まで見たいにgccではなくgcc特有の機能を使う
・CGG以外のコンパイラの利用
・アセンブリコードの挿入
・複数のマシンでの実験

ノートPCでやるとうまいデータが取れない可能性がわずかにある。
辺にいい結果が出ることがある。→節電の設計がたくさんあるから。
→CPEが計算しているときはクロックを供給する
→メモリ使ってCPUが暇になると、CPUにクロックの供給を止める設計のBIOSがある。
→サイクルカウントが止まって進まないPower savingをoffにする。
→コンセントに差して使う。

データが変だと思ったら、すぐ質問をする。(色々な要因が複雑に絡まっているから)

CPEについて。
最適化しないと10。大抵は１～100の間
→1以下の人は正確に測れていない
→100以上の人は頑張らなさ杉。
1を若干数切ることはありうるが、0,0Xという値は無い。

配列のサイズは大幅に変える。
・等差数列
・等比数列
・1,5,10,50,100,500は良くない

1,2,4,8,16,32も微妙
→メモリが特定の部屋にいく傾向がある。
キリのいい数字はプログラムの性能を悪くする。
若干きりの悪い数値も使ってみるべし！

Tweet