# 2017q1Homework3(software-pipelining)
contributed by <`janetwei`>

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

### 背景知識
* hardware prefetcher
* stride prefetcher
發生於固定間隔的 cache misses， 會 prefetch 接下來相同間隔的 data
例如：
Miss address streams：1,4,7,10
Prefetch：13,16,19
* [Global History Buffer(GHB)](http://www.eecg.toronto.edu/~steffan/carg/readings/ghb.pdf):
以 FIFO table 儲存完整的 miss addresses ，並藉由 hash table 作為 index ，增加搜尋速度以及減少空間上的浪費
Two advantages:
1. 藉由排除 table 中舊的資料增加 prefetcher 精確度
2. 包含完整的 cache misses 紀錄，有機會產生更有效率的 prefetching methods

* stream prefetcher
發生於連續的 cache misses， 會 prefetch 連續的 data
例如：
Miss address streams:1, 2, 3, 4
Prefetch:5, 6, 7
* software prefetcher
* prefetch intrinsics on top of **gcc** or **icc** compiler-inserted prefetching

* 不同結構與其所對應到的prefetching

### 名詞解釋
* **state-of-the-art compiler：** icc&gcc
state-of-the-art refers to the highest level of general development

## Transpose 比較
* 修改 Makefile 讓 `naive_transpose`， `sse_transpose` 以及 `sse_prefetech_transpose`分別產生一個執行檔，並且用 perf 得出 cache-misses
* 為了使` main.c `更簡潔，不用宣告過多的變數，因此在` impl.c `用 `ifdef` 區分三種方法，在` main.c `中皆用` transpose `表示
* `perf stat` 執行` naive_transpose `， ` sse_transpose ` 以及 ` sse_prefetech_transpose ` 的結果：
* **naive_transpose**

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

         2373,2361      cache-misses              #   91.823 % of all cache refs      ( +-  0.18% )
         2584,5669      cache-references                                              ( +-  0.22% )
      14,4992,4249      instructions              #    1.27  insns per cycle          ( +-  0.07% )
      11,4518,7288      cycles                                                        ( +-  0.14% )

       0.429675541 seconds time elapsed                                          ( +-  0.15% )

*
* **sse_transpose**

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

         1112,3866      cache-misses              #   87.496 % of all cache refs      ( +-  0.13% )
         1271,3513      cache-references                                              ( +-  0.16% )
      12,3722,9010      instructions              #    1.56  insns per cycle          ( +-  0.02% )
       7,9074,0895      cycles                                                        ( +-  0.40% )

       0.314147189 seconds time elapsed                                          ( +-  0.37% )

*
* **sse_prefetech_transpose**

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

          817,8491      cache-misses              #   83.515 % of all cache refs      ( +-  0.32% )
          979,2892      cache-references                                              ( +-  0.15% )
      12,8305,7252      instructions              #    2.04  insns per cycle          ( +-  0.00% )
       6,2876,9073      cycles                                                        ( +-  0.22% )

       0.235844855 seconds time elapsed                                          ( +-  0.31% )

由 perf stat 的結果比較， sse_prefetch_transpose 的 cache misses 最少

## Code
### `impl.c`
* **sse_transpose()**
__m128i 為 data type
* `__m128i _mm_loadu_si128 (__m128i *p);`
Loads 128-bit value. Address p not need be 16-byte aligned
而整數為 32bits，每次 load 可以載入 4個整數（column），因此程式碼中呼叫四次，可以紀錄一個 4*4的矩陣

|***矩陣***|**a0**|**a2**|**a3**|**a4**|
|:-:|:-:|:-:|:-:|:-:|
|***I0***|**01**|**02**|**03**|**04**|
|***I1***|**11**|**12**|**13**|**14**|
|***I2***|**21**|**22**|**23**|**24**|
|***I3***|**31**|**32**|**33**|**34**|

* `__m128i _mm_unpacklo_epi32 (__m128i a, __m128i b);`
將兩個 128 bits 的 data 取出低位的 64bits(兩組 32bits的整數) 並交叉組合
r0 = a0 ; r1 = b0 ; r2 = a1 ; r3 = b1;
* `__m128i _mm_unpackhi_epi32 (__m128i a, __m128i b);`
將兩個 128 bits 的 data 取出高位的 64bits(兩組 32bits的整數) 並交叉組合
r0 = a2 ; r1 = b2 ; r2 = a3 ; r3 = b3

>> 上述兩個函數是將原始的矩陣轉置

|***轉置矩陣***|***a0***|***a2***|***a3***|***a4***|
|:-:|:-:|:-:|:-:|:-:|
|***I0***|**01**|**11**|**21**|**31**|
|***I1***|**02**|**02**|**22**|**32**|
|***I2***|**03**|**13**|**23**|**33**|
|***I3***|**04**|**14**|**24**|**34**|
* `_mm_storeu_si128 (__m128i *p, __m128i a);`
Stores 128-bit value. *p = a;
將轉置矩陣的結果存回陣列中

**由於一次 load 和 store 為4個整數，因此若要實現sse_transpose 矩陣的行與列必須要為4的倍數**