ノルム計算
１．実験環境
| マシン名 ： |
serra |
| CPU ： |
Pentium-M |
| コンパイラ ： |
gcc |
| コンパイラオプション ： |
-O2 |
２．実験結果
gnuplotでグラフを作成した。
このマシンのキャッシュサイズ等の理論値は調べてもわからなかったので（cpuinfo、dmesg等）、
実験の結果から推測される値を以降の実験で用いることにする。
２．１．ベクトル長nと性能の関係
このグラフを見ると、ベクトル長が長くなるにつれて性能が上がっていることがわかる。
約32Kでピークになった後に一度性能が低下し、１M付近でまた低下している。
性能が低下したこの2つの場所を拡大して詳しく見てみることにする。
32Kを過ぎると一気に80Mflops程度性能が低下した。これは一次キャッシュのあふれによる
ものだと考えられる。そのあとは多少上下していたが大きな変化はなかった。
１Mを過ぎると再び性能が低下し始め、７M程度まで徐々に低下し続ける。
これは２次キャッシュのあふれによるものだと思われる。
２．２．ストライドと性能の関係
上の実験より１次キャッシュは３２K、2次キャッシュは１Mであると予測できる。
そのそれぞれについてストライドを変更して性能との関係を見る。
n=128K/mとして、配列全体が2次キャッシュに入るようにした。
ストライドが８までは性能が低下し、以降安定したが、１２からまた上昇し始めた。（原因不明）
ストライドが８の時に安定したので１次キャッシュのラインは８ワード=６４バイトと予測できる。
n=16M/mとして、配列全体が2次キャッシュに入るようにした。
ストライドが８までは性能が低下し、以降安定した。
ストライドが８の時に安定したので２次キャッシュのラインは８ワード=６４バイトと予測できる。
二つのグラフをひとつにまとめてみると、一次キャッシュのグラフのm=8の値と
二次キャッシュのグラフのm=1の値がほぼ等しいことがわかる。
２．３．ラインアドレス
データ数n=64(＜１次キャッシュのライン数=３２K／６４=５１２)で固定し、
ストライドを広げてみると、所々で性能が低下していることがわかる。
m=8の倍数の時、128、256の時に大きく性能を落としていることがわかる。これは
(ストライド：m=128)×(データ数：n=64)×(double型：8byte)=64K(=一次キャッシュの倍)より、
ちょうどラインを毎回読み直さないといけなくなり、そのために性能を落としているのだと考えられる。
このことを確かめるため、mが64の倍数の場合を調べる。
m=64の倍数の時、128の倍数の時に性能を落としていることがわかる。
さらに、1024の時にやや性能を落とし、2048の時に大きく性能を落としていることがわかる。
詳しく調べるため、mが512の倍数の時を見てみる。
m=512の倍数の時、2048の倍数の時に大きく性能を落としていることがわかる。
mが2048の倍数の時に性能を落としているのは、読み直しが全て同じラインに当たっているためだと思われる。
なぜ1次キャッシュサイズ=4096（=32Kbyte）ではないのかは、アソシアティビティによると思われる。
（アソシアティビティについては2.5で述べる）
さらに、最初のグラフを見てみると、mが128Kの時に大きく性能を落としていることが読み取れる。
これは二次キャッシュのライン衝突によるものだと思われる。
２．４．TLB（Translation Look-aside Buffer）とページ
TLBのサイズを測定するため、ストライドの数を固定し、データ数を変化させる。
データ数n=32のとき、m=256で一次キャッシュ衝突。
m=4096で急に性能が低下し、キャッシュサイズの倍数を外しても性能が低いまま。
データ数n=64のとき、m=128で一次キャッシュ衝突。
m=2048で急に性能が低下し、キャッシュサイズの倍数を外しても性能が低いまま。
データ数n=128のとき、m=64で一次キャッシュ衝突。
m=1024で急に性能が低下し、キャッシュサイズの倍数を外しても性能が低いまま。
データ数n=256のとき、m=32で一次キャッシュ衝突。
m=512で急に性能が低下し、キャッシュサイズの倍数を外しても性能が低いまま。
以上のことより、（ストライド：m）×（データ数：n）=131072（=1Mbyte）のときに
性能を落としていることがわかる。よって1MBでTLBを使い果たすと予測される。
データ数n=512のとき、m=16で一次キャッシュ衝突。m=256で性能が低下し、さらに512で
性能が低下している。これはm=256のときはTLBあふれが2回で1ページ、512のときは毎回
新しいページが必要になるためだとすると、ページサイズは512（=4Kbyte）だと考えられる。
するとエントリ数は256ということになるが、この数は多すぎる気がする。
データ数n=1024のとき、m=8で一次キャッシュ衝突。m=128、256、512で性能が低下している。
これはm=256のときはTLBあふれが4回で1ページ、256のときはTLBあふれが2回で1ページ、
512のときは毎回新しいページが必要になるためだと考えられる。
２．５．アソシアティビティ
m：ストライドをキャッシュサイズ（=4096）にし、n：データ数を1024とし、l飛びに次々とアクセスする。
もしl飛びのデータが異なるラインにあたるときはひとつのラインにJ個のデータが載ることになり、
l飛びのデータが同じラインに当たるときはひとつのラインに2J個のデータが載ることになる。
J=1のとき、性能は落ちないと思ったが、l=4096のときに大きく性能を落とした。
2way set associativeではない？
J=2のとき、l=2048のときに性能を落とし、l=4096のときに性能を上げている。
J=3のときもl=2048のときに性能を落とし、l=4096のときに性能を上げている。
３つのグラフをまとめてみると、l=4096のときに何か起こっているようである。
この値は一次キャッシュの大きさであるのでそのことに関係しているのかもしれない。
2way set associativeでないと、2.3のラインアドレスの際の説明ができないので、
この実験はよくわからない結果になってしまった。
２．６．パイプライン
データ数：n=1024とし、アンロールを行い性能の変化を調べる。
ループアンローリングを３回したときが一番性能が上がった。
結合変換を５回したときが一番性能が上がった。
比較すると、ループアンローリングを３回行ったとき以外は結合変換のほうが性能が上がった。
アンロールが３回のときは結合変換をしないほうがよい結果になった。
戻る
