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

論文閱讀紀錄

• 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 語言：物件導向程式設計篇 學習封裝技巧，然後改寫 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 發現除了 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 只要不要挑太小，效能就不會太差。