CPUにおける仮想アドレスと物理アドレスについて

MAP＝関数。
「V→P U 空集合」の順番にアクセスする
V＝仮想アドレス
P＝物理アドレス
U＝ユニオン

[たとえ話]]
起き上がって仕事をしようとしても、今まで休んでいたから、
以前使っていたメモリ使用領域はDiskに追い出されていることがある


[想定されるケース]
MAPで物理アドレスが求まる場合と
物理的なメモリには無くてDiskに追い出されている場合(→空集合へいくケース)がある。

//深い話については3年次のOSの授業でやる。
！！表は試験に出ないけど、表の理解はとても大事！！

[Pageについて]
今の多くのコンピュータは4kB(4096=12bit)単位でメモリ領域間を移動する。
1pageが標準。
2^10≒1,000
2^20≒1,000,000
ページは読み書きしたいアドレスが属する番号を示している。


[仮想アドレス]
仮想アドレスのうち
上位20bitは残る→PPNへ
上位20bitを使って、メインメモリの中にキャッシュされているページテーブルの場所を示して、
ページテーブルのエントリーを見に行く。
※ページテーブルは必ずどこかにある！


[validの役割]
validが立っている(valid=1)と、
validが立っていない(valid=0)場合がある
→ページフォールトになるととても時間がかかる。

virtualアドレスをコンピュータの中のアドレスに変換する(=phisicalアドレスを作る)。


[仮想アドレス下位]
下位12bitは上位20bitで得たアドレスを読み書きするのに使用する。


[単語説明]
MMU＝Memory Management Unit :メモリを管理するユニット
VA=Virtual Address :仮想アドレス
PTEA=Page Table Entry Address :情報のありかを示す場所。(一種の索引で「どこを見るか」ということ)
PTE= Page Table Entry :情報の中身？
PA=Physical Address:物理アドレス


[MMUの動作]
一般的に一往復多い(②と③の部分)→もったいない。
最近のプロセッサーはそこを頑張ってなんとかしようとしている cf."TLB"
キャッシュに当たったとしても②と③はもったいない。


[悲惨場合]
1. ②でMMUにない場合
2. ④Exceptionで"Page faultだった"という報告をする。
→その後の作業はOSに任せる
3. victim pageをDiskに追い出しnew pageをキャッシュに置く。
→この動作もまた、とても時間がかかる

(補足)
ページテーブルのアドレスがあればMMUに帰ってくる。
PAもキャッシュにあればProcessorを介してMMUに戻る。
無ければL２やMemoryにアクセスしていく。


[往復問題]
L1にあったとしても、L1キャッシュが込んでくると、
他のメモリ参照のせいで、キャッシュしたのが追い出されてしまう。
また、読み出すのに少なくとも1サイクルの遅れがある。

・MMUの中にキャッシュがあればよいのではないか？
→(HOTな話題)TLB = Translation Lookaside Buffer
small hardware cache in MMU

ハードウェアでそもそもメモリを扱おうとするプロジェクト？
ページテーブルは大きい。1Pは4kだから運十万ぐらいにいく。
だからそのうちの、とってもよく使う部分だけをMMUに入れてしまおうという内容。

[第2ラウンドの話]
TLB hit
TLBに物理アドレスと論理アドレスの関係の表がキャッシュされていたら、
VPN(= Virtual Page Number)で聞き、PTEで返してもらう。
結果：1サイクル得する。

不幸にもTLBにキャッシュされていなかったら、キャッシュメモリに行って2往復する。

なるべくメモリをうまく使えるプログラムを作って、VAの無いようにする。

実際にはTLB MissはあまりMissらない。
→何故？→教科書参照


[64bitと32bitについて]
1Pは4kB単位
最近の64bit(athronとか)は、全部のbitを使うわけではない。

PTEが４バイトで済む→物理メモリの何テーブル目かが分かる。
64bitマシーンはhardwareサポートしている。256GBある？→ただし効率が悪い。
→表というのは大きくなりすぎると、検索するのが大変。
→索引を幾つかに分ける。索引のための索引を作る。cf.Level1 table ⇔ Lebel2 tables
たくさんある索引のうちのどの索引にあるか調べる。
→2 Lebel Tables、一般的なpentiumでは大体用いられている。

256GBの使ってないものを置く必要性をなくしている？


[Case study]
-Pentium系のマシンはどうなっているのか？-

INTEL P6
core2とかpentiumとかその辺のマシンについて
Pentium →93年に出来た。　cf.教科書参照15-213, F'06
2～3年前はPentium4

ただし、pentium4はpentium3にはない問題が浮上した
→発熱が大きい

INTELもここら辺で気付いた。
・4GHzを出そうというプロジェクトを辞めて、Pentium3に戻り、拡張してCore2duoを作った。
→熱の問題に対処した。
dual core→一個のCPUにたくさんのプロセッサを乗っけること。

だから、Pentium4を勉強する必要はあまり無い。

※技術が進歩しているので教科書の具体値は微妙に違う。

