# 2017q1 Homework3 (software-pipelining)
contributed by < `xdennisx` >

## 論文研讀
閱讀論文：[When Prefetching Works, When It Doesn’t, and Why](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)

論文中前五大點[這裡](https://hackmd.io/s/HJtfT3icx)都有做大部分的解釋

### Case Studies

#### Positive Group
- <i>433.milc</i>
下面程式碼是有關一個 3x3 的矩陣運算
`milc` 大部分的 cache-miss 都是發生在存取小規模的陣列，因為這些 matrix access 都是屬於 **short stream**，所以無法用 HW prefetch 去訓練它，因此他在 function call 的附近做了 SW prefetch 的動作，有了 SW prefetch，速度甚至比最好的 HW prefetch 快了 2.3 倍。

- <i>459.GemsFDTD</i>
`GemsFDTD` 大部分的問題出在 **complex indirect memory accesses**，像下面的變數 m 就是一個 indirect index，而 HW prefetch 對這種 irregular index 的加速效能有限，在這邊只增加了 12%(stream prefetcher)，然而 SW prefetch 卻能降低超過 50% 的執行時間(與 Baseline 相比)

- <i>429.mcf</i>
`mcf` 有密集的記憶體操作，他也使用了 array of pointer 的操作，由於 array of pointer 也是屬於 irregular behavior，所以 HW prefetcher 也不會表現太好。
這邊將 `arc` structure 做 prefetch，利用下一個 array index 去計算 next address，這是 HW prefetcher 做不到的。而使用 SW+STR 可以讓原本只有 STR 的效能提升 180%

- <i>470.lbm</i>
`lbm` 計算兩個 3-D array，這讓 GHB 跟 STR 可以有效預測 address，即使如此，實驗過後還是發現 SW prefetcher 還是可以表現的比較好，大大提升 cache hit ratio。
另外發現 `lbm` 對 prefetch distance 非常敏感，下圖顯示 SW prefetching 可達到將近 100% coverage，因為幾乎所有 `srcGrid` 的元素都會被 prefetch 到
這張圖說明不同的 distance 對 performance 的影響
下圖說明一個 prefetch distance unit 取決於下一個 loop iteration

- <i>462.libquantum</i>
`libquantum` 主要存取的方式都是 **fixed-stride streaming**，所以 SW 跟 HW 都可以預測 `reg->node` 的 address，可是 SW 可以做到 1.23 倍速的提升，因為 HW 有太多的 L1 cache miss penalties。
下圖顯示因為有太多的 L1 cache miss，所以 execution cycles 跟 on-chip L2 traffics 都會增加。GHB 在 SW 的訓練下，因為產生過多沒用的 prefetch，造成效能下降 55%。

- <i>403.gcc</i>
`gcc` 屬於 RDS，是非常 irregular，而且他的 access 是 indirect，藉由 insert prefetch 我們得到 14% 的效能提升，下面是程式碼片斷

- <i>434.zeusmp</i>
`zeusmp` 也是一個 3-D 的計算，每次 iteration 都會存取每個 dimension 的所有鄰近點，`v3` 可以同時被 HW 跟 SW prefetch，SW 降低了 L1 cache misses 而 HW 除去了一些 late prefetches，分別提升了 10%,4% 的效能

#### Neutral Group
- <i>401.bzip2</i>
`bzip2` 的核心演算法是[Burrows–Wheeler Transform](https://zh.wikipedia.org/wiki/Burrows-Wheeler%E5%8F%98%E6%8D%A2)，當中有很多的 branch，所以 HW prefetchers 沒有什麼用處，SW 在這裡也沒有表現的很好
下圖顯示當中有很多的 early prefetch，不過 software prefetching 還是能提升 8% 左右的效能

- <i>436.cactusADM</i>
`cactusADM` 也是計算 3-D 陣列，每次 iteration 都會存取一個維度鄰近的點，下圖在 `alp`、`ADM_kxx_stag_p` 插入 prefetch，雖然這裡的 data strcture 都是很好預測的，GHB 的表現還是比 STR 好很多，因為有太多的 in-flight stream，不過 SW prefetcher 可以縮小他們之間的差距(5%)。GHB 經過 training 之後可以減少 7% 的 late prefetcher

- <i>450.soplex</i>
`soplex` 中大部份 cahce-miss 發生在 C++ class overloaded operators 跟沒有迴圈的 member function，因為不知道實際的 data structure 長怎樣，所以不知道要在哪邊插入 prefetcher，但是他的 memory access 有一定程度的規律，所以 HW prefetching 就變得相對有用。
上圖顯示雖然 SW perfetching 是有用的，但是他被歸類在 neutral group 是因為 bandwidth consumption 以及太多錯誤的 SW prefetches

- <i>410.bwaves</i>

#### Negative Group
- <i>482.sphinx3</i>
`sphinx3` 有許多不同的資料存取方式，像是 RDS, array of pointers, regular strides，不過主要是 unit-stride streams，因此 HW prefetchers 很適合用在這上面。因為 prefetch timeliness 和小陣列的關係，SW prefetchers 不會用到每一個 data structure 上。

- <i>437.leslie3d</i>
`leslie3d` 有非常規律的 stride，但因為每個 iteration 之間的運算很受限，非得要用大的 prefetch distance，造成過多的 instruction 反而抵消原本預期帶來的利益。

## 測試環境

dennis@dennis-X550CC:~/prefetcher$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              58
Model name:            Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
製程：              9
CPU MHz：             993.585
CPU max MHz:           2700.0000
CPU min MHz:           800.0000
BogoMIPS:              3592.01
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

## 最初實驗數據

### 時間

naive: 		 250935 us
sse: 		 124485 us
sse prefetch: 	 65676 us

### 用 **perf stat** 看一下cache-miss

 Performance counter stats for './naive_transpose' (100 runs):

        19,145,519      cache-misses              #   95.049 % of all cache refs      ( +-  0.13% )
        20,142,743      cache-references                                              ( +-  0.04% )
     1,449,345,026      instructions              #    1.17  insns per cycle          ( +-  0.01% )
     1,238,612,771      cycles                                                        ( +-  0.66% )

       0.492766897 seconds time elapsed                                          ( +-  0.73% )

 Performance counter stats for './sse_transpose' (100 runs):

         6,959,105      cache-misses              #   91.276 % of all cache refs      ( +-  0.52% )
         7,624,244      cache-references                                              ( +-  0.26% )
     1,237,818,237      instructions              #    1.38  insns per cycle          ( +-  0.01% )
       899,769,987      cycles                                                        ( +-  0.75% )

       0.358673348 seconds time elapsed                                          ( +-  0.81% )

 Performance counter stats for './sse_prefetch_transpose' (100 runs):

         6,752,137      cache-misses              #   89.026 % of all cache refs      ( +-  0.22% )
         7,584,432      cache-references                                              ( +-  0.08% )
     1,283,460,940      instructions              #    1.75  insns per cycle          ( +-  0.01% )
       733,322,586      cycles                                                        ( +-  0.29% )

       0.286447261 seconds time elapsed                                          ( +-  0.46% )

好像用了 prefetch，cache-miss 就會下降的樣子，而且時間也有明顯下降。不過用 perf 所測得的 cache-miss 是**整體**的，而 prefetch 所減少的是 **L1-dcache cache misses**

### L1-cache-test

 Performance counter stats for './sse_transpose' (100 runs):

         8,513,522      L1-dcache-load-misses                                         ( +-  0.04% )
         4,136,589      L1-dcache-store-misses                                        ( +-  0.29% )
            65,288      L1-dcache-prefetch-misses                                     ( +-  0.38% )
            94,785      L1-icache-load-misses                                         ( +-  5.73% )

       0.345807079 seconds time elapsed                                          ( +-  0.60% )

 Performance counter stats for './sse_prefetch_transpose' (100 runs):

         8,517,476      L1-dcache-load-misses                                         ( +-  0.02% )
         4,175,545      L1-dcache-store-misses                                        ( +-  0.19% )
            64,775      L1-dcache-prefetch-misses                                     ( +-  0.43% )
            82,900      L1-icache-load-misses                                         ( +-  4.33% )

       0.284601743 seconds time elapsed                                          ( +-  0.50% )

ㄜ....所以這是沒有減少的意思嗎...

我嘗試不同的 prefetch distance 看看

D = 4
 Performance counter stats for './sse_prefetch_transpose' (100 runs):

         8,527,637      L1-dcache-load-misses                                         ( +-  0.03% )
         4,130,140      L1-dcache-store-misses                                        ( +-  0.36% )
            68,948      L1-dcache-prefetch-misses                                     ( +-  0.31% )
            88,588      L1-icache-load-misses                                         ( +-  4.91% )

       0.294001054 seconds time elapsed                                          ( +-  0.58% )
D = 16
 Performance counter stats for './sse_prefetch_transpose' (100 runs):

         8,552,080      L1-dcache-load-misses                                         ( +-  0.03% )
         4,115,989      L1-dcache-store-misses                                        ( +-  0.41% )
            64,701      L1-dcache-prefetch-misses                                     ( +-  0.42% )
            92,911      L1-icache-load-misses                                         ( +-  5.27% )

       0.304326302 seconds time elapsed                                          ( +-  0.72% )
D = 32
 Performance counter stats for './sse_prefetch_transpose' (100 runs):

         8,580,343      L1-dcache-load-misses                                         ( +-  0.03% )
         4,080,988      L1-dcache-store-misses                                        ( +-  0.41% )
            65,730      L1-dcache-prefetch-misses                                     ( +-  0.38% )
           112,045      L1-icache-load-misses                                         ( +-  4.02% )

       0.301808613 seconds time elapsed                                          ( +-  0.54% )
D = 64
 Performance counter stats for './sse_prefetch_transpose' (100 runs):

         8,595,820      L1-dcache-load-misses                                         ( +-  0.03% )
         4,089,623      L1-dcache-store-misses                                        ( +-  0.32% )
            65,383      L1-dcache-prefetch-misses                                     ( +-  0.38% )
           107,591      L1-icache-load-misses                                         ( +-  4.24% )

       0.303709076 seconds time elapsed                                          ( +-  0.52% )

D = 8 的時候是最好的
> 之後該來探討為啥 8 是最好的

### Raw Counter
在一些系統架構下，有一些 counter 沒有在 `perf list` 裡面，如果是 Intel CPU 的話可以看 [Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3B的19章](http://www.intel.com/content/www/us/en/processors/core/core-technical-resources.html)，要對應到自己的 CPU 型號查 mask number 及 event number。
我的 CPU 是 Intel Core i5-3337U，是屬於第三代的，對應可用的 Raw Counter 是 **LOAD_HIT_PRE.SW_PF** 跟 **LOAD_HIT_PRE.HW_PF**

#### 測試(這邊 D = 8)

- `perf stat -e r014c ./raw_counter_sse`

 Performance counter stats for './sse_transpose' (100 runs):

               309      r014c                                                         ( +-  2.23% )

       0.344172960 seconds time elapsed                                          ( +-  0.48% )

- `perf stat -e r014c ./raw_counter_sse_prefetch`

 Performance counter stats for './sse_prefetch_transpose' (100 runs):

           656,289      r014c                                                         ( +-  2.72% )

       0.288038377 seconds time elapsed                                          ( +-  0.47% )

- `perf stat -e r024c ./time_sse`

 Performance counter stats for './sse_transpose' (100 runs):

           599,852      r024c                                                         ( +-  0.34% )

       0.347760797 seconds time elapsed                                          ( +-  0.65% )

- `perf stat -e r024c ./time_sse_prefetch`

 Performance counter stats for './sse_prefetch_transpose' (100 runs):

           614,884      r024c                                                         ( +-  0.79% )

       0.293914743 seconds time elapsed                                          ( +-  0.82% )

整體來說，prefetch 還是有增加 cache-hit 的次數

## SSE/AVX intrinsic
這裡有一個很不一樣的是 `__m256i _mm256_permute2x128_si256 (__m256i a, __m256i b, const int imm8)`，利用控制 `imm8` 可以達到 unpack_ep128 的效果

- Operation

SELECT4(src1, src2, control){
	CASE(control[1:0])
	0:	tmp[127:0] := src1[127:0]
	1:	tmp[127:0] := src1[255:128]
	2:	tmp[127:0] := src2[127:0]
	3:	tmp[127:0] := src2[255:128]
	ESAC
	IF control[3]
		tmp[127:0] := 0
	FI
	RETURN tmp[127:0]
}

dst[127:0] := SELECT4(a[255:0], b[255:0], imm8[3:0])
dst[255:128] := SELECT4(a[255:0], b[255:0], imm8[7:4])
dst[MAX:256] := 0

> 發現我的電腦根本不能用 AVX2，WTH 該買新電腦了

## Reference
- [吳彥寬學長筆記](https://hackmd.io/s/ryTASBCT)
- [kaizsv](https://hackmd.io/IwVmCMGMCYFMGYC0A2e5mICwAYDs5EBDAMwBMAORWU8ATl2N2EhHNiA=?view)