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點多倍，

OpenMp

stackoverflow 討論 OpenMp task

tags: assigment_8 software-pipelining
Select a repo