# 2017q1 Homework3 (software-pipelining)
contributed by <`tina0405`>
>>中英文字間請以空白隔開
>>[name=課程助教][color=red]
>>好,已改。謝謝助教 [name=tina0405]
## 作業要求1：
#### 論文筆記
* About software and hardware prefetching:
* 文中寫在改進軟體預取方面：
* Positive 的表現增加 5%。
* Negative 的表現減少 5%。
（Q：但是我在這段看不出與和者做比較，5% 是全部的 5% 嗎？所以來看看 Table V）
* (TABLE V)只有軟體預取沒有硬體的情形下，各個 baseline 上的執行時間。
* 此篇論文也丟出3個問題：
* 在軟體預取上什麼是它的限制和 overhead？
* 在硬體預取上什麼是它的限制和 overhead？
* 硬體的預取受限於 stream 和 stride 的預取。
* 應用軟體+硬體預取有什麼好處？
>> 在 steaming prefetch 和 GHB prefetch,intrinsics 上目前還沒看到明確的解釋
* TABLE.I說不只針對普通的資料結構還有特別的，例如：RDS（Recursive Data Structure）insert prefetch intrinsics。
* hashing 更難有效的預取。
* 很多軟體和硬體的預取目的都是在預測之後的 cache miss addresses
註：Temporal — Data will be used again soon
參考[論文 When Prefetching Works, When It Doesn’t, and Why 重點提示和解說](https://hackmd.io/s/HJtfT3icx#)
* Software Prefetch Intrinsics:
* 例子：_mm_prefetch(char *ptr,int hint)
* --> 需要有預取的地址及要用到的 hint (上圖)
* 一個 intrinsic 大致上可以分成 2個指令（直接獲取的地址預取）或是4個指令（間接獲取的記憶體地址）
>>關於這裡的直接和間接：
我的理解是
直接：直接得到(eg.A[i])的東西。
間接：透兩層以上值的傳遞(eg.B[A[i]])才得到。
* 預取分為六類：
* Software Prefetch Distance：
* 簡稱 D=[l/s]
* l->prefetch latency,s->loop bady 的最短路徑。
* 對 cache miss 而言，D 有重大的影響：
* 不幸的是，平均的 memory lantency 和 執行迭代迴圈的時間都一直在改變。
* 所以 D 要夠大，大到可以剛好不會遇到 lantency
* 但如果 D 太大，預取的資料將會被移出有效的快取，導致以下缺點：
1. 原本的資料將不再被預取（導致2）
2. 很少有機會覆蓋
3. 綜合以上兩點，cache miss 增加（我們不樂見的）
* Direct and Indirect Memory Indexing
* direct memory indexing:
* only one prefetch load instruction
* 建議用硬體做，更容易預取。
-->因為記憶體的地址在 STREAM 和 STRIDE 上是有規律的
* indirect memory indexing:
* 用軟體做相對硬體簡單
* 需要更多的 overhead 比起 direct
>>想法：
>>預取就像間接的索引，會有更多的 overhead，但我之前一直覺得有很多的 overheads 是應該會更慢嗎？可是忽略了其實預取解決了 latency 的問題，在L1->L2->L3->中找不到所發生的cache miss，再回到主記憶體去找的 latency 是比 overhead更久的。
* 軟體預取的好處（比起硬體）：
* 大量的stream
* 當stream數超過硬體的容量（硬體缺點）
* 軟體的預取插入時會要求獨立每一筆 stream ，但硬體卻只會覺得收到極大的資料量。
* 極短的stream
* 硬體至少會花費兩個 cache misses 去偵測 stream/stride 的距離
* stream 太短沒有足夠的 cache misses 去做硬體的預取和載入有用的 cache block 。
* 不規則的記憶體拿取（軟體的優點）
* 舉例：因為硬體是有規則的拿取，所以如果像 RDS 這樣的 indirection ，會需要非常複雜的結構。
* cache locality hint
* 現今高效能的硬體依然是放置資料在lower level cache ， 而軟體則是放在 L1 ，那如果硬體要從 L2->L1 就會發生 Latency 。
* loop bounds
* 軟體再這邊可以贏硬體是因為多了一些像是 loop unrolling , software pipelining , branch instruction。(在名詞解釋中討論)
* 軟體預取的負面衝擊
* 增加指令數：
* 不像硬體，軟體的預取會消耗掉拿取和執行的頻寬還有機械的資源。拿例子來說圖中的bwave就因為軟體預取而增加100%。
* 關於靜態的插入
就是因為再軟體內沒有一套固定的機制（不像硬體），所以也沒有一種可以適應的改變，那些變化的 memory latency 或 快取的大小也都無從掌握，導致插入靜態參數的困難。
* 程式結構的改變
* 因為執行時增加的指令數，讓軟體預取變困難，有時候適當的改變結構是必要的，例如：拆迴圈。
>>本來在 indirection 的時，軟體的不規則是優點，但在insert 這裡，反而變成了缺點。
* 軟體和硬體合用以增加效用
* 剛剛有看到軟硬體面對 stream 的優缺點，所以這裡的作法是：
* 硬體去負責有規律的stream
* 軟體去負責沒規律的stream
* 利用軟體去 training 硬體，當軟體預取慢時，就由硬體預取來改進時間。
>>在這邊我對 training 一詞有不太理解的地方，如果以之前影像處理所說的 training 就是跑過一次後記住那些特徵，但這邊難道也是硬體跑過後要去紀錄哪個指令特別快或慢，再去補足嗎？
* 軟體和硬體合用卻反效果
* 這邊early request說5.2.1再說明，有點看不懂為什麼是缺點，等看到那再回來補：
* 軟體預取的請求會減低硬體 training
* 軟體預取的指令會觸發硬體預取->造成 early request
* 實驗方法
* prefetch intrinsic insertion algorithm
* prefetch 候選人應符合以下條件:
* L1 cache misses / 1000 個指令 (MPKI) > 0.05
1.k 是常數
2.L = average memory latency
3.IPCbench = profiled average IPC/one benchmack
4.Wloop 是迴圈平均每一圈的指令數
## 名詞解釋
* [prefetch:](https://zh.wikipedia.org/zh-tw/CPU%E7%BC%93%E5%AD%98)
可以隨機性地在資料被用到之前就將其取入快取。這一技術稱為Prefetch。本質上，加載整個快取塊其實即是一種預取。
因為還是不是很理解，想拿實際例子看看:
* [DDR(雙倍資料傳輸)預取原理](http://www.techbang.com/posts/17190-development-history-of-memory-ddr-and-gddr-difference)
Prefetch（預取）技術，DDR、DDR2、DDR3的分別採用2bit、4bit、8bit預取技術，藉此得以讓時脈翻倍。預取簡單來說，就是在I/O控制器發出請求之前，預先準備好2bit、4bit、8bit的資料。可將其視為並行（Parallel）轉換為串行（Serial）。其轉換類似多條水管連接到某個裝置，若輸出的水管口徑相同，那麼水壓（速率）必定提升。
~~~
自己的理解p refetch:
在 I/O 發出時脈前，就先將他就先將所需的資料存入快取，當資料真正被需要時，
就可以很快地拿出來比起去 request from memory 快很多。
~~~
* Software Prefetch Intrinsics:
文中解釋，是 X86 SSE SIMD延伸的一部份，後面的例子有舉出軟體預取的函式說明。（會在論文筆記中討論）
* 參考 [迴圈展開](https://www.ptt.cc/bbs/C_and_CPP/M.1246071002.A.A54.html)：
* 文中的意思是希望減少判斷次數，因此將迴圈內的式子展開，例如：
~~~ clike=
for ( i = 0; i < 100; ++i )
sum += a[ i ];
//展開成下列
for ( i = 0; i < 100; i += 5 )
{
sum += a[ i ];
sum += a[ i + 1 ];
sum += a[ i + 2 ];
sum += a[ i + 3 ];
sum += a[ i + 4 ];
}
~~~
* 參考 [loop bound](http://dsp.ee.ncu.edu.tw/course/VDSP_99/lecture/ch2.pdf):
* loop 的運算時間/延遲的迴圈數
* 參考 [branch instruction](http://ithelp.ithome.com.tw/articles/10158857)
* 可以分成兩種：
* 條件式 (Conditional Branch):
1.branch if equal (beq)
2.branch if not equal (bne)
* 非條件式:
1.jump (j)
* 參考 [pipeline1](https://zh.wikipedia.org/zh-tw/%E6%8C%87%E4%BB%A4%E7%AE%A1%E7%B7%9A%E5%8C%96)，[pipeline2](http://blog.xuite.net/fishrabbit/BroadBand/4502419-Pipeline+Hazard)
1.讀取指令
2.指令解碼與讀取暫存器
3.執行
4.記憶體存取
5.寫回暫存器
* 本來要一行一行讀的指令，現在經過 pipeline 降低CPU的閒置時間，進而提升效率
* [ 頻寬（Bandwidth）](http://blogger.gtwang.org/2013/12/network-lantency-and-bandwidth.html)：傳輸媒介的最大吞吐量（throughput）。
>>如同上面所說的如果當 Bandwidth 就只有這麼大，那我軟體增加的指令數就會佔用有限的頻寬。
## 作業要求2：
# 開發環境
~~~
tina@tina-X550VB:~$ 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-3230M CPU @ 2.60GHz
製程： 9
CPU MHz： 1270.750
CPU max MHz: 3200.0000
CPU min MHz: 1200.0000
BogoMIPS: 5188.47
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
~~~
#### 1.執行 [prefetcher](https://github.com/sysprog21/prefetcher)
~~~
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
sse prefetch: 96069 us
sse: 155224 us
naive: 294317 us
~~~
#### 2.說明 `naive_transpose`, `sse_transpose`, `sse_prefetch_transpose` 之間的效能差異，以及 prefetcher 對 cache 的影響
先看一下定義：參考[Microsoft](https://technet.microsoft.com/en-us/library/x8atst9d(VS.90).aspx)
Loads 128-bit value.
~~~ clike=
__m128i _mm_load_si128 (__m128i *p);
/*Return Value
Returns the value loaded in a variable representing a register.*/
~~~
Interleaves the lower 2 signed or unsigned 32-bit integers in a with the lower 2 signed or unsigned 32-bit integers in b.
~~~ clike=
__m128i _mm_unpacklo_epi32 (__m128i a, __m128i b);
/*Return Value
r0 := a0 ; r1 := b0
r2 := a1 ; r3 := b1*/
~~~
#### 原版的 transpose：
~~~ clike=
void naive_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x++)
for (int y = 0; y < h; y++)
*(dst + x * h + y) = *(src + y * w + x);
}
~~~
#### sse 版本：
* 我覺得以下版本利用了論文中的 loop unrolling 以減少判斷次數，減少 4 倍之多判斷次數，我認為這是他變快的原因。
~~~ clike=
void sse_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x += 4) {
for (int y = 0; y < h; y += 4) {
__m128i I0 = _mm_loadu_si128((__m128i *)(src + (y + 0) * w + x));
__m128i I1 = _mm_loadu_si128((__m128i *)(src + (y + 1) * w + x));
__m128i I2 = _mm_loadu_si128((__m128i *)(src + (y + 2) * w + x));
__m128i I3 = _mm_loadu_si128((__m128i *)(src + (y + 3) * w + x));
__m128i T0 = _mm_unpacklo_epi32(I0, I1);
__m128i T1 = _mm_unpacklo_epi32(I2, I3);
__m128i T2 = _mm_unpackhi_epi32(I0, I1);
__m128i T3 = _mm_unpackhi_epi32(I2, I3);
I0 = _mm_unpacklo_epi64(T0, T1);
I1 = _mm_unpackhi_epi64(T0, T1);
I2 = _mm_unpacklo_epi64(T2, T3);
I3 = _mm_unpackhi_epi64(T2, T3);
_mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0);
_mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1);
_mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2);
_mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3);
}
}
}
~~~
#### sse 和 prefetch版本：
~~~ clike=
void sse_prefetch_tranint w, int h)
{
for (int x = 0; x < w; x += 4) {
for (int y = 0; y < h; y += 4) {
#define PFDIST 8
_mm_prefetch(src+(y + PFDIST + 0) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + PFDIST + 1) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + PFDIST + 2) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + PFDIST + 3) *w + x, _MM_HINT_T1);
//......
}
}
}
~~~
* _mm_prefetch(char *ptr,int hint)
* 需要有預取的地址及要用到的 hint
* 我認為他在預取地址輸入 src+(y + PFDIST + 0) *w + x 是為了用最簡單方式但又不至於重複使用到地址的方法。
* 這裡使用 MM_HINT_T1 -> temporal data with respect to first level cache
* 快取的確有幫助 fetch 資料的速度，減少 lantency ，相對真的快很多，但我心裡想的是如果可以用 MM_HINT_T0 ，有 all level cache 可以幫助，那等等 fetch 資料時如果L1找不到再去L2->L3 找的速度應該還是比L1找不到往下找最後到 main memory 去找快很多吧！
### 測試（每組測三次）：
~~~
MM_HINT_T0:
sse prefetch: 90836 us
sse: 157197 us
naive: 335376 us
sse prefetch: 92018 us
sse: 151436 us
naive: 317203 us
sse prefetch: 98582 us
sse: 161148 us
naive: 355007 us
MM_HINT_T1:
sse prefetch: 88544 us
sse: 134979 us
naive: 282280 us
sse prefetch: 83574 us
sse: 138647 us
naive: 277921 us
sse prefetch: 83886 us
sse: 140416 us
naive: 281465 us
MM_HINT_T2
sse prefetch: 118629 us
sse: 177054 us
naive: 354652 us
sse prefetch: 114252 us
sse: 178407 us
naive: 363896 us
sse prefetch: 130989 us
sse: 194430 us
naive: 380923 us
~~~
>>結果並不如預 MM_HINT_T1 （在 L1 的資料之後將會被使用）其實整體而言是花費最少時間的，我猜測應該是 MM_HINT_T2（在 L1，L2 的資料之後將會被使用），雖然多了空間去存放資料，但如果那些資源卡在那裡還未 access 或 release ， 其等待時間將可能增加其他方面 latency。
## 作業要求3：
#### 在 github 上 fork [prefetcher](https://github.com/sysprog21/prefetcher)，參照下方「見賢思齊：共筆選讀」的實驗，嘗試用 AVX 進一步提昇效能。分析的方法可參見 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx)
#### 1.修改 `Makefile`，產生新的執行檔，分別對應於 `naive_transpose`, `sse_transpose`, `sse_prefetch_transpose`(學習 [phonebook](s/S1RVdgza) 的做法)，學習 [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/s/HJLyQaQMl) 提到的封裝技巧，以物件導向的方式封裝轉置矩陣的不同實作，得以透過一致的介面 (interface) 存取個別方法並且評估效能
* 參考第一次作業[compute-pi](https://github.com/tina0405/compute-pi)，和[makefile的撰寫規則](http://linux.org.tw/CLDP/OLD/doc/makefile-ch2.html)
* 先把 makefile 分成三個執行檔`naive`, `sse_transpose`, `sse_prefetch_transpose`
~~~ clike=
all: $(GIT_HOOKS) main.c
$(CC) $(CFLAGS) main.c -DNAIVE -o naive
$(CC) $(CFLAGS) main.c -DSSE -o sse
$(CC) $(CFLAGS) main.c -DSSEPRE -o ssep
~~~
* 在 main.c 裡分組，需要用到的再 malloc 位置，還有記得要free() ,一開始就是因為忘記 free() ，一直程式記憶體區段錯誤。
~~~ clike=
struct timespec start, end;
int *src = (int *) malloc(sizeof(int) * TEST_W * TEST_H);
srand(time(NULL));
for (int y = 0; y < TEST_H; y++)
for (int x = 0; x < TEST_W; x++)
*(src + y * TEST_W + x) = rand();
#if defined(SSEPRE)
int *out0 = (int *) malloc(sizeof(int) * TEST_W * TEST_H);
clock_gettime(CLOCK_REALTIME, &start);
sse_prefetch_transpose(src, out0, TEST_W, TEST_H);
clock_gettime(CLOCK_REALTIME, &end);
printf("sse prefetch: \t %ld us\n", diff_in_us(start, end));
free(out0);
#endif
#if defined(SSE)
int *out1 = (int *) malloc(sizeof(int) * TEST_W * TEST_H);
clock_gettime(CLOCK_REALTIME, &start);
sse_transpose(src, out1, TEST_W, TEST_H);
clock_gettime(CLOCK_REALTIME, &end);
printf("sse: \t\t %ld us\n", diff_in_us(start, end));
free(out1);
#endif
#if defined(NAIVE)
int *out2 = (int *) malloc(sizeof(int) * TEST_W * TEST_H);
clock_gettime(CLOCK_REALTIME, &start);
naive_transpose(src, out2, TEST_W, TEST_H);
clock_gettime(CLOCK_REALTIME, &end);
printf("naive: \t\t %ld us\n", diff_in_us(start, end));
free(out2);
#endif
free(src);
~~~
* ### Makefile的一般結構：
target：dependency
command
* target（目標）：一個目標檔，可以是Object檔，也可以是執行檔。還可以是一個標籤（Label）。
* dependency
（依賴）：要產生目標檔（target）所依賴哪些檔。
* command（命令）：
建立專案時需要執行的shell命令
* 注意：
command部分的每行的縮進必須要使用Tab鍵，就算用空白推到相應位置也不行，會出現紅色警示。
最後要記得執行檔也要clean：
* RM：刪除檔命令
~~~ clike=
Clean:
$(RM) naive sse ssep
~~~
想說改成下面：（直接跑結果）
~~~ clike=
sse_transpose: main.c
$(CC) main.c -DSSE -o sse
./sse
sse_prefetch_transpose: main.c
$(CC) $(CFLAGS) main.c -DSSEPRE -o ssep
./ssep
naive_transpose: main.c
$(CC) $(CFLAGS) main.c -DNAIVE -o naive
./naive
~~~
*
#### 2.用 perf 分析 cache miss/hit
#### 3.學習 `perf stat` 的 raw counter 命令
#### 4.參考 [Performance of SSE and AVX Instruction Sets](http://arxiv.org/pdf/1211.0820.pdf)，用 SSE/AVX intrinsic 來改寫程式碼
Sign in with Wallet
Connect another wallet