2016q3 Homework (software-pipelining)
===
contributed by <`kaizsv`>
:::info
第四周作業要比較不同大小的矩陣的影響，我另外還比較了不同 prefetch distance 的影響。 [跳到書籤](/s/r1IWtb9R#不同distance對prefetch的影響)
:::

### sse_transpose
用`8X8`矩陣終於懂了，它把大矩陣分成許多的`4X4`矩陣，如果是在對角線上，反轉後放回原位，若是其它的，反轉後放在其對角的位置。

相比於`navie_transpose`是一個一個放在對角的位置。

### sse_prefetch_transpose
這裡使用固定長度8的`prefetch distance`，每次執行時候會告訢CPU載入下一次運算用的資料，如果超出範圍CPU就不會載入([SSE 介紹 [Page 7]](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_7.html))，而`_MM_HINT_T1`告訴CPU要把載入的資料放在 L2 Cache。

因為每一次`for`迴圈的載入是 row base，而儲存到新的 dst 是 column base，因此用`prefetch`可以降底`cache miss`。

### perf raw counter
在一些系統架構下，有一些 counter 沒有在`perf list`裡面，參考這篇文章[perf Examples](http://www.brendangregg.com/perf.html)，如果是 Intel CPU 的話可以看[Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3B](http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3b-part-2-manual.html)的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

`r80a2`80是 mask number，a2 是 event number，可以查出`raw 0x80a2`是`RESOURCE_STALLS.OTHER`用來查看因為其它 resource issues 而被 stall 的 cycle數。`r2b1`同理是`UOPS_DISPATCHED.CORE`。

### avx_prefetch_transpose
在寫`avx_prefetch`版本時遇到一個問題，PFDIST 到底要多少，從[官網的資料](https://software.intel.com/node/524263)`_mm_prefetch()`會載入一個 cache line 的長度，我的 CPU cache line = 64B，
:::info
這裡的 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](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf) 5.1.4提到，若程式移植到不同的機器上，最佳的 distance 是會變動的
:::info
應該要像 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 變動不大。參考[吳彥寬](https://hackmd.io/EYMwbAhgDArAnAFgLQmGATEhB2AppiCAZhCQBMBGXGBGXCkCMEIA#最初實驗數據)同學筆記，`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](http://stackoverflow.com/questions/13788638/difference-between-section-and-task-openmp)

###### tags: `assigment_8` `software-pipelining`