2020q3 專題: Assignment 5.13

# 2020q3 專題: Assignment 5.13 contributed by < `yceugene` > ###### tags: `linux2020` `sysprog2020` `final project` > 題目: 參照 [Assign 5.13](https://hackmd.io/@dange/H1bmDn5am)，進行 CS:APP 第 5 章作業 `5.13` (Page 393)，要有可執行的驗證環境 > 參考前一分學員的 Github 實作: [allenchen8210](https://github.com/allenchen8210/team15) > ## 實驗環境實驗環境: :::spoiler ``` shell $ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=18.04 DISTRIB_CODENAME=bionic DISTRIB_DESCRIPTION="Ubuntu 18.04.5 LTS" $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 6 On-line CPU(s) list: 0-5 Thread(s) per core: 1 Core(s) per socket: 6 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 158 Model name: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz Stepping: 10 CPU MHz: 800.249 CPU max MHz: 4400.0000 CPU min MHz: 800.0000 BogoMIPS: 6000.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 9216K NUMA node0 CPU(s): 0-5 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp md_clear flush_l1d $ uname -sr Linux 5.4.0-52-generic $ gcc --version gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0 ``` ::: :::warning 預期進行方式: 1. 重新闡述 CS:APP 作業 5.13 之要求 (用中文解釋搭配必要的背景知識說明) 2. 在自己的電腦上 (不能透過虛擬機器，需要將 Ubuntu Linux 安裝於電腦中) 重現 [Assign 5.13](https://hackmd.io/@dange/H1bmDn5am) 裡頭的實驗，並確認行為符合預期 3. 指出 [Assign 5.13](https://hackmd.io/@dange/H1bmDn5am) 原本的缺失並予以改進 4. 充分解釋效能落差原因，特別要比對 CS:APP 和 Intel Microarchitecture 的敘述 ::: ## :memo: 目錄 [TOC] ## 內容簡介 * 這份實作是針對 CS:APP Homework 5.13 作討論，內容如下: * 以四種方式實做 `inner()`，搭配不同 datatype (integer、float) 比較程式的 CPE 差異。 * 改善 [Assign 5.13](https://hackmd.io/@dange/H1bmDn5am)： * 消除 memory leak 問題 * 改善其利用 `<time.h>` 計算 CPE 並轉成圖像時，會有異常點的問題。 * 以 [CS-APP3e-labs/performancelab](https://github.com/zxc479773533/CS-APP3e-labs/tree/master/performancelab) 重新計算程式的 CPE。 * 搭配 [perf](https://perf.wiki.kernel.org/index.php/Main_Page) 和 [valgrind](https://valgrind.org/) 分析程式。 * 嘗試透過 inline assembly 實做 `inner()`。 * 總結和歸納可能的效能落差原因。 ## 作業要求 [CS:APP Homework Problems 5.13 題目原文](https://hackmd.io/ie7S8KRFRcapEMFYacfHrg) * 題意: `inner4` 是在計算兩向量 `u` 、 `v` 的內積，以不同的資料型態 (`integer` 或 `floating-point`)，在 `x86-64` 下執行這段程式，其 `CPE` 約為 `14~18`。比照第五章 combine 1~4 的改良方式，修改 `inner4` 程式碼: * `inner4` 程式碼: ``` c= void inner4(vec_ptr u, vec_ptr v, data_t *dest) { long i; long length = veclength(u) data_t *udata = get_vec_start(u); data_t *vdata = get_vec_start(v); data_t sum = (data_t) 0; for(i = 0; i < length; i++){ sum = sum + udata[i] * vdata[i]; } *dest = sum; } ``` 書上的實測結果: * integer data: CPE 為 1.50 * floating-point data: CPE 為 3.00 * 考慮 datatype 為 double，`inner4` 的 inner loop 對應的 x86-64 assembly code 如下: ``` assembly= (Inner loop of inner4. data_t = double, OP = * udata in %rbp, vdata in %rax, sum in %xmm0 i in %rcx, limit in %rbx) .L15: vmovsd 0(%rbp,%rcx,8), %xmm1 vmulsd (%rax,%rcx,8), %xmm1, %xmm1 vaddsd %xmm1, %xmm0, %xmm0 addq $1, %rcx cmpq %rbx, %rcx jne .L15 ``` 動作流程: * 每個 iteration 計算的內積值，以及 udata[i] 的值會放在 register) * line 3 是將 udata[i] 從 memory 搬到 register。 * line 4 是將 register 內的 udata[i] 和 memory 內的 vdata[i] 相乘，在把結果存回 register。 * functional units ![](https://i.imgur.com/VjsfuAu.png) * A. 比照 Figures 5.13, 5.14，描繪出程式碼的 instruction sequence 如何運作以及資料相依性問題。[參考來源1](https://www.programmersought.com/article/87743749665/), [參考來源2](https://www.programmersought.com/article/87743749665/) ``` bash +----+----+----+----+-----+-----+ |%rbp|%rcx|%rax|%rbx|%xmm1|%xmm0| +----+----+----+----+-----+-----++----+ +----|----|----|----------|--->| | | +----|----|----------|--->|load| vmovad 0(%rbp,%rcx,8),%xmm1 | | | | +-----|----| | | | | | | | +----+ | +----|----|----------|--->| | | | | | | | |load|---+ | | +----|----------|--->| | | | | | | | | +----+ | vmulsd (%rax,%rcx,8),%xmm1,%xmm0 | | | | | | | |<--+ | | | | +-----|--->|mul | | | | | +-----|----| | | | | | | | +----+ | | | | +-----|--->| | | | | | | +--->|add | vaddsd %xmm1,%xmm0,%xmm0 | | | | | +----| | | | | | | | +----+ | +----|----|----------|--->| | | | | | | |add | addq $1, %rcx | +----|----|----------|----| | | | | | | | +----+ | +----|----|----------|--->| | | | | | | | |cmp |---+ cmpq %rbx, %rcx | | | +----|-----|--->| | | | | | | | | +----+ | | | | | | | | | | | | | | | | |jne |<--+ jne .L15 | | | | | | | | | | | | | | +----+ v v v v v v +----+----+----+----+-----+-----+ |%rbp|%rcx|%rax|%rbx|%xmm1|%xmm0| +----+----+----+----+-----+-----+ ``` * B. 當資料型別為 double，程式碼 critical path 的 CPE lower bound 為何? [參考來源](https://www.programmersought.com/article/87743749665/) >The lower bound is the delay limit of floating-point addition, and the CPE is 3.00. * C. 當資料型別為 integer，程式碼 critical path 的 CPE lower bound 為何? [參考來源](https://www.programmersought.com/article/87743749665/) >Delay limit for integer addition, CPE is 1.00 * D. 解釋為何當資料型別為 floating-point 時，CPE 為 3.00 (multiplication operation requires 5 clock cycles)? [參考來源](https://www.programmersought.com/article/87743749665/) >There is only floating point addition on the critical path. ## 以 C 語言實做 4 個版本的 inner, 並比較 CPE 差異 ### 四種版本 `inner()` 如下 * inner1 ```c= void inner1(vec_ptr u, vec_ptr v, data_t *dest) { long i; for (i = 0; i < vec_length(u); i++) { data_t udata; get_vec_element(u, i, &udata); data_t vdata; get_vec_element(u, i, &vdata); *dest += udata OP vdata; } } ``` * inner2 ``` c= void inner2(vec_ptr u, vec_ptr v, data_t *dest) { data_t i; data_t length = vec_length(u); for (i = 0; i < length; i++) { data_t udata; get_vec_element(u, i, &udata); data_t vdata; get_vec_element(u, i, &vdata); *dest += udata OP vdata; } } ``` 改善 inner1 中每次 iteration 都要重取 vec_length 的問題。 * inner3 ```c= void inner3(vec_ptr u, vec_ptr v, data_t *dest) { data_t i; data_t length = vec_length(u); data_t *udata = get_vec_start(u); data_t *vdata = get_vec_start(v); for (i = 0; i < length; i++) { *dest += udata[i] OP vdata[i]; } } ``` 改善 inner2 中每次 iteration 都要重取 vector element 的問題。 * inner4 ```c= void inner4(vec_ptr u, vec_ptr v, data_t *dest) { data_t i; data_t length = vec_length(u); data_t *udata = get_vec_start(u); data_t *vdata = get_vec_start(v); data_t sum = 0; for (i = 0; i < length; i++) { sum += udata[i] OP vdata[i]; } *dest = sum; } ``` 改善 inner3 中每次 iteration 都要透過 pointer 寫入計算結果的問題，改成全部計算完再寫入。 ### Performancelab study performancelab 主要是利用 `rdtsc` 指令去讀取 clock cycle 個數。 #### 先利用 Assign 5.13 的程式計算不同 inner 的 CPE * datatype: integer ![](https://i.imgur.com/pBFpESQ.png) * datatype: float-point ![](https://i.imgur.com/e17VyFM.png) * CPE 測量結果: ![](https://i.imgur.com/jh0Y43E.png) * 分析: 原本 5_13.c 中是使用 clock_gettime() 及 cpu_freq 固定 1.5G 來處理 CPE 計算，測量結果可能失真，我們參考了 performancelab 的計算方式: * 一開始會先對系統的 time() 及 counter (rdtsc) 做校正(calibrate) 並將結果存在 cyc_per_tick 以為後來測量 element 時的修正依據.(COMPENSATE=1) * 實際測量時,讀取 target element 前後 time 及 counter (rdtsc) 的值, 並以 cyc_per_tick 修正.(COMPENSATE=1) * 取三次誤差小於 1% 的sample值中, 最佳的值來計算 CPE.(COMPENSATE = 0 or 1) #### 修改 Assign 5.13 ，搭配 performance lab 重新計算不同 inner 的 CPE * 將 performancelab 的 clock.c 及 fcyc.c 導入後, 以 `COMPENSATE=1` 執行的結果可得的 CPE 分別是 21, 16, 10 及 6. gnuplot 執行 output cycle 的結果可得到下圖: * datatype: integer ![](https://i.imgur.com/HVbGvDA.png) * datatype: float-point ![](https://i.imgur.com/2TjovCs.png) * CPE 測量結果: ![](https://i.imgur.com/G47gFFK.png) * 將 performancelab 的 clock.c 及 fcyc.c 導入後, 以 `COMPENSATE=0` 執行的結果可得的 CPE 分別是 21, 16, 10 及 6. gnuplot 執行 output cycle 的結果可得到下圖: * datatype: integer ![](https://i.imgur.com/CqOMMV2.png) * datatype: float-point ![](https://i.imgur.com/mn5VsXS.png) * CPE 測量結果: ![](https://i.imgur.com/dZ9b0l9.png) #### 修正 COMPENSATE = 1 時可能出現的異常狀況 ![](https://i.imgur.com/P3Q3DLU.png) 另外發現在 COMPENSATE=1 時, 有時會得到上圖. 這是很糟糕的結果. 經查發現 performancelab clock.c 有一段程式碼如下: ```c= double get_comp_counter() { double time = get_counter(); double ctime; struct tms t; clock_t ticks; times(&t); ticks = t.tms_utime - start_tick; ctime = time - ticks * cyc_per_tick; /* printf("Measured %.0f cycles. Ticks = %d. Corrected %.0f cycles\n", time, (int) ticks, ctime); */ return ctime; } ``` line #9, ctime=time - ticks*cyc_per_tick, 這會造成 ctime < 0, 以至於出現 1.8x$10^{18}$ 的奇怪 cycle. 看了一下程式碼, 修改一下如下: ```c= #define MAX_CYC 10000000000 double get_comp_counter() { double time = get_counter(); double ctime; struct tms t; clock_t ticks; times(&t); ticks = t.tms_utime - start_tick; ctime = time - ticks*cyc_per_tick; #ifdef MAX_CYC if( ctime > MAX_CYC || ctime < 0) { printf("Measured %.0f cycles. Ticks = %d. Corrected %.0f cycles, cyc_per_tick=%f\n", time, (int) ticks, ctime, cyc_per_tick); ctime += MAX_CYC; } #endif return ctime; } ``` >也許這不是正解, 關鍵在於 rdtsc 與 time() 之間的修正應如何進行? 執行起來如下圖, 感覺好多了！ ![](https://i.imgur.com/OlO8Dgo.png) * 分析: COMPENSATE 為 0 或 1, 在這實驗中, 看不出明顯的差異, CPE 也差不多, 反倒是要注意,　cycle 必須大於 0. ## 消除 memory leak 問題 ### 先使用 valgrind 測試原程式 * 將原 5_13.c 更名成 w75_13.c > 為了測試方便, 先將 line #11, 改為 10: unsigned long dimRange = 100; * compiler 時加上 -g > $ gcc -g -o w75_13 w75_13.c * valgrind --leak-check=full ./w75_13 ``` bash= ==4765== LEAK SUMMARY: ==4765== definitely lost: 144,000 bytes in 12,000 blocks ==4765== indirectly lost: 0 bytes in 0 blocks ==4765== possibly lost: 0 bytes in 0 blocks ==4765== still reachable: 0 bytes in 0 blocks ==4765== suppressed: 0 bytes in 0 blocks ==4765== ==4765== For lists of detected and suppressed errors, rerun with: -s ==4765== ERROR SUMMARY: 12 errors from 12 contexts (suppressed: 0 from 0) ``` 由執行結果可以看出發生 memory leak. 主要是 malloc() 與 free() 不匹配造成. ### 觀察程式: * inner1 ~ inner4 的處理迴圈中的 u, v 及 dest 在結束前並沒有 free()，修改完再測一次, 可以發現沒有 error! (改過後測試結果如下:) ``` bash= ==6265== ==6265== HEAP SUMMARY: ==6265== in use at exit: 0 bytes in 0 blocks ==6265== total heap usage: 20,009 allocs, 20,009 frees, 1,779,296 bytes allocated ==6265== ==6265== All heap blocks were freed -- no leaks are possible ==6265== ==6265== For lists of detected and suppressed errors, rerun with: -s ==6265== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ``` ## 效能分析（datatype 為 integer）兩個長度為 1000000 的 integer vector 計算內積, 不同 inner() 花費時間差異 ### 1. 使用 valgrind 搭配 kcachegrind > $ valgrind --tool=callgrind -v ./5_13 執行完會輸出 callgrind.out.#### 檔案 ("####" 是 pid). 這個檔案需使用 KCachegrind 來讀取. 在安裝好(安裝如下)後, 在 callgrind.out.#### 相同目錄下輸入 kcachegrind 即可. > * KCachegrind install: > $ sudo apt-get update -y > $ sudo apt-get install -y kcachegrind kcachegrind 會讀取 callgrind.out.#### 並顯示出分析結果: ![](https://i.imgur.com/T8Di4sP.png) >觀察測量結果，不同 inner function 佔整體程式執行時間的比例如下: * inner1: 37.77% * inner2: 33.36% * inner3: 9.81% * inner4: 7.85% :::info 參考: [valgrind & kcachegrind 使用說明](https://baptiste-wicht.com/posts/2011/09/profile-c-application-with-callgrind-kcachegrind.html) ::: ### 2. 使用 perf 分析程式碼 #### 前置作業 > perf operation 需要 root 權限, sudo is required for most command: #### 安裝 perf 並設定系統權限 * 安裝 perf: > $ sudo apt install linux-tools-$(uname -r) linux-tools-generic * check installation: > $ which perf * 設定系統權限 (更改 kernel 權限, 以便讀取 perf 及 CPU 資料): * method 1 ``` bash $ sudo su # As Root $ sysctl -w kernel.perf_event_paranoid=-1 $ echo 0 > /proc/sys/kernel/kptr_restrict $ exit ``` * method 2 ``` bash $ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict" ``` #### 改寫程式碼以取得執行程式的 pid 使用前須修改程式碼以取得 pid, printf("pid:%d\n", getpid()); 並加上 delay (sleep(10)) 來爭取 perf 執行時間。 #### 使用 perf top * 執行時, 同時開啟兩個 terminal, * terminal A: 先更改 kptr_restrict 為 0, 如上前置作業.等待 terminal B PID, 並輸入以下指令: ``` $ perf top -p [PID] ``` * terminal B: 執行w75_13perf (如下, 記住 PID) ``` bash $ ./w75_13perf pid: 16824 ``` * 最後 terminal A 會顯示如下畫面: ![](https://i.imgur.com/s7ibqVk.png) #### 使用 perf record * perf record 指令如下: ``` bash $ perf record -e cpu-clock -g ./w75_13 ``` * pert script ``` bash > $ perf script -i perf.data &> perf.unfold ``` * stackcollapse-perf.pl ``` bash＝ Samples: 117 of event 'cpu-clock', Event count (approx.): 29250000 Children Self Command Shared Object Symbol + 99.15% 0.00% test513_perf [unknown] [.] 0x0fae258d4c544155 + 99.15% 0.00% test513_perf libc-2.27.so [.] __libc_start_main + 96.58% 0.00% test513_perf test513_perf [.] main + 38.46% 24.79% test513_perf test513_perf [.] new_vec + 25.64% 25.64% test513_perf test513_perf [.] get_vec_element + 23.08% 11.11% test513_perf test513_perf [.] inner1 + 21.37% 7.69% test513_perf test513_perf [.] inner2 + 13.68% 0.00% test513_perf [kernel.kallsyms] [k] page_fault + 13.68% 0.00% test513_perf [kernel.kallsyms] [k] do_page_fault + 13.68% 5.98% test513_perf [kernel.kallsyms] [k] __do_page_fault + 7.69% 7.69% test513_perf test513_perf [.] inner3 + 6.84% 0.85% test513_perf [kernel.kallsyms] [k] handle_mm_fault + 5.98% 0.85% test513_perf [kernel.kallsyms] [k] __handle_mm_fault + 5.98% 5.98% test513_perf test513_perf [.] inner4 + 3.42% 0.85% test513_perf [kernel.kallsyms] [k] __alloc_pages_nodemask + 3.42% 0.00% test513_perf [kernel.kallsyms] [k] alloc_pages_vma + 2.56% 0.85% test513_perf [kernel.kallsyms] [k] release_pages + 2.56% 1.71% test513_perf [kernel.kallsyms] [k] get_page_from_freelist + 1.71% 0.00% test513_perf libc-2.27.so [.] __munmap + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] entry_SYSCALL_64_after_hwframe + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] do_syscall_64 + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] __x64_sys_munmap + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] __vm_munmap + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] __do_munmap + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] unmap_region + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] tlb_finish_mmu + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] tlb_flush_mmu + 1.71% 0.00% test513_perf [kernel.kallsyms] [k] free_pages_and_swap_cache + 0.85% 0.85% test513_perf [kernel.kallsyms] [k] __lock_text_start + 0.85% 0.85% test513_perf [kernel.kallsyms] [k] clear_page_erms + 0.85% 0.85% test513_perf [kernel.kallsyms] [k] free_unref_page_list + 0.85% 0.85% test513_perf [kernel.kallsyms] [k] get_mem_cgroup_from_mm + 0.85% 0.85% test513_perf [kernel.kallsyms] [k] vmacache_find + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] lru_cache_add_active_or_unevictable + 0.85% 0.85% test513_perf libc-2.27.so [.] printf + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] __lru_cache_add + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] mem_cgroup_try_charge_delay + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] find_vma + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] mem_cgroup_try_charge + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] pagevec_lru_move_fn + 0.85% 0.00% test513_perf [kernel.kallsyms] [k] prep_new_page + 0.85% 0.85% test513_perf libc-2.27.so [.] _int_malloc ``` >觀察測量結果，不同 inner function 佔整體程式執行時間的比例如下: * inner1: 23.08% * inner2: 21.37% * inner3: 7.69% * inner4: 5.98% * flamegraph.pl generate svg file $ ./flamegraph.pl perf.folded > perf.svg ![](https://i.imgur.com/0zdDcjY.png) * perf svg graph ![](https://i.imgur.com/k4uGSnn.png) ## 嘗試透過 inline assembly 實做 inner() 原先自己預期的目標是把題目給定的 double data type 組合語言，整合到 inner4 的 C 程式碼中，再分析效能變化，但因為對 assembly 和 asm 呼叫方式還不夠熟悉，實做上有些瓶頸還在克服中。 * 題目提供的 assembly code: ``` c= .L15: vmovsd 0(%rbp,%rcx,8), %xmm1 vmulsd (%rax,%rcx,8), %xmm1, %xmm1 vaddsd %xmm1, %xmm0, %xmm0 addq $1, %rcx cmpq %rbx, %rcx jne .L15 ``` ### integer vector ``` c= #include <stdint.h> #include <assert.h> #include <stdio.h> #include <unistd.h> typedef int data_t; typedef struct{ long length; data_t *data; } vec_rec, *vec_ptr; #define ASM_SUPPORT void for_5(long length, data_t *src_v1, data_t *src_v2, data_t *dest, vec_ptr u, vec_ptr v) { data_t sum = 0; for (long i = 0; i < length; i++ ) { #ifndef ASM_SUPPORT // sum = sum + src_v1[i] * src_v2[i]; #else asm volatile ("movl %0, %%ebx\n\t" // sum "movq %1, %%rcx\n\t" // i "movq %2, %%r8\n\t" // v1 "leaq 0(%%r8,%%rcx,4), %%rax\n\t" // &v1[i] "movl (%%rax), %%edx\n\t" // v1[i] "movq %3, %%r9\n\t" // v2 "leaq 0(%%r9,%%rcx,4), %%rax\n\t" // &v2[i] "movl (%%rax), %%eax\n\t" // v2[i] "imul %%edx, %%eax\n\t" // v1[i]xv2[i] "addl %%eax, %%ebx\n\t" // + sum "movl %%ebx, %0" // sum : "+r" (sum) : [i] "r" (i), [src_v1] "r" (src_v1), [src_v2] "r" (src_v2) : "rax", "ebx", "rcx", "edx", "r8", "r9", "r10" ); #endif printf("%d,\n", sum); } *dest = sum; } int main() { data_t v1[] = {10, 20, 30}; data_t v2[] = {200, 300, 400}; data_t output; for_5(3, (data_t *)v1, (data_t *)v2, (data_t *)&output, (vec_ptr)0, (vec_ptr)0); printf("output: %d\n", output); } ``` ## 歸納和總結可能的效能落差原因 * inner1 ~ inner4 逐步降低了 iteration 所需要的 memory 存取次數，這樣的改動在 vector 長度夠長的情況下，clock cycle 會有明顯的差異。 * 不論是透過 <timer.h>, performancelab, valgring 或是 perf 來測量，都可以看出 inner4 CPE 明顯少了許多。 ## 嘗試更精準量測 cock cycle ### 閱讀 Control Intel CPUs energy performance policy 為了更好的測量 clock cycle, 嘗試將 CPU clock speed 設成 constant。（參考: [Control Intel CPUs energy performance policy](https://wiki.archlinux.org/index.php/CPU_frequency_scaling#Control_Intel_CPUs_energy_performance_policy)） * 檢查linux kernel 版本和 CPU-freq 有關可用 modules: ``` bash $ uname -r 5.4.0-60-generic $ cd /lib/modules/5.4.0-60-generic/kernel/drivers/cpufreq $ ls amd_freq_sensitivity.ko p4-clockmod.ko speedstep-lib.ko ``` * 使用 `cpupower` 查看 CPU 時脈資訊, 主要是了解目前 CPU 可選擇的時脈範圍 (如下資訊可知，我們的 CPU 時脈範圍是: 800 MHz ~ 4.40 GHz): ```bash # cpupower frequency-info analyzing CPU 0: driver: intel_pstate CPUs which run at the same hardware frequency: 0 CPUs which need to have their frequency coordinated by software: 0 maximum transition latency: Cannot determine or is not supported. hardware limits: 800 MHz - 4.40 GHz available cpufreq governors: performance powersave current policy: frequency should be within 800 MHz and 4.40 GHz. The governor "powersave" may decide which speed to use within this range. current CPU frequency: Unable to call hardware current CPU frequency: 800 MHz (asserted by call to kernel) boost state support: Supported: yes Active: yes ``` * 調整 CPU 電源機制(同個時間點只能採用一種機制: `Linux-CPUFreq governors`)，這裡將 CPU 時脈設為常數 `4300MHz`。指令可參考 [cpufreq的五種模式](https://www.cnblogs.com/augusite/p/13813559.html)。 * 將 CPU 時脈設為常數 `4300MHz` ``` bash $ sudo cpupower frequency-set -u 4300MHz ``` * 檢查 CPU 時脈，可發現時 frequency 和預期結果雖然仍有誤差，但已接近指定的常數。 ``` bash # cpupower frequency-info analyzing CPU 0: driver: intel_pstate CPUs which run at the same hardware frequency: 0 CPUs which need to have their frequency coordinated by software: 0 maximum transition latency: Cannot determine or is not supported. hardware limits: 800 MHz - 4.40 GHz available cpufreq governors: performance powersave current policy: frequency should be within 800 MHz and 4.30 GHz. The governor "performance" may decide which speed to use within this range. current CPU frequency: Unable to call hardware current CPU frequency: 4.27 GHz (asserted by call to kernel) boost state support: Supported: yes Active: yes $ watch grep \"cpu MHz\" /proc/cpuinfo Every 2.0s: grep "cpu MHz" /proc/cpuinfo eugene-Z390-AORUS-ELITE: Mon Jan 18 00:01:47 2021 cpu MHz : 4280.825 cpu MHz : 4273.806 cpu MHz : 4276.668 cpu MHz : 4260.979 cpu MHz : 4288.227 cpu MHz : 4288.728 ``` ### 調整 Processor affinity 接著嘗試只使用一個特定 CPU core (CPU:1) 來執行程式，這是為了在多核心處理器上更精確的量測程式所需的 clock cycle。 (參考: [Processor affinity](https://en.wikipedia.org/wiki/Processor_affinity)) * 安裝和使用 taskset ``` bash $ sudo apt-get install util-linux $ sudo taskset -cp 1 9030 set cpu 1 to execute PID [9030], or $ sudo taskset 0x1 ``` * 修改程式碼ˋ，讓程式能以特定的 CPU core 執行程式 (使用 CPI:1) * 必須先指定好要使用的 CPU core 和取得執行程式的 pid, 再呼叫 `sched_setaffinity()` (參考: [sched_setaffinity](https://man7.org/linux/man-pages/man2/sched_setaffinity.2.html)) * 添加程式碼如下: ``` c= // set affinity cpu_set_t set; int setCPU = 1, cpuNums = -1; CPU_ZERO(&set); CPU_SET(setCPU, &set); if(sched_setaffinity(getpid(), sizeof(set), &set) == -1) { printf("sched_setaffinity error!\n"); return 0; } if(-1 == (cpuNums = sched_getcpu())) { printf("sched_setaffinity error!\n"); return 0; } ``` ### 執行結果 * datatype: Integer ![](https://i.imgur.com/OgvQ7Xq.png) 執行結果 datatype: Integer * datatype: Floating-point ![](https://i.imgur.com/SUZaSLh.png) * 量測到的 CPE 數值約為: | CPE (限制只使用 CPU1) | inner1 | inner2 | inner3 | inner4 | | -------- | -------- | -------- |-------- |-------- | | Integer | 16.04 | 12.16 | 8.54 | 4.78 | | Floating-point | 16.67 | 12.90 | 9.60 | 6.71 | | CPE (未限制 Processor affinity)| inner1 | inner2 | inner3 | inner4 | | -------- | -------- | -------- |-------- |-------- | | Integer | 16.32 | 12.03 | 8.43 | 5.02 | | Floating-point | 16.70 | 12.26 | 9.54 | 9.52 | * 分析: 對照上述兩分表格可發現，有綁定 CPU-core 的程式，其所計算的 clock cycle 數較小，特別是 inner4 floating point 的部分，差異又更是明顯。 :::info ## TODO * 完成 floating point vector 的 inline assembly 實做 * 比對 CS:APP 和 Intel Microarchitecture 的敘述 ## 開會討論內容 * 如何更精準量測 cock cycle: * [Control Intel CPUs energy performance policy](https://wiki.archlinux.org/index.php/CPU_frequency_scaling#Control_Intel_CPUs_energy_performance_policy) * [Processor affinity](https://en.wikipedia.org/wiki/Processor_affinity) * Intel Microarchitecture : * 例如: 一道乘法指令在 CPU 上執行需要多少 cycle * Perf 輸出會反映到 Microarchitecture * turbo mode * [Hardware Accelerated 2D Rendering for Android](https://www.slideshare.net/jserv/accel2drendering) ::: ## 參考資料 * CS:APP solution * https://www.programmersought.com/article/87743749665/ * https://www.programmersought.com/article/87743749665/ * 前一份同學的共筆: * https://hackmd.io/@dange/H1bmDn5am * Github 實作: https://github.com/allenchen8210/team15 * Valgring: * https://baptiste-wicht.com/posts/2011/09/profile-c-application-with-callgrind-kcachegrind.html * Inline assembly * https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html * http://locklessinc.com/articles/gcc_asm/ * https://en.wikipedia.org/wiki/X86_instruction_listings * https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/nios2/n2cpu_nii51017.pdf?wapkw=registerset * http://progforperf.github.io/C2Assembly.pdf * http://sourceware.org/binutils/docs/as/index.html * https://en.wikipedia.org/wiki/X86_instruction_listings * http://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html * Perf * https://perf.wiki.kernel.org/index.php/Main_Page * http://www.brendangregg.com/perf.html * https://jasonblog.github.io/note/linux_tools/linuxxia_de_nei_he_ce_shi_gong_ju_2014_2014_perf_s.html * https://codertw.com/%E4%BC%BA%E6%9C%8D%E5%99%A8/192/ * http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial * https://medium.com/statementdog-engineering/using-framegraph-to-find-out-application-bottleneck-ac5596b01736 * [Assembly code programming in Ubuntu](http://www.egr.unlv.edu/~ed/assembly64.pdf)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.