2019q3 Homework3 (quiz3)

contributed by < uccuser159 >

注意細節！第一行有明確的格式規範

jserv

測驗 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;
}

思考

• 在 union 中，全部的共用體成員共用一個空間，而且同一時間僅僅能儲存當中一個成員變量的值。

1. union 中能夠定義多個成員，且 union 的大小由最大的成員的大小決定。
2. union 成員共享同一塊大小的儲存空間， 一次僅僅能使用當中的一個成員。
3. 對某一個成員賦值 當指定數值到特定的成員時，由於他們共享一塊儲存空間，會覆蓋其它成員的值。

避免用彆扭的詞彙書寫，傳統台灣科技刊物不用「賦值」這詞來表示 assignment，而該用簡單明確的話語來陳述。請尊重台灣資訊科技前輩的付出，儘量用傳統術語和書寫方式。

jserv

從第一手資料找出 union 的描述，翻閱 C 語言規格書，摘錄並解析

jserv

• 分析 out.i = out.i OP1 ~(out.i >> V2) ：

  • 由於 ReLU 函式要判斷輸入數值的正負，所以~(out.i >> V2)要取參數 x 的 sign bit，可以得到 V2 = 31。
  • 若
    $x<0$ ，則~(out.i >> 31)得到的結果為111…11(32bits)；若
    $x>=0$ ，則~(out.i >> 31)得到的結果為000…00(32bits)
  • 與參數做 AND 運算恰好即是 ReLU 函式的定義：
    $x<0$ →
    $ReLU(x)=0$；
    $x>=0$ →
    $ReLU(x)=x$，所以 OP1 填入 &。

• 延伸問題

---

測驗 2

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

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

思考

因為要判別正負號，又 union 能保存不同的數據類型，所以struct{uint32_t lo, hi; }結構的大小(64 bits)要與TYPE w相同，所以TYPE 應為 uint64_t，最後回傳參數 x 做 sign extend 的 w.hi 部分。

• 延伸問題

1.解釋程式運作原理，並改寫為適用於 big/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};
    if(z.hi==0 || z.hi==-1)
        return z.hi;
    else if(z.lo==0 || z.lo==-1)
        return z.lo;
    else
        return;
}

避免執行時期的條件判斷，透過 C preprocessor 改寫為編譯時期處理 endian 議題

jserv

參考資料：Big/Little Endian

測驗 3

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

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

思考

• sex32(x) 的作用為判別正負號，可以作為 mask ：
  • $x<0$ 則 sex32(x)=111…11(32 bits)
  • $x>=0$ 則sex32(x)=000…00(32 bits)

因為 x ^ 1 = ~x 、 x ^ 0 = x ，所以透過 XOR 的特性，當作(x ^ sex32(x))此運算，分為兩種情況：

• $x<0$
  要將一個小於 0 的數做 abs() ，即是將此數取2補數。此時的 sex32(x)=111…11(32 bits) ，且與 x 作 XOR 運算得到 ~x ，sex32(x) 的值又為 -1，所以 abs(x) = ~x - (-1)，OP2 為 -

• $x>=0$
  要將一個大於 0 的數做 abs() ，即是原來的數。此時的 sex32(x)=000..00(32 bits) ，且與 x 作 XOR 運算得到 x ，sex32(x) 的值又為 0，所以 abs(x) = x - 0，OP2 為 -