2019q3 第 3 週測驗題 (上)

目的: 檢驗學員對

$O(1)$ 的認知

---

測驗 1

考慮深度學習領域中，使用激勵函數 ReLU:

$$ReLU(x)=\{\begin{array}{ll}x& \text{if }x\ge 0\\ 0& \text{if }x<0\end{array}$$
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

延伸題目:

1. 解釋上述 ReLU 程式碼運作原理和應用場域 (歡迎寫篇深度學習的科普文章)，並寫出另一個常數時間的實作;
2. 研讀 CMSIS-NN: Efficient Neural Network Kernels for Arm Cortex-M CPUs，在 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，進行加速 ReLU 的實驗;

---

測驗 2

在 8 位元 Motorola 6809 處理器上，有道指令叫做 SEX，寓意是 "Sign EXtend"

Motorola 68000 (68K) 系列處理器，還有道指令名為 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

延伸問題:

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

---

測驗 3

延伸測驗 2 的 sex32，用以改寫 解讀計算機編碼 提及的常數時間 abs 實作 (輸入是 32 位元整數)，程式碼如下:

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

作答區:

OP2 = ?

• (a) +
• (b) -
• (c) |
• (d) &

---