[P6 Memory System][
この図はそれほど勉強する必要は無い。


[Review of Addreviations]　略語集

[Overview of P6 Address Translation]
これが理解できたら大丈夫。

CPUは左上にある。
一周するのには、様々なルートがある。→様々なサイクル数が考えられる。
Virtual　Addressは上と下で20bit=VPN, 12bit=VPOに分かれている。
VPOはPhysical Addressを読み書きする。＝PPO
PPNとPPOでキャッシュを見に行く。
CO＝Cache offset (5bit)
L1は一個ずつの箱が32bit?
全部で512個
cf.車両。店員512名。隣の列車には移れない。

CI = Cache Index :索引
CT = Cache Tag :聞きに行くためのタグ

見つからなかったら、残念ですね。ということでL2 and DRAMに行く。
→とても遅くなります。


[VAの上位20bitの部分について]
ページテーブルはどういう風になっているのか。
1ページ＝12bit
あまり利用されないPage Tableは遠いところに追い出される。

PDBR=Page Directly Base Register


[今日のスライド9P]
さっきの絵の左下の拡大図
20bitをさらに10bit/10bitに分けて、
VPN1でLevel 1を、VPN2でLevel2 Tablesを示す。
レベル１のエントリ…この部分はあまり理解しなくても良い。
//省略


[大事なところ＝一番うまくいくケースについて考える]
VPNがPPNを効率的に引ける場合。
TLBはキャッシュと大体同じ構成をしている。
本当に書いているかどうかはTLBTと一致しているかどうかで調べる。
店員は64ページ。TLBはほぼ確実に当たってほしい。


[製作者の意図する理想]
64P×4kB=256kBぐらいのメモリアドレス空間はとても早く実行してあげましょう
それ以外は遅くなってしまうでしょう。

TLBIで何号車にいるかを調べる。
TLBTで比較。

コレがうまくいくと、あとはキャッシュにいく。

アドレスを計算するためのキャッシュ＝TLB
データを計算するためのキャッシュ＝L1,L2,Memory and so on

VPNの仮想番地から物理番地を求めるにはある程度の手間がかかる。
キャッシュを求めるためには、またある程度の手間がかかる。

キャッシュの切れ目に注目すると、
→一致している！
→VPOはPPOと変わらないので、VPIがごちゃごちゃやっている間にキャッシュの表を引く作業を実行している。


[CPUの見方]
キャッシュがどれだけ乗っていたか。
テストプログラムからassociabiltyを見ている。

例、先生のCPU
L1は32kB
L1 8way
Line size 64kB

一個64biteが８個並ぶ。←キャッシュセット
512kB/setが縦に64set並んでいる。


[TLBの話]
L1 D-TLB
Entries 128
Associavilty 4-way
□□□□
↑Entry

コレが
□□□□
□□□□
…
□□□□
↑32setsある。


[何故ストライドアクセスでスパイクが起こるのか？]
//Page2参照

ストライド1024kBで何が起こっているのか。
----------------------------------
・stride 1024=1024*int=4kB
4kB毎にアクセスする→1 pageあたり一個のIntegerしか読まない。
つまり、全部で256 pageにアクセスする。
256 pageの命令でload/store命令を起こす。

つまり、
129個目をアクセスするときは、先客を追い出す必要がある。
よって、後半のアクセスはTLBは外れて追い出しながらアクセスしなくてはならない。

→よって、2回目以降の計測は、TLBがはずれまくるゾーンとなってしまう。


・stride 512 = 512*int = 2kB
→1 page(4kB)あたりにintegerが２個ある。
→128 page分のアドレスが作られる。
128 pageの空席がある。
→for loopなので、制御命令も含めると微妙に追い出されてしまうこともあるが、ほぼ全員座れる。
TLBは完全に満杯の状態だと右上がりに上昇する。

規則的な(64byte毎の)スパイクについて
stride 64:256kBおきにアクセスしている。
TLBに関しては問題は多分起きていないだろう
→他の理由があるはずだ。


さっきのアドレス表を思い出す。
PA 64
□□□□←6bit
↑6bit
全部で64×8＝512 lines (entries)
つまりL1キャッシュに８つの座席がある？

64bit = int 16個分

-------------------
■■■■
-------------------
□□□□
-------------------
□□□□
-------------------
□□□□
-------------------
■■■■
…

4lineおきに使われる。→全てのlineが有効活用出来ない

最初：L1cacheを追い出しながらやる。
２回目の測定を始めると、後半を追い出しながら前半が入って息。
L1cacheの追い出し、追い出されが毎回起きている。
同様の理由で、stride 128とかも起こる。

画像を弄るときは1024*1024よりは1025*1025にした方が良い。
→2のべき乗は要注意

試験の話。
PC以外なら何でも持ち込み可能。

[質疑応答]
・２のべき乗の問題について
000/000000
100/000000
1000/000000
1100/000000
…
↑下位6bitは使われない。→使われないsetが存在する。

Tweet

The Memory Mountain ver 2

(↑さっき計測したメモリマウンテン。Throughput≒3500。うちのPCはやれば出来る子らしい)

こんなもんかなぁ。

最後の方の計算式ちゃんとあってるんだろうか・・・ちょっと不安だ。

まぁ心配したところでどうしようもないか。

でもまぁ、今日でフーリエ実験も終わったし、CPEの計測も…まぁこれでpre完成ってことにして、

残るは、フーリエ発展課題と、数学B課題と、まだ見ぬプログラミング言語論課題03か。

さっさと終わらせて、期末対策に入ろう。

CPEの計測 ―行列N×Nの90度左回転―　[図、表、ソースコードは省略]

目次
0.　動作環境
1. 実験内容
1.1 ドライバの作成
1.2 最適化の工夫をした関数を揃える
2. 実験結果
2.1 分割した場合の測定結果
2.2 他最適化に関する工夫の測定結果
3. 考察
3.1 最適化の観点から実験結果を解析/追加実験
3.2配列の上限要素数”ARRAY_MAX”とCPEの関係
4. 感想・まとめ
5. 参考資料
6. 添付資料
添付資料1 “ドライバex02a.cのソースコード”
添付資料2 “測定に用いたアルゴリズム(一部)”



0.　動作環境
本実験は全て、以下のCPUをもつノートPCで実験を行った。
(CPU-Zの実行結果と、mountain.cの実行結果を図示したもの)

/*picture is abbreviated*/

Clock frequency is approx. 1709.9 MHz

1. 実験内容
本実験は、以下の手順で行った。
1.1 ドライバの作成
1.2 高速化の工夫をした関数を揃える

1.1 ドライバの作成
　本実験では、以下の仕様を満たすドライバが必要である。
・ 行列N×Nを扱う2次元配列Matrix
・ Matrixを90度左回転するアルゴリズム
・ 任意のNに対してサイクルカウント値を測定し、その後CPE値を求める関数
よって、本実験を開始するために、まず上記の条件を満たすドライバを作成した。ドライバのソースコードは6.添付資料1に示した。
また、本実験で使用したプリプロセッサ・構造体・関数について、その仕様を以下に示す。

　-プロプロセッサ-
ARRAY_MAX
本プログラムにて用いられる、各配列の各要素の限界値を指定する。サイクルカウント値の測定結果の保存にも使われるので繰り返し回数(LOOP)以上の値をとることが望ましい。

　SPLIT
行列N×Nをいくつに分割するかを定義する。

　LOOP
関数func内で、サイクルカウント値を測定する回数を定義する。

　STANDARD
サイクルカウント値が観測された回数が「信用できる」と思える観測回数の定義。(ただし、本実験では結果の分散が激しかったので、“1”で観測した)


-構造体-
Matrix
行列N×Nを実現するためのint型2次元配列

Item
サイクルカウント値に関する情報を保存する構造体
doble cycle[ARRAY_MAX]
サイクルカウント値を保存する。
int count[ARRAY_MAX]
そのサイクルカウント値が観測された回数を保存する。


-関数-
void initialize(int a[], int N)
コマンドライン引数から得た値をNとし、行列N×Nの各要素に乱数を格納する。また、構造体の中身を初期化する。

　void showMatrix(Matrix m, int N)
デバッグ用関数。行列mの各要素を出力する

void showITEM()
Itemの内容を全て出力する。

void swapITEM(int i, int j)
Item a[i]とItem a[j]の内容を交換する。
void insertionSort()
Itemに対して、サイクルカウント値を基準とした挿入ソートを行う。

double getCycle(Item a)
Item aの中から複数回観測された小さな値を出力する関数。ただし、Itemの内容が既にソートされている必要がある。

int saveCycle(double cycle)
観測されたサイクルカウント値が初出ならば、そのサイクルカウント値を登録し、既出ならば、その出現回数をインクリメントする関数。

　void native_rotate(Matrix src, Matrix dst, int N)
行列srcを90度左回転させた結果を行列dstに格納する関数。

　void native_rotateA(Matrix src, Matrix dst, int line, int column, int N)
関数native_rotateを任意の数に分割して行う関数。例えば、行列64×64を8×8マスに分割した場合、各マスに対して計64回の90度左回転作業を行う。

void check_matrix(Matrix src, Matrix dst, int N)
行列dstが行列srcを90度左回転した行列と同じであるかどうかを確認する関数。

　void func(Matrix src, Matrix dst, int N)
行列srcの各要素を90度左回転させた位置に格納する。元の要素を上書きしないように、格納先は行列dstとする。また、この関数内で、サイクルカウント値の測定を行い、複数回観測された小さなサイクルカウント値を出力する。CPEはメイン関数で求める。

main()
仕様を満たすように各関数をそれぞれ実行していく。また、複数回観測された小さなサイクルカウント値を求め、そのCPEを出力する。

1.2 最適化の工夫をした関数を揃える
　今回の課題では、以下のアルゴリズムを用意した。

・ 課題説明のpdfに示された単純な関数
・ 行列N×NをX×X (X≦N)に分割して90度左回転をかけるアルゴリズム
本実験ではX=2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048を測定した。

上記のアルゴリズムの中から最も早いアルゴリズム”X×X”を見つけたら、次にその数値を使って、以下に示すような最適化の工夫を施した。右側には、施した工夫の説明を示した。

・ X×X in LF (Local Field) 測定に使う変数をlocal fieldにおく。
・ X×X invoked –O3 オプションの“O2”を”O3”に変えてコンパイル
・ X×X for文-Y 測定関数で使用されているfor文をY個減らす
・ X×X inc 変数lineまたはcolumnをインクリメントで表現する

本実験では、上記の手順に従い、各関数のサイクルカウント値を測定していく。そして、最も最適化できた関数を導き出す。
2. 実験結果
2.1 分割した場合の測定結果
行列N×Nを、X×Xのマス目に分割したときのCPE値について、以下の表1に示す。

表1.1 90度左回転の方法と行列N×NにおけるCPEの値
　 行列N×N
64 128 256 512 1024 2048
Function Normal 14.35 14.43 15.37 19.02 112.15 126.29
partition 2×2 15.80 17.29 17.89 24.80 62.28 65.64
partition 4×4 8.56 9.23 10.36 13.27 31.99 34.35
partition 8×8 7.33 6.61 6.27 11.21 27.45 29.43
partition 16×16 14.25 13.92 13.96 17.70 21.94 22.58
partition 32×32 14.08 13.79 13.81 17.78 19.74 20.07
partition 64×64 14.20 13.87 13.75 17.69 18.91 19.36
partition 128×128 NaN　 13.96 13.84 18.31 19.20 19.82
partition 256×256 NaN　 NaN　 13.86 18.64 19.38 19.96
partition 512×512 NaN　 NaN　 NaN　 18.94 20.71 21.80
partition 1024×1024 NaN　 NaN　 NaN　 NaN　 113.78 114.00
partition 2048×2048 NaN　 NaN　 　NaN NaN　 NaN　 124.66
※ 赤文字は最も早いCPE値

表1.1から分かること
・ N=64, 128, 256, 512においては行列を8×8マスずつRotateさせたほうが早い
・ N=64, 128, 256, 512においては行列を64×64マスずつRotateさせたほうが早い

表1.1を折れ線グラフで表示させたものを以下の図1.2に示す。


図1.2から分かること
・ 行列512×512から1024×1024にかけて、急激にCPEが大きくなる
・ 64×64に分割するとCPEの線がほぼ並行になる


図1.2の0 <>

図1.3からわかること
・ N=256からN=512にかけて、どの折れ線も若干CPE値が大きくなっている
・ N=1024からN=2048にかけて、どの折れ線もほぼ水平になっている
・ X=64の折れ線が、最も水平に近い折れ線になっている。


以上の結果より、各行列N×Nに対して、最も適切な分割X×Xは以下の通りとなった。
行列64×64 　→ 分割8×8
行列128×128 　→ 分割8×8
行列256×256 　→ 分割8×8
行列512×512 　→ 分割8×8
行列1024×1024　→ 分割64×64
行列2048×2048 　→ 分割64×64




2.2 他最適化に関する工夫の測定結果
実験2.1の結果からN=8, 64に絞り、様々な最適化の工夫を施して、CPEの計測を行った。その結果を以下の表2に示す。

表2. 8×8または64×64に高速化の各工夫を施したサイクルカウント値
　 行列N×N
64 128 256 512 1024 2048
function partition 8×8 7.33 6.61 6.27 11.21 27.45 29.43
partition 64×64 14.20 13.87 13.75 17.69 18.91 19.36
8×8 in Local Field 6.92 6.64 6.34 11.54 27.15 29.31
64×64 in Local Field 14.20 13.82 13.75 17.65 18.83 19.29
8×8 invoked -O3 in LF 7.02 6.34 6.12 11.28 27.23 29.56
8×8 for文-1in LF 6.62 5.96 5.65 10.72 26.91 28.83
8×8 for文-2 in LF 6.47 5.83 5.49 10.70 26.94 28.80
8×8 for文-2 in LF and Matrix in LF 6.57 5.88 7.01 14.10 27.44 29.20
8×8 for文-2 in LF and increment 6.54 5.87 5.50 10.75 27.05 28.83
8×8 for文-2 in LF and inc at Array 6.52 5.84 5.53 10.71 27.24 29.11
※赤文字は、最も小さいCPE値

表2の結果から、各Nに対して最も小さいCPEを返すアルゴリズムは以下のようになった。

行列64×64 　→　分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列128×128 　→　分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列256×256 　→　分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列512×512 　→　分割8×8 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列1024×1024　→　分割64×64 + for文の内側2つを崩し、変数をLocal Fieldに置く
行列2048×2048　→　分割64×64 + for文の内側2つを崩し、変数をLocal Fieldに置く



3. 考察
3.1 最適化の観点から実験結果を解析/追加実験
　今回の実験結果から、最適化できた箇所と出来なかった箇所について、キャッシュサイズを考慮しながら考察していく。また、考察を通して試してみたい方法を見つけたら、その都度実験を行い、その結果を示していく。
まず、表1.1の実験結果を通して判明した最適化の法則と、その理由を以下に挙げる。
・ 分割回数は引数ではなく#defineの方がよい
→#defineは単純な置換なので、変数を呼び出す手続きを減らすことが出来る。

・ for文の内側で関数を呼び出さないほうが良い
→関数を呼び出す手続きにも、サイクルが必要になるから。

・ O3よりO2オプションの方が良い
→O3はO2の各オプション機能に加えて-finline-functions, -fweb, -frename-registersが追加され、これらのオプションが最適化に対して改悪となっているから。

・ int sepN=N/SPLITという変数は用意せず、直接N/SPLITを使った方がよい。
→sepNという変数用にメモリを割り当てなくてはいけないから。一方でint Nは最もよく使われる変数なので、大抵の場合は既にCPUに近いメモリに入っている。よって、sepNを用いる場合と違い、無駄なメモリ領域を使わずに済む。

・ for文のネストする回数は出来るだけ減らした方が良い
→for文を呼び出すためのサイクルが必要になるから。
また、キャッシュにうまく乗る可能性が増えるから。

・ static MatrixはLocal Fieldに置かない方がよい
→Matrixの内容をコピーするサイクルが追加されるから。

・ column++よりcolumn+Xの方が若干早い
→即値アドレスで実現できるので、サイクルでの差はあまりないから。
　インクリメントなので、columnの値が毎回書き換えなければいけないから。
　Columnを書き換えた値を元に戻す作業が必要になるから。

・ 配列内でインクリメントしても、あまり最適化できない
→同上の理由で、インクリメントした方が若干サイクルは早くなるが、逆に無駄なサイクルも必要になってくるから。

次に、表1.1において、行列N×NをX×X分割したときの最適化について考察したい。
実験結果の表1.1を見ると、明らかにキャッシュに乗っていないnormalや2×2分割アルゴリズムと最も早かったアルゴリズムのCPEを見比べると、ほぼ全てのN×N行列のMiss Rateを抑えることに成功したと分かる。特に、N=64, 128, 256の部分については、CPEが3～8の範囲に入っていることから、Miss Rateも限りなく低い割合になっていることが分かる。
　一方で、N=512, 1024, 2048の部分については、元の単純なアルゴリズムと比べると、確かにMiss Rateは下がったといえるが、CPEが3～8の範囲を多少超えているところを見ると、まだまだ改善の余地は残っているように見える。

　そこで、N=512, 1024, 2048に焦点を当てて、Miss Rateをさらに下げることができないか検討してみた。
そこで、まずは表1.1を参考にして、行列N×Nと分割X×Xの効率の良い比率を調べた。結果を、以下の表3に示す。
表3. 行列N×Nの容量を分割X×Xの容量で割った値
　 行列N×N
64 128 256 512 1024 2048
分割X×X (容量[Byte]) 行列N×Nの容量[Byte] 16,384 65,536 262,144 1,048,576 4,194,304 16,777,216
2×2 (16) 1024 4096 16384 65536 262144 1048576
4×4 (64) 256 1024 4096 16384 65536 262144
8×8 (256) 64 256 1024 4096 16384 65536
16×16 (1,024) 16 64 256 1024 4096 16384
32×32 (4,096) 4 16 64 256 1024 4096
64×64 (16,384) 1 4 16 64 256 1024
128×128 (65,536) NaN 1 4 16 64 256
256×256 (262,144) NaN NaN 1 4 16 64
512×512 (1,048,576) NaN NaN NaN 1 4 16
1024×1024 (4,194,304) NaN NaN NaN NaN 1 4
2048×2048(16,777,216) NaN NaN NaN NaN NaN 1
*赤文字は表1で最も小さいサイクルカウント値が出た位置
表3の結果から、各要素Nに対して最もMiss Rateをうまく抑えることのできた部分(文字部分)を見ると、分割後のマス目の数は64～4,096あたりがMiss Rateをうまく抑えられる範囲だと理解できる。また、N=64,128,256,512の赤文字部分と、N=1024,2048の赤文字部分が横並びになっていないことから、前者と後者の乗っているキャッシュレベルは異なっているのではないかと推測できる。
　これらの結果を元に、N=512, 1024について、行列N×Nを分割するXの値を、多少変化させて再度CPEの結果を行った。また、方針としては、表3の結果から、N=512についてはXを大きくする方向に動かしていき、N=1024についてはXを小さくしていく方向に動かしていくことにする。
その結果を以下の表4.1, 4.2に示す。ただし、SPLITの値で行列Nをうまく分割しきれるように、Nの値は適宜変更させてある。

表4.1 行列N×NをX×Xで分割したときのCPE値(1)
行列N 511 513 510 517.00 516.00
分割X 7 9 10 11 12.00
CPE 11.34 11.77 13.37 15.37 16.11

表4.2行列N×NをX×Xで分割したときのCPE値(2)
行列N 1035 1029 1000 1020 1045
分割X 45 49 50 51 55
CPE 19.05 18.94 18.64 18.88 18.69

　表4.1, 4.2を見ると、特にMiss Rateが小さくなった箇所見られない。よって、SPLITの値を変化させていってもこれ以上Miss Rateを小さくすることは難しいことがわかる。また、Conflict Missの観点から、多少キリの悪い数字を考慮しながらSPLITの値を決めたが、それもあまり功を成さなかった。つまり、Capacity Missに目を向ける必要がある。言い換えれば、N=512, 1024, 2048について、さらにMiss Rateを小さくするためには、notive_rotateAのアルゴリズム自体を見直す必要がある。

　そこで、まずはUnrolling 8を試してみた。ただし、N=512と1024, 2048ではキャッシュレベルが違う可能性があるので、今回はN=1024と2048にのみ焦点を当てた。加えて、代入する順序を逆順にする方法、lineとcolumnを逆にする方法も試してみた。結果を以下の表5に示す。
表5. N=1024, 2048に各工夫を施したCPE値
　 行列N×N
1024 2048
現時点での最速値 18.83 19.29
unrolling 8 18.93 19.39
unrolling 8 reverse 18.99 19.42
column⇔line 12.07 12.16
　表5を見ると,unrolling 8, unrolling 8 reverse共にあまり良い成果は出なかったが、columnとlineについては大幅にMiss Rateを小さくすることに成功した。これは、メモリ領域には横にアクセスしていくよりは、縦にアクセスした方が早いことを表している。
　ここで、他のNの値に対しても同様の方法でMiss Rateをさらに下げられるのではないかと考え、この方法を用いて再度計測しなおした。その結果を以下の表6に示す。
表6 アクセスする順を縦横反転した場合のCPE
　 行列N×N
64 128 256 512 1024 2048
function 現時点での最速値 6.47 5.83 5.49 10.70 18.83 19.29
partition 2×2 10.10 10.94 11.16 23.58 73.96 73.50
partition 4×4 6.41 6.69 6.70 15.96 35.54 37.70
partition 8×8 5.25 4.98 5.00 15.88 23.89 25.03
partition 16×16 5.72 5.37 5.26 13.42 15.91 16.91
partition 32×32 6.88 6.56 6.68 12.52 12.78 13.03
partition 64×64 6.64 6.41 6.47 11.43 12.02 12.18
partition 128×128 NaN 9.22 9.14 12.81 13.62 13.50

表6から、N=512を除いた全てのNは、やはり縦横反転したほうMiss Rateが小さくなることが分かった。ちなみに、N=512に対して望んだ結果が得られなかったのは、N=64,128,256とN=1024,2048の各キャッシュレベルを跨いでいることが原因ではないかと伺える。

　以上の結果から、行列N×Nに対して、要素1つあたりにたいするサイクルカウント値を最も小さくする方法は、以下の通りになった。

N=64 → 行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
N=128 → 行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
N=256 → 行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
N=512 → 行列を8×8マスずつに分割して、※2の方法でsrcにアクセスする。
N=1024 → 行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
N=2048 → 行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。

※1 Matrix src [A][B]にアクセスするときはfor文の最も内側でAにアクセスし、外側のfor文でBにアクセスする
※2 Matrix src [A][B]にアクセスするときはfor文の最も内側でBにアクセスし、外側のfor文でAにアクセスする
3.2 配列の上限要素数”ARRAY_MAX”とCPEの関係
　2008年1月9日の講義でARRAT_MAXとCPEの関係を聞いたので、その知識を元に考察3.1の結果を掘り下げて、再度実験と考察を行っていきたい。

　まずは、授業中に言われていた、ある突出した地点と現在のARRAY_MAXの地点が重なっているのではないかと考えた。その部分を検証するために、ARRAY_MAX=2048の値を少し変更して場合のCPE値を調べた。その結果を以下の表7に示す。

表7 分割8×8におけるARRAY_MAXとCPEの関係
　 行列N×N
64 128 256 512 1024 2048
ARRAY_MAX 現時点での最速値 5.25 4.98 5.00 10.70 12.02 12.18
2045 3.91 4.24 4.26 5.95 9.53 Corrupt
2046 4.36 4.56 4.67 7.37 9.92 Corrupt
2047 4.88 4.87 6.12 8.14 9.97 Corrupt
2048 5.25 4.98 5.00 15.88 23.89 25.03
2049 5.06 4.81 4.61 6.82 10.20 10.50
2050 4.97 4.73 4.53 6.84 10.12 11.84
2051 4.35 4.37 4.33 6.50 9.63 9.95
2052 4.15 4.24 4.17 7.03 10.17 10.30
2053 4.06 4.17 4.27 6.28 9.60 10.07
2054 3.95 4.13 4.24 6.46 9.66 10.26
2055 3.99 4.11 4.23 5.82 9.46 10.18
2056 3.97 4.08 4.30 6.28 10.26 12.01
2057 3.94 4.00 4.25 5.81 9.52 10.47
2058 3.91 3.92 4.20 6.26 9.66 10.15
2059 3.91 3.88 4.22 6.03 9.94 10.50
※ 赤文字は最も表の各列中で最も早かった箇所

結果は、予想したとおりであった。表7から今まで使っていたARRAY_MAX=2048の部分だけ明らかに突出した結果が出ていることがわかる。これはつまり、ARRAY_MAXにキリのよい数字を使っていたが故に、満遍なくキャッシュを活用出来ず、キャッシュの同じ場所に何度もアクセスされたと考えられる。言い換えれば、ARRAY_MAXをキリの悪い数字にすることで、キャッシュに満遍なくアクセスさせることが出来たといえる。

ここで、ふと疑問に浮かんだのが、”ARRAY_MAXの値と分割X×Xは相互に依存しているかどうか”という点である。それを確かめるために、ARRAY_MAXを2059に固定し、分割X×Xを変数として再度実験を行った。その結果を以下の表8に示す。

表8 ARRAY_MAX=2059における分割X×X
　 行列N×N
64 128 256 512 1024 2048
function 現時点での最速値 3.91 3.88 4.17 5.81 9.46 9.95
partition 2×2 9.27 9.60 10.29 14.09 16.57 16.58
partition 4×4 5.56 5.66 6.26 8.25 10.15 10.69
partition 8×8 3.91 3.92 4.20 6.03 9.94 10.50
partition 16×16 3.15 3.13 3.25 5.98 10.23 10.60
partition 32×32 2.91 2.88 2.90 6.96 10.61 10.69
partition 64×64 2.80 2.80 2.80 6.99 10.92 11.30
partition 128×128 NaN 5.09 5.31 8.95 12.45 13.00
※ 赤文字は最も表の各列中で最も早かった箇所

表8からARRAY_MAXを2059に変更すると、今まで分割8×8のとき早かったN=64, 128,256の部分が分割64×64で最も早くなるという結果が出た。また、今まで64×64が最も早かったN=1024,2048が分割8×8のとき早くなるという結果が出た。
このことから、少なくともARRAY_MAXの値と分割X×Xは相互に依存している関係、ということが分かる。言い換えれば、各ARRAY_MAXの値に対して、それぞれ分割X×Xの計測を行わないと、最も早いCPEは分からないということになる。

しかし、現在使用しているドライブではそこまで大規模な実験は出来ないので、表6,7,8から、ある程度目星をつけた部分にのみ計測を行った。結果を以下の表9に示す。

表9 表6,7.8から気になるところのCPE値
N ARRAY X×X CPE 結果
256 2052 64×64 2.84 ×
256 　2052 32×32 2.93 ×
512 2057 8×8 5.78 ○
1024 2055 8×8 10.18 ×
2048 2051 8×8 9.98 ×
※ 赤文字は今までのCPEより早かった箇所
今回の計測で更新されたCPEはN=512の部分だけである。しかし、更新前との差が0.03しかないところも踏まえると、あまり”結果を出すことが出来た”とはいえない内容である。CPEの最適化とは関係ないが、この結果からCPEの計測では帰納的な計測方法ではなく、なるべく演繹的な計測方法の方が効率的だと分かる。


　以上、今回の考察/結果をまとめると、以下のようになる。
・ ARRAY_MAXが2^N乗ではスパイクと重なっている場合が多い。スパイクと重なっている場合は、重なっていない場合と比べMiss Rateが非常に大きくなる。
・ CPEはARRAY_MAXの値をインクリメント、またはデクリメントしただけでも大きな変化を示す。
・ ARRAY_MAXの値と分割X×Xは互いに依存していて、ARRAY_MAXの値を変えると最も効率的な分割Xの値も変わる。
・ CPEの計測は帰納的ではなく、演繹的に行った方が結果は出やすい。

また、今回の考察を通して、Nの各値の最も早いCPEとその状態は以下のようになった。

[N=64, CPE=2.80]　ARRAY_MAXを2059と定義して、行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
[N=128, CPE=2.80]　ARRAY_MAXを2059と定義して、行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
[N=256, CPE=2.80]　ARRAY_MAXを2059と定義して、行列を64×64マスずつに分割して、※1の方法でsrcにアクセスする。
[N=512, CPE=5.78]　ARRAY_MAXを2057と定義して、行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
[N=1024, CPE=9.46] 　ARRAY_MAXを2055と定義して、行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。
[N=2048, CPE=9.95]　ARRAY_MAXを2051と定義して、行列を8×8マスずつに分割して、※1の方法でsrcにアクセスする。

※1 Matrix src [A][B]にアクセスするときはfor文の最も内側でAにアクセスし、外側のfor文でBにアクセスする

　今回の実験の最終的な成果は上記のような結果となった。

ここで、相対的に今回の実験結果が良い結果だったのかどうかを見分けるために、メモリマウンテンの結果から行列のCPEの概算を算出し、考察したい。

動作環境で示してあるメモリマウンテンを見ると、working set sizeが16kBのとき、L１キャッシュに乗り、Z軸のread throughputからうまくいけば約3,250[Mb/s]程の性能を出せるはずである。つまり、今回の実験のN=64(16kB)とき、L1キャッシュにうまく乗せることが出来れば、以下のCPEを出すことが出来る。

周波数=1,709,000,000[cycle/s],容量=16,000[byte],Throughput=3,250,000,000[byte/s]より、16kBを読むのに必要なcycle = (周波数×Throughput / 容量) = 8,42[cycle]　となる。
ここで、N=64のとき要素の数は64×64= 4096なので、１要素あたりに必要なcycleは
8,417 / 4,096 = 2.06[cycle]となる。

ただし、ここで考慮しなくてはいけないことは、メモリマウンテンのスループットはreadに対するスループットなので、read以外のcycle数は考慮されていない、ということである。しかし、これは言い換えれば、行列の１要素あたりに必要なサイクル数は2.06+α(α=read以外にかかるサイクル数)となるので、理想のCPE≒2.06と、概ねの目安を立てることができる。

同様にして、他の各Nの値に関しても計算してみると、
N = 128 →　CPE = 2.34+α
N = 256 → CPE = 2.34+α
N = 512 → CPE = 2.34+α
N = 1024 → CPE = 2.84+α
N = 2048 → CPE = 2.97+α (mountain.cを拡張して求めた)
となった。
上記の計算値と最終的な実験結果を比較すると、今回の実験の最終結果はN=64, 128, 256については、ほぼ理想の状態に近づけることが出来たといえる。一方でN=512, 1024, 2048とNが増えていくにつれて、キャッシュにうまく乗せることが出来ず、Miss Rateが増えた、と推測することができる。つまり、N=512, 1024, 2048については、まだまだ改善の余地が残っている、と分かる。


4. 感想・まとめ
今回の課題を通して、CPUに関する知識を掘り下げられたのと、コンピュータアーキテクチャの勉強、またTechnical Termを学ぶことができたのは、とても良かったと思う。
ただ、実験中とても疑問に思ったのがメモリマウンテンの結果が、日をおいて実行すると大きく異なる値を示すことである。本レポートでは、3000[MB/s]のスループットが実行結果として出たものを使用したが、場合によっては600[MB/s]のときもあった。処理速度は”偶然遅くなることはあっても、偶然早くなることはあまりない”という特徴があるので、3000[MB/s]を採用したが、何故そこまで差が出るのか、という考察もいずれ行いたい。

5. 参考資料
CPUID(CPU-Zの製作元)
http://www.cpuid.com/

添付資料1 “ドライバex02a.cのソースコード”
添付資料2 “測定に用いたアルゴリズム(一部)”

Tweet

The Memory Mountain

　　　　　　　　　　　　　　My Memory Mountain　↑　　　　　
↓Sample Memory Mountain(2002)　

…え～と、2007年購入のMy notePCは2002年のPC(sever）に２倍以上の差で負けますたorz

しかし、先生のノートPCは3,200だったよな…。これが一般人と研究者のスペックの差かorz orz

フーリエ課題は終わったけど、発展課題もやっておかなくてはな。

でも、解析学は若干苦手だ。。。

ということで、フーリエ解析の発展問題は、一旦置いておいて、ほかの事をやってみるテスト。

結果：

プログラミング言語論(課題+発展提出)、CPE計測(追加考察&校正終了)、

MIT lecture summary(これ以上のdownsizeは無理ぽorz)

[reference:"Computer Systems: A Programmer's Perspective" (CS:APP)]
プリント(A3)2枚
・Class14
・Class19(2002)/16(2006)
・Class20(2002)/17(2006)

(.../opt)
☆.../mem/mountain/mountain.c

warm upと
各strideの実行と
その結果表示を
同時にやってくれるプログラム。

Excelに出力させると、とてもわかりやすい。
教科書の著者はさらに、グラフを作っている。
→上2行を省けば、ほぼ等高線に近いグラフになっている。


・図に関して、
ストライドは"s1, s4, ... ,s22まで
容量は32m, 512k, 8k

→メモリの性能は、アクセスする幅によって、大幅に変わる

ゲレンデみたいなところ(右側中部)で、プログラムがかけると嬉しい。
谷底みたいなところには、出来ればいきたくない。


・L1cacheにのると、メモリマウンテンの一番高いところの性能が出る
・L2は真ん中のゲレンデあたりの性能が出る。
・キャッシュから外れると谷底。
→ストライドが小さいと中々性能が良い。
→何故→1回はずれると、あとの7回が当たるから。


・メモリマウンテンは眺める角度を変えることが出来る
→裏面から見ると、実は崖になっている。
つまり、アクセスする幅が少なすぎるとそれはそれでマズイ。

2002年頃の性能結果(講義資料：server)→1MB/s
現代のPCの性能結果(先生のノートPC)→3Mb/s
つまり、当時と今では、3倍ぐらい早さが違う


・メモリマウンテンの一番左側のラインをプロットすると、そこの局所性が分かる。
→結果：明らかに3つのゾーンがあることが分かる。
S1から順番に[キャッシュはずれ, L2, L1]で早くなっていく？※要確認


・真ん中のゲレンデのところ
→S1からS16に向けて段々遅くなっていく。
始めは、つまり、一つの要素が外れると７つがうまくいく
グラフ右側のフラットな部分は、一個の部分を読み込んで他の部分を読み捨てている。
→もったいない！！


・真ん中のslope→降りる場所はs16
1キャッシュラインに16個のキャッシュがある？


・メモリマウンテンを見ると１次キャッシュ、２次キャッシュが明確に分かる。
→一番右側奥のstrideを大きくすると隆起した部分は、現段階ではとても難しい話でまだ説明できない。


・東大、Quad coreのopteron搭載の国内最速スパコン。（日立協力）
～約15,000コアで理論ピーク性能140TFLOP
→作るのは簡単。つなげればいいだけ。
ただし、2.3Ghzを4個(16コア)搭載したものを繋げる。→これは難しい。
先生の研究室もそれを買おうとしている？


・AMD's "TLB"について
年末に売り出そうとして、延期になっている。→株価下落。
論理設計にミスがあることが分かった。
opteron2.3Ghzは世の中にはまだ売り出されていない。
Bug in AMD's quad-core Barcelona and phenom may be more serious than previously suspected.
→そのバグは結構重大だぞ。といっている。


・Quad-coreのメモリ性能？
・メモリ性能はそんなに変わらない。
・最上部がフラットになっている(3Mb/s)
・L2のスキーヤーゾーンっぽい傾斜が長い。
・スロープがさらにもう一個ある→L3がある。
・ゲレンデだとCPUのコアが独立で出来る？

バグフィックスのために今の性能より、若干性能が落ちると予測できる。

→課題はなるべく谷底には行かないようなプログラムを作ってね(はぁと。



・2次元配列のコピーについて
srcからdstにコピーする。
→for文外側の添え字は配列の左側に、
for文内側の添え字は配列の右側に送ったほうが早い
（常識らしい)

まともなプログラム CPE=14.10 (ただし、最適化は行っていない)
うっかり添え字を逆にしたプログラム CPE=370
結果：20倍性能が違う

・本当にそれほど遅くなるのか？実験してみる
ためしに配列のサイズARRAY_MAXを一つ大きくしてみる　2048→2049 ←※重要
→うっかり間違えプログラムを実行
結果：CPE=34.57

つまり、配列の要素を2^Nで確保すると、悲惨なことが起こる
[例2]1024で下手なプログラムを書く 結果：CPE=300
1023で下手なプログラムを書く 結果：CPE=27
→何故このような結果が出るのか考えてみる→課題の考察に追加で書いた方が良いっぽい？


・今度は違う形で実験
メモリマウンテンでは3200万個ぐらいアクセスするけど、

今回は、アクセス256個、ストライド1～1400まで(1024を包括するため)で実験してみる。
直感では全部キャッシュに乗る、はず。
どんなへたくそなプログラムでも、256個のintegerデータなら
全て１次キャッシュに乗る、はず。
結果；256個の一回分のクロックサイクルを見ていくと
前半：大体600付近 + ところどころ1600の突出がある(スパイクと呼ぶ)
後半：ほとんど1600になる

→何故かこのような結果になるのか？

・グラフにしてみる
結果：arc tangentみたいなぐらふ？
序盤 ＝ フラット＋ところどころにスパイク(64の倍数の定期的なスパイク + 不定期なスパイク)
中盤1＝ 右肩上がり(大) + ところどころのスパイク
中盤2＝ 右肩上がり(中) + ところどころのスパイク
終盤 ＝ とても遅い数値のフラット＋(スパイク？あったけ？うる覚え)



・opteronの場合。
この実験をすると、いいプログラムは CPE=600 → これはよい
また、悪いところ(終盤)でも2倍ぐらい → まぁよい

!!ただし!!
・あちこちでスパイクの不定期な頻出と定期的な頻出が出ている。
特に、1024の部分が"とんでもなく遅い"
また、512の部分が"とても遅い"

ModernのCPUだとこれだけ複雑な結果がでてくる。
下手な数(つまり、キリのいい数)を書くと、
スパイクに当たってしまい、非常に遅いプログラムになる可能性がある。
また、逆に考えれば、メモリアクセスの管理は恐ろしく複雑なことをやっていることが分かる。

＊2006年版の資料の方が2002年版より分かりやすいらしいよ。



【仮想記憶について】
CPUから効率的に取る必要がある。
複雑なロジックだからAMDの人もバグに苦労してしまった。

※CAUTION ※
！！ここら辺からちょっと教室がうるさくなったので、聞き逃し部分がある！！
！！講義資料とノートを比較して、事実を確認した方がよい　　　　　　　！！

消費電力を少なくする。
→これだとサーバーの世界には勝てない。
・講義：Virtual Memory
来年はOSの授業がある→そこでも仮想記憶について触れる→その予習と思って聞いてほしい。

機械語の命令なので番地がある。
メモリの番地とその番地が同じであるかというと、そうではない→バーチャルな番地がある
→4100番地でも4100番地にいくとは限らない。

つまり、キャッシュには無くても仮想記憶にはある場合がある。
desktopやlaptopはほとんどこんな感じ。
→仮想記憶はとても偉大なアイデアだ、と著者は述べている。


[Address Spaces]
この授業は3年前に大幅に模様替えした。
なぜなら、そのころはCPUのアドレスは32bitだった
しかし、今はcore2やopteronだと64bitになった。
→大きなアドレスに触れるようになった。

例えば、積んでいるメモリ1Mでも、最低メモリ4MB必要な動作を行うことが出来る。
→どうして？
→Nがバーチャルなアドレススペースとなる。
→Mはフィジカルなアドレススペース(物理アドレス)
32bit→4GB
64bit→4GB×2^32（=約４０億）

→64bitだと仮想記憶はいらないのでは？

では、何故使うのか。

→"性能を超えたプログラムでも動かすことが出来る！"

Main memory is a chache for rhw contents of a virtual address space stored on disk
→必要に応じて読んだり読みこなかったりする。

読み書きしちゃいけないメモリを触ってブルースクリーンになることはよくある。

記憶管理には慎重に。→あるプロセスはメモリ領域を勝手に読み書きしてはいけない。

中にはOSの秘密な情報があったりする。→勝手に読み込まれては困る

[1]は効率、[2][3]はOSについての話
今回は[1]について重点的に話していく。

・仮想記憶の空間があって、ある程度大きい。
→バーチャルメモリは、どこの物理メモリがのっかっているか、という情報を持っている必要がある。


理論的には通じるけど、定常的には変わってくる。→プリントP.7
キャッシュに乗るプログラムとならないプログラム。
一般的に
キャッシュ　→　SRAM
メインメモリ→　DRAM
DRAMにも乗らないところ　→　DISKに行く (この場合、性能は10万倍ぐらい違う)
となっている。

EX.レポート書きながらエクセル,音楽,画像弄くるなどをやってると、
全体のメモリ量はバカにならない。同時に実行すると、急に遅くなる。
これは、全体としてメモリに乗らないので、ある仕事に必要な容量はDisk間とやりとりしてしまう
→動作が遅くなる and "disk"がカタカタ音を出し始める。これを”Thrashing”という
→補足：よってThrashingが起こる＝とても動作が遅くなる。

メモリとDiskのやりとりは 4 or 8 KBが典型的
一個のキャッシュライン
→3号車のどこに目的の値があるか探すのが大変。
すきなモノが好きなフィジカルページに行ける。
いける場所は多少限られている。

any virtual page can be places in any physical page.
メインメモリとDiskのreplacement algorithmsは複雑。
メインメモリにすぐに書き続けていくと、大変
メインメモリには反映させるけどDiskまでは反映させない。遅いから→write-back方式 を採用？

virtual memory(disk上にある)
仮想的にDiskにある。
実際に積んでるメモリ→physical memory(DRAM)

ページテーブル。4kBの単位で管理/情報の受渡が行われている。
nullは全然使ってない。
物理なのか仮想なのかどこに乗っかっているかを管理するところ。→必ずある。

乗ってたらページヒット。
プログラムが見にいたアドレスがDiskにある→"ページフォールト"→これが遅くなる理由
メインメモリに乗っていないところにアクセスした場合のこと。


大体何やっているか→プリントP12
"DMA"　= direct memory access
DisKを一旦メモリのおいて、その後processorから読み取る。よって、とても遅い。

【大事な言葉集】
VM
Page failt
DMA
working set
Thrashing

同時に使う総量はたいしたことがない。
プログラムの実行中のある時点の前後0,何秒ぐらいでは、
バーチャルページのいくつかの選ばれた場所、部分集合にアクセスする。
(部分集合→ワーキングセット？)

ワーキングセットがメインメモリより小さければ、最初はミスするけど、その後は良い性能が起こる。

・メモリマネジメントの話。OSの話なので省略
・残りの話→最終回

【期末試験について】
日付、1月30日
資料持込可、基本的には何でもOK(パソコン不可)。
CS:APPの講義スライドのコピーも持ち込みか
(持ち込むことを進めます)
試験範囲は授業で扱った内容
・配点
期末試験：約50%
レポート：約50%

Tweet

行列N×Nの90度左回転における最適化 ver 2

やっと終わった～。そして約10,000字。ってか最近10,000字越え多杉orz
高校の卒論がどれだけ糞だったか、分かった気がするわ。


さて、コレで残す課題はプログラミング言語論と数学Bとフーリエ解析の答え確認だけだぜ。

…って終わるわけがないがなorz


いや、でも出来るだけ終わらさなければな。

このままじゃ、課題と試験勉強のダブルブッキングで死亡フラグ立つわ。

目指すはA+。

[CPE optimization NOTE and exercise]

memo

[class11～12.pdf]
vector=<コ>一次元配列、ベクトル
persist=存続する、持続する、生き残る
sensitive=敏感に反応する
ocnventional=標準となった、オリジナリティのない、型にはまった
eventually=最終的には、結局のところは
volatile=揮発性(の)
retain=保持する、実行し続ける
generic=一般的な、総称の
retrieve=(情報を)検索する、読み出す、回収する、取ってくる
geometry=(関連ある部分同士の)配置、配列、(表面の)形状、幾何学
concentric=<数学>同心の、集中的な
platter=円盤状の記録媒体、大皿(に盛った料理)
aligned=位置合わせした
density=密度、濃さ、密集(度)、濃度
squeeze=圧搾する、締め付ける、強制する
attach=貼り付ける、添付する、加える
radially=半径方向に、放射状に
unison=調和、一致
approximate=
1.おおよその、概算の、近時の adj
2.接近する、に近づける、概算する
permute=～の順序を変える
Hierarchy=階層型組織、序列、優先度、順位
exhibit=展示する、発表する、(証拠を)提示する、(感情を)表に出す

[class14.pdf]
exploit=
1.セキュリティ上の弱点、突破口、バグを利用した裏技、手柄、功績
2.不当に使う、(性能を)十分に引き出す
dimension=寸法、面積、容量、次元、様子、様相

[Blog -Cache Memories-]
conflict=不一致、衝突、衝突する、抵触する、矛盾する
adjacent=近くの、隣接した、隣り合った、直前の
consecutive=連続した、継続的な、結果の、(論理の)一貫した
allocate=割り当てる、割り振る、配置する
fraction=分数、有理数、比、割合、端数、一部分
spatial=空間の

-hit time-
1 clock cycle for L1
3-8 clock cycles for L2
Miss Penalty Typically 25-100cycle



[instruction cache]別名:命令キャッシュ
マイクロプロセッサ内部に設けられた高速な記憶装置であるキャッシュメモリの一種で、
プログラムを一時的に保管する領域。

CPUは高速にアクセスできるキャッシュメモリに使用頻度の高いデータを
蓄積しておくことで低速なメインメモリへのアクセスを極力減らすよう設計されているが、
このうちプログラム(プロセッサへの命令群)を保存しておく装置のこと。

データを保存しておくデータキャッシュと異なり、
処理によって内容が更新されてメインメモリへそれを反映させるといった動作が
必要ないため、構造が単純化されている。

[firmware]
ハードウェアの基本的な制御を行なうために機器に組み込まれたソフトウェア。

機器に固定的に搭載され、あまり変更が加えられないことから、
ハードウェアとソフトウェアの中間的な存在としてファームウェアと呼ばれている。

パソコンや周辺機器、家電製品等に搭載されており、
機器に内蔵されたROMやフラッシュメモリに記憶されている。

パソコンのBIOSもファームウェアの一種である。
機能の追加や不具合の修正のため、後から変更できるようになっているものが多い。

Tweet

行列N×Nの90度左回転における最適化

ん～、最適化の実験は、前回同様いつも思うような結果にはなってくれないな。

最近のCPUはほとんど中身がカオスで、実際に何がどう動作しているのか、
本職の人にもわからないらしいし、これはもう実験しまくるしかないないわww


しかし、初回の課題でドライバ作ってて良かった。。
ドライバ作成は一瞬で終了。頑張って作っててよかったわぁ。



最適化に関しては、とりあえずN×Nを分割して各々を90度回転させて、組み立てる関数は完成。

8×8～64×64あたりに分割すると、うまくどっかのキャッシュに乗るっぽい。

最適化のために他にやってみることは、

・変数をローカルフィールドに置く
・関数を解体して、直接書き込む
・gcc特有のオプションを使ってみる

とかかなぁ。とりあえず、このぐらいは最低限実験してみるか。

アセンブリコードは…まぁやってみたいけど、プログラミング言語論の課題が終わってからだな。


結局、冬休みはあってないようなものだったな。


以下メモ＠Gcc optimization option (refer to "man gcc" in cygwin)

Options That Control Optimization

These options control various sorts of optimizations.


Without any optimization option, the compiler's goal is to reduce the cost of compilation and to make debugging produce the expected results.
*compilation=編集

Statements are independent: if you stop the program with a breakpoint between statements,　you can then assign a new value to any variable or change the program counter to any other statement in the function and get exactly the results you would expect from the source code.
*assign=割り当てる、指定する

Turning on optimization flags makes the compiler attempt to improve the performance and/or code size at the expense of compilation time and possibly the ability to debug the program.
*expense=コスト(高)

The compiler performs optimization based on the knowledge it has of the program.

Using the -funit-at-a-time flag will allow the compiler to consider information gained from later functions in the file when compiling a function.

Compiling multiple files at once to a single output file (and using -funit-at-a-time) will allow the　compiler to use information gained from all of the files when compiling each of them.
*multiple=複数の

Not all optimizations are controlled directly by a flag. Only optimizations that have a flag are　listed.

-O
-O1 Optimize. Optimizing compilation takes somewhat more time, and a lot more memory for a large function.

With -O, the compiler tries to reduce code size and execution time, without performing any optimizations that take a great deal of compilation time.

-O turns on the following optimization flags: -fdefer-pop -fmerge-constants -fthread-jumps -floop-optimize -fif-conversion -fif-conversion2 -fdelayed-branch -fguess-branch-probability
-fcprop-registers

-O also turns on -fomit-frame-pointer on machines where doing so does not interfere with debugging.


-O2 Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff.
*tradeoff=見返り、交換(条件)

The compiler does not perform loop unrolling or function inlining when you specify -O2.
*in-line=一列に並んだ、直列(形)の , specify=指定する、明確にする

As compared to -O, this option increases both compilation time and the performance of the generated code.

-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags: -fforce-mem -foptimize-sibling-calls -fstrength-reduce -fcse-follow-jumps -fcse-skip-blocks -frerun-cse-after-loop -frerun-loop-opt -fgcse -fgcse-lm -fgcse-sm -fgcse-las -fdelete-null-pointer-checks -fexpensive-optimizations -fregmove -fschedule-insns -fschedule-insns2
-fsched-interblock -fsched-spec -fcaller-saves -fpeephole2 -freorder-blocks -freorder-functions -fstrict-aliasing -funit-at-a-time -falign-functions -falign-jumps -falign-loops -fsched-interblock -fsched-spec -fcaller-saves -fpeephole2 -freorder-blocks -freorder-functions -fstrict-aliasing
-funit-at-a-time -falign-functions -falign-jumps -falign-loops -falign-labels -fcrossjumping

Please note the warning under -fgcse about invoking -O2 on programs that use computed gotos.

-O3 Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -fweb and -frename-registers options.
*specified=指定の、規定の、特定の 、仕様が～の

-O0 Do not optimize. This is the default.

-Os Optimize for size. -Os enables all -O2 optimizations that do not typically increase code size. It also performs further optimizations designed to reduce code size.

-Os disables the following optimization flags: -falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -fprefetch-loop-arrays

If you use multiple -O options, with or without level numbers, the
last such option is the one that is effective.

Tweet

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