# [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 對程式正確性和效能的影響嗎？
- 當我所存取的資料位置不在 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，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？
#### 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) 為標準，他所能表達的數值範圍比較廣，但缺點是在極大與極小值的精度較差，且計算效率較差。
### 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
- N: Negative
- Z: Zero
- C: Carry
- V: Overflow
- 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.
Sign in with Wallet
Connect another wallet