2017q1 Homework3 (software-pipelining)

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 ``` # [論文](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)閱讀紀錄 - 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 的情況分類為六種 : ![](https://i.imgur.com/llyvNac.png) - 文中透過實驗得出的一些結果 - 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 語言：物件導向程式設計篇](https://hackmd.io/s/HJLyQaQMl) 學習封裝技巧，然後改寫 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](https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=4077,4080,4081) 發現除了 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 ``` ![](https://i.imgur.com/Xql8aJl.png) 首先比較特殊的地方是只有最一開始 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 ``` ![](https://i.imgur.com/OBt9szS.png) 和 D = 8 時差異不明顯，還是跟只用 AVX 差不多，如同論文內所說，Distance 只要不要挑太小，效能就不會太差。