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

User/DyslexiaS

DyslexiaS(曹穎)

簡介:

  • 成功大學 資訊工程系108級

聯絡資訊

  • email: exist02593@gmail.com
  • Github: DyslexiaS

2015秋季班 個人評量

(秋季班)作業及筆記

(秋季班)所見所聞心得

以前覺得我以後要做軟體，不想碰硬體，但這根本不可能，發現要寫出一個好的軟體，非常需要對於硬體的了解，除此之外，對於機率統計，物理，數學也要有一定的掌握程度。上了這門課程也學到許多電腦架構，底層，系統，bit的神奇操作，記憶體配置問題，組合語言…等，那些我原本非常排斥，並打算再也不想接觸的部分，都在這堂課程中有了最初步的了解。最重要的事：讓我意識到這些東西的重要性，以及更能接受去學習這方面的知識了。

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

９級分 這堂課程是我這學期最認真的，也是大學課程中少數常有在閱讀的科目，有自己去閱讀全班訂購的參考書籍，也有每週複習老師上課的內容，以及釐清課間的測驗，算是花最多時間的一堂課了。 - 學到許多 github 的技巧，例如如何開分支修復再 merge，或是修復 conflict - 學會如何撰寫 Makfile ，使用變數，使用迴圈寫 perf，將檔案寫成可用 define flag 做客製化的編譯

  1. 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章) x - y 可能產生 overflow 的情況，不能全然推倒成 x < y

  2. 知道 C 語言規格書如何解釋 ptr++ 和 ptr++ 行為的差異嗎？ ptr++ 把 ptr 的位置加一，再取其值 ptr++ 直接把位置加一

  3. 知道通訊領域中如何應用 parity bit 嗎？ 在通訊的時候，如果包含校正位奇數的個數發生改變，表示傳輸過程有錯誤，但無法找出錯誤的位置，因此當錯誤發生，只能重新傳輸。

  4. 知道 void (signal(int sig, void (handler)(int))) (int); 這樣的宣告該如何解讀嗎？

  • signal 是個有兩個參數的函式，第一個參數是 int sig，另一個為 function pointer handler，handler return void 並且傳入一個參數 int 。
  • signal return 一個指向 function 的 function pointer，此函式 return void 並且傳入一個參數 int 。

  1. 知道 Linux 核心 < include/linux/list.h> 裡頭 #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head); pos = pos->prev) 這樣的巨集到底在做什麼？以及 head 使用時需要加小括號，為何？ 走訪 list 的每一個節點。 確保傳進來的 head 不會和因為 function 內的 -> ，優先權不同，而導致程式錯誤。

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

  3. 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？

  4. 知道 memory misalignment 對程式正確性和效能的影響嗎？能否舉出 Linux 核心對應的處理機制？

  • 沒有做 memory aligment ，在存取資料時，可能會需要額外計算 bitshifting
  1. 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？ 使用類似二分法的概念去計算
  1. 知道 C 語言規格書中如何定義 object 的生命週期嗎？能否舉出至少兩相對應的 CVE 呢？
  • C99 6.2.4 For the objects that are declared with automatic, static, and thread storage duration, lifetime equals their storage duration (note the difference between non-VLA and VLA automatic storage duration).

  1. 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？ #include <stdint.h> int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; }

  2. 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？ 假設main 呼叫 F(A) ， F(A) call F(B)，在 A 呼叫 B 時，沒有把 A 的位置存起來就直接跳到 B ，當 B 執行結束時，直接將 pc 退回到 main

  3. 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說 a.程式在存取記憶體時產生錯誤 多出現在

  • 修改 string literal
  • Access 已經 free 的空間
  • Dereference 越界的指標 b.發生 page fault 時， CPU 會發出 interrupt 給作業系統，像是傳送 signal 會由一個函式來處理。

  1. 知道 CVE/CWE 嘛？你對資訊安全有什麼認知嗎？

  2. 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？

  • Fixed 較不佔容量
  • 運算上需要的資源較少
  • 用於音訊轉換

  1. 知道中國剩餘定理和 RSA 加密演算的關聯嗎？你知道哪些開放原始程式碼用到中國剩餘定理嗎？ 使用RSA演算法在解密的計算時會需要較多時間，可以利用中國剩餘定理來加速

  2. 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？

  3. 知道 pipeline hazard 該如何消除嗎？有什麼議題須考慮？

  • structural hazard:把 function unit 切的更小，讓硬體資源夠用
  • data hazard：forwarding 或是把指令順序調換
  • control hazard：delay, 硬體技術消除

  1. 知道一個 singly-linked list 的新增節點操作，該如何用 Y86-64 組合語言實作嗎？

  2. 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？

  3. 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？

  4. 知道傅立葉分析在通訊領域的應用嗎？舉例說明

  • 傳輸前利用傅立葉轉換來壓縮數據，再經由反傅立葉轉換得到原始資料

  1. 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？

  2. 知道如何用 bitwise operator 實作出沒有分支的 FizzBuzz 程式嗎？ https://github.com/jserv/fizzbuzz/blob/master/bitwise.c

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

  • 產生出現頻率的統計模型
  • 利用統計模型，將出現頻率高的用較小的位元數表示，反之亦然
  • 位元序列編碼的演算法可使用霍夫曼編碼
  1. 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處
  • Bloom filter 為空間效率極高，將資料分類的演算法