# [2020 進階電腦系統理論與實作] 期末自我評量填寫及內容要求 contributed by < `ccs100203` > ###### tags: `linux2020` :::spoiler reference - 張家榮: http://wiki.csie.ncku.edu.tw/User/JaredCJR - 陳品睿: http://wiki.csie.ncku.edu.tw/User/ggary9424 - 蕭奕凱: http://wiki.csie.ncku.edu.tw/User/Veck ::: ### a) 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章) - overflow 時就會出問題 - 又假設 x 跟 y 都是 signed-integer x 是任一正數, y 是 signed-integer 所能表達的最小的數值。那麼 $x - y < 0$ 恆成立，因為 $y==-y$，則 $y < x$ 必然成立，就會與題目的判斷式相違背。 ### b) 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？ #### ptr++ 根據 c99 6.5.2.4.2 > The side effect of updating the stored value of the operand shall occur between the previous and the next sequence point. ```c= int i = 0; int *ptr = &i; printf("%x\n", ptr++); printf("%x\n", ptr); ``` - result ``` 90520084 90520088 ``` 可以看出第三行印出位置後，ptr 才會做 + 1，並且在下一次的 output 體現出來。 #### *ptr++ 由於 `++` 的 precedence 高於 `*`，所以可以理解為 `*(ptr++)` ```c= int i[3] = {3,6,9}; int *ptr = i; printf("%x\n", ptr); printf("%x\n", *ptr++); printf("%x\n", ptr); printf("%x\n", *ptr); ``` - result ``` 9b317844 3 9b317848 6 ``` 可以看出第四行先執行 `ptr++` 後，會對 0x9b317844 做 dereference，在 `printf` 結束後再把 `ptr + 1`，所以可以看到第五行的 `ptr` 已經指到了下一個位置。 ### c) 知道 void (*signal(int sig, void (*handler)(int))) (int); 這樣的宣告該如何解讀嗎？ - 宣告一個 function `signal()` - ```void (*handler)(int)``` 是一個 function pointer，傳入 int 然後 return void. - ```signal(int sig, void (*handler)(int))``` 是一個 function，傳入 int sig, void (*handler)(int) 並 ruturn 一個 function pointer. - 假設 singal 回傳的變數為 fp, 那麼就會變成```void (*fp) (int); ```, 可以看出最後我們會得到一個 function pointer. ### d) 知道 Linux 核心 <include/linux/list.h> 裡頭, 這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？ ```c #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head); pos = pos->prev) ``` This macro will iterate over a list backwards. - `pos` is a loop cursor. - `head` is the head of list. If we don't use parenthesis, we will suffer some problems. e.g. ```list_for_each_prev(pos, head + 1)``` If I pass `head + 1` into the macro, but I don't use parenthesis. Because of the operator precedence, it's execution order is ```(head + (1 -> prev))```, and the compiler will report the error. ### e) 知道從 color space RGBA8888 轉換為 8-bit 灰階的程式如何撰寫，又如何透過 SIMD 進行最佳化嗎？ ### f) 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？ 在 [lab0 q_sort()](https://hackmd.io/@cccccs100203/linux2020-lab0#q_sort) 時有實作過 merge sort。 e.g. Sorted() is a function in python, which uses Timsort as its algorithm, and Timsort is a hybrid algorithm of insertion sort and merge sort. ### g) 知道 memory misalignment 對程式正確性和效能的影響嗎？ ![](https://i.imgur.com/pggcFmP.png) - 當我所存取的資料位置不在 4 的倍數上時，processor 會先讀取上半邊的區塊，篩掉不需要的資料，再讀取下半邊的區塊，一樣過濾掉不需要的資料，最後再將兩者整合再一起，完成一次的存取。很明顯的這樣多了一次的操作，於是就會對效能產生影響。 - Atomic instruction 是不可分割的，當 processor 執行 atomic instruction 時，如果所需存取的資料存放在不同的 page 上，又其中一個 page 在記憶體裡，而另一個不在。此時會發生 page fault，並且執行 virtual memory management。這樣會導致 atomicity 被破壞，正確性會有疑慮。 e.g. PowerPC 上要求 atomic instruction 存取的資料至少要對齊 4 byte。 參考 [Data alignment: Straighten up and fly right](https://developer.ibm.com/technologies/systems/articles/pa-dalign/) ### h) 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？ ### i) 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？ ### j) 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？ ```c #define abs(num) (((num >> 63) ^ num) - (num >> 63)) ``` #### 程式概念: - 遇到負數的話就先將他轉變成一補數，然後再做 +1 轉換成二補數，如果是正數或 0，則不需改變他。 - `number ^ 1` 會是 Toggle，而 `number ^ 0` 不會有任何改變。 - `(num >> 63)`可以做出全部都是 1 或 0 的 mask - 正數以及 0: 得到 0 - 負數: 得到 -1, 即為 111...1111 - ```((num >> 63) ^ num)``` - 正數以及 0: 會得到相同的數字 - 負數: 會得到 1 補數 - ```(num >> 63)``` - 正數以及 0: 會得到 0 - 負數: 會得到 -1 ### k) 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？ - [Tail Call Optimization](https://en.wikipedia.org/wiki/Tail_call) (TCO)，好處是不用保留上一層 stack 的資訊，可以把他當作一個 for loop 使用，這樣會比原本的 recursion 還省空間，更不容易 stackoverflow。 - 引用 2020q3 [quiz7](https://hackmd.io/@sysprog/2020-quiz7#測驗-2) ```c= int *global_var; void f(void) { int x = 3; global_var = &x; ... /* Can the compiler perform TCO here? */ g(); } ``` - 要是 `g()` 對 `global_var` 做 dereference，代表 `f` 內的資料需要保存而不能提前從 stack pop。 - 要是 `g()` 沒有對 `global_var` 做 dereference，那麼就有機會做 TCO. ### l) 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說 ### m) 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？ ![](https://i.imgur.com/x7cHYfp.png) #### fixed point 將小數點的位置固定，以固定量的 bit 數目表達整數與小數的部分。 優點是運算快速省效能，缺點是表達的範圍很小。 #### floating point 以 [IEEE 754 single-precision](https://en.wikipedia.org/wiki/Single-precision_floating-point_format#IEEE_754_single-precision_binary_floating-point_format:_binary32) 為標準，他所能表達的數值範圍比較廣，但缺點是在極大與極小值的精度較差，且計算效率較差。 ![](https://i.imgur.com/IlPB6PW.png) ### n) 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？ ### o) 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？ ### p) 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？ ### q) 知道傅立葉分析在通訊領域的應用嗎？舉例說明 ### r) 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？ https://hackmd.io/@cccccs100203/linux2020-quiz3#%E6%B8%AC%E9%A9%97-4 ### s) 知道如何實作無失真資料壓縮嗎？你知道有哪些相關演算法？ 無失真資料壓縮為: 資料經過壓縮後，資訊不被破壞，還能完全恢復到壓縮前的原樣。 - Huffman Coding 算是最經典的演算法之一 - 平常會用到的像是 FLAC, PNG等，都很常見 ### t) 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處 ### u) 知道 ARMv7-A 指令的 conditional execution 嗎？請舉例說明其用法。 參考 [Conditional Execution](http://www.davespace.co.uk/arm/introduction-to-arm/conditional.html)，藉由設立 Processor flags 去決定下面的指令是否需要執行，此方法可以移除所需要的 branch，並且避免 pipeline stall。 - Processor flags ![](https://i.imgur.com/ABWu0NP.png) - N: Negative - Z: Zero - C: Carry - V: Overflow ![](https://i.imgur.com/gBlcQ5Q.png) - Example ```c= CMP r0, #0 ; if (x <= 0) MOVLE r0, #0 ; x = 0; MOVGT r0, #1 ; else x = 1; ``` ### v) 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明 ### w) 知道 locality of reference 嗎？請以本學期教材或作業的程式碼，說明 locality 對於 cache 的影響 Take the matrix transpose in [lab7](https://cs61c.org/su20/labs/lab07) of Computer Architecture for example: It compares two situations: careful locality (cache blocking) and careless locality (naive method) - This is a careful locality situation ```c void transpose_blocking(int n, int blocksize, int *dst, int *src) { for (int i = 0; i < n; i += blocksize) { for (int j = 0; j < n; j += blocksize) { for (int k = i; k < blocksize + i && k < n; k++) { for (int l = j; l < blocksize + j && l < n; l++) { dst[l + k * n] = src[k + l * n]; } } } } } ``` - n: 1000, blocksize: 20 ``` Testing naive transpose: 1.651 milliseconds Testing transpose with blocking: 0.914 milliseconds ``` The careful locality program got a better performance.