2020q3 Homework6 (quiz6)

# 2020q3 Homework6 (quiz6) contributed by < `RainbowEye0486` > ## 測驗一測驗開始之前，先稍微理解 `bfloat16` 。`bfloat16` 是針對高運算以及高吞吐量選擇降低精準位數的 trade off，與IEEE定義的 `float32` 比較能夠加速訓練神經網路，並且透過截斷的方式降低 DNN 可能出現[梯度消失](https://www.jianshu.com/p/841ac51c7961)的風險；跟 float16 相比之下則可以解決如訓練 `Multibox SSD network`[^SSD]時因為動態範圍不夠導致約一半的梯度無法更新。 [^SSD]:參考資料 [MIXED PRECISION TRAINING](https://arxiv.org/pdf/1710.03740.pdf) ```cpp float fp32tobf16(float x) { float y = x; int *py = (int *) &y; unsigned int exp, man; exp = *py & 0x7F800000u; man = *py & 0x007FFFFFu; if (!exp && !man) /* zero */ return x; if (exp == 0x7F800000u) /* infinity or NaN */ return x; /* Normalized number. round to nearest */ float r = x; int *pr = (int *) &r; *pr &= 0xff800000; r /= 256; y = x + r; *py &= 0xffff0000; return y; } ``` #### 1. 解釋上述程式碼的運作機制，需要搭配 [BFloat16: The secret to high performance on Cloud TPUs](https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus) 和 [Making floating point math highly efficient for AI hardware](https://engineering.fb.com/2018/11/08/ai-research/floating-point-math/) 解說對於程式碼的解說: 1. 首先`float32` 的 x 強制轉型成 unsign int 的形式，才能透過 `bit mask` 取出原本 `float32` 的 `exponent` 以及 `mantissa` 值 2. 處理0、NaN的情形，用 IEEE754 浮點數規範[^IEEE754]判別( exponent 項為 255) 3. 為了實做 rounding ，我們從已知部分下手: - bfloat16 的 fraction 只記錄 7 bit 而已 - 如果原本 float32 fraction 的第 8 個 bit 是0則不須進位，如果是1則進位 - 如果在原本的 fraction bit8 加一，就可以判斷進位，原本是1的話會進位到 bit7 去，原本是0的話加一也不會進位，而是等待截斷後面的16 bit 時，便會自動被截掉 :::warning :warning: 如果是負數的操作則會變成是減一 ::: 5. `*pr &= 0xff800000;` 將 mantissa 變成0，原因是這樣我們可以做出想要的1(運用浮點數特性，1.011101...去掉 fraction 後可以得到) 6. `r /= 256` :指數-8，移動到 bit8 的位置，接著和原數相加，獲得進位後的浮點數 7. `*py &= 0xffff0000;` :最後截斷後面16位數，完成。 [^IEEE754]:![](https://i.imgur.com/w23kYSj.png) :::success 文章摘要: **Google** 1.DNN能夠接受較低精度的浮點數運算，原因是層級結構的關係，神經網絡對 exponent 的大小要比 fraction 敏感得多，而想要做到推論及預測，高精度的浮點數反而會在層數增加時產生誤差上升的現象；除此之外，整數運算也從原本的32 bit 降為短整數的 8 bit，記憶體消耗與儲存空間也能夠被大幅下降。 2.TPU 是 google 開發為自己量身訂做使用深度神經網路硬體加速器，本身為了追求低延遲性而放棄了更大的通量；內部將相同的運算單元串接以減少記憶體存取時間，適合矩陣乘法和普及於特徵辨識的卷積運算，諸多規格的調整能夠讓運算速度上比傳統的 CPU 和 GPU 快個 15~30 倍 3.bfloat16 能夠讓內存空間更像是翻倍一樣，原本16G大小的儲存空間因為 4.根據老師的提醒，**記憶體頻寬(Memory bandwidth)** 的定義是從記憶體讀取資料或將資料儲存到記憶體的速率，我看到比較好理解的例子是，如果說記憶體本身是倉庫，記憶體頻寬就如同運輸的橋樑，對於硬體限制橋梁並沒有變寬的情況下(通常因為硬體不便宜所以從其他方向著手)， bfloat16 就如同將原本笨重的大型貨車改成輕量的小型轎車，如此一來，單位時間內通過的車輛就會比之前還要多，從而提高運算速度。 **Facebook** 1.提出高精度浮點數可能在複雜模型中造成過擬合而沒辦法符合常態情形。 2.高效能浮點數優化方向 - 減少 word 數 : 大多數神經網絡在-10.0到10.0等相對較小的範圍內執行計算，因此開發出 **錐形浮點** 的方式，透過變動的 exponent 跟 fraction 使浮點數在此一小範圍內的精度提高，同時還能夠降低所需的表示長度。 - 我們常常在矩陣運算時，會使用到 $c = c+ab$ 這個形式，根據 CS:APP 2.4 章提到，浮點數的運算並不符合 **Associative** 和 **Distributive** 的性質，因此可能會因為在捨入時產生誤差。普通的浮點數運算情形，會先針對 $a*b$ 做一次捨入，得到的乘積和 $c$ 相加時再捨入一次，FMA 則一次計算完後只做一次的捨入，能夠降低誤差值。 Kulisch 累加器實作 FMA 時，注意到在尾數對齊時缺點是假設是 FP32 運算，Kulisch 累加的代價很高，因為累加器、移位器和加法器的大小可能大於 500 位，因此在低精度的 bfloat16 運算時可能較為適合。 3.最後提到 facebook 會朝著 EMLA 乘加電路以及結合 IEEE 半精度和 bfloat16 的方向邁進。從這兩篇文章看下來， google 已為專屬的 TPU 開發出了一套相對完善的系統，用於未來加速深層神經網路的運算、降低記憶體消耗以及增加記憶體頻寬，並且在硬體軟體的結合考慮也比較全面，可以看出 google 對這方面的準備十分充足。facebook 也注意到在未來如果想要鞏固市場的地位， AI 加速器可以說是必要關鍵，他們也想辦法運算大量用戶的數據，[facebook跨界打造AI深度學習晶片](https://www.eettaiwan.com/20180917nt01-facebook-builds-chip-team-asic/)一文中也提及 facebook 有野心想要打造屬於自己的 AI 晶片。原文網址：https://kknews.cc/tech/a45nx5g.html ::: ![](https://i.imgur.com/17mPztM.png) :::warning :bulb: 問題: 1.文章中提到混和精度的運算，是不是如上圖所表示的，因為權重如果使用 bfloat16 或是 float16 均會造成捨入誤差隨著遞增的層數擴大，所以有必要使用 FP32 更新?權重會不會有梯度消失的情形?混和精度在實際處理上會不會造成太多的運算效能負擔，也就是花很多時間在浮點數轉型上? ::: #### 2. 改進上述程式碼，實作 DP/SP 轉換程式，並針對 BFloat16 撰寫測試程式，應儘量涵蓋有效的數值輸入和輸出範圍首先需要改進的部分肯定是浮點數除法的部分: ```cpp=16 r /= 256; ``` 原本的目的是想做出$(-1)^s⋅2^{exp}⋅2^{-8}$，但是浮點數除法浪費過多運算時間。考慮到這邊想要實做的最終目的是進位，所以我們可以直接對已經轉變成 unsign int 的 `*py` 做 **bitwise 運算**。想法如下: 1. **對 fraction 部分的 $b^8$ 加一** 2. **fraction overflow 則指數項加一當進位** ```cpp= float M_fp32tobf16(float x) { float y = x; int *py = (int *) &y; unsigned int exp, man; exp = *py & 0x7F800000u; man = *py & 0x007FFFFFu; if (!exp && !man) /* zero */ return x; if (exp == 0x7F800000u) /* infinity or NaN */ return x; /* Normalized number. round to nearest */ exp >>= 23; man += 0x00008000;//bit8 plus 1 if (man & 0x00800000 !=0) exp += 1; *py &= 0x80000000; *py |= (exp << 23); *py |= (man & 0x007FFFFFu); *py &= 0xffff0000; return y; } ``` :::success TODO : 分析效能並且測試 ::: #### 3. 考慮批次轉換 FP32/FP64 為 BFloat16 的需求，請改進上述程式碼，得以提高轉換的效率 :::success :bulb:想法: 考慮到批次轉換，可使用 `AVX-512` 指令集作為批量處理的方式，可一次處理8~16個 FP64/FP32 的轉換 ::: 程式碼: **待補** ## 測驗二考慮以下 [ring buffer](https://en.wikipedia.org/wiki/Circular_buffer) 的實作: ```cpp #define RINGBUF_DECL(T, NAME) \ typedef struct { \ int size; \ int start, end; \ T *elements; \ } NAME #define RINGBUF_INIT(BUF, S, T) \ { \ static T static_ringbuf_mem[S + 1]; \ BUF.elements = static_ringbuf_mem; \ } \ BUF.size = S; \ BUF.start = 0; \ BUF.end = 0; #define NEXT_START_INDEX(BUF) \ (((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0) #define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0) #define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start) #define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start) #define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end] #define ringbuf_write_skip(BUF) \ do { \ (BUF)->end = NEXT_END_INDEX(BUF); \ if (is_ringbuf_empty(BUF)) \ (BUF)->start = NEXT_START_INDEX(BUF); \ } while (0) #define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start] #define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF); #define ringbuf_write(BUF, ELEMENT) \ do { \ ringbuf_write_peek(BUF) = ELEMENT; \ ringbuf_write_skip(BUF); \ } while (0) #define ringbuf_read(BUF, ELEMENT) \ do { \ ELEMENT = ringbuf_read_peek(BUF); \ ringbuf_read_skip(BUF); \ } while (0) ``` #### 1. 解釋上述程式碼的運作機制，包含 do { ... } while (0) 使用的考量 * `RINGBUF_DECL(T, NAME)` :定義結構 * `RINGBUF_INIT` :初始化一個 `circular buffer` * `NEXT_START_INDEX(BUF)` :判斷 `START` 下一個位置，如果 buffer 滿了則回到起點(0)，沒滿則 **+1** * `NEXT_END_INDEX(BUF)` :判斷 `END` 下一個位置，如果 buffer 滿了則回到起點(0)，沒滿則 **+1** * `is_ringbuf_empty(BUF)`: buffer 為空 * `is_ringbuf_full(BUF)`: buffer 已滿 * `ringbuf_write_peek(BUF)`:`END` 寫入 * `ringbuf_write_skip(BUF)`:移動當前 `END` 的位置到下一個 * `ringbuf_read_peek(BUF)`:取得 `START` 的 `element` 值 * `ringbuf_read_skip(BUF)`:移動當前 `START` 的位置到下一個 * `ringbuf_write(BUF, ELEMENT) `:相當於 queue 的 push * `ringbuf_read(BUF, ELEMENT)`:相當於 queue 的 pop 根據[C 語言前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)提到，我們的preprocesser在編譯之前，會先將 macro 定義取代進我們呼叫他的地方，也就是會把 macro 定義的部分直接替換進程式當中，這時候可能會出現一個問題，也就是[C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick)提到的，可能會出現 `dangling else` 的問題，這個問題源自於如果我們的原方程式當中已經有 else 在我們呼叫的 macro 下面的話，可能出現把 macro 定義代入後 else 配對錯誤的問題: ```cpp= #define macro(para) if(condition2)\ ... if(condition) macro(para); else{ ...; } ``` 前處理器處理後的結果: ```cpp= if(condition) if(condition2) ...; else{ ...; } ``` 當 if 後面只接巨集呼叫時，因為沒有 block 會使後面緊接的 else 直接配對錯誤。因此使用 `do{}while(0)` 的好處就是能夠把巨集定義封裝完整，避免了後面的 else 配對錯誤 #### 2.研讀 [Super Fast Circular Ring Buffer Using Virtual Memory trick](https://abhinavag.medium.com/a-fast-circular-ring-buffer-4d102ef4d4a3)，指出效能改善的機制並用 C99/C11 (可搭配 GNU extension) 重新實作文章中利用了 VM 讓電腦以為自己是在使用一段連續記憶體的方式，將環形 buffer 的頭尾相接。第一版的 `enqueue` 實作方式如下: ```cpp= template <typename T> void Queue::enqueue(const T* data, const size_t size) { for (int i = 0 ; i < size; ++i) { this->buffer[(this->tail + i) % this->buffer_size] = data[i]; } this->tail = (this->tail + size) % this->buffer_size; } ``` 其實就是看一開始的 `data` 要塞多少資料進去，如果存完一圈後繼續從頭覆蓋。第二種實作方式 : ```cpp= template <typename T> void Queue::enqueue(const T* data, const size_t size) { const size_t part1 = std::min(size, this->buffer_size - this->tail); const size_t part1_sz = part1 * sizeof(T); const size_t part2_sz = size * sizeof(T) - part1_sz; memcpy((void*)(this->buffer + this->tail), data, part1_sz); memcpy((void*)(this->buffer), data + part1, part2_sz); this->tail = (this->tail + size) % this->buffer_size; } ``` - `part1` 決定的是"這個 buffer size 還剩多少空間才會回到頭(wrap-around)"，但是如果想要儲存的 data 長度比所剩的空間還短，那就會選擇 data 的 `size` 就好，也就是所剩的空間足夠放入整個 data。 - `part2` 決定的是如果 data 塞滿當前的 tail 到 end 這段距離後， wrap-around 開始放入剩下的 data 需要的大小 :::warning :warning: 這個做法目前沒有限制 data 的 size 大小，如果這個 size 超過兩個 buffer size ， `part2_sz` 的大小仍舊會比一個 buffer size 大，這樣在做 `mcpy` 時會儲存到非法記憶體，第三種情形的程式碼也是一樣，也許第二和第三種作法已經事先限制了 size 大小? ::: 這種分段的方式可以省下 for 迴圈中每次做 modulo 需要花費的運算時間，而第三種實作方式能夠甚至將兩次的 `mcpy` 變成只需要一次: ![](https://i.imgur.com/3sLNpn0.png) 透過虛擬記憶體與實體記憶體的對應關係，我們成功的讓程式得到了一個兩倍 buffer size 的(虛擬)記憶體。假設前提是 size 的大小不超過兩倍的 buffer size ， ```cpp= template <typename T> void Queue::enqueue(const T* data, const size_t size) { memcpy((void*)(this->buffer + this->tail), data, size * sizeof(T)); this->tail = (this->tail + size) % this->buffer_size; } ``` :::success TODO : 實作 ::: ## 測驗三考慮到以下靜態初始化的 singly-linked list 實作: ```cpp= #include <stdio.h> /* clang-format off */ #define cons(x, y) (struct llist[]){{y, x}} /* clang-format on */ struct llist { int val; struct llist *next; }; void sorted_insert(struct llist **head, struct llist *node) { if (!*head || (*head)->val >= node->val) { SS1; SS2; return; } struct llist *current = *head; while (current->next && current->next->val < node->val) current = current->next; node->next = current->next; current->next = node; } void sort(struct llist **head) { struct llist *sorted = NULL; for (struct llist *current = *head; current;) { struct llist *next = current->next; sorted_insert(&sorted, current); current = next; } *head = sorted; } int main() { struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D); struct llist *p; for (p = list; p; p = p->next) printf("%d", p->val); printf("\n"); sort(&list); for (p = list; p; p = p->next) printf("%d", p->val); printf("\n"); return 0; } ``` 輸出結果為 ``` 9547 4579 ``` #### 1.解釋上述程式碼的運作機制，參照 [C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick)，需要列出相關的 C 語言規格描述並解讀 * 在巨集 `#define cons(x, y) (struct llist[]){{y, x}}` 中，我們發現傳入 x 、 y ，連結的方式其實是 y 是 value， x 是下一個節點，因此如果輸出結果是 `9457` ，可以回推當初輸入的順序應該是 **cons(cons(cons(cons(NULL, 7), 5), 4), 9)** * `sorted_insert` 中，首先 `if (!*head || (*head)->val >= node->val)` 說明當這個 list 是空的時候，或是 head 比想要插入的節點 value 還要大的時候，插入節點會成為新的 `*head` ，而接著處理其他情形下，走訪這個由小排到大的 list ，並且以升冪的方式插入 list 。因此: **SS1 = `node->next = *head`** **SS2 = `*head = node`** * `sort(struct llist **head)` 函式中，創建一個新的 llist 並且從原本的 list 取出節點並用 `sorted_insert` 函式放入新 llist 中重新排列 [C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick)中利用 compound literal 建立 static linked list - 可針對未知大小的 array/struct 初始化，也可以直接對特定位置的 array 或 struct 指定內容 - compound literal 可以做 lvalue ，可以傳特定型別或自己定義的 struct >C99 [6.5.2.5] Compound literals >- The type name shall specify an object type or an array of unknown size, but not a variable length array type. >- A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list. >- If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue. - 規格書解釋第一點代表雖然可以針對未知大小的 array/struct 初始化，但是如果像是浮動陣列這樣長度不固定的類型無法表示 - 第二點解釋 compound literal 怎麼在程式碼中表示。 - 第三點解釋 compound literal 大小由 initialize list 而定，而型別則是由陣列型別(未指定)或是已指定的型別名稱決定，但是兩者回傳結果皆為算術左值 #### 2.研讀 [Doubly Linked Lists in C](http://locklessinc.com/articles/dlist/) 並比對 Linux 核心的 linked list 實作予以解說首先，題目敘述的 linfed list 有個問題，當新增另一條 llist sorted 的時候，我們必須要額外多分配 $O(n)$ 的記憶體空間，而這條新的 llist 中的元素和原本的 llist 式完全一樣的，換言之，用 `double linked list` 就可以避免掉空間的浪費。因為 `double linked list` 能夠紀錄上一個節點以及下一個節點，我們只需要再多一個 buffer 的 size 當作節點移動用就可以直接在原本的 llist 中排序，實作方式類似 llist 版本的 `insertion sort` :::success TODO : 驗證 ::: #### 3. 練習 LeetCode 148. [Sort List](https://leetcode.com/problems/sort-list/)，嘗試將 Optimizing merge sort 的手法引入到 C 程式中實作 :::success TODO: 練習 LeetCode ::: ## 測驗四 [LeetCode 287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/) 給定一個整數序列，其中會有一個數值重複，請找出。 ```cpp= int findDuplicate(int *nums, int numsSize) { int res = 0; const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize); for (size_t i = 0; i < log_2; i++) { int bit = 1 << i; int c1 = 0, c2 = 0; for (size_t k = 0; k < numsSize; k++) { if (k & bit) ++c1; if (nums[k] & bit) ++c2; } if (c1 < c2) res += bit; } return res; } ``` #### 1.解釋上述 LeetCode 題目和程式碼的運作機制，指出改進空間並實作程式碼解析 1. `log_2 = 8 * sizeof(int) - __builtin_clz(numsSize)` :因為不同架構的 sizeof(int) 不盡相同，所以 `8 * sizeof(int)` 得出位元架構，減掉 `__builtin_clz(numsSize)` 得到以**2為底的對數值**，也就是最少需要幾位元來表示n-1以內的數值 2. 從 log_2 的 LSB 開始，往左移動，每次檢查在數值是0到 n-1 沒有重複的情形下總共有幾個 set bit ，紀錄為 **c1** 3. 接著檢查在 `*num` 中，同一個位元位置累積的 set bit 數，紀錄為 **c2** 4. 如下表所示，可以發現比較同個位置的 **c1** **c2** 時，如重複數字在這個位置 `c1>=c2` 代表0， `c1<c2` 則代表重複數字在這個bit 是1 | \*num/log_2 | | | | | -- | -- | -- | -- | |**0**|0|0|0| |**1**|0|0|1| |**2**|0|1|0| |**3**|0|1|1| |**4**|1|0|0| |**5**|1|0|1| |**c1**|**2**|**2**|**3**| | \*num/log_2 | | | | | -- | -- | -- | -- | |**1**|0|0|1| |**2**|0|1|0| |**3**|0|1|1| |**4**|1|0|0| |**4**|1|0|0| |**4**|1|0|0| |**c1**|**3**|**2**|**2**| :::warning :warning: 關鍵在於沒有重複的情形下的 0 這個值和重複數字相比較，必定會使重複數字的 set bit 多出來，clear bit一樣或較少 ::: output: $100_2$($4_{10}$) :::success **改進部分:** 程式碼在空間上需使用$O(n)$的空間紀錄數值，時間複雜度則是$O(nlog(n))$，單就這個實作上，我認為空間複雜度已經十分精減了；就時間複雜度來說，除非更換架構，使用這個實作方式似乎還是要掃過 `*nums` 中的 $log(n)×n$ 個 bit ，就空間複雜度來說，還有可以優化的空間，但是**在不更動原本程式碼結構的情形下，不清楚如何優化** ::: #### 2.實作不同的程式碼 (合法的 C 程式，可運用 GNU extension)，使其表現優於上述程式碼 :::success :bulb:想法: 以大小為 numSize 的 bool array 當作一個 set table ，並且用 bit 的 set 和 clear 確定否重複: * 假如位置是0(第一次出現)則設置為1 * 假如位置是1(曾經出現過)則回傳 index 一但發現重複則立即 return ::: 程式碼實作 ```cpp= int findDuplicate(int *nums, int numsSize) { bool setTable[numsSize]; memset(setTable,0,sizeof(setTable)); for (int i = 0; i < numsSize; i++) { setTable[nums[i]] ^= 1; //taggle if (!setTable[nums[i]]) return nums[i]; } return -1; } ``` 結果展示，由於對於這種實作方式來說，時間複雜度只需要$O(n)$就好，可以加快運算時間，而空間複雜度依然維持$O(n)$不變 ![](https://i.imgur.com/cflb0mM.png) :::success :bulb:**能不能更好?** 待實作的部分，想法是就算用 bool array 當作紀錄 set bit 的方法，但是其實對於每個數字而言只需要1個 bit 紀錄就好，根本不需要用到 sizeof(bool)，也就是GCC x86 中的一個 byte 的大小，因此可以考慮使用 uint_32 當作 table ， index 則為 **32×第幾張table + offset** ，如此一來能夠減少75%的使用空間 ::: 程式碼: **待補**

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.