CacheのABC
Computer Architecture, Third Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design) (CA:AQA)によればメモリアクセス性能を上げるには
平均メモリアクセス時間＝ヒット時間＋キャッシュミス率＊ミスペナルティ
となるので、ヒット時間(キャッシュにヒットした時のアクセス時間)をさらに短くするか、キャッシュミス率を下げるか、ミスペナルティ(キャッシュミスした時のアクセス時間)を下げるという方法がある。例えばL１ヒット時間が1ns(ナノセカンド、１０億分の１秒)でL２ヒット時間が5ns、メインメモリアクセスが150nsで、L１ヒット率が９割、L２ヒット率が９％、とすると、
平均メモリアクセス時間＝1 + 0.1*(5 + 0.1*150)=1 + 0.1*(5+15)=1+2=3ns
となる。これがL１ヒット率が５割で、L２ヒット率が25％、25％がメインメモリにアクセスするとなると、
平均メモリアクセス時間＝1 + 0.5*(5 + 0.5*150)=1 + 0.5*(5+75)=1+40=41ns
10数倍時間がかかるようになる。L１／L２／メインメモリへのアクセス時間はハードウェアによって決定されるので、キャッシュミス率を下げる事が性能向上の要となる。
CA:AQAの分類によってメモリアクセス時間を削減する方法を紹介すると
- キャッシュミスの削減
- キャッシュミスペナルティの削減
- 読みミスを書きミスより優先
- サブブロック置き換え
- early restart/critical word first
- ブロックしないキャッシュ
- ２次キャッシュ
- キャッシュヒットした時のアクセス時間の削減
- 小さいキャッシュ
- アドレス変換を避ける
- 書き込みのパイプライン
になる。棒読みした感じではあるが、ソフトウェアで制御できるのは、プリフェッチとかコンパイラによる最適化くらいなものである。
プリフェッチは文字通り、データが必要になる前にあらかじめデータをフェッチしておこうというものである。キャッシュにプリフェッチしたり、レジスタにプリフェッチしたりする。レジスタのプリフェッチというのは、単にメモリにアクセスしているだけなのだが、キャッシュミスをしても、その間他の命令が実行されていればデータが本当に必要になった時点までにデータを準備できればミスペナルティはなくなる。最近のプロセッサだとキャッシュミスをしても他の命令がストールすることなく実行できるので、このようなテクニックが使える。
ソフトウェアの最適化では、配列のマージ、ループの置換、ループの融合、ブロッキング、などのテクニックが紹介されている。CA:AQAにはcache pollutionという言葉は索引にも載っていなかったので、Intelの言葉なのかもしれないが(Hyper Threadingのように)、ひょっとしたらCA:AQAでは未知のテクニックなのかもしれない。
