分享到plurk 分享到twitter 分享到facebook

chewei3(李哲緯)

學歷

  • 成功大學資訊工程系碩士班108級(2019-2021)

聯絡資訊

2020冬季班 個人評量

作業及筆記

期末專題 Final Project

  • 主題 Topic：Render Github, HackMD
  • 工作 Work：整合同學的成果，並繼續深入研究其相關議題，並更新、補充與改善內容.
  • 成果 Presentation：

自我評量分數 (1 到 10 級分)

9級分。學期剛開始的時候會花時間寫作業，以及研究每周的教材及小考。期中之後將時間花在論文以及其他雜事，花費在這堂課的心力也大幅減少，但是也只能說是自己的決心不夠，儘管如此還是從這堂課中充分認識自己，以及了解自己許多不足之處，所以之後還是會繼續閱讀教材。我心裡給自己的分數是 2 分，但是為了我的學分費，只能給自己 9 分了。

  1. 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章)

因為可能會造成 Overflow: x = 2b’1…1, y = 2b’01…1，因此 (x - y < 0) == false，但是 (x < y) == True

  1. 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？

c= The result of the postfix ++ operator is the value of the operand.

  • ptr++ 是 ptr 加上對應的資料型態大小，*ptr++ 是將 ptr dereference 後，再做 ptr++
  1. 知道 void (\*signal(int sig, void (\*handler)(int))) (int);這樣的宣告該如何解讀嗎？
  • signal is a pointer to a function that takes two parameters: * an int named sig. * a pointer to a function that takes an int as a parameter named handler * and returning void.
  • and returning void.
  1. 知道 Linux 核心 < include/linux/list.h> 裡頭 #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head); pos = pos->prev) 這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？

從 head->prev 走訪整個 link list，加小括號是因為帶入的 head 有可能是 *ptr 的型態，若沒有加小括號會變成 pos = *head->prev，因為 -> 的 precedence 大於 *，所以會出錯

  1. 知道從 color space RGBA8888 轉換為 8-bit 灰階的程式如何撰寫，又如何透過 SIMD 進行最佳化嗎？

c= bw = (uint32_t) (r \* 0.299 + g \* 0.587 + b \* 0.114); 可事先建立表格減少浮點數運算，用 offset 取代bitwise operation 參考

  1. 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？ 程式碼參考

  2. 知道 memory misalignment 對程式正確性和效能的影響嗎？

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

參考

  1. 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？
  1. 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？
  2. 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？
foo:
  call B
  call A
  ret

TCO:

 foo:
  call B
  jmp  A

gcc 9.3.0 執行 tco-test

$ gcc -Wall -Wextra -Wno-unused-parameter -O0 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                no TCO
One argument:                                no TCO
Additional int argument:                     no TCO
Dropped int argument:                        no TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          no TCO

開啟最佳化 (-O2)編譯，得到以下執行結果

$ gcc -Wall -Wextra -Wno-unused-parameter -O2 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                TCO
One argument:                                TCO
Additional int argument:                     TCO
Dropped int argument:                        TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          TCO
  1. 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說
  2. 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？
  3. 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？
  4. 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？
  5. 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？
  6. 知道傅立葉分析在通訊領域的應用嗎？舉例說明
  7. 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？

將判斷偶數的部分改寫為int shift = min(__builtin_ctz(u), __builtin_ctz(v)); u >>= shift; v>>= shift; quiz3 的測驗 4

  1. 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處 Bloom filter 為一個 n-bits table，將一個元素從 k 個 hash function 獲得的 k 個 table index 設為 1，用於O(1)查找元素是否存在於集合中，因為多個元素可能會共用一個 bit，所以查找存在 false-positive，且無法刪除元素 程式碼參考

  2. 本學期課程內容中，讓你印象最深刻、顛覆過往認知的部分是什麼？請舉例說明 發現自己對於 C 語言的認知還是不夠深入，尤其是 bitwise operation 以及浮點數

  3. 知道 locality of reference 嗎？請以本學期教材或作業的程式碼，說明 locality 對於 cache 的影響