# 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`
待補