# prefetcher
:::info
本實驗出自 [Cache 原理和實際影響](https://hackmd.io/s/HkyscQn2z)，本篇僅針對數據與文章作整理
:::
[prefetcher 程式碼](https://github.com/vonchuang/prefetcher)
此程式碼是針對一個 4X4 的矩陣作旋轉，將 row 和 col 的值互換，並考慮 navie_transopse、sse_prefetch_transpose、sse_prefetch_transpose 的效能
* Makefile
分別有以下三種程式可執行
* navie_transopse
* sse_prefetch_transpose
* sse_prefetch_transpose
皆透過定義巨集 ```#define NAIVE 1``` 、 ```#define SSE 1``` 、 ```#define SSE_PREFETCH 1``` 來分別執行各個 transpose ， 將各個 .c include 到 main.c 裡去執行
* cache-test
```perf stat --repeat 10``` 針對以下目標進行分析，重複執行 10 次該程序，並顯示每個 event 的變化區間，以分析 cache miss/hit。
```
cache-misses,cache-references,instructions,cycles,L1-dcache-loads,L1- dcache-load-misses,L1-dcache-prefetches,L1-dcache-prefetch-misses,LLC- loads,LLC-load-misses,LLC-prefetches,LLC-prefetch-misses
```
* main.c
```#include IMPL```依據 Makefile 的 DIMPL 分別 include 不同的 transpose 檔，再依該檔判斷並執行不同的 transpose
```=c
#if defined(NAIVE)
naive_transpose(testin, testout, 4, 4);
#elif defined(SSE)
sse_transpose(testin, testout, 4, 4);
#elif defined(SSE_PREFETCH)
sse_prefetch_transpose(testin, testout, 4, 4);
#endif
```
* naive_transpose.c
```=c
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);
}
```
假設 cache line 為 4 words，1 word 就是 sizeof(int)，也就是 4Bytes
可以得到此矩陣為
|src[i][j]|j=0|j=1|j=2|j=3|
|:--:|:--:|:--:|:--:|:--:|
|i=0|0|1|2|3|
|i=1|4|5|6|7|
|i=2|8|9|10|11|
|i=3|12|13|14|15|
將 src 的數值 + row 的值乘 4 + col，輸入相對應的 dst
將程式運作的情形換成一維陣列的 address 操做的話
src + 0x4 + 0 **miss!**
src + 1x4 + 0 **miss!**
src + 2x4 + 0 **miss!**
src + 3x4 + 0 **miss!**
src + 1x4 + 1 **miss!**
src + 2x4 + 1 **miss!**
src + 3x4 + 1 **miss!**
src + 4x4 + 1 **miss!**
src + 1x4 + 2 **miss!**
src + 2x4 + 2 **miss!**
src + 3x4 + 2 **miss!**
src + 4x4 + 2 **miss!**
src + 1x4 + 3 **miss!**
src + 2x4 + 3 **miss!**
src + 3x4 + 3 **miss!**
src + 4x4 + 3 **miss!**
可以發現幾乎每次相鄰的指令所需要的位置都差了 4 ，在換 row 的時候位置還差更遠，超過了我們假設的 cache line，因此在 src 的部份每次都是 cache miss ，影響效率。
dst 的部份
|src[i][j]|j=0|j=1|j=2|j=3|
|:--:|:--:|:--:|:--:|:--:|
|i=0|0|4|8|12|
|i=1|1|5|9|13|
|i=2|2|6|10|14|
|i=3|3|7|11|15|
dst + 0x4 + 0 **miss!**
dst + 0x4 + 1 **hit!**
dst + 0x4 + 2 **hit!**
dst + 0x4 + 3 **hit!**
dst + 1x4 + 0 **miss!**
dst + 1x4 + 1 **hit!**
dst + 1x4 + 2 **hit!**
dst + 1x4 + 3 **hit!**
dst + 2x4 + 0 **miss!**
dst + 2x4 + 1 **hit!**
dst + 2x4 + 2 **hit!**
dst + 2x4 + 3 **hit!**
dst + 3x4 + 0 **miss!**
dst + 3x4 + 1 **hit!**
dst + 3x4 + 2 **hit!**
dst + 3x4 + 3 **hit!**
由於 dst 會先改變 col 的值，所以除了在更換 row 之外，所需的位置相差都只有一，可以放進 cache 裏面，cache miss 約是 25%。
```
./naive_transpose
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
naive: 286608 us
Performance counter stats for './naive_transpose' (10 runs):
36,323,247 cache-misses # 84.896 % of all cache refs ( +- 0.42% )
42,785,537 cache-references ( +- 0.34% )
1,448,818,638 instructions # 1.52 insns per cycle ( +- 0.00% )
954,753,577 cycles ( +- 0.49% )
0.407341478 seconds time elapsed ( +- 0.75% )
```
* sse_transpose.c
```=c
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);
}
}
}
```
矩陣內的資料是 int，所以 32 bytes
* __m128i
在 [emmintrin.h](https://github.com/gcc-mirror/gcc/blob/master/gcc/config/i386/emmintrin.h) 內的一種資料型態
```typedef long long __m128i __attribute__ ((__vector_size__ (16), __may_alias__));```
簡單來說，就是 [SSE](https://zh.wikipedia.org/wiki/SSE) 暫存器的資料型態。
* _mm_loadu_si128
```=c
extern __inline __m128i __attribute__((__gnu_inline__,
__always_inline__, __artificial__))
_mm_loadu_si128 (__m128i_u const *__P)
{
return *__P;
}
```
load in 到 sse 暫存器裏面
* _mm_unpacklo_epi32 / _mm_unpackhi_epi32
```=c
extern __inline __m128i __attribute__((__gnu_inline__,
__always_inline__, __artificial__))
_mm_unpacklo_epi32 (__m128i __A, __m128i __B)
{
return (__m128i)__builtin_ia32_punpckldq128 ((__v4si)__A, (__v4si)__B);
}
```
* _mm_storeu_si128
```
extern __inline void __attribute__((__gnu_inline__,
__always_inline__, __artificial__))
_mm_storeu_si128 (__m128i_u *__P, __m128i __B)
{
*__P = __B;
}
```
將後者的 sse 暫存器的值 store 到某個位置裏面
* 這裡使用 Blocking 來提升效能，將一個程式中的數據組織後加載到 Cache 中，並在這個片中進行所有的讀和寫，然後就丟掉這個片。用以提高 Temporal Locality，在一些沒有 Prefetch 的系統上獲得性能收益。
```
./sse_transpose
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: 156674 us
Performance counter stats for './sse_transpose' (10 runs):
14,862,894 cache-misses # 76.874 % of all cache refs ( +- 0.27% )
19,334,067 cache-references ( +- 0.12% )
1,236,929,124 instructions # 1.69 insns per cycle ( +- 0.00% )
732,059,630 cycles ( +- 0.25% )
0.293016506 seconds time elapsed ( +- 0.51% )
```
* sse_prefetch_transpose.c
```=c
void sse_prefetch_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) {
#define PFDIST 8
_mm_prefetch(src+(y + PFDIST + 0) *w + x, _MM_HINT_NTA);
_mm_prefetch(src+(y + PFDIST + 1) *w + x, _MM_HINT_NTA);
_mm_prefetch(src+(y + PFDIST + 2) *w + x, _MM_HINT_NTA);
_mm_prefetch(src+(y + PFDIST + 3) *w + x, _MM_HINT_NTA);
}
}
}
```
在使用 上個 sse blocks 的技巧之前，先將資料用軟體的方式放入 cache 裏面
prefetch 指令的主要目的，是提前讓 CPU 載入稍後運算所需要的資料。通常是在對目前的資料進行運算之前，告訴 CPU 載入下一筆資料。這樣就可以讓目前的運算，和載入下一筆資料的動作，可以同時進行。
* _mm_prefetch(char *p, int i)
* p : 存取資料的位置
* i : 選擇事先存取的方式（_MM_HINT_T0,_MM_HINT_T1,_MM_HINT_T2,_MM_HINT_NTA）
* T0 : 事先載入資料到所有層級的 Cache 中
* T1 : 事先載入資料到層級為 2 級及以上的 Cache 中（除了 L1 以外的所有 Cache）
* T2 : 事先載入資料到層級為 3 級及以上的 Cache 中（除了 L1 和 L2 以外的所有 Cache）
* NTA : 事先載入資料到非臨時且靠近 processor 的 Cache 中（通常是 L1 cache 或 L2 cache），可最小化對 Cache 的汙染
```
./sse_prefetch_transpose
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: 53462 us
Performance counter stats for './sse_prefetch_transpose' (10 runs):
7,985,899 cache-misses # 62.299 % of all cache refs ( +- 0.82% )
12,818,659 cache-references ( +- 0.57% )
1,282,884,219 instructions # 2.19 insns per cycle ( +- 0.00% )
584,641,155 cycles ( +- 0.20% )
0.172537169 seconds time elapsed ( +- 0.68% )
```
:::info
todo Raw counters
:::
Sign in with Wallet
Connect another wallet