HackMD
2016q3 Homework (software-pipelining)
contributed by <kaizsv>
第四周作業要比較不同大小的矩陣的影響，我另外還比較了不同 prefetch distance 的影響。 跳到書籤
sse_transpose
用8X8矩陣終於懂了，它把大矩陣分成許多的4X4矩陣，如果是在對角線上，反轉後放回原位，若是其它的，反轉後放在其對角的位置。
相比於navie_transpose是一個一個放在對角的位置。
sse_prefetch_transpose
這裡使用固定長度8的prefetch distance，每次執行時候會告訢CPU載入下一次運算用的資料，如果超出範圍CPU就不會載入(SSE 介紹 [Page 7])，而_MM_HINT_T1告訴CPU要把載入的資料放在 L2 Cache。
因為每一次for迴圈的載入是 row base，而儲存到新的 dst 是 column base，因此用prefetch可以降底cache miss。
perf raw counter
在一些系統架構下，有一些 counter 沒有在perf list裡面，參考這篇文章perf Examples，如果是 Intel CPU 的話可以看Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3B的19章，要對應到自己的 CPU 型號查 mask number 及 event number。
基本用法如下
# perf stat -e cycles,instructions,r80a2,r2b1 gzip file1
Performance counter stats for 'gzip file1':
5,586,963,328 cycles # 0.000 GHz
8,608,237,932 instructions # 1.54 insns per cycle
9,448,159 raw 0x80a2
11,855,777,803 raw 0x2b1
1.588618969 seconds time elapsed
r80a280是 mask number，a2 是 event number，可以查出raw 0x80a2是RESOURCE_STALLS.OTHER用來查看因為其它 resource issues 而被 stall 的 cycle數。r2b1同理是UOPS_DISPATCHED.CORE。
avx_prefetch_transpose
在寫avx_prefetch版本時遇到一個問題，PFDIST 到底要多少，從官網的資料_mm_prefetch()會載入一個 cache line 的長度，我的 CPU cache line = 64B，
這裡的 cache-misses 及 seconds 有包含了兩個 clock_gettime() 及一個 printf()，我想說若只是比較的話沒有必要把多餘的程式碼刪掉。
| cache-misses | seconds | |
|---|---|---|
| naive | 23,787,617 | 0.414481027 |
| sse | 11,093,003 | 0.294677882 |
| sse_prefetch (DIST 8) | 8,311,259 | 0.236825513 |
| avx | 8,671,298 | 0.244085014 |
| avx_prefetch (DIST 8) | 9,273,692 | 0.227254568 |
| avx_prefetch (DIST 16) | 8,783,887 | 0.232082226 |
sse+prefetch 確實讓 cache-misses 下降，但avx加上 prefetch 後 cache-misses 不降反升，雖然執行時間有稍微下降，我在想會不會跟兩件事有關。
- 前面提到的 prefetch cache line 的問題。
- static distance and optimal distance
在When Prefetching Works, When It Doesn’t, and Why 5.1.4提到，若程式移植到不同的機器上，最佳的 distance 是會變動的
應該要像 Fig. 7 那樣畫出不同 distance 的影響，但我時間拿捏不好
矩陣更大或更小有無影響，cache-misses
不同Distance對prefetch的影響
下圖是 distance 從 0～16 跑 10 次的平均時間 (us)，從圖的趨勢可以觀察到 distance 為0, 8, 16是比較有代表性的，因此抓出這三個 distance 的 perf stat 在下表。block size 固定為 4096。
| sse_prefetch | avx_prefetch | |
|---|---|---|
| cache-misses (DST = 0) | 11,109,048 | 8,928,395 |
| L1-dcache-load-misses (DST = 0) | 8,519,002 | 8,182,973 |
| L1-icache-load-misses (DST = 0) | 50,920 | 48,207 |
| cache-misses (DST = 8) | 8,294,171 | 9,254,506 |
| L1-dcache-load-misses (DST = 8) | 8,518,941 | 8,176,969 |
| L1-icache-load-misses (DST = 8) | 46,718 | 50,224 |
| cache-misses (DST = 16) | 8,837,080 | 8,634,863 |
| L1-dcache-load-misses (DST = 16) | 8,518,229 | 8,169,116 |
| L1-icache-load-misses (DST = 16) | 46,210 | 48,421 |
用perf stat計算cache-misses還包含了
fopen,fprintf等呼叫
因為我的hint是_MM_HINT_T1很明顯 L1 cache misses 變動不大。參考吳彥寬同學筆記，register L1 L2的成本不一樣，因此又用_MM_HINT_T0做了同樣的實驗。
| sse_prefetch | avx_prefetch | |
|---|---|---|
| cache-misses (DST = 0) | 11,111,058 | 8,930,902 |
| L1-dcache-load-misses (DST = 0) | 8,519,557 | 8,188,156 |
| L1-icache-load-misses (DST = 0) | 47,861 | 44,154 |
| cache-misses (DST = 8) | 8,010,660 | 8,967,156 |
| L1-dcache-load-misses (DST = 8) | 8,816,422 | 9,012,397 |
| L1-icache-load-misses (DST = 8) | 40,924 | 43,270 |
| cache-misses (DST = 16) | 8,779,192 | 8,477,066 |
| L1-dcache-load-misses (DST = 16) | 12,701,238 | 10,329,813 |
| L1-icache-load-misses (DST = 16) | 43,528 | 45,176 |
就 runtime 的圖來看，趨勢是差不多的，但在DST = 8的時候時間又減少了一點，再看 L1-cache，L1-icache-misses有減少，L1-dcache-misses增加，而 cache-misses 在DIST = 8時略微下降 |
不同block size的影響
y軸是對數座標，prefetch distance 固定為 8，跑 10 次的平均值，就時間上來看，1024 2048 4096 8192的 runtime 正好差 4 倍，cache-misses 大約比 4 倍多一點。
| cache-misses | naive | sse | sse_prefetch | avx | avx_prefetch |
|---|---|---|---|---|---|
| 1024 | 1,091,966 | 602,467 | 500,244 | 514,517 | 528,372 |
| 2048 | 5,899,170 | 2,705,538 | 2,087,994 | 2,119,224 | 2,282,681 |
| 4096 | 23,868,323 | 11,098,391 | 8,260,486 | 8,633,959 | 9,254,081 |
| 8192 | 95,162,778 | 45,083,319 | 36,873,007 | 35,296,137 | 39,163,892 |
| 16384 | 523,578,908 | 148,994,080 | 156,092,042 | 145,099,308 | 150,593,769 |
我的想法
- software prefetch distance對於 cache-misses 有明顯的影響，
sse一次處理 4x4 個 int，DST = 8 表示會載入下一次迴圈的資料，同理avx一次處理 8x8 的矩陣，DST = 16 時的 cache-misses 較低，但 cache-misses (L1 cache-misses)及 runtime 就沒有明顯的關係。 - 就不同 block-size 的實驗而言，runtime 正好都差4倍，而 block-size 愈大 cache-misses 也差不多是差 4 倍，其中
naive異外得多，sse大楖差 3點多倍，
