2020q3 Homework2 (quiz2)

# 2020q3 Homework2 (quiz2) contributed by < `joey3639570` > ###### tags: `進階電腦系統理論與實作` :::danger :warning: 注意共筆書寫規範，中英文之間用一個半形空白區隔，從小處做起！ :notes: jserv ::: 經過測驗 2，發現自己對於 bitwise 操作相當不熟，參照老師給的下列連結給自己複習: - [C Bitwise Operators Quiz](https://doc.callmematthi.eu/C_Bitwise_Operators.html) - [線上測驗 (附上解答)](https://pconrad.github.io/old_pconrad_cs16/topics/bitOps/) - [Bitwise Practice](https://web.stanford.edu/class/archive/cs/cs107/cs107.1202/lab1/practice.html) ### 實例： **ASCII** > A= 0x41, a= 0x61, ' '= 0x20, '_'=0x5f - 將字元轉成小寫: 免除使用分支 ```cpp ('a' | ' ') // 得到 'a' ('A' | ' ') // 得到 'a' ``` 0110 0001 | 0010 0000 -> **0110 0001** 0100 0001 | 0010 0000 -> **0110 0001** - 將字元轉為大寫: 免除使用分支 ```cpp ('a' & '_') // 得到 'A' ('A' & '_') // 得到 'A' ``` 0110 0001 & 0101 1111 -> **0100 0001** 0100 0001 & 0101 1111 -> **0100 0001** - 大小寫互轉: 避免使用分支 ```cpp ('a' ^ ' ') // 得到 'A' ('A' ^ ' ') // 得到 'a' ``` 0110 0001 ^ 0010 0000 -> **0100 0001** 0100 0001 ^ 0010 0000 -> **0110 0001** :::warning 延伸思考：課堂多次提到「避免分支」，這在程式碼的效能 (提示: 複習計算機組織/結構提到的 superscalar) 和資訊安全有什麼特別考量呢？ :notes: jserv ::: ### 為何要避免分支? - 參考 [Why is it good to avoid instruction branching where possible?](https://stackoverflow.com/questions/5662261/why-is-it-good-to-avoid-instruction-branching-where-possible) :zap:於效能而言，可以先從 [Instruction Prefetch](https://en.wikipedia.org/wiki/Cache_prefetching) 來看，其為處理器增加 performance 的主要方法之一，能藉此有能夠**提前**執行 instruction 的可能性，但是需要確定**下一個指令**才能有效果。此時可以再引入 [Instruction Pipeline](https://en.wikipedia.org/wiki/Instruction_pipelining) 的思考，更能了解為何 Branch 會影響 Performance，可參見 [Instruction Pipeline : Branches](https://en.wikipedia.org/wiki/Instruction_pipelining#Branches) >Programs written for a pipelined processor deliberately **avoid branching to minimize possible loss of speed.** #### 管線處理五個步驟 (Five stages, one step per stage) - IF: Instruction Fetch (**擷取指令**) 從記憶體擷取指令 (Instruction fetch from memory) - ID: Instruction Decode (**指令解碼**) 解碼指令並讀取暫存器 (Instruction decode & register read) - EX: Execution (**執行指令**) 執行運算或計算位址 (Execute operation or calculate address) - MEM: Memory Access (**記憶體存取**) 存取記憶體運算元 (Access memory operand) - WB: Write Back (**寫回**) 將結果寫回至暫存器 (Write result back to register) ```graphviz digraph foo { rankdir=BT; node_1 [shape=plaintext,label="Fetching next instruction depends on branch outcome in ID stage."] { node [shape=record]; rankdir=LR; node_A [shape=record label="{Instruction Pipeline|{IF|<t>ID|EX|MEM|WB}}"]; node_1->node_A:t } } ``` :bomb:**影響效能的關鍵問題 - Control Hazard :** >當 Branch 指令尚未決定是否分支，但後續指令已進入管線,故執行順序發生錯誤 :zap: **有 Branch ，便意指下一個 Instruction 有兩個或以上的可能** :zap: 然而， pre-fetching 便有了以下三種應對方法: - 不 prefetch 分支後的 Instructions ，而讓 instruction pipeline 空下來，等待分支判斷後再去取要執行的 instruction (**worse performance**) - Processor 可以先猜要走哪個 branch ( [branch prediction](https://en.wikipedia.org/wiki/Branch_predictor) ) ， prefetch 之後執行，但如果猜錯 branch ，就必須把先做完的部分丟掉，然後 fetch 正確的 instruction - Processor 同時 fetch 且執行兩個分支，分支後把沒有走的 branch 的部分丟掉 ( [eager execution](https://en.wikipedia.org/wiki/Speculative_execution#Eager_Execution) ) :::success :boom: 但不管怎樣，減少 branch 的使用，也就是減少**猜測**行為，就更能確保 Performance！ ::: #### Superscalar? > - A **superscalar processor** is a CPU that implements a form of parallelism called **instruction-level parallelism within a single processor**. > - Superscalar processor can execute **more than one instruction during a clock cycle** by simultaneously dispatching multiple instructions to different execution units on the processor. > > 參見 [Wikipedia: Superscalar Processor](https://en.wikipedia.org/wiki/Superscalar_processor#Limitations) :::warning :boom: 不要把 Superscalar 跟 Pipelining 搞混！ - Pipelining: several instructions are simultaneously **at different stages** of their execution - Superscalar: several instructions are simultaneously **at the same stages** of their execution ::: 於 Superscalar 架構下，**efficiency of speculation** 是一個 key issue ，若能每次都能精準的完成 Branch Prediction，將能使 Processor 的整體 Performance 上升。 #### Branch 和資訊安全有關? 相關資訊可閱讀: [Side-Channel Attacks](https://zh.wikipedia.org/wiki/旁路攻击) 參考[BranchScope: A New Side-Channel Attack on Directional Branch Predictor](https://www.cs.ucr.edu/~nael/pubs/asplos18.pdf) >Modern microprocessors rely on **branch prediction units(BPUs)** to sustain uninterrupted instruction delivery to the execution pipeline across conditional branches. #### BPU, Branch Prediction Units - 通常由兩個部分組成: **branch target buffer** (BTB) and the **irectional predictor**. :::warning **:BOOM:當多個 Processes 在同個 Physical Core 執行時**，他們會使用同一個 BPU ，此動作開了一個**能操控共享的 BPU 狀態的洞給攻擊者**，正是一個 **Side-Channel**，能導出受攻擊者的 Branch Instruction 的方向或目標，此 leakage 可能危及到較重要的 data ::: Attack example: >When a branch instruction is conditioned on a bit of a secret key, **the key bits are leaked directly**. This occurs in implementations of exponentiation algorithms and other key mathematical operations of modern cryptographic schemes. The attacker may also **change the predictor state**, changing its behavior in the victim. >**Side-channel attack on the BTB that creates BTB collisions** between the victim and the attacker processes, thus allowing the attacker to discover the location of a particular victim’s branch instruction in the address space, bypassing address space layout randomization. ## Quiz ### 測驗`1` ```cpp #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <string.h> bool is_ascii(const char str[], size_t size) { if (size == 0) return false; int i = 0; while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); if (payload & MMM) return false; i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` #### `MMM` 為`0x8080808080808080` 原理可以參照： >7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。 #### 推論重點: - uint64_t payload，64 位元 - `0x8080808080808080` 共 16 個十六進位的位數，每一個數字代表 4 bits，參閱題目上原本用 `& 0x80` 判斷是否為 ASCII。 ### 延伸問題 > 1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性 **程式運作原理** 1. 傳入 string 陣列及其 `size` 2. 如果 `size` 為 0，回傳 `false`，即不是 ASCII 3. 之所以使用 `while ((i + 8) <= size)` 是因為基本比較就以 `& 0x80` 起跳，以下為迴圈內 1. **透過 memcpy，告知 compiler 以 uint64_t 進行 data alignment，對於效能有影響(?，待實驗)** 2. **13~14行**藉`bitwise 操作`，得知是否為ASCII 3. 以兩碼( 8 bits )為單位往後移 4. 最後在以原始方法，把剩下的部分一個個確定真的不是 ASCII 5. 都通過後，回傳 True ![](https://i.imgur.com/zN3ekbU.png) ![](https://i.imgur.com/CZRUevh.png) [data alignment 參考](https://hackmd.io/@sysprog/c-memory) > data alignment 的意思就是， data 的 address 可以公平的被 1, 2, 4, 8,這些數字整除，從這些數字可以發現他們都是 2 的 N 次方 (N為從 0 開始的整數)。換句話說，這些 data object 可以用 1, 2, 4, 8 byte 去 alignment > 現代的處理器處理一般的讀取跟寫入資料，如果沒有效能考量，不用特別處理 data alignment 的議題，例如 **intel x86 系統是允許 data unalignment** 的！（老師上課有提到） [data alignment 問題參考](https://stackoverflow.com/questions/26381206/why-does-an-uint64-t-needs-more-memory-than-2-uint32-ts-when-used-in-a-class-a) > The rule for alignment (on x86 and x86_64) is generally to align a variable on it's size. In other words, **32-bit variables are aligned on 4 bytes, 64-bit variables on 8 bytes, etc.** e.g. uint32_t v.s. uint64_t > 2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」可以參考測驗 `5` 來取得 A~Z 的範圍! 參考 `RinHizakura`... >如果字元是小寫的英文子母，則 `lower_mask` 對應的 8 bits 就會是 `0x80`，大寫的字母亦然，`upper_mask` 對應的 8 bits 會是 `0x80`，因此，如果 `str` 的內容僅由大小寫字母組成，則 `lower_mask | upper_mask` 會得到 `0x8080808080808080`，我們可以藉此來判斷一個已知長度的字串，是否包含有效的英文大小寫字母。 **英文大小寫字母 ASCII 範圍:** A~Z: **0x41~0x5A** a~z: **0x61~0x7A** ```cpp #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <string.h> bool is_char(const char str[], size_t size) { if (size == 0) return false; int i = 0; while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); uint64_t A = payload + PACKED_BYTE(128 - 'A' ); uint64_t Z = payload + PACKED_BYTE(128 - 'Z' - 1); uint64_t a = payload + PACKED_BYTE(128 - 'a' ); uint64_t z = payload + PACKED_BYTE(128 - 'z' - 1); uint64_t lower_mask = (a ^ z) & PACKED_BYTE(0x80); uint64_t upper_mask = (A ^ Z) & PACKED_BYTE(0x80); if ((lower_mask | upper_mask ) ^ PACKED_BYTE(0x80)){ return false; } i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` > 3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4 (20200924 未撰寫) --- ### 測驗`2` ```cpp= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0xf; } ``` ### 延伸問題 >1. 解釋上述程式的運作原理 **程式運作原理** `MASK` = **0x40**，這個 mask 是有用來判斷是否為字母，字母範例如下: F = 0**1**00 0110 f = 0**1**10 0110 故利用 `0x40(0100 0000)` 作為 mask 根據上述兩例帶入，`letter` 為**0100 0000** 若為數字，`letter` 則為**0000 0000** **shift** 於數字的 case 用不到，於字母的 case，在此需要以**9**為起點，故`AAA` = 3，`BBB` = 6 帶入上兩例 (F,f)，可得到**0000 1001**，也就是**9** 在帶入底下 `(in + shift)` -> 0100 0110 + 0000 1001 = **0100 1111** 最後`& 0xf`的目的是用於清除掉前面4碼上例便是得到**1111**，也就是**15** >2. 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值此題解題想來自 [convert-hex-string-char-to-int](https://stackoverflow.com/questions/10156409/convert-hex-string-char-to-int)。 ```cpp #include <stddef.h> #include <stdint.h> #include <string.h> uint64_t haxcharstr2val(const char str[]) { int len = strlen(str); // Check length of string assert(len <= 18); // Check if start with '0x' assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X')); int i = 2; uint64_t val; while (i <= size) { uint8_t byte = str[i]; byte = hexchar2val(byte); // shift 4 to make space for new digit, and add the 4 bits of the new digit val = (val << 4) | (byte & 0xF); } return val; } ``` --- ### 測驗`3` ```cpp const uint32_t D = 3; #define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)) /* compute (n mod d) given precomputed M */ uint32_t quickmod(uint32_t n) { uint64_t quotient = ((__uint128_t) M * n) >> 64; return n - quotient * D; } ``` 預期 `quickmod(5)` 會得到 `2`, `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (`555` 是 3 的倍數)。 ### 延伸問題: >1. 解釋上述程式的原理; 數學式 $\frac{n}{D} = n * \frac{\frac{2^N}{D}}{2^N}$ ，此段程式首要解決的便是 `M`，也就是$\frac{2^N}{D}$ 值得注意的是**程式第6行**，`uint64_t quotient = ((__uint128_t) M * n) >> 64;`，在此**向右 Shift 了 64個位元**，意同於除以 $2^{64}$，藉此得知`M`應要代表 $2^{64}$ `XXX`便為`0xFFFFFFFFFFFFFFFF` >2. 由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距; (20200924 未撰寫) --- ### 測驗`4` >延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 `D` 和 `M` 都沿用的狀況下，程式碼如下: ```cpp= bool divisible(uint32_t n) { return n * M <= YYY; } ``` >以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即白痴是三的倍數) 參考 `RinHizakura`... >$n * M$ 可以想成是把數字位移到剩下 $\frac{n}{D}$ 的小數部份，而 M - 1 則是 $\frac{1}{D}$ 的小數部份，要判斷 n 是否可以整除 D，思路是判斷 $\frac{n}{D}$ 的小數部份是否小於 $\frac{1}{D}$ (因為小數部份只能是 0、$\frac{1}{D}$、$\frac{2}{D}$…$D-\frac{1}{D}$) 根據上述推斷，可以得知 `YYY` 為 `M-1` ### 測驗`5` ```cpp= #include <ctype.h> #include <stddef.h> #include <stdint.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) /* vectorized implementation for in-place strlower */ void strlower_vector(char *s, size_t n) { size_t k = n / 8; for (size_t i = 0; i < k; i++, s += 8) { uint64_t *chunk = (uint64_t *) s; if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3); uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; *chunk ^= mask; } else strlower(s, 8); } k = n % 8; if (k) strlower(s, k); } ``` ### 延伸問題: >1. 解釋上述程式的原理 - 先解釋`PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)`如下: - `(uint64_t)(b) & (0xff)` 可以取出最後八個位元 - `* 0x0101010101010101u` 用於複製這八個位元八次 - `VV1` 就是在測驗 1 中有用到的技巧，故選 `(e) 0x80` - 確認為 ASCII 後，便是要利用 bitwise 製作出 `if(c - 'A' >= 0 && c - 'Z' <= 0)` 的效果 - 變數 `A` 用於判斷是否大於 `A` (若最左邊的 bit 為 1 則為 1) - 變數 `Z` 用於判斷是否小於 `Z` (若最左邊的 bit 為 1 則為 1) - 參考 `RinHizakura`... >- 因此如果 c 同時滿足 >= 'A' 且 <= 'Z'，c + 128 - 'A' XOR c + 128 - 'Z' + 1 的結果會是 0b10000000，否則就是 0b00000000。 >- 又如果 s 是 'A' ~ 'Z' 之間的字元，最終對 chunk 處理的 mask 是 0b00100000(對應 **strtolower 的 1 << 5**)，也就是前面的結果 0b10000000 >> 2 所得到的 mask，不然就是 0b00000000。因此: VV2 = `(b) 0` VV3 = `(c) -1` VV4 = `(e) 0x80` >2. 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為參照:[你所不知道的 C 語言：指標篇](https://hackmd.io/@ofAlpaca/SyzamVp_Q?type=view) >`char *s="Hello world"` 此為string literal，和 `char s[]="Hello world"` 不同，前者存於read-only data section ，後者則是 stack 的 local variable。底下是測資: ```cpp #include <stdio.h> #include <string.h> int main() { /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */ char str[] = "This eBook is for the use of anyone anywhere at no cost and with \ almost no restrictions whatsoever. You may copy it, give it away or \ re-use it under the terms of the Project Gutenberg License included \ with this eBook or online at www.gutenberg.net"; int n = strlen(str); strlower_vector(str, n); puts(str); } ``` 在這裡 `char str[]` 改成 `char *str` 的話， `strlen()` 不能接受 null pointer ，會造成未定義的行為 (**undefined behavior**)。可藉底下這段解決: ```cpp #define strlens(s) (s==NULL?0:strlen(s)) ``` ### 測驗`6` ```cpp= int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { lower ^= nums[i]; lower &= KKK; higher ^= nums[i]; higher &= JJJ; } return lower; } ``` ### 延伸問題: >1. 解釋上述程式的原理 - 由於一開始無法直接理解這題的解法，故決定直接帶答案進去理解，答案如下: - 參考 `sammer1107` ，解了一個困惑許久的觀念： >首先每個 bit 的動作是獨立的，不會互相影響。所以我們其實是在分別計算每個 bit 的出現次數。 - `xor` 這個動作可以當作是**兩者相加，但不進位**，這個觀念可以用於判斷出現兩次。 | a | b | output | | --- | --- |:------:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | - 推廣到判斷三次，程式內的 `lower` 和 `higher` ，其實概念是兩個位元代表2進位的數字，出現第一次`01`,第二次`10`，第三次`00`來代表以**5 (101)** 為例: **第一次** 000 ^ 101 = 101 (`lower ^=`) 101 & 111 = 101 (`lower &= ~higher`) 000 ^ 101 = 101 (`higher ^=`) 101 & 010 = 000 (`higher &= ~lower`) 結果而論 `lower` 為 101 ， `higher` 為 000 **第二次** 101 ^ 101 = 000 (`lower ^=`) 000 & 111 = 000 (`lower &= ~higher`) 000 ^ 101 = 101 (`higher ^=`) 101 & 111 = 101 (`higher &= ~lower`) 結果而論 `lower` 為 000 ， `higher` 為 101 **第三次** 000 ^ 101 = 101 (`lower ^=`) 101 & 010 = 000 (`lower &= ~higher`) 101 ^ 101 = 000 (`higher ^=`) 000 & 111 = 000 (`higher &= ~lower`) 結果而論 `lower` 為 000 ， `higher` 為 000 綜合上述，其實可以看出來，第一次我們使用 `lower` 保留紀錄，第二次這個紀錄會被傳到 `higher` ，若遇到第三次，則兩者歸零，因此在遇到只有一次的case ， `lower` 會保留住只出現一次的數字，故在最後 return `lower`。 >2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時 (20200924 未撰寫) >3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼 - 重複4次這種偶數，原本可能直覺要套用 `mod 4` 算法，其實套用 `mod 2` 的算法就可以了，因為最主要是要選擇一個 `m` 確保 `4k mod m == 0` - 重複5次，會想到要套用 `mod 5` ，但這樣必須要用到3個位元來記錄次數了。 - 此時可以回想前面，主要目的是要找到 `mod m == 0` 的 `m` ， `m` 可以推想為 `n` (重複次數) 的最小質因數，舉例而言，重複9次可以套用 `mod 3` 的算法。

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.