[2020 進階電腦系統理論與實作] 期末自我評量填寫及內容要求

contributed by < ccs100203 >

tags: `linux2020`

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.




int i = 0;
int *ptr = &i;
printf("%x\n", ptr++);
printf("%x\n", ptr);

result

90520084
90520088

可以看出第三行印出位置後，ptr 才會做 + 1，並且在下一次的 output 體現出來。

*ptr++

由於 ++ 的 precedence 高於 *，所以可以理解為 *(ptr++)






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

可以看出第四行先執行 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 使用時需要加小括號，為何？

 #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() 時有實作過 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

h) 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？

i) 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？

j) 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？

#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 (TCO)，好處是不用保留上一層 stack 的資訊，可以把他當作一個 for loop 使用，這樣會比原本的 recursion 還省空間，更不容易 stackoverflow。
引用 2020q3 quiz7









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 為標準，他所能表達的數值範圍比較廣，但缺點是在極大與極小值的精度較差，且計算效率較差。

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#測驗-4

s) 知道如何實作無失真資料壓縮嗎？你知道有哪些相關演算法？

無失真資料壓縮為: 資料經過壓縮後，資訊不被破壞，還能完全恢復到壓縮前的原樣。

Huffman Coding 算是最經典的演算法之一
平常會用到的像是 FLAC, PNG等，都很常見

t) 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處

u) 知道 ARMv7-A 指令的 conditional execution 嗎？請舉例說明其用法。

參考 Conditional Execution，藉由設立 Processor flags 去決定下面的指令是否需要執行，此方法可以移除所需要的 branch，並且避免 pipeline stall。

Processor flags
- N: Negative
- Z: Zero
- C: Carry
- V: Overflow

Example



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 of Computer Architecture for example:

It compares two situations: careful locality (cache blocking) and careless locality (naive method)

This is a careful locality situation

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.