# 核心定點數機制與 EWMA
> 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)
本文探討 EWMA ([Exponential Weighted Moving Average](https://en.wikipedia.org/wiki/Moving_average)，指數加權移動平均) 如何追蹤動態數值，並分析 Linux 採用整數位元移位逼近浮點衰減的精妙手法。
相較於 Kahan summation 著重不丟失誤差的哲學，EWMA 採取截然相反的立場：以固定比例主動折扣歷史資料，讓越久遠的訊號影響力越弱。如此刻意遺忘的設計，是針對即時監控場景，近期趨勢遠比歷史精確性重要的明確選擇。
## EWMA 定義與三個關鍵特質
Linux 核心廣泛以 EWMA 追蹤 Wi-Fi 訊號強度、區塊 I/O 延遲與網路吞吐量等動態指標。EWMA 以遞迴方式計算加權均值，對最新取樣給予較高權重，讓歷史資料逐步衰減：
$$
S_n = \alpha \cdot x_n + (1 - \alpha) \cdot S_{n-1}, \quad 0 < \alpha \leq 1
$$
$\alpha$ 越小，均值對新資料反應越遲緩(長記憶)；$\alpha$ 越大，均值越迅速追蹤最新取樣 (短記憶)。
EWMA 的實用性建立在三個特質上：其一，僅需保存一個狀態值 $S_n$，不必保留完整的歷史序列，記憶體需求為常數；其二，以 $(1 - \alpha)$ 固定比例折扣過去，越久遠的歷史影響越弱，這種「刻意遺忘舊資料」的設計，使它在長期運行中自然抑制老舊噪聲；其三，藉由單一參數 $\alpha$ 在「噪聲抑制」($\alpha$ 小，平滑穩定) 與「即時響應」($\alpha$ 大，靈敏追蹤) 之間提供連續的設計空間，不需修改演算法結構即可適應不同場景。這些特質使 EWMA 成為嵌入式系統、作業系統與網路裝置中追蹤動態數值的常用工具。
上述公式若直接以浮點數實作，在核心空間並不可行：每次 context switch 需保存並恢復 FPU 暫存器，延遲顯著，因此核心原則上禁止在中斷上下文與核心執行緒中使用浮點數。
## 定點數化：將分數乘法轉為整數移位
將 $\alpha$ 限制為 $1 / W$($W$ 即 `_weight_rcp`，必須為 2 的冪)，則 $1 - \alpha = (W - 1) / W$。令 $w = \log_2 W$，乘法與除法均可用位元移位替代；核心巨集內部以 `ilog2(_weight_rcp)` 計算 $w$。
同時，將 EWMA 的真實值乘以 $2^p$($p$ 稱為 `_precision`)後存入整數欄位 `internal`，以保留小數部分的精度：
$$
\text{internal} = S \cdot 2^p
$$
每次更新的推導過程：從遞推公式出發，
$$
S_\text{new} = \frac{W - 1}{W} S_\text{old} + \frac{1}{W} x
$$
兩側同乘 $2^p$，換成 `internal` 表示：
$$
\text{internal}_\text{new} = \frac{(W - 1) \cdot \text{internal}_\text{old} + x \cdot 2^p}{W}
$$
因 $W = 2^w$，除以 $W$ 等同右移 $w$ 位：
$$
\text{internal}_\text{new} = \bigl((\text{internal}_\text{old} \ll w) - \text{internal}_\text{old} + (x \ll p)\bigr) \gg w, \quad w = \log_2 W
$$
所有步驟均為整數加法與位元移位，完全不涉及浮點運算。
## Linux 原始碼：`include/linux/ewma.h`
`include/linux/ewma.h` 以巨集的方式提供型別安全的 EWMA 程式碼產生器：
```c
DECLARE_EWMA(name, _precision, _weight_rcp)
```
以 `DECLARE_EWMA(signal, 10, 8)` 為例 (`_precision = 10`，`_weight_rcp = 8`，$w = \mathrm{ilog2}(8) = 3$，衰減因子 $\alpha = 1/8$)，巨集展開後的核心邏輯等效於：
```c
struct ewma_signal {
unsigned long internal; /* stores EWMA × 2^10, i.e., 1024x the actual value */
};
static inline void
ewma_signal_add(struct ewma_signal *e, unsigned long val)
{
unsigned long internal = READ_ONCE(e->internal);
unsigned long w = ilog2(8); /* w = 3; folded to a compile-time constant */
WRITE_ONCE(e->internal,
internal
? (((internal << w) - internal) + (val << 10)) >> w
: (val << 10)); /* first sample: store scaled directly, skip decay */
}
static inline unsigned long
ewma_signal_read(const struct ewma_signal *e)
{
return e->internal >> 10; /* right-shift to restore the actual value */
}
```
`READ_ONCE()` / `WRITE_ONCE()` 底層為 `volatile` 轉型，防止編譯器快取、合併或撕裂對 `internal` 的記憶體存取，確保每次存取都對應一次實際記憶體讀寫；這與練習 C 中阻止代數化簡的問題屬於不同層次：前者約束的是記憶體存取的語意，後者約束的是算術結合律的假設，二者著重不同層面的正確性議題。
## `lib/average.c` 的 `struct ewma`
在 `DECLARE_EWMA` 巨集 (自 Linux v3.11 引入) 成為標準之前，核心以 `lib/average.c` 提供通用的 EWMA 工具函式，以下是其核心介面的重建 (教學版本，以位移量直接作為參數；歷史實作的 `ewma_init()` 接收 2 的冪值並在內部以 `ilog2()` 轉換儲存)：
```c
struct ewma {
unsigned long internal; /* stores EWMA × 2^factor */
unsigned long factor; /* precision shift count, e.g., 10 (scale factor 2^10 = 1024) */
unsigned long weight; /* decay shift count, e.g., 3 (alpha = 1/2^3 = 1/8) */
};
```
```c
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
avg->factor = factor;
avg->weight = weight;
avg->internal = 0;
}
```
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal +
(val << avg->factor)) >> avg->weight)
: (val << avg->factor);
return avg;
}
```
```c
unsigned long ewma_read(const struct ewma *avg)
{
return avg->internal >> avg->factor;
}
```
與 `DECLARE_EWMA` 的對應關係：
| `struct ewma` 欄位 | `DECLARE_EWMA` 參數 | 說明 |
|---|---|---|
| `avg->factor` | `_precision` | 放大位移量，如 10 |
| `avg->weight` | `ilog2(_weight_rcp)` | 衰減位移量，如 3 (對應 `_weight_rcp = 8`) |
舊 API 以執行期欄位儲存位移量，使得 `ewma_add()` 為通用函式，但每次呼叫都需讀取結構體欄位；`DECLARE_EWMA` 將這二個值改為編譯期常數，讓編譯器在展開時直接嵌入常數移位指令，省去執行時期的欄位讀取與間接尋址。
## 精度與衰減速率的工程取捨
- [ ] `_precision`
控制 `internal` 的縮放倍率。精度越高，讀回時的截斷誤差越小，但 `internal` 的數值範圍越大。使用前須確認不溢位：`internal` 的上限估算為 `max_input << _precision`，必須在 `unsigned long` 的表示範圍之內。
- [ ] `_weight_rcp`
控制衰減速率，必須為 2 的冪 (核心以 `BUILD_BUG_ON_NOT_POWER_OF_2` 強制檢查)。`_weight_rcp = 8` 意味著 $\alpha = 1/8$，每次更新僅納入新資料的 $1/8$，保留前次 EWMA 的 $7/8$；值越大衰減越慢(對突發值越不敏感)，值越小衰減越快(追蹤越靈敏)。
實務上，`ath9k` Wi-Fi 驅動程式以 `precision = 10, weight_rcp = 8`($\alpha = 1/8$)追蹤訊號強度；區塊 I/O 延遲追蹤則依量測週期選用不同參數，反映各場景對即時性與穩定性的不同權衡。
## 與 Kahan、Welford 的設計哲學對照
```
演算法 核心策略
────────────────────────────────────────────────
Kahan 追蹤每步被捨去的低位，事後補回
Welford 改用差值遞增，從根本避免大數相消
EWMA 固定比例衰減歷史，刻意遺忘舊資料
```
EWMA 的數值損失是設計使然：以 $(1 - \alpha)$ 折扣過去，資訊有意識地逐輪衰減。這與 Kahan 絲毫不丟失誤差的目標正好相反，卻是它在延遲追蹤、負載均衡等即時監控場景的價值所在：精確的歷史不重要，對近期趨勢的快速感知才是目標。在核心定點數實作中，「以整數移位逼近浮點衰減」的技巧，與 `xtime_nsec` 儲存 fixed-point 分數位、`period_contrib` 留存週期餘量，都是同一精神的體現：在整數的約束下，以合理的近似保留最有價值的資訊。
## PELT 的排程負載追蹤
`DECLARE_EWMA` 在 CPU 排程器的 [PELT](https://docs.kernel.org/scheduler/schedutil.html) (Per-Entity Load Tracking) 機制中以更精細的形式出現。PELT 以固定時間間隔(通常每 1 ms，對應一次 [scheduler tick](https://wiki.linuxfoundation.org/realtime/documentation/howto/tools/ticklesskernel))量測行程或 cgroup 在該週期內的 CPU 佔用比例 $r_n$($0 \le r_n \le 1$)，再以 EWMA 遞迴更新負載估計值 $u_n$：
$$
u_n = k \cdot u_{n-1} + (1 - k) \cdot r_n
$$
此處衰減因子 $k$(扮演一般 EWMA 公式中 $1 - \alpha$ 的角色，即 $\alpha = 1 - k$)由更新週期 $\Delta t$ 與時間常數 $\tau$ 決定：
$$
k = \exp\!\left(-\frac{\Delta t}{\tau}\right)
$$
PELT 預設的半衰期 (half-life) $t_{1/2}$ 為 32 ms，對應 $\tau = t_{1/2} / \ln 2 \approx 46.16$ ms。以 $\Delta t = 1\,\text{ms}$ 代入，$k \approx e^{-1/46.16} \approx 0.9785$，即每輪更新僅納入 $1 - k \approx 2.15\%$ 的即時使用率，歷史負載資料的影響力大約每經過 32 ms 衰減一半。
將此離散遞迴推廣至連續時間，等價於指數衰減核的卷積 (convolution)：
$$
u(t) = \frac{1}{\tau} \int_{-\infty}^{t} r(s)\, e^{-(t-s)/\tau}\, ds
$$
$u(t)$ 是對過去所有時刻的即時使用率 $r(s)$ 以指數衰減核積分的結果：時間差 $(t - s)$ 越大，權重 $e^{-(t-s)/\tau}$ 越小。
## 重尾負載下的 PELT 特性
重尾分布 (heavy-tailed distribution) 的特徵是極端事件出現的機率，遠高於常態分布等指數衰減分布的預測。現實世界的網路流量、雲端資源使用模式和 CPU 工作負載皆呈現此類分布，短暫但強度極高的負載尖峰出現的頻率不可忽視。
以持續時間為 $T$ 的滿載尖峰 ($r(s) \approx 1$ 於該時段) 為例：$u(t)$ 在尖峰期間快速累積並趨近飽和值 1；尖峰結束後，$u(t)$ 以固定的指數速率 $1/\tau$ 衰減，此速率與尖峰持續時間 $T$ 或其總量無關。這種「快上慢下」的特性，使 PELT 在尖峰過後仍長時間維持高位的負載估計，可能導致不必要的任務遷移或 CPU 頻率調節失當。
$\arctan(x)$ 的積分提供一個概念性類比 (非嚴格數學等價，借其函數形式)：
$$
\int \arctan(x)\, dx = x \arctan(x) - \frac{1}{2}\ln(1 + x^2) + C
$$
$\arctan(x)$ 從 0 快速上升並趨近飽和 $\bigl(\lim_{x \to \infty}\arctan x = \pi/2\bigr)$，類比於 $u(t)$ 在持續滿載期間的快速累積；積分結果中的對數項 $-\frac{1}{2}\ln(1 + x^2)$ 以緩慢增長方式累積，類比尖峰後由固定 $\tau$ 主導、與尖峰特性脫鉤的殘留效應。此外，$\arctan(x)$ 的導數
$$
\frac{d}{dx}\arctan(x) = \frac{1}{1 + x^2}
$$
正比於標準 [柯西分布](https://en.wikipedia.org/wiki/Cauchy_distribution) (Cauchy distribution) 的 PDF (差一個常數因子 $1/\pi$)，這是典型的重尾分布，恰好點明 PELT 需要有效應對的訊號背景。
## 動態調適與多層應對機制
針對固定半衰期在重尾負載下的侷限，Google 與 Arm 的開發者提出 [sched/pelt: Change PELT halflife at runtime](https://lore.kernel.org/lkml/6281126b-3b93-86fa-25d6-d637b6c7dd87%40arm.com/t/)，允許在執行期動態調整半衰期(例如從 32 ms 縮至 16 ms 或 8 ms)，加快尖峰後 $u(t)$ 的回落速度，顯著減少任務遷移抖動 (migration churn) 和 CPU 頻率震盪 (frequency scaling oscillations)。更具實驗性的方向是在偵測到顯著尖峰時暫時縮短 $\tau$，尖峰後恢復預設值，在估計穩定性與響應靈敏度之間動態平衡。
現代 Linux 以三層機制共同應對具重尾特性的工作負載：
* `PELT` (估算層) : 在由 $\tau$ 定義的近因時間窗口內以 EWMA 累積歷史負載，提供排程決策的統計基礎；但易受柯西式尖峰短時拉高，留下衰減較慢的殘留效應
* `EEVDF` (微觀排程層) : 透過虛擬截止時間 (virtual deadline) 與 slice 機制，在毫秒級時間尺度上限制單一行程偏離其公平份額的程度，防止尖峰行程長期獨佔 CPU
* `BWC 與 CPU Burst` (宏觀控制層) : BWC (Bandwidth Control，cgroup CPU 頻寬控制) 在 cgroups 層面，於較長週期(如 100 ms)內提供確定性(quota)或統計性(burst)的 CPU 使用上限。CPU Burst 允許行程在用盡配額後預支至多 `quota × b` 的額度，下個週期若實際用量低於 quota 則自動歸還，其有效性建立在多個尖峰同時出現機率較低的統計假設 (尖峰互補效應) 之上
Sign in with Wallet
Connect another wallet