Try   HackMD

2017q1 Homework3 (software-pipelining)

contributed by <tina0405>

中英文字間請以空白隔開
課程助教

好,已改。謝謝助教 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 重點提示和解說

  • 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:
    可以隨機性地在資料被用到之前就將其取入快取。這一技術稱為Prefetch。本質上，加載整個快取塊其實即是一種預取。

因為還是不是很理解，想拿實際例子看看:

  • DDR(雙倍資料傳輸)預取原理
    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延伸的一部份，後面的例子有舉出軟體預取的函式說明。（會在論文筆記中討論）

  • 參考 迴圈展開：

    • 文中的意思是希望減少判斷次數，因此將迴圈內的式子展開，例如：











     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:

    • loop 的運算時間/延遲的迴圈數

  • 參考 branch instruction

    • 可以分成兩種：
      • 條件式 (Conditional Branch):
        1.branch if equal (beq)
        2.branch if not equal (bne)
      • 非條件式:
        1.jump (j)

  • 參考 pipeline1，pipeline2

    1.讀取指令
    2.指令解碼與讀取暫存器
    3.執行
    4.記憶體存取
    5.寫回暫存器

    • 本來要一行一行讀的指令，現在經過 pipeline 降低CPU的閒置時間，進而提升效率

  • 頻寬（Bandwidth）：傳輸媒介的最大吞吐量（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

  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
Loads 128-bit value.





__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.






__m128i _mm_unpacklo_epi32 (__m128i a, __m128i b);

/*Return Value
r0 := a0 ; r1 := b0
r2 := a1 ; r3 := b1*/

原版的 transpose：







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 倍之多判斷次數，我認為這是他變快的原因。























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版本：














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，參照下方「見賢思齊：共筆選讀」的實驗，嘗試用 AVX 進一步提昇效能。分析的方法可參見 Matrix Multiplication using SIMD

1.修改 Makefile，產生新的執行檔，分別對應於 naive_transpose, sse_transpose, sse_prefetch_transpose(學習 phonebook 的做法)，學習 你所不知道的 C 語言：物件導向程式設計篇 提到的封裝技巧，以物件導向的方式封裝轉置矩陣的不同實作，得以透過一致的介面 (interface) 存取個別方法並且評估效能





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() ，一直程式記憶體區段錯誤。































        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：刪除檔命令



Clean:
        $(RM) naive sse ssep

想說改成下面：（直接跑結果）










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，用 SSE/AVX intrinsic 來改寫程式碼

Last changed by 
 
許雅雯
0
638
Published on HackMD