版本 b17af3c4131602c19b1cc851cf98ff137815fdb8
Changes from b17af3c4131602c19b1cc851cf98ff137815fdb8 to current
DyslexiaS(曹穎)
------------------
**簡介:**
- 成功大學 資訊工程系108級
聯絡資訊
=====================
- email: ``exist02593@gmail.com``
- Github: ``DyslexiaS``
2015秋季班 個人評量
=======================
(秋季班)作業及筆記
------------------------
- HW1 [你所不知道的Ｃ語言](https://hackmd.io/c/HyAvnSsuQ/)
- HW2 [list](https://hackmd.io/BZ8fmMrBS1-L8veNFkH5_w)
- HW3 [review](https://hackmd.io/xxw1xW0aRnaFMDl5A3-CGA)
- HW3 [dict](https://hackmd.io/Y6X2DKZ_SXKWGkH7pa4WJA)
- HW4 [assessment](https://hackmd.io/eL4qdgy4S5G4xY7LiRP0VQ)
- HW5 [bits](https://hackmd.io/VV-gytfhSQab9AOJZPz2pQ)
- Team work1 [quiz4](https://hackmd.io/1BFNi_UpTOmG3yvpyq0_hg)
- Team work2 [Matrix multiplication](https://hackmd.io/goqvUCsCQem9xWoGKxLx_w)
(秋季班)所見所聞心得
------------------------
以前覺得我以後要做軟體，不想碰硬體，但這根本不可能，發現要寫出一個好的軟體，非常需要對於硬體的了解，除此之外，對於機率統計，物理，數學也要有一定的掌握程度。上了這門課程也學到許多電腦架構，底層，系統，bit的神奇操作，記憶體配置問題，組合語言...等，那些我原本非常排斥，並打算再也不想接觸的部分，都在這堂課程中有了最初步的了解。最重要的事：讓我意識到這些東西的重要性，以及更能接受去學習這方面的知識了。
(秋季班)自我評量分數 (1 到 10 級分)
---------------------------
９級分
這堂課程是我這學期最認真的，也是大學課程中少數常有在閱讀的科目，有自己去閱讀全班訂購的參考書籍，也有每週複習老師上課的內容，以及釐清課間的測驗，算是花最多時間的一堂課了。
- 學到許多 github 的技巧，例如如何開分支修復再 merge，或是修復 conflict
- 學會如何撰寫 Makfile ，使用變數，使用迴圈寫 perf，將檔案寫成可用 define flag 做客製化的編譯
a) 知道 x - y < 0 敘述為何不能寫為 x < y 嗎？ (CS:APP 第 2 章)
x - y 可能產生 overflow 的情況，不能全然推倒成 x < y
b) 知道 C 語言規格書如何解釋 ptr++ 和 *ptr++ 行為的差異嗎？
*ptr++ 把 ptr 的位置加一，再取其值
ptr++ 直接把位置加一
c) 知道通訊領域中如何應用 parity bit 嗎？
在通訊的時候，如果包含校正位奇數的個數發生改變，表示傳輸過程有錯誤，但無法找出錯誤的位置，因此當錯誤發生，只能重新傳輸。
d) 知道 void (*signal(int sig, void (*handler)(int))) (int); 這樣的宣告該如何解讀嗎？
1. signal 是個有兩個參數的函式，第一個參數是 int sig，另一個為 function pointer handler，handler return void 並且傳入一個參數 int 。
2. signal return 一個指向 function 的 function pointer，此函式 return void 並且傳入一個參數 int 。
- signal 是個有兩個參數的函式，第一個參數是 int sig，另一個為 function pointer handler，handler return void 並且傳入一個參數 int 。
- signal return 一個指向 function 的 function pointer，此函式 return void 並且傳入一個參數 int 。
e) 知道 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 內的 -> ，優先權不同，而導致程式錯誤。
f) 知道從 color space RGBA8888 轉換為 8-bit 灰階的程式如何撰寫，又如何透過 SIMD 進行最佳化嗎？
g) 知道如何對 linked list 進行 merge sort 嗎？真實世界中的應用場景為何？
h) 知道 memory misalignment 對程式正確性和效能的影響嗎？能否舉出 Linux 核心對應的處理機制？
h) 知道 memory misalignment 對程式正確性和效能的影響嗎？能否舉出 Linux 核心對應的處理機制？
* 沒有做 memory aligment ，在存取資料時，可能會需要額外計算 bitshifting
i) 知道如何用 bit-wise operator 實作 clz / ctz (count leading/tailing zero) 嗎？
使用類似二分法的概念去計算
j) 知道 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).
k) 知道如何寫出時間複雜度和空間複雜度皆為 O(1) 的 abs64 嗎？(沒有分支) 這樣的 abs64 又可用於真實世界哪邊？
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
l) 知道 C 語言編譯器如何做 Tail Call Optimization (TCO) 嗎？以 gcc 來說，什麼樣的遞迴程式可做 TCO，又有什麼樣的遞迴程式無法呢？
假設main 呼叫 F(A) ， F(A) call F(B)，在 A 呼叫 B 時，沒有把 A 的位置存起來就直接跳到 B ，當 B 執行結束時，直接將 pc 退回到 main
m) 知道 page fault 嗎？Segmentation fault 的訊息是如何顯示出來，請以 GNU/Linux 為例解說
1. 程式在存取記憶體時產生錯誤
a.程式在存取記憶體時產生錯誤
多出現在
* 修改 string literal
* Access 已經 free 的空間
* Dereference 越界的指標
2. 發生 page fault 時， CPU 會發出 interrupt 給作業系統，像是傳送 signal 會由一個函式來處理。
b.發生 page fault 時， CPU 會發出 interrupt 給作業系統，像是傳送 signal 會由一個函式來處理。
n) 知道 CVE/CWE 嘛？你對資訊安全有什麼認知嗎？
o) 知道 fixed point 嗎？相較於 floating point，這樣的機制有何優缺點呢？知道真實世界如何運用嗎？
- Fixed 較不佔容量
- 運算上需要的資源較少
- 用於音訊轉換
p) 知道中國剩餘定理和 RSA 加密演算的關聯嗎？你知道哪些開放原始程式碼用到中國剩餘定理嗎？
使用RSA演算法在解密的計算時會需要較多時間，可以利用中國剩餘定理來加速
q) 知道 Poisson distribution 在本學期的課程主題中，出現在哪？以及為何工程議題需要考慮機率統計，能舉例嗎？
r) 知道 pipeline hazard 該如何消除嗎？有什麼議題須考慮？
- structural hazard:把 function unit 切的更小，讓硬體資源夠用
- data hazard：forwarding 或是把指令順序調換
- control hazard：delay, 硬體技術消除
s) 知道一個 singly-linked list 的新增節點操作，該如何用 Y86-64 組合語言實作嗎？
t) 知道 LRU replacement policy 對程式碼效能的影響嗎？如何撰寫程式去驗證某個處理器的 cache 行為呢？
u) 看懂 CS:APP 第 9 章講虛擬記憶體的描述嗎？知道 Linux 如何處理嗎？
v) 知道傅立葉分析在通訊領域的應用嗎？舉例說明
1.
- 傳輸前利用傅立葉轉換來壓縮數據，再經由反傅立葉轉換得到原始資料
w) 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在
x86_64 上可省下多少 cycle 呢？
w) 知道如何用 gcc 內建的 __builtin_ctz 改寫 GCD (最大公因數) 求值程式嗎？做了這樣的最佳化，預期在 x86_64 上可省下多少 cycle 呢？
x) 知道如何用 bitwise operator 實作出沒有分支的 FizzBuzz 程式嗎？
老師提供的
https://github.com/jserv/fizzbuzz/blob/master/bitwise.c
y) 知道如何實作無失真資料壓縮嗎？你知道有哪些相關演算法？
1. 產生出現頻率的統計模型
2. 利用統計模型，將出現頻率高的用較小的位元數表示，反之亦然
3. 位元序列編碼的演算法可使用霍夫曼編碼
- 產生出現頻率的統計模型
- 利用統計模型，將出現頻率高的用較小的位元數表示，反之亦然
- 位元序列編碼的演算法可使用霍夫曼編碼
z) 知道 Bloom filter 嗎？以你寫過或用過的程式，舉例說明這機制帶來的好處
- Bloom filter 為空間效率極高，將資料分類的演算法
