# 2019q3 Homework3 (quiz3)
contributed by < `davinais` >
###### tags: `sysprog` `sysprog2019`
## 測驗 `1`
考慮深度學習領域中，使用[激勵函數 ReLU](https://mropengate.blogspot.com/2017/02/deep-learning-role-of-activation.html):
$$
ReLU(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
0 & \text{if } x \lt 0
\end{cases}
$$
RelU 計算量小，只要判斷輸入是否大於 `0`，沒有指數運算。下方程式 (`ReLU.c`) 是個常數時間的實作:
```cpp
float ReLU(float x) {
union {
float f;
int32_t i;
} out = {.f = x};
out.i = out.i OP1 ~(out.i >> V2);
return out.f;
}
```
:::warning
Ans:
`OP1 = &`, `V2 = 31`
:::
:::success
延伸題目:
1. 解釋上述 ReLU 程式碼運作原理和應用場域 (歡迎寫篇深度學習的科普文章)，並寫出另一個常數時間的實作;
2. 研讀 [CMSIS-NN: Efficient Neural Network Kernels for Arm Cortex-M CPUs](https://arxiv.org/pdf/1801.06601.pdf)，在 Arm Cortex-M 微處理器架構中，透過 SWAR (SIMD within a register) 的手法，可帶來 4 倍效能提升。嘗試解釋其原理;
3. 透過 Intel SSE / AVX 等 SIMD 指令集，比照 [CMSIS-NN: Efficient Neural Network Kernels for Arm Cortex-M CPUs](https://arxiv.org/pdf/1801.06601.pdf)，進行加速 ReLU 的實驗;
:::
1. 上面的程式很聰明的運用了 sign bit 為 1 時是負數的技巧，首先用 union 讓 `float` 可以以 `int32_t` 的方式存取，隨後我們右移 31 個位元，因為 `i` 為有號數，因此在右移時會在最高位填充 sign bit，最後我們便能得到一個全部都是 sign bit 的 mask，反轉之後即符合我們所需要的負值為 `0` ，正值不變了。
2. 在該論文中，原本我們要對 `q7_t` 8bit 的型態做 ReLU 操作，如果我們一個一個操作可謂相當沒有效率。但是我們發現 `q7_t` 的大小，剛好能在 32bit 的 register 中放入 4 個元素，如果我們一次將 4 個 `q7_t` 放入 register 中，並且透過 sign extend 分別取得每個 byte 的 mask，最後再直接 AND 即可做完 4 個元素的 ReLU。一次就可以處理 4 個元素，因此理論有 4 倍效能提升。
:::danger
可以解釋實驗結果嗎？
:notes: jserv
:::
---
## 測驗 `2`
在 8 位元 [Motorola 6809 處理器](https://en.wikipedia.org/wiki/Motorola_6809)上，有道指令叫做 [SEX](https://en.wikipedia.org/wiki/SEX_(computing))，寓意是 "Sign EXtend"
> [Motorola 68000](https://en.wikipedia.org/wiki/Motorola_68000) (68K) 系列處理器，還有道指令名為 [BRA](http://68k.hax.com/BRA)，寓意是 "branch"，以前的工程師都很有創意 (?)
`SEX 123` 應該輸出 `0`, 而 `SEX -3` 要輸出 `0xffffffff` (取決於有效位數)
考慮一個 32 位元版本的 `SEX` 實作如下，假設執行環境是 little-endian:
```cpp
#include <stdint.h>
static inline uint32_t sex32(int32_t x) {
union {
TYPE w;
struct { uint32_t lo, hi; }; /* FIXME: little-endian */
} z = {.w = x};
return z.hi;
}
```
::: warning
Ans:
`TYPE = uint64_t`
:::
:::success
延伸問題:
1. 解釋程式運作原理，並改寫為適用於 big/little-endian 的程式碼;
2. 找出 Sign EXtend 的應用案例，特別是密碼學的應用
:::
本段程式的運作利用了 union 的技巧，我們將 `uint64_t` 與有兩個 `uint32_t` 的 struct 設成 union，並將 `x` 直接給 `z.w` 賦值。
:::info
不同大小與符號型態的整數在 assignment 時會有什麼表現？
雖然有在 C99 規格書的 6.3 節看到相關敘述，提到了 Conversion Rank ，也有提到 Conversion 會轉成哪個型態，但是沒有特別提到處理的行為，待研究。
:::
在我們指派 `x` 的內含值到 `z.w` 時，`x` 會在被擴充成 64bit 後轉為 unsigned 型態。不過在擴充時，就會根據 sign bit 對高位做填充了。這正是我們要的效果，我們只要接著將代表高位的 `uint32_t` 取出來即可。
不過上面的程式碼只對 Little Endian 有效，因為 Big Endian 的順序是相反的，那麼怎麼樣能解決這個問題呢？
我的想法很簡單，我們把 mask 也一起放進去就好了：
```c
static inline uint32_t sex32(int32_t x) {
union {
uint64_t w;
struct { uint32_t lo, hi; };
} z = {.w = x}, mask = {.w = 1};
mask.w = ~((mask.w << 32) - 1);
return (z.hi & mask.hi) | (z.lo & mask.lo);
}
```
首先在 `mask.w` 製造出一個高位為 `1` ，低位為 `0` 的 mask，再來將這個 mask 和原本的數字對應的高低位做 AND，最後再 OR 起來即可。我們不需要知道高位存在哪裡，只需要知道 `z` 與 `mask` 的高位兩者必定是存在同樣的地方就好。
### 使用 qemu 驗證
為了驗證正確性，我使用 qemu 來模擬 MIPS 架構的處理器來運行上面的程式，MIPS 架構雖然 Big Endian 與 Little Endian 都可以使用，不過預設是使用 Big Endian，我們便可以拿來驗證程式的正確性。
qemu 有兩種方式可以模擬處理器：
1. System Mode： `qemu-system-*` 系列，這種方式會模擬整個平台，包含硬體的部分，如同一台完整的電腦一般能夠操作，類似 VirtualBox、VMware 的運作模式，不同的是它可以模擬不同的 CPU。
2. User Mode： `qemu-user-*` 系列，它透過 kernel module `binfmt_misc` ，讓 Kernel 能夠透過預先註冊在 `/proc/sys/fs/binfmt_misc` 的資訊，藉由所提供 interpreter 等來解釋所執行的程式，達成模擬的效果。如果只是要模擬不同平台的執行檔的話，使用這個模式就已經足夠了。
此處由於這個只是簡單的小程式，因此使用 `qemu-user-*` 系列中靜態連結版本的 `qemu-mips-static` 來模擬，在我的 Mint 17 電腦上要安裝也相當簡單：
```shell
$ sudo apt-get install binfmt-support qemu-user-static
```
它就會連同 `binfmt_misc` 的註冊資訊也一併幫你處理完成，相當便捷。
:::info
由於大多數的程式基本上都應該是動態連結版本的，所以應該有不少是無法在 static 版本模擬的。而動態連結版本的 `qemu-user-*` 還需要搭配該平台基本的 library 以及配置才能夠使用，對於 Debian 系使用者可以參考 [Debian wiki 的教學](https://wiki.debian.org/QemuUserEmulation)，也能夠搭配 `chroot` 共同使用，如 [此篇文章](https://coldnew.github.io/1ad4bf6d/) 所述。
:::
當然，我們還需要 cross compiler 才能夠在我們的平台上編譯出 MIPS 架構的程式，由於 Ubuntu 的套件庫裡也已經收錄了 MIPS 的 cross compiler，因此我們也只需要一行指令便能完成安裝，因為我們要在我們的 Linux 環境下直接模擬，這裡就選用 `linux-gnu` 版本：
```shell
$ sudo apt-get install gcc-mips-linux-gnu
```
完成安裝之後，便可以來編譯測試程式了，我使用以下的 code 做測試：
```cpp
#include <stdint.h>
#include <stdio.h>
static inline uint32_t sex32(int32_t x) {
union {
uint64_t w;
struct { uint32_t lo, hi; };
} z = {.w = x}, mask = {.w = 1};
mask.w = ~((mask.w << 32) - 1);
return (z.hi & mask.hi) | (z.lo & mask.lo);
}
int main () {
int n = 1;
if (*(char *)&n == 1) {
puts("Little Endian");
}
else {
puts("Big Endian");
}
printf("%x, %x\n", sex32(12), sex32(-98));
return 0;
}
```
儲存成 `sex.c` 並進行編譯，首先先在 host 平台 (Little Endian) 進行測試：
```shell
$ gcc -o sex_host sex.c
$ ./sex_host
```
結果輸出：
```
Little Endian
0, ffffffff
```
符合我們的預期，接下來在 MIPS 平台進行測試，這裡因為我安裝的是靜態版本的 `qemu-mips` ，因此要在編譯時加入 `-static` 讓它變成靜態連結的執行檔：
```shell
$ mips-linux-gnu-gcc -o sex_mips sex.c -static
$ ./sex_mips
```
結果輸出：
```
Big Endian
0, ffffffff
```
測試成功，程式確實可行。
---
## 測驗 `3`
延伸測驗 `2` 的 `sex32`，用以改寫 [解讀計算機編碼](https://hackmd.io/@sysprog/rylUqXLsm) 提及的常數時間 `abs` 實作 (輸入是 32 位元整數)，程式碼如下:
```cpp
static inline int abs_with_sex(int x) {
return (x ^ sex32(x)) OP2 sex32(x);
}
```
::: warning
`OP2 = -`
:::
比照原本的 `(x + mask) ^ mask` 可得出。
---
## 測驗 `4`
待補
Sign in with Wallet
Connect another wallet