(↑さっき計測したメモリマウンテン。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 “測定に用いたアルゴリズム(一部)”
0 件のコメント:
コメントを投稿