# quiz2 測驗1 EWMA問題(第2版)
###### tags: `linux2022`
## [測驗 `1`](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-1)

:::success
延伸問題:
3. 研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)，探討其 [Exponentially weighted moving average](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) (EWMA) 實作，以及在 Linux 核心的應用

:::

`#define DECLARE_EWMA(name, _precision, _weight_rcp)`
其中3個輸入參數定義
* `name`: 表示整個 macro 定義出來的一組 macro 以及 struct 的名稱。
* `_percision`: 表示用多少個 bits 來表示內部儲存的小數部分。
* `_weight_rcp`: 表示權重 $\alpha$ 的倒數, $\alpha=1 / weight\_rcp$。

## EWMA 數學式推導
$S_t = \begin{cases}
Y_0, & t = 0 \\
\alpha Y_t + (1 - \alpha) \cdot S_{t-1}, & t > 0
\end{cases}$

$\begin{aligned}
S[N]&=\alpha Y[N]+(1-\alpha)S[N-1]\\
&=\alpha \{Y[N]+ ({1\over\alpha} - 1)S[N - 1]\}\\
&=\alpha\{Y[N]+{1\over\alpha}S[N-1]-S[N-1]\}
\end{aligned}$

在 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 中對應的程式段落為

static inline void ewma_##name##_add(struct ewma_##name *e,	\
                     unsigned long val)		\
{
    WRITE_ONCE(e->internal, internal ?			\
        (((internal << weight_rcp) - internal) +	\
            (val << precision)) >> weight_rcp :	\
        (val << precision));				\
}    

裡面的

WRITE_ONCE(e->internal, internal ?			\
    (((internal << weight_rcp) - internal) +	\
        (val << precision)) >> weight_rcp :	\
    (val << precision));

即為對應的EWMA數學式運算
$\begin{aligned}
S[N]=\alpha\{Y[N]+{1\over\alpha}S[N-1]-S[N-1]\}
\end{aligned}$

其中

internal ?
(((internal << weight_rcp) - internal) + (val << precision)) >> weight_rcp : (val << precision));

為[條件運算子](http://kaiching.org/pydoing/c/c-operator.html)
> `expr1?expr2:expr3`
> 運算式 **expr1 為真** ==>運算結果會是**運算式 expr2**
> 運算式 **expr1 為假** ==>運算結果則是**運算式 expr3**

對應到我們的程式相當於

internal ?
expr2:expr3

internal有值==> 做運算式expr2
internal為0==> 做運算式expr3

:::info
因此相當於
`WRITE_ONCE(e->internal,第二個變數);`

**第二個變數**根據**internal值條件**，切換代入

if(internal) //internal有值時
{   第二個變數代入值為
    (((internal << weight_rcp) - internal) + (val << precision)) >> weight_rcp;
    
}else{
    第二個變數代入值為
    (val << precision);
}

`(((internal << weight_rcp) - internal) + (val << precision)) >> weight_rcp;`
和
$\begin{aligned}
S[N]=\alpha\{Y[N]+{1\over\alpha}S[N-1]-S[N-1]\}
\end{aligned}$
對比

1.

((internal << weight_rcp) - internal)

為$\begin{aligned}
{1\over\alpha}S[N-1]-S[N-1]
\end{aligned}$
因為$\alpha$小於1，所以**乘$1\over\alpha$，相當於左移<< weight_rcp**

2.

(val << precision)

為$\begin{aligned}
Y[N]
\end{aligned}$

3.

>> weight_rcp

為乘 $\alpha$ 倍
因為$\alpha$小於1，所以**乘$\alpha$，相當於右移>> weight_rcp**
:::
## [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 其他內容
引用 [meyr 同學](https://hackmd.io/@meyr543/B1lLmZV-5#3Exponentially-weighted-moving-average-EWMA) 介紹
> #### 名詞解釋
>
>
> | Funciton Name | Description |
> | ---------------------- | -------------------------- |
> | **BUILD_BUG_ON(cond)** | 停止compile如果cond是true. |
> |**BUILD_BUG_ON_NOT_POWER_OF_2(var)** | 停止compile如果var不是2的次方。
> |**__builtin_constant_p(var)** | 判斷var是否為常數，返回1為常數，返回0則否。
> |**READ_ONCE/WRITE_ONCE** | 參考[這裡](/YcjVoBx5R_mnKxX9-H6pEg#READ_ONCEWRITE_ONCE)</br>就是volatile的封裝。當需要用的時候把變數轉換成volatile型態，編譯器只是保證 2 個 volatile 變數之間讀取不會被亂序。

## READ_ONCE/WRITE_ONCE 介紹
[WRITE_ONCE READ_ONCE 函數的介紹與使用](https://blog.csdn.net/Adrian503/article/details/106921769)
> 為什麼要用READ_ONCE()和WRITE_ONCE()這兩個宏呢？這裡起到關鍵作用的就是volatile ，它主要告訴編譯器：
>
> 1、聲明這個變量很重要，不要把它當成一個普通的變量，做出錯誤的優化。
>
> 2、保證CPU 每次都從內存重新讀取變量的值，而不是用寄存器中暫存的值。
>
> 因為在 多線程/多核 環境中，不會被當前線程修改的變量，可能會被其他的線程修改，從內存讀才可靠。
>
> 還有一部分原因是，這兩個宏可以作為標記，提醒編程人員這裡面是一個多核/多線程共享的變量，必要的時候應該加互斥鎖來保護。

[Linux内核中的READ_ONCE和WRITE_ONCE宏](https://zhuanlan.zhihu.com/p/344256943)

[Linux内核中的READ_ONCE和WRITE_ONCE宏2](https://blog.csdn.net/Roland_Sun/article/details/107365134)

## EWMA 實作，在 Linux 核心的應用
依照 `DECLARE_EWMA()` 定義
> `#define DECLARE_EWMA(name, _precision, _weight_rcp)`
> 其中3個輸入參數定義
> * `name`: 表示整個 macro 定義出來的一組 macro 以及 struct 的名稱。
> * `_percision`: 表示用多少個 bits 來表示內部儲存的小數部分。
> * `_weight_rcp`: 表示權重 $\alpha$ 的倒數, $\alpha=1 / weight\_rcp$。

[drivers/net/wireless/mediatek/mt76/mt76x02_mac.h](https://github.com/torvalds/linux/blob/dbe69e43372212527abf48609aba7fc39a6daa27/drivers/net/wireless/mediatek/mt76/mt76x02_mac.h)

DECLARE_EWMA(pktlen, 8, 8);

struct mt76x02_sta {
	struct mt76_wcid wcid; /* must be first */

	struct mt76x02_vif *vif;
	struct mt76x02_tx_status status;
	int n_frames;

	struct ewma_pktlen pktlen;
};

`DECLARE_EWMA(pktlen, 8, 8);` 代表
* `name`: pktlen
* `_percision`: 表示**用 8 bits** 來表示內部儲存的**小數部分。**
* `_weight_rcp`: 表示權重 $\alpha$ 的倒數, $\alpha=1 / weight\_rcp=1 / 8$。

## 參考資料
* [meyr 同學](https://hackmd.io/@meyr543/B1lLmZV-5#3Exponentially-weighted-moving-average-EWMA)
* [Exponential Moving Average](https://tttapa.github.io/Pages/Mathematics/Systems-and-Control-Theory/Digital-filters/Exponential%20Moving%20Average/Exponential-Moving-Average.html)
* [Frequency Response of the Running Average Filter](https://ptolemy.berkeley.edu/eecs20/week12/freqResponseRA.html)