ライン衝突、TLBあふれ

アクセスするよう素数nを比較的小さい値に固定し、ストライドの間隔mを大きくしていくと、配列のサイズがキャッシュサイズの２倍の倍数になったとき、ライン衝突が起こり、性能が低下します。いくつかのライン上に全てのアクセスが集中するため、nが小さくキャッシュサイズに余裕があるにもかかわらす、毎回キャッシュミスが起きてしまうためです。また、mがキャッシュの1way分のサイズ（＝キャッシュサイズ／way数）の倍数のとき、全てのアクセスが同じラインにくるため、さらに性能が低下します。

また、配列TLBのサイズを超えると、TLBあふれによる大幅な性能低下が起こります。この時、ストライドの間隔mがページサイズ以下の場合は、mを増やすとページ更新の頻度が上がる為に性能が次第に低下していきますが、ページサイズ以上になった時点で毎回新しいページが必要になり、上記のライン衝突部分以外では性能はほぼ一定になります。

プログラム：line.c

実行結果（クリックすると詳細な図を表示）

図１．n=32	図２．n=64
図３．n=128 その１	図４．n=128 その２
図５．n=256 その１	図６．n=256 その２
図７．n=512 その１	図８．n=512 その２

全体的に、原因不明の性能低下が多く、あまりきれいなグラフは得られませんでした。

どのグラフでも、mが大きくなると等間隔で性能が低下する部分がでてきましたが、mが小さいうちは規則性は見られませんでした。それぞれ何の倍数のところで性能が低下しているのかをまとめると次のようになります。m×nが一定、もしくはmが一定の部分が同じ列にくるようにしてあります。

mの間隔が8K（64KB）のところでは、n=32のとき以外では性能低下が起こっています。間隔が64KBと１次キャッシュの容量より大きいので、２次キャッシュのライン全衝突と考えられます。ここから、２次キャッシュは4-way set associativeだろうと考えました。（256KB÷64KB＝4より。）しかし、実際には２次キャッシュは8-way set associativeでした。

右から二列目の性能低下は、m×nが64Kの倍数、すなわち配列のサイズが512KBの倍数のときです。これは２次キャッシュの容量の２倍なので、２次キャッシュのライン衝突によるものと考えられます。それ以外にも、m×nが一定の値で遅くなっていますが、原因はよくわかりません。これらの中には、あまり大きな変化ではないものもありますが、はっきりとその部分だけ遅くなっているものもあります。

また、nが128以上の場合、2のべき以外の場所での速度が途中で次第に遅くなっていき、m=512で一定になっています。このときの間隔は512×8＝4KBで、TLBのページサイズと一致しました。TLBのエントリ数は64なので、nがTLBのエントリ数を超えた場合にTLBあふれが起こっていることがわかります。

nが64以下の場合、m×n＝64K（512KB）以上ではなぜかmが小さいときより速くなっています。これは、配列のサイズが２次キャッシュの２倍以上になったときに相当します。何か理由がありそうな値ですが、原因はよく分かりません。

Prev. ストライドアクセス Next ループアンローリング
性能測定メニューへ戻る

最終更新日：2003/1/28