2017q1 Homework3 (software-pipelining)
===
contributed by < `vtim9907` >
# 開發環境
- OS : Ubuntu 16.04.2 LTS
- Kernel Version : 4.8.0-36-generic
- Memory : 32 GB
- CPU : Intel® Core™ i5-6600 Processor
- cache :
- L1i cache : 4*32 KB
- L1d cache : 4*32 KB
- L2 cache : 4*256 KB
- L3 cache : 6144 KB
- L1 cache imformation ( sudo dmidecode -t cache ) :
```
Handle 0x001E, DMI type 7, 19 bytes
Cache Information
Socket Designation: L1 Cache
Configuration: Enabled, Not Socketed, Level 1
Operational Mode: Write Back
Location: Internal
Installed Size: 256 kB
Maximum Size: 256 kB
Supported SRAM Types:
Synchronous
Installed SRAM Type: Synchronous
Speed: Unknown
Error Correction Type: Parity
System Type: Unified
Associativity: 8-way Set-associative
```
# [論文](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)閱讀紀錄
- SW prefetching 用在短陣列、不規則的記憶體存取、減少 L1 cache miss 時，結果幾乎都是正向影響、提升效能。
- 當 SW prefetching 對 HW prefetcher 的 training 產生干擾時，會造成劇烈的負面影響，造成效能下降，尤其是當正在使用 SW prefetch 一部分 streams 的指令。
> 這裡的 training of the hardware prefetcher 的意思應是指因為 HW prefetcher 是做在硬體上的機制，所以這個機制必須要依靠一些先前的紀錄來做判斷，所以才用 "training" 來表達。
- Data structure 的複雜程度也會影響效能，比如說 array 或 RDS 就比較好預測，所以就容易用 SW prefetch；但像 hashing 就比較難預測，所以比較難有效的作 prefetch。
- streams & strided
- unit-stride cache-line accesses as streams
- access stride distances greater than two cache lines as strided
- 將 prefetch 的情況分類為六種 :
- 文中透過實驗得出的一些結果
- SW prefetch 優點
1. Large Number of Streams
2. Short Streams
3. Irregular Memory Access
4. Cache Locality Hint
5. Loop Bounds
- SW prefetch 缺點
1. Increased Instruction Count
2. Static Insertion
3. Code Structure Change
- SW + HW prefetch 優點
1. Handling Multiple Streams
2. Positive Training
- SW + HW prefetch 缺點
1. Negative Training
2. Harmful Software Prefetching
# 分析效能
首先參考 [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/s/HJLyQaQMl) 學習封裝技巧，然後改寫 Makefile 把每個轉置的方法獨立出一個執行檔，之後就比較好做分析。
### NAIVE
- 執行時間
```
naive: 237184 us
```
- 觀察 cache miss 情形
```
Performance counter stats for './naive_transpose' (100 runs):
4143,0725 cache-misses # 86.427 % of all cache refs ( +- 0.33% )
4793,7357 cache-references ( +- 0.30% )
14,4837,4541 instructions # 1.54 insn per cycle ( +- 0.00% )
9,3915,6402 cycles ( +- 0.12% )
0.354528643 seconds time elapsed ( +- 0.21% )
```
### SSE
- 執行時間
```
sse: 154895 us
```
- 觀察 cache miss 情形
```
Performance counter stats for './sse_transpose' (100 runs):
1464,3696 cache-misses # 76.178 % of all cache refs ( +- 0.06% )
1922,2917 cache-references ( +- 0.06% )
12,3647,2526 instructions # 1.80 insn per cycle ( +- 0.00% )
6,8775,1007 cycles ( +- 0.10% )
0.271588039 seconds time elapsed ( +- 0.17% )
```
### SSE prefetch
用 D = 8 跑。
- 執行時間
```
sse prefetch: 43993 us
```
- 觀察 cache miss 情形
```
Performance counter stats for './sse_prefetch_transpose' (100 runs):
807,7417 cache-misses # 64.951 % of all cache refs ( +- 0.19% )
1243,6203 cache-references ( +- 0.13% )
12,8248,3639 instructions # 2.39 insn per cycle ( +- 0.00% )
5,3685,5417 cycles ( +- 0.03% )
0.143776019 seconds time elapsed ( +- 0.13% )
```
### AVX
原本 SSE 是一次 for loop 跑 4 * 4 的矩陣，但換成 AVX 後，一次可以塞的東西是原來的兩倍，所以我把 code 改成一個 loop 就跑 8 * 8 大小的矩陣。
- 執行時間
```
avx: 59237 us
```
- 觀察 cache miss 情形
```
Performance counter stats for './avx_transpose' (100 runs):
1069,2092 cache-misses # 70.618 % of all cache refs ( +- 0.20% )
1514,0732 cache-references ( +- 0.07% )
11,4047,2529 instructions # 2.08 insn per cycle ( +- 0.00% )
5,4719,4266 cycles ( +- 0.12% )
0.185405113 seconds time elapsed ( +- 0.19% )
```
### AVX + (SSE prefetch)
> 原本想用 AVX prefetch 跑跑看，但後來看了 [Intel Intrinsics Guide](https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=4077,4080,4081) 發現除了 SSE 有 prefetch 的指另外，AVX 只有 AVX-512 有 prefetch 的指令可用，而我的 cpu 沒支援，所以沒辦法用。
但我還是想用用看 prefetch ，所以就直接用 SSE prefetch 指令下去跑。
D = 8
- 執行時間
```
avx prefetch: 45097 us
```
- 觀察 cache miss 情形
```
Performance counter stats for './avx_prefetch_transpose' (100 runs):
1120,9174 cache-misses # 71.177 % of all cache refs ( +- 0.10% )
1574,8256 cache-references ( +- 0.10% )
11,6350,5367 instructions # 2.17 insn per cycle ( +- 0.00% )
5,3675,9191 cycles ( +- 0.09% )
0.161260544 seconds time elapsed ( +- 0.14% )
```
## 比較執行時間
目前主要想到變動兩個變數來測量執行時間的差異
1. Array size 的大小
2. Distance 的大小
首先我變動 array size，從原來的 4096 * 4096 開始，之後矩陣的 row 和 column 每次都增加 96，增加 100 次，去觀察各個不同方式的執行時間變化。
```
SSE prefetch : D = 8
AVX using SSE prefetch : D = 8
```
首先比較特殊的地方是只有最一開始 N = 4096 的時候，SSE prefetch 是最快的，可是當矩陣逐漸擴大，使用了 AVX 指令集的矩陣轉置速度卻比 SSE prefetch 還快，而且矩陣大小越大，時間差越多。
> 為何 SSE prefetch 只有最一開始比較快我還沒想清楚，會不會是我 code 寫錯 ＠＠
> 還不確定為何圖中的抖動如此劇烈，我已經盡量把可能會擾亂測試的程式或網頁都關了，可是跑了好幾次，抖動的程度和頻率好像都幾乎一樣，應該不是巧合？ 也許跟 cache 有關，還在思考中。
改變 AVX + SSE prefetch 的 Distance 再測測看：
```
SSE prefetch : D = 8
AVX using SSE prefetch : D = 16
```
和 D = 8 時差異不明顯，還是跟只用 AVX 差不多，如同論文內所說，Distance 只要不要挑太小，效能就不會太差。
Sign in with Wallet
Connect another wallet