# 2019q3 Homework3 (quiz3)
contributed by < `kaeteyaruyo` >
## 測驗 `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;
}
```
請補完。
:::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 的實驗;
:::
### 解題
```cpp
// 當輸入 x 大於等於 0 時，回傳 x，否則回傳 0
float ReLU(float x) {
// 宣告一個 union，由兩個 field 組成
// 一個型態為 float，用以儲存原本的資料
// 一個型態為 int，用以進行位移運算
// 由於 union 中的所有欄位共用同一份記憶體
// 且 float 和 int32_t 都佔四個 byte
// 因此對 i 操作時等同於在變更 f 的值
union {
float f;
int32_t i;
} out = {.f = x}; // 將資料存入 union 當中
// 由於 int32_t 是有號數，因此位移時是採用算數位移（帶號）
// 將此數向右位移31次，會使 4 個 byte 被 sign 值填滿
// （若非負則為 0，否則為 1）
// 將其反相後，即成為 & 運算的遮罩
// 以此遮罩與原本的資料做 & 運算，若非負則內容不變
// 否則會全部變成 0
out.i = out.i & ~(out.i >> 31);
// 將處理完的結果以 float 的型態回傳
return out.f;
}
```
### 延伸問題
1. 解釋上述 ReLU 程式碼運作原理和應用場域，並寫出另一個常數時間的實作
運作原理如解題中的註解所示。
線性整流函數(Rectified Linear Unit, ReLU)，是近代機器學習領域當中，在訓練深度神經網路時最常被使用的激勵函數(Activation funtion)之一。
所謂的激勵函數，是用來為類神經網路增加非線性特徵的函數。在早期還沒發展出深層網路時，時常被拿來做資料預測的算法為[線性回歸法（Linear Regression）](https://en.wikipedia.org/wiki/Linear_regression)。但就如同他的名字一樣，線性回歸法只能用來預測呈線性分佈的資料，非線性的關係就難以用這樣的函數來描述。
但現實生活中大部分的現象都是非線性的。舉例來說：[美國人的收入與年齡之間的關係呈曲線分佈](https://www.reddit.com/r/dataisbeautiful/comments/1dqsxn/us_total_money_income_distribution_by_age_2012/)，這樣要給定一個年紀的人，去預測他的收入，就顯然難以利用線性回歸。因此，為了解決更複雜的問題，人們就發展出了帶有非線性特徵的 [Logistic Regression](https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8-%E7%B5%B1%E8%A8%88%E5%AD%B8%E7%BF%92-%E7%BE%85%E5%90%89%E6%96%AF%E5%9B%9E%E6%AD%B8-logistic-regression-aff7a830fb5d)，開始可以解決簡單的二分法問題。
然而一個 Logistic Regression 的能力還是有限，[即便是二分法都有無法正確分類的狀況](https://youtu.be/hSXFuypLukA?list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&t=3388)，因此為了得到更 powerful 的函數，數學家嘗試將好幾個 Logistic Regression 給串接起來，形成了初步的類神經網路。
[Sigmoid function](https://en.wikipedia.org/wiki/Sigmoid_function) 作為 Logistic Regression 的激勵函數，是這個算式當中非線性特徵的由來。由於 Logistic Regression 的目的是做分類，其輸出是一個機率值，故其值域會介於 $[0, 1]$ 之間。在[反向傳播算法(Backpropagation)](https://www.youtube.com/watch?v=ibJpTrp5mcE&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&index=12)被發明出來之後，人們發現在計算神經網路中每一層結點的參數時，由於 Sigmoid 會把 $(- \infty , \infty)$ 的輸入映射到 $[0, 1]$ 之間，會造成在反向傳播參數時每一層的數字愈算愈小，到最後幾層的數字全都是 0 的梯度消失(Gradient Vanishing)現象。後來出現的 [Hyperbolic tangent function (tanh)](https://en.wikipedia.org/wiki/Hyperbolic_function)（長高了的 Sigmoid，其值域在 $[-1, 1]$ 之間）也有類似的問題。
因此，在[ Yoshua Bengio 的這篇論文（p.318）](http://proceedings.mlr.press/v15/glorot11a/glorot11a.pdf)當中，他提到了以 ReLU 取代其它激勵函數的好處：
> The rectifier activation function allows a network to easily obtain sparse representations.
> ......
> Apart from being more biologically plausible, sparsity also leads to mathematical advantages (see previous section).
> ......
> Computations are also cheaper: there is no need for computing the exponential function in activations, and sparsity can be exploited.
簡單統整（包含本篇論文其它頁中的描述）：
* ReLU 較容易使得神經網路的結構變得稀疏，因為算出來參數為負的結點被視為沒有貢獻，因此 output 為 0，相當於是從神經網路中被拿掉了
* ReLU 的行為比較符合生物學當中觀察到的神經活化現象（全有全無律，也就是在刺激不夠大的時候，神經根本不會有反應回饋出現的現象）
* ReLU 的計算量比較小
因此， ReLU 成為現代訓練類神經網路時最常被使用的激勵函數。
另一個常數時間實作為：
```cpp
float ReLU(float x) {
return x < 0 ? 0 : x;
}
```
:::danger
上方程式碼有分支
:notes: jserv
:::
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 倍效能提升。嘗試解釋其原理
第 8 頁中段提到：
> A simple implementation (e.g. in Caffe) loops over all elements and make them 0 if they are negative.Since we mostly use q7_t type data, ReLU can be implemented using a similar concept as SWAR (SIMD within a register).
說明了最簡單的 ReLU 實作法是 loop 過一個 layer，去看每一個結點的 output 是否非負，來決定要回傳原值還是 0。但由於他們通常都用 *q7_t* 這種只有 8 bits 那麼大的資料型態來表示節點 output，因此可以利用這個特點來加速 ReLU loop 過每一個節點的運算過程。作法為（參照論文中附圖）：
```
inA = *__SIMD32(pIn)++
buf = __ROR(in & 0x80808080, 7)
mask = __QSUB(0x00000000, buf)
*__SIMD32(pOut)++ = inA & (~mask)
```
由附圖可知，一個 32 bits 大小的暫存器可以放的下 4 個 8 bits 的 *q7_t* 型態的資料，該晶片每次都取 4 個資料一次放進暫存器中，統一對他們進行 sign extend，再利用 sign extend 的結果作為遮罩進行運算，最後一次返回 4 個 ReLU 後的值。原本沒有運用到這項技術的時候，單獨處理一個數字一樣要做 sign extend 和遮罩處理，但現在同樣一輪指令，一次可以處理四組數字，因此效能上就快了 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 的應用案例，特別是密碼學的應用
:::
### 解題
```cpp
#include <stdint.h>
static inline uint32_t sex32(int32_t x) {
// 因為 union 中的另一個欄位有 8 byte 那麼長
// 為了讓填入的內容可以佔滿另一個欄位的所有空間
// 這個型態只能是 64 bits 的長度，因此是 uint64_t
union {
uint64_t w;
struct { uint32_t lo, hi; };
} z = {.w = x};
return z.hi;
}
```
### 延伸問題
1. 解釋程式運作原理，並改寫為適用於 big/little-endian 的程式碼
* 程式碼的運作原理
我找不到 C99 有關整數型態轉換的文件...所以我從 [Microsoft Docs - Conversions from signed integral types](https://docs.microsoft.com/en-US/cpp/c-language/conversions-from-signed-integral-types?view=vs-2019) 當中節錄以下這段：
> long -> unsigned long long: Sign-extend to long long; convert long long to unsigned long long
> (In the Microsoft compiler, int and long are distinct but equivalent types.)
中文為
> long -> unsigned long long: 先將 long 作sign-extend 變成有號的 long long， 然後再把有號的 long long 轉換成無號的 long long
> （在 Microsoft 的編譯器中， long 和 int 被視為是不同但等價的型態）
我猜想 gcc 應該也會是一樣的行為？於是做了以下實驗：
```cpp
#include<stdio.h>
#include<stdint.h>
void print_32(int32_t number){
printf("--------------------------------");
for(int i = 31; i >= 0; --i){
printf("%d", (int)((number >> i) & 1));
}
printf("\n");
}
void print_u64(uint64_t number){
for(int i = 63; i >= 0; --i){
printf("%d", (int)((number >> i) & 1));
}
printf("\n");
}
int main(){
int32_t a;
printf("Enter a numner: ");
scanf("%d", &a);
uint64_t b = a;
printf("%d =\n", a);
print_32(a);
print_u64(b);
return 0;
}
```
其輸出為
```shell
$ ./a.out
Enter a numner: 2742804
2742804 =
--------------------------------00000000001010011101101000010100
0000000000000000000000000000000000000000001010011101101000010100
$ ./a.out
Enter a numner: -2421531
-2421531 =
--------------------------------11111111110110110000110011100101
1111111111111111111111111111111111111111110110110000110011100101
$ ./a.out
Enter a numner: 0
0 =
--------------------------------00000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
$ ./a.out
Enter a numner: -1
-1 =
--------------------------------11111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
```
可以確定 gcc 在做型態轉換上也會有一樣的行為。因此我們可以知道，當 `int32_t` 在被轉換為 `uint64_t` 時，將會由 MSB 填滿多出來的 32 位數，相當是在多出來的 32 bit 當中儲存了 sign extension 的結果。
又因為 union 中的所有成員共享同一個記憶體，因此 lo / hi 將會個別佔據 w 的前後 32 bit （這裡的「前」是指記憶體位址較低的地方，「後」則是記憶體位址較高的地方）。我們只需要知道我們的記憶體是採用 Big-endian 還是 Little-endian，來決定要拿取 hi 還是 lo 即可。
由於 Little-endian 的架構下，接近 MSB 側的資料會儲存在記憶體位址較高的地方，因此應該拿取 hi；但如果是 Big-endian 的話，接近 MSB 側的資料會存在位址較低的地方，所以必須拿取 lo。
* 改寫為適用於 big/little-endian 的程式碼
```cpp
#include <stdint.h>
static inline uint32_t sex32(int32_t x) {
union {
uint64_t w;
struct { uint32_t lo, hi; };
} z = {.w = x};
return -!!(z.hi & z.lo);
}
```
由於 big/little-endian 勢必會把資料存在顛倒的兩個地方，為了要通用在兩種不同的位元組順序下，必須要同時利用到 hi 跟 lo 兩個成員的內容。
首先我們將 hi 跟 lo 做 and 運算，如果 x 為正數，則 and 過後的結果會是 0 （因為 hi 或 lo 其中一人會是 0）；如果 x 是負數，則結果會是 x （因為 hi 或 lo 其中一人會是 x，另一人則是 -1）。也就是：
$$
z.hi \cdot z.lo =
\begin{cases}
0&, x \geq 0\\
x&, x < 0
\end{cases}
$$
接下來對這樣的數字做兩次邏輯 not，由於在 C 語言中，非 0 者為 true，且 true 的值為 1；而 0 則為 false， false 的值也為 0。所以對一個數字做兩次邏輯 not，就會得到這個數字對應的邏輯值（1 或 0）。也就是：
$$
\neg \neg (z.hi \cdot z.lo) =
\begin{cases}
0&, x \geq 0\\
1&, x < 0
\end{cases}
$$
此時非負數已經可以回傳正確的答案，但負數應該要回傳 -1 而非 1，因此我們將結果加上負號，由於 -0 = 0，因此不會影響到非負數的結果。所以：
$$
-(\neg \neg (z.hi \cdot z.lo)) =
\begin{cases}
0&, x \geq 0\\
-1&, x < 0
\end{cases}
$$
因此，此版本可以通用在不同的位元組順序下。
:::info
為什麼不直接使用 `return x >> 31;` 就好呢？
:::
:::warning
注意 portability，不是每個處理器指令集架構都有算術及邏輯 shift，而且行為多少有出入，可比較 Intel 與 Arm 架構
:notes: jserv
:::
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)` &
### 解題
```cpp
static inline int abs_with_sex(int x) {
return (x ^ sex32(x)) - sex32(x);
}
```
XOR 運算規則如下表：
|x|y|x ^ y|equivalent to|
|-|-|-|-|
|0|0|0|x|
|1|0|1|x|
|||||
|0|1|1|~x|
|1|1|0|~x|
因為 sex(x) 的結果，要嘛是 0 (`0x0000`)，要嘛是 -1 (`0xffff`)，這兩種數值作為 XOR 運算的遮罩時，分別有保留原資料與將原資料反相的效果。
絕對值函數的功能是「在資料非負時回傳原資料，否則回傳其負值」，因此我們便可以利用 XOR 與這個遮罩的特點，得出以下算式
$$
\begin{split}
x
&= x + 0 \\
&= (x \oplus 0) - 0 \\
-x
&= \sim x + 1 \\
&= (x \oplus -1) - (-1)
\end{split}
$$
由此可知，該運算子為減號`-`
## 測驗 `4`
延伸 [C 語言: goto 和流程控制](https://hackmd.io/s/B1e2AUZeM)，考慮以下 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 實作程式碼: (`coroutine.c`)
```cpp
/*
* Stackless coroutines.
* This is an async/await implementation for C based on Duff's device.
*
* Features:
* 1. the async state is caller-saved rather than callee-saved.
* 2. Subroutines can have persistent state that is not just static state,
* because each async subroutine accepts its own struct it uses as a
* parameter, and the async state is stored there.
* 3. Because of the more flexible state, async subroutines can be nested
* in tree-like fashion which permits fork/join concurrency patterns.
*/
/* event status */
typedef enum ASYNC_EVT { ASYNC_INIT = 0, ASYNC_DONE = -1 } async;
/* Declare the async state */
#define async_state unsigned int _async_kcont
struct async { async_state; };
/* Mark the start of an async subroutine */
#define async_begin(k) \
XXX1 \
XXX2
/* Mark the end of a generator thread */
#define async_end \
default: \
return ASYNC_DONE; \
}
/* Wait until the condition succeeds */
#define await(cond) await_while(!(cond))
/* Wait while the condition succeeds */
#define await_while(cond) \
case __LINE__: \
if (cond) return __LINE__ \
/* Initialize a new async computation */
#define async_init(state) (state)->_async_kcont = ASYNC_INIT
/* Check if async subroutine is done */
#define async_done(state) (state)->_async_kcont == ASYNC_DONE
/* Resume a running async computation and check for completion */
#define async_call(f, state) \
(async_done(state) || ASYNC_DONE == ((state)->_async_kcont = (f)(state)))
struct async_sem { unsigned int count; };
/**
* Initialize a semaphore
*
* This macro initializes a semaphore with a value for the
* counter. Internally, the semaphores use an "unsigned int" to
* represent the counter, and therefore the "count" argument should be
* within range of an unsigned int.
*
* \param s A pointer to the object representing the semaphore.
* \param c (unsigned int) The initial count of the semaphore.
*/
#define init_sem(s, c) (s)->count = c
/**
* Wait for a semaphore
*
* This macro carries out the "wait" operation on the semaphore. The
* wait operation causes the protothread to block while the counter is
* zero. When the counter reaches a value larger than zero, the
* protothread will continue.
*
* \param s A pointer to the object representing the semaphore.
*/
#define await_sem(s) \
do { \
await((s)->count > 0); \
XXX3; \
} while (0)
/**
* Signal a semaphore
*
* This macro carries out the "signal" operation on the semaphore. The
* signal operation increments the counter inside the semaphore, which
* eventually will cause waiting protothreads to continue executing.
*
* \param s A pointer to the object representing the semaphore.
*/
#define signal_sem(s) XXX4
/* Use case */
#include <stdio.h>
#include <unistd.h>
#define NUM_ITEMS 32
#define BUFSIZE 8
static int buffer[BUFSIZE];
static int bufptr;
static void add_to_buffer(int item) {
printf("Item %d added to buffer at place %d\n", item, bufptr);
buffer[bufptr] = item;
bufptr = (bufptr + 1) % BUFSIZE;
}
static int get_from_buffer(void) {
int item = buffer[bufptr];
printf("Item %d retrieved from buffer at place %d\n", item, bufptr);
bufptr = (bufptr + 1) % BUFSIZE;
return item;
}
static int produce_item(void) {
static int item = 0;
printf("Item %d produced\n", item);
return item++;
}
static void consume_item(int item) {
printf("Item %d consumed\n", item);
}
static struct async_sem full, empty;
static async producer(struct async *pt) {
static int produced;
async_begin(pt);
for (produced = 0; produced < NUM_ITEMS; ++produced) {
await_sem(&full);
add_to_buffer(produce_item());
signal_sem(&empty);
}
async_end;
}
static async consumer(struct async *pt) {
static int consumed;
async_begin(pt);
for (consumed = 0; consumed < NUM_ITEMS; ++consumed) {
await_sem(&empty);
consume_item(get_from_buffer());
signal_sem(&full);
}
async_end;
}
static async driver_thread(struct async *pt) {
static struct async cr_producer, cr_consumer;
async_begin(pt);
init_sem(&empty, 0);
init_sem(&full, BUFSIZE);
async_init(&cr_producer);
async_init(&cr_consumer);
await(producer(&cr_producer) & consumer(&cr_consumer));
async_end;
}
int main(void) {
struct async driver_pt;
async_init(&driver_pt);
while (!async_call(driver_thread, &driver_pt)) {
usleep(10); /* why? */
}
return 0;
}
```
這段程式碼是經典的[生產者——消費者問題](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem)，預期執行輸出為:
```shell
Item 0 produced
Item 0 added to buffer at place 0
Item 1 produced
Item 1 added to buffer at place 1
Item 2 produced
Item 2 added to buffer at place 2
Item 3 produced
Item 3 added to buffer at place 3
Item 4 produced
Item 4 added to buffer at place 4
Item 5 produced
Item 5 added to buffer at place 5
Item 6 produced
Item 6 added to buffer at place 6
Item 7 produced
Item 7 added to buffer at place 7
Item 0 retrieved from buffer at place 0
Item 0 consumed
Item 1 retrieved from buffer at place 1
Item 1 consumed
Item 2 retrieved from buffer at place 2
Item 2 consumed
Item 3 retrieved from buffer at place 3
Item 3 consumed
Item 4 retrieved from buffer at place 4
Item 4 consumed
Item 5 retrieved from buffer at place 5
Item 5 consumed
Item 6 retrieved from buffer at place 6
Item 6 consumed
Item 7 retrieved from buffer at place 7
Item 7 consumed
```
請補完程式碼
:::success
延伸問題:
1. 解釋上述程式運作原理，特別是和 [Duff's device](https://en.wikipedia.org/wiki/Duff%27s_device) 的關聯;
2. 參照 [ProtoThread](http://dunkels.com/adam/pt/) 程式碼，比較上述差異，需要設計實驗，分析兩者在切換 coroutine 的執行時間和記憶體開銷成本
3. 整合 timeout 機制，允許 callback function 在指定的時間執行，如 [TimerCallback callback function](https://docs.microsoft.com/en-us/previous-versions/windows/desktop/legacy/ms686790(v=vs.85))
:::
### 解題
```cpp
// 仿 Duff's device 的作法，配合 await 和 async_end 完成一個同步區段
#define async_begin(k) \
switch ((k)->_async_kcont) { \
case 0:
...
// 對信號做 wait，即對信號的值減 1。不可將 decrement 與 s 括在一起，這樣會更改到錯誤的位址
#define await_sem(s) \
do { \
await((s)->count > 0); \
--(s)->count; \
} while (0)
...
// 對信號做 signal，即對信號的值加 1
#define signal_sem(s) ++(s)->count
```
:::info
* 為什麼 `await_sem` 的部份不要直接執行就好，必須要用一個必定只會執行一次的 do-while 包起來呢？ => ==避免 [dangling else](https://en.wikipedia.org/wiki/Dangling_else)==
* 程式碼開始處的定義，為什麼要給 enum 和 struct 取一樣的名字呢？請問這樣為什麼不會造成命名衝突呢？
```cpp
typedef enum ASYNC_EVT { ASYNC_INIT = 0, ASYNC_DONE = -1 } async;
/* Declare the async state */
#define async_state unsigned int _async_kcont
struct async { async_state; };
```
* 那些 async function 的回傳值為 `async` 型態，在 debugger 下可以看到，指的是 enum 的那個 `async`。但明明這些 function 的回傳值是用來 assign 給 `async_state` 的，那為何不是宣告為 `unsigned int` 呢？以及為什麼可以讓回傳值的型態是一個 enum ？
:::
:::warning
請詳閱 C 語言規格對於 identifier 的描述，C 語言編譯器可輕易區分看似同樣名稱的 enum 和 struct，但在 C++ 編譯器卻可能混淆。enum 型態只是個整數
:notes: jserv
:::
### 延伸問題
1. 解釋上述程式運作原理，特別是和 [Duff's device](https://en.wikipedia.org/wiki/Duff%27s_device) 的關聯
為了更方便 vscode 的 debugger 追蹤程式碼執行的順序，我把幾個主要的程式碼內部由 `define` 簡寫的部份展開了（雖然編譯之後同樣可以執行，輸出結果也一樣，但是我想其實展開之後是會影響程式碼的正確性的，尤其是有關`__LINE__`的使用的部份。僅是為了方便理解才做展開，實際應用上應當使用原本的程式碼），附上展開後的說明如下：
```cpp=
int main(void) {
struct async driver_pt;
// async_init(&driver_pt);
driver_pt._async_kcont = ASYNC_INIT;
// while (!async_call(driver_thread, &driver_pt)) {
// while (！(async_done(state) || ASYNC_DONE == ((state)->_async_kcont = (f)(state))))
while (1) {
if(driver_pt._async_kcont != ASYNC_DONE){
driver_pt._async_kcont = driver_thread(&driver_pt);
if(ASYNC_DONE == driver_pt._async_kcont) break;
}
else {
break;
}
usleep(10);
}
return 0;
}
```
* `struct async` 是一個定義 `async` 狀態的結構。任何一個需要同步執行的函式，都應該要有一個這樣的結構來管理該函式的執行狀態。此物件應當宣告在呼叫該函式的 scope 下，並將該函式的回傳值儲存在這裏面。裡頭的物件 `async_state` 總共只可能有三種值:
* `ASYNC_INIT = 0`: 代表這個需要同步執行的函式第一次被呼叫
* `__LINE__`： 在 gcc 裡面事先定義好的一個變數，代表執行當下所在的行數，因為是行數，所以必定是一個非負值，且不太可能超過 `unsigned int` 可代表的範圍。以這個任意的非負值代表此函式還沒執行完成
* `ASYNC_DONE = -1`： 代表這個函式執行完了
* 第 3 行 `async_init` 的呼叫，實際上就是將上述 `struct async` 的狀態初始化為 `ASYNC_INIT`，也就是第 4 行，其對象為 `driver_thread` 的 async state
* 第 6 行原本的 `async_call` 真的非常簡潔（嘆為觀止，真的很厲害 XD），展開如下：
* `async_call` 其實是一行條件運算式（如第七行所示）。由於 C 語言當中，`||` 運算子會先執行左邊的 expression，若結果為 `false`，才執行右邊的 expression （若為 `true` 就不執行了），又這個 `while` 迴圈只在 `async_call` 回傳 0 （也就是 `||` 的兩個expression 都回傳 0）的情況下才會繼續執行，於是可以根據語意將第 6 行拆解成第 8 行到第 15 行
* 拆解完後可以清楚知道這個 `while` 迴圈做了什麼事：
* 首先檢查欲呼叫的函式是不是其實已經執行完畢，如果是的話直接跳出迴圈
* 如果不是的話，則執行這個函式，並且更新其狀態
* 如果更新完之後發現函式已經執行完畢，那麼也跳出迴圈
* 否則暫停 10 毫秒，然後重新執行上述步驟
* 第 16 行之所以要暫停 10 毫秒，是因為可以從上述步驟看到，這是一個 [busy waiting](https://en.wikipedia.org/wiki/Busy_waiting) 實作，為了避免過度頻繁的檢查耗費 CPU 資源、或是避免短時間重複呼叫會造成 race condition，所以必須間隔一段時間才做下一次的 `async_call` (因為 `usleep` 會使 progress suspend，這個動作會讓出 CPU time 給其它人)
:::info
以上是我關於 `usleep(10)` 的作用的推論，不知道是否正確Q
:::
:::danger
為何不做實驗，分析 `usleep` 對 CPU 佔用的衝擊呢？另外對照看 [sched_yield](http://man7.org/linux/man-pages/man2/sched_yield.2.html)
:notes: jserv
:::
```cpp=
static struct async_sem full, empty;
static async driver_thread(struct async *pt) {
static struct async cr_producer, cr_consumer;
// async_begin(pt);
switch ((pt)->_async_kcont) {
case 0: // It should be `ASYNC_INIT`
// init_sem(&empty, 0);
empty.count = 0;
// init_sem(&full, BUFSIZE);
full.count = BUFSIZE;
// async_init(&cr_producer);
cr_producer._async_kcont = 0;
// async_init(&cr_consumer);
cr_consumer._async_kcont = 0;
// await(producer(&cr_producer) & consumer(&cr_consumer));
case __LINE__:
if (！(producer(&cr_producer) & consumer(&cr_consumer)))
return __LINE__;
// async_end;
default:
return ASYNC_DONE;
}
}
```
* 第 1 行的 `struct async_sem` 是生產者-消費者問題中用來同步兩者行為的信號燈
* `driver_thread` 是這個程式中的 async function （就是 JavaScript 中的那個 async function）。 [Async function](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Statements/async_function) 作為 JavaScript 當中的同步機制 [Promise](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/Promise) 的語法糖，其運作機制簡單舉例如下：
```javascript
// 宣告一個 async function，在這裡面的程式碼保證會依序執行
async function func(url){
// 在 async function 裡面 await 一個 Promise 物件
// (fetch 的回傳值會是一個 Promise 物件) resolve，
// 並取得他的返回值。
// 就是在這一行，在 Promise 依然 pending 時，不會進到下一行
let data = await fetch(url);
return data;
}
```
* `driver_thread` 當中的 `await`，就是在模擬 JavaScript 中的那個 `await` 的行為。在 await 的對象還沒執行完之前，程式必須卡在那裡。以 `driver_thread` 來說，他 await 的對象是 `producer(&cr_producer) & consumer(&cr_consumer)`
* 這個程式巧妙的地方在於，使用了 `switch` [fallthrough](https://en.wikipedia.org/wiki/Switch_statement#Fallthrough) 的特性控制執行順序：
* 第一次被呼叫的 async function 才會進行初始化（被當作參數傳進來的他的 async state 必定是 `ASYNC_INIT`，所以其實第 8 行應該寫 `case ASYNC_INIT:`）
* 因為 `switch` 的 fallthrough，接著會直接進行 await，如果沒等到 await 的對象完成，就回傳該行行數作為 async 程式未結束的狀態，然後跳出此程式
* 由於在 `main` 當中會記錄這個 async function 的狀態，如果 async function 是在還沒結束的情況下跳出的，則下一次進來就會掉到 `case __LINE__：` 裡頭，繼續 await（所以其實這個程式不能分拆，因為一旦拆了 `__LINE__` 就會變成在不同行）
* 直到 await 的對象回傳，才掉入 `default`，回傳完成的 state
* 第 9 行與第 11 行是在做生產者-消費者問題的 buffer （以 semephore 實作）的初始化
* 由於生產者 / 消費者的函式也分別是 async function，所以他們也需要自己的 async state。第 14 行與第 16 行分別是在初始化他們的 async state
```cpp=
static async producer(struct async *pt) {
static int produced;
// async_begin(pt);
switch ((pt)->_async_kcont) {
case 0:
for (produced = 0; produced < NUM_ITEMS; ++produced) {
// await_sem(&full);
do {
case __LINE__:
if (full.count <= 0)
return __LINE__;
--full.count;
} while (0);
add_to_buffer(produce_item());
// signal_sem(&empty);
++empty.count;
}
// async_end;
default:
return ASYNC_DONE;
}
}
// Consumer 行為類似，不贅述
```
* 第 2 行的 `static int`，是用來跨呼叫計數用的（不使用 static 關鍵字的話， local variable 的生存週期無法持續到出函式之後）
* 這段程式碼應用了 Duff's device 的技巧： 鑲嵌的迴圈和 switch 結構。在 Duff's device 中，這樣的結構是為了用來處理 loop unroll 後無法被 unroll 的數量除盡的剩下來的指令。而在這裡則是用來讓因為 await 未完成而跳出的程式回來之後依然可以從迴圈的中斷處繼續執行用的
* `producer` 第一次被呼叫之後立刻進入 `for` 迴圈，由於 `for` 迴圈與 `switch` 鑲嵌，因此就算 `await_sem` 失敗， `producer` 退出之後，下次呼叫依然可以從上一次中斷的地方繼續執行；如果 `await_sem` 成功，則 `producer` 進行生產，然後再度回到迴圈開頭，直至因為 buffer 佔滿而離開。迴圈成功結束後脫離，才回傳完成的狀態。 `consumer` 也是一樣的行為。
* 但是因為在 `driver_thread` 中， await 的對象為 `producer(&cr_producer) & consumer(&cr_consumer)`，由於沒有經過 `async_call` 呼叫，所以狀態並不會被暫存下來，所以沒辦法觀察到生產者和消費者進行 async / await 的行為，程式會在這兩個程式都 return `__LINE__` （非 0 數）之後就結束
* 若將 `driver_thread` 中的 await 處改為 ` await(async_call(producer, &cr_producer) & async_call(consumer, &cr_consumer));`，則可以觀察到完整的生產者-消費者行為
2. 參照 [ProtoThread](http://dunkels.com/adam/pt/) 程式碼，比較上述差異，需要設計實驗，分析兩者在切換 coroutine 的執行時間和記憶體開銷成本
待補充
3. 整合 timeout 機制，允許 callback function 在指定的時間執行，如 [TimerCallback callback function](https://docs.microsoft.com/en-us/previous-versions/windows/desktop/legacy/ms686790(v=vs.85))
不是很理解要求是什麼 @@...（Callback function 是指？）
:::danger
請閱讀上面的連結，去推敲 callback function 的作用
:notes: jserv
:::
## 參考資料
### 測驗 1
* [The Disadvantages of Linear Regression - Sciencing](https://sciencing.com/disadvantages-linear-regression-8562780.html)
* [[Day 32] Deep learning -- activation function - iT邦幫忙](https://ithelp.ithome.com.tw/articles/10189085)
* [Linear Regression - Wikipedia](https://en.wikipedia.org/wiki/Linear_regression)
* [U.S. Total Money Income Distribution by Age, 2012 - Reddit](https://www.reddit.com/r/dataisbeautiful/comments/1dqsxn/us_total_money_income_distribution_by_age_2012/)
* [機器/統計學習: 羅吉斯回歸(Logistic regression) - Medium](https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8-%E7%B5%B1%E8%A8%88%E5%AD%B8%E7%BF%92-%E7%BE%85%E5%90%89%E6%96%AF%E5%9B%9E%E6%AD%B8-logistic-regression-aff7a830fb5d)
* [Machine Learning (Hung-yi Lee, NTU) - YouTube](https://www.youtube.com/watch?v=CXgbekl66jc&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49)
* [Sigmoid function - Wikipedia](https://en.wikipedia.org/wiki/Sigmoid_function)
* [Hyperbolic function - Wikipedia](https://en.wikipedia.org/wiki/Hyperbolic_function)
* [Glorot, Xavier, Antoine Bordes, and Yoshua Bengio. "Deep sparse rectifier neural networks." Proceedings of the fourteenth international conference on artificial intelligence and statistics. 2011.](http://proceedings.mlr.press/v15/glorot11a/glorot11a.pdf)
### 測驗 2
* [Conversions from signed integral types - Microsoft Docs](https://docs.microsoft.com/en-US/cpp/c-language/conversions-from-signed-integral-types?view=vs-2019)
### 測驗 4
* [Busy waiting - Wikipedia](https://en.wikipedia.org/wiki/Busy_waiting)
* [Async function - MDN](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Statements/async_function)
* [Promise - MDN](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/Promise)
* [Switch statement - Wikipedia](https://en.wikipedia.org/wiki/Switch_statement#Fallthrough)
Sign in with Wallet
Connect another wallet