# 2019q3 第 3 週測驗題 (上)
:::info
目的: 檢驗學員對 $O(1)$ 的認知
:::

---

### 測驗 `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`) 是個常數時間的實作:

float ReLU(float x) {
    union {
        float f;
        int32_t i;                          
    } out = {.f = x};
    out.i = out.i OP1 ~(out.i >> V2);
    return out.f;
}

請補完。

==作答區==

`OP1` = ?
* `(a)` `+`
* `(b)` `-`
* `(c)` `&`
* `(d)` `|`
* `(e)` `^`

`V2` = ?
* `(a)` 32
* `(b)` 31
* `(c)` 16
* `(d)` 15
* `(e)` 0

:::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 的實驗;
:::

---

### 測驗 `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:

#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;
}

==作答區==

`TYPE` = ?
* `(a)` `int8_t`
* `(b)` `uint8_t`
* `(c)` `int16_t`
* `(d)` `uint16_t`
* `(e)` `int32_t`
* `(f)` `uint32_t`
* `(g)` `uint64_t`

:::success
延伸問題:
1. 解釋程式運作原理，並改寫為適用於 big/little-endian 的程式碼;
2. 找出 Sign EXtend 的應用案例，特別是密碼學的應用
:::

---

### 測驗 `3`

延伸測驗 `2` 的 `sex32`，用以改寫 [解讀計算機編碼](https://hackmd.io/@sysprog/rylUqXLsm) 提及的常數時間 `abs` 實作 (輸入是 32 位元整數)，程式碼如下:

static inline int abs_with_sex(int x) {
    return (x ^ sex32(x)) OP2 sex32(x);
}

作答區:

`OP2` = ?
* `(a)` +
* `(b)` -
* `(c)` |
* `(d)` &

---