miss(よく起こるので、なるべく避けるようにする)→メモリの値は入れる場所が分かれている。同じキャッシュブロックに入ろうとする。よって、効率的にキャッシュが使えなくなる。→つまり、キリのいい数では悪くなり、キリの悪い数だと良くなる場合がある。miss→ランダムにたくさんのメモリを触りまくると、うまくいかなくなる。・一番上にはCPUのレジスターファイル・レベル1キャッシュ・レベル2キャッシュ一般には、一バイトごとに関するのではなくて、16,32,64byte単位でキャッシュとメモリの間を行き来する。index)一番上のbitsをtagに使う(=tag)そこがvalidだったら、下位bitsで読めばよい。set.一号室の店員一つ、自分の入れる号室は決まっている→そうすると、柔軟性が無くなってしまう→だから真ん中のビットを使う。onetimeキャッシュが小さくて4色しかなかった場合。右側がメモリだとする。有効かどうか調べて有効だったらブロックを調べる。validタグが2つあるときは、両方調べる?最後は一番下を調べて、そこのワードをCPUに読んだり書き込んだりする。→柔軟性がある変わりに、個々の部屋が大きければ大きいほどタグを比較する回数が増える。→データと命令は異なるので多くのCPUではデータキャッシュとインストラクションキャッシュにかわる。→memoryに入らなければ仮想メモリを使ってdiskに入るPentium3ぐらいだと、associativityは4-way(基本情報でやったやつ)※要意味確認!!間違ってるかも。dataに書くだけで終わらせる。→毎回書いてると大変だから、MainMemoryに書かないこと→忙しいときは、キャッシュだけを使ってやる→L1とL2にだけ書く。memoriesに書く。→L2には書く、メインメモリーに書かない。プログラムの中で、ポインターとか使わないプログラムだったら配列が一番問題になる。典型的ないい確率だったら、L1は3-10%。localityアドレスは行順で繋がっている。キャッシュブロックが16byteだと4回に一回は外れる。一回外れると、3回当たる。64byteだと1回外れると、15回当たる。配列の場合は列順にアクセスされるから、毎回キャッシュから外れてしまう。→横並びに読み込めば、キャッシュに当たっていたのに。performance.教科書の表紙→先生のお気に入り。今は飛ばす?・大事なこと配列をたくさんアクセスしたときに、飛び飛びにアクセスするのは大損する・世の中でとってもよくやる計算行列の掛け算。どれだけよくなるのかを話す。普通の行列の掛け算のプログラム→3重ループ普通に3重ループで書くとあまり良いことにはならない→全体のキャッシュサイズとキャッシュブロックのサイズを考えてプログラムを書く。ココはN回読まれる・Bの各要素もN回読まれる。・Bの各要素もN回読まれる。・Cは内積だから、N回の足し算はためておいて、最後に計算する。→AやBに頻繁にアクセスするので、そこをうまくやらなくてはいけない。wordsN)はとてもでかい。よって、個々の配列のごく一部しか、L1やL2には乗っからない。そのときどうすればよいか?→配列のプログラムを良く見て、for文一番内側のプログラムに注目する。→添え字に注目→アクセスパターンを見る→工夫をすれば添え字kを一番外側に持っていくことが出来る。0.5詳しくは言わないが工夫のしがいがある。添え字の順番→3の階乗個ある一番内側のループを図ってみた→何故かijkの方が早い→キャッシュミスレートだけでは分からない。行列の掛け算をやるときどういうやりかたがいいか?→ブロッキング小行列4つの小行列。小行列ごとで計算した方が嬉しい。→AやBが小さいとキャッシュに載りやすいから。大きな配列ではまずい。小行列でやっては差し込む、これを繰り返す。プログラムがややこしくなる50loopぐらいになる。→一見難しいように見えるが、小行列の掛け算だからキャッシュにあたる。キャッシュの升目はかなりでかい!下に行きまくると外れまくるが、4×4とか小さいレベルなら外れない→だから小行列を使う。elements]以下で収まっている。→割といい性能が維持されている→2倍ぐらい早い。メモリマウンテンは来年のお楽しみ。個々の性能に非常に依存する。期限:年明け→2次元配列をひっくり返す。