# 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`) 是個常數時間的實作: ```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; } ``` 請補完。 ==作答區== `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: ```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; } ``` ==作答區== `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 位元整數),程式碼如下: ```cpp static inline int abs_with_sex(int x) { return (x ^ sex32(x)) OP2 sex32(x); } ``` 作答區: `OP2` = ? * `(a)` + * `(b)` - * `(c)` | * `(d)` & ---