--- # System prepended metadata title: 「Linux 核心設計」第 6 週測驗題 tags: [linux2026] --- --- tags: linux2026 --- # [2026q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 6 週測驗題 > [作答表單](https://forms.gle/MXL7Xb6LyXF3YAoj7) :::warning :warning: 回答延伸問題時，務必優先以[課程教材](https://wiki.csie.ncku.edu.tw/linux/schedule)為主要出處，隨後參照 C 語言規格書、Linux 核心原始程式碼及其 git log 和 LKML (Linux Kernel Mailing-List)，和權威素材 (如 GCC 和 glibc 手冊，但絕對不是 CSDN 或者尋常的網路日誌/筆記) AI 工具是輔助性質，可用來撰寫測試程式碼和收集資訊，但主要的推測、查證、分析，和討論，都該由人類進行。 ::: 檢驗學員對於 CS:APP 第 2 章、數值系統、C 語言規格、Linux 核心風格、紅黑樹實作與程式開發等議題的掌握。 注意須知 (Linux 核心合規標準)：本測驗的作答規範仿照 Linux 核心的 [`checkpatch.pl`](https://docs.kernel.org/dev-tools/checkpatch.html) 風格檢查與巨集定義慣例，要求學員以系統程式設計的嚴謹度撰寫答案。 時代脈絡補充：C23 已正式將有號整數的表示法明定為 two's complement，讓 `time_after()`、`ERR_PTR()` 這類長期依賴位元保持性的系統程式技巧有了更清楚的語言背景。不過，這不表示 signed overflow 與所有有號位移都已自動變成可攜且安全；實作仍必須避免未定義或 implementation-defined 的邊界案例。換言之，現代標準吸收了核心世界的實務現實，但工程紀律並沒有因此放鬆。 | 約束類別 | 規定格式 | 技術理由 | 範例 | |---|---|---|---| | 運算式語法 | 填空答案採最精簡形式；嚴格不含空白、`?`、`;` | 評估 bitwise 操作或巨集層級運算式的關鍵邏輯，排除語法填充；題目內程式碼可保留排版空白以利閱讀 | `a^b` | | 十六進位表示 | 大寫字母；32 位元值以 8 位數字表示 (含前導零) | 確保記憶體對齊視覺化的一致性，避免 endianness 或截斷歧義 | `00200000`、`ABC` | | 數值填空 | 依題目指定基底作答；十六進位不含 `0x` 字首且以大寫表示 | 讓評分聚焦於數值本身，不混入語法或格式噪音 | `3F801000`、`112` | | 邏輯運算式填空 | 允許合法 C 語法；維持最短且語義直接的表達 | 這類題目要檢查的是位元操作邏輯，不是常數抄寫能力 | `~3`、`1u` | | 常數與型別字尾 | 預設十進位整數；嚴格小寫型別字尾 | 遵循 ISO C 標準表示法，防止核心空間中的隱式型別提升錯誤 | `112`、`1u`、`-1.0f` | | 記憶體存取 | 嚴格以 `[]` 陣列索引表示 | 區分高階陣列迭代與原始指標算術，提高語義清晰度 | `a[i]` | | C 語言術語 | 全部小寫，至多一個半形空白 | 與 C 語言規格書 (如 C99/C11) 的正式術語格式一致 | `unsigned int` | ### 背景：TurboQuant 向量量化 本測驗的程式碼取材自 [TurboQuant](https://arxiv.org/pdf/2504.19874) 高維向量的量化系統。 > $\to$ [過度依賴 AI 幫我統整，卻沒有盡到回去翻閱原始論文查證的義務，最後導出錯誤的結論](https://youtu.be/YlxQuyy3Mu0), [很 drama 的論文](https://www.facebook.com/thegiivee/posts/pfbid0QDYDWa98XKrE3iuqH1kZkLGTMbhF37tz5zWZece7FsSTNqgtq5jd4ecU934Zem1nl) > 新聞報導： > * [TurboQuant 衝擊記憶體 外媒曝 : DDR5 價格出現下跌](https://ec.ltn.com.tw/article/breakingnews/5386988) > * [Google 新技術 TurboQuant 嚇崩記憶體股？](https://www.wealth.com.tw/articles/f8a6ce0f-dd06-49b9-8f11-cb6685392eec) 閱讀前，學員應當先掌握以下： * 線性代數面：向量、內積、L2 norm、正交矩陣與基底變換 * 系統面：知道 Linux 核心為何在意位元寬度、記憶體配置、快取區域性與有號/無號轉換 雖以 TurboQuant 為背景，但每題真正要驗證的仍是 CS:APP 第 2 章的基本功與 Linux 核心程式設計常見陷阱。 [向量量化](https://en.wikipedia.org/wiki/Vector_quantization) (vector quantization, VQ) 的主體想法：把原本連續的浮點向量 $x \in \mathbb{R}^d$，改寫成少量代表點加上一個索引。做法是先挑出有限個代表點 (centroid) $\{c_1, \ldots, c_K\}$，再把每個輸入向量對映到最接近的代表點。於是原本必須儲存整個浮點向量，現在只要儲存代表點的索引即可。線性代數上，這等於把空間切成多個 [Voronoi 區域](https://en.wikipedia.org/wiki/Voronoi_diagram)，每個區域共用一個代表點。代價是一定會有失真，常見的衡量方式是重建誤差 $\mathbb{E}[\|x - c_{q(x)}\|_2^2]$。 經典的 [Lloyd-Max 演算法](https://en.wikipedia.org/wiki/Lloyd%27s_algorithm) 可視為反覆調整代表點、讓平均誤差愈來愈小的過程：先依目前代表點分群，再更新每群的中心，重複直到收斂。LBG 演算法則把這件事推廣到高維向量。若學員曾學過 [k-means 分群](https://en.wikipedia.org/wiki/K-means_clustering)，可把它視為同一族方法在不同語境下的表述。 對高維向量有二個極端做法。第一個極端是逐座標各自量化，也就是[純量量化](https://en.wikipedia.org/wiki/Quantization_(signal_processing)#Scalar_quantization)。這樣做最簡單，但若不同座標彼此相關，就會浪費很多表示能力。第二個極端是直接對整個 $d$ 維向量做完整的高維 VQ。這在理論上最好，但 codebook 大小會隨維度快速爆炸，實作上通常不可行。 線性代數提供的折衷方法是先做基底變換。若向量的統計相關性可由[共變異數矩陣](https://en.wikipedia.org/wiki/Covariance_matrix) $\Sigma$ 描述，則可用[正交對角化](https://en.wikipedia.org/wiki/Orthogonal_diagonalization) 找到一組較適合量化的新座標系：$\Sigma = P \Lambda P^\top$，其中 $P$ 是[正交矩陣](https://en.wikipedia.org/wiki/Orthogonal_matrix)，$\Lambda$ 是對角矩陣。把向量旋轉到新基底後，新的座標 $y = P^\top x$ 彼此較不相關，此時再逐座標量化，通常比直接在原座標系逐座標量化更有效。TurboQuant 的核心精神就是先做把座標轉成較容易量化形式的步驟，再做後續量化。 TurboQuant 的運作原理可類比於 [JPEG/MPEG 等 transform coding](https://hackmd.io/@sysprog/linux2026-quiz4)： ``` JPEG TurboQuant pixel block (8×8) embedding vector (d-dim) │ │ ▼ ▼ ┌────────────┐ ┌──────────────────┐ │ DCT │ orthogonal │ random rotation │ orthogonal │ (discrete │ transform │ y = Π · x │ transform │ cosine) │ (decorrelate) └──────────────────┘ (decorrelate) └────────────┘ │ │ ▼ ▼ ┌──────────────────┐ ┌────────────┐ │ Lloyd-Max scalar │ │ quantize │ per-coefficient │ quantize │ per-coordinate │ matrix │ (non-uniform) │ per coordinate │ (uniform) └────────────┘ └──────────────────┘ │ │ ▼ ▼ compressed bits b-bit packed indices ``` 小結： * JPEG 以 DCT (離散餘弦轉換) 將空間域的畫素區塊轉為頻域係數，利用影像能量集中於低頻的特性，對高頻係數分配較少位元。DCT 的基底向量是固定的餘弦函式族，構成 $\mathbb{R}^n$ 的標準正交基底 (orthonormal basis)。TurboQuant 以隨機正交矩陣 $\Pi$ 將 embedding 向量旋轉至新基底，利用高維空間中 concentration of measure 的性質，使旋轉後的座標近乎獨立且服從已知分布。二者的共同數學結構是基底變換 (change of basis)：以正交矩陣 $Q$ 將向量從原始座標系轉至新座標系 $y = Qx$，在新座標系中逐座標處理後，再以 $Q^\top y$ 轉回原始座標系。 * 二者皆為 lossy compression (失真壓縮)，無法完美還原原始資料，但皆提供可控的失真上界，使品質損失極低且可預測。正交轉換保範 (norm-preserving)，這是正交矩陣 $Q^\top Q = I$ 的直接推論：$\|Qx\|_2^2 = x^\top Q^\top Q x = x^\top x = \|x\|_2^2$。DCT 對應的特例即 Parseval 定理 ($\sum |x_i|^2 = \sum |X_k|^2$)。保範性質確保轉換本身不引入任何失真，所有失真僅來自後續的量化步驟。 * TurboQuant 不區分 token 的重要性，每個 KV embedding 一視同仁地經過旋轉、量化、打包，品質保證是對所有向量的 worst-case bound。這與 SnapKV、PyramidKV 等 token-level 壓縮方法 (選擇性丟棄低重要性的 token) 形成對比。 此問題的理論根基可溯至 Shannon 的 [source coding theory](https://en.wikipedia.org/wiki/Source_coding_theorem) (1948)。Shannon 的 [rate-distortion theory](https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory) 建立失真壓縮的基本極限：對任何來源分布與失真度量，存在 distortion-rate function $D(R)$，給定位元率 $R$ 時，任何編碼方案的失真不可能低於 $D(R)$；反之，只要位元率足夠，總存在達到 $D(R)$ 的編碼。此定理為量化器設計劃定不可突破的物理極限，類似 Carnot 效率之於熱機。TurboQuant 論文 Theorem 3 藉由 [Shannon lower bound](https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory) 與 [Yao's minimax principle](https://en.wikipedia.org/wiki/Yao%27s_principle) 證明，對任意 randomized $b$-bit quantizer $Q$，存在 hard instances $x, y \in \mathbb{S}^{d-1}$ 使 MSE 下界 $D_{\text{mse}}(Q) \geq 1/4^b$ 成立。TurboQuant 的實際失真與此下界僅差 $\sqrt{3}\pi / 2 \approx 2.7$ 倍常數，在工程意義上已逼近理論極限。 VQ 在大型語言模型 (LLM) 推論中扮演關鍵角色。decoder-based transformer 模型在推論時以 key/value (KV) 快取儲存先前 token 的 attention embedding，大小計算如下： ``` KV cache size = 2 x n_kv_heads x head_dim x n_layers x seq_len x sizeof(dtype) ^ ^ key + value context length Llama-3.1-8B (GQA, 8 KV heads, head_dim=128, 32 layers, 128K context, FP16): = 2 x 8 x 128 x 32 x 131072 x 2 bytes ≈ 16 GiB ``` 16 GiB 已接近消費級 GPU 的 HBM 容量上限 (NVIDIA RTX 4090: 24 GB)，而更大的模型 (70B 以上) 或更長的 context 會使此數字進一步膨脹。可將 KV 快取視為一個三維結構： ``` KV 快取的三個壓縮維度： ┌─────────────────────────────────────────────────┐ │ │ ↕ 寬：資料精度 │ context length │ (每個數值佔幾 bit) │ ◄──────────────────────────────────────────► │ FP16 = 16 bit │ │ 量化後 = 2~4 bit │ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │ t₁│ t₂│ t₃│ t₄│ t₅│ t₆│ t₇│ t₈│...│ tₙ│ │ ↕ 高：狀態大小 │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ │ (head_dim × n_heads │ │ × n_layers) └─────────────────────────────────────────────────┘ 三種壓縮策略分別對應不同維度： 長 (context length) ── sliding window attention / token pruning 限制保留的 token 數量，丟棄過舊的記憶 (SnapKV, PyramidKV, Scissorhands) 高 (state size) ── recurrent / state-space compression 將歷史記錄壓縮為固定大小的隱狀態 (Linear Attention, Mamba, RWKV) 寬 (data precision) ── vector quantization ← TurboQuant 降低每個數值的位元寬度 FP16 (16-bit) → 2~4 bit ``` TurboQuant 專攻資料精度維度的壓縮：將每個 $d$ 維 FP16 向量壓縮為 $b$-bit 整數索引 (每座標僅 2 至 4 位元)，可將 KV 快取縮減 $4.5\times$ 以上 (論文 Table 1)。壓縮帶來的加速並非源自計算量減少，因為 GPU 的 Tensor Core 有最低精度要求 (如 NVIDIA H100 原生支援 FP8/INT8)，低於此精度的量化索引仍需反量化後才能參與矩陣運算。真正的加速來自記憶體頻寬的節省。 LLM 推論的記憶體頻寬瓶頸源自 decoder-based transformer 的自迴歸 (autoregressive) 生成特性：每個新 token 的產生需讀取整個 KV 快取以計算 attention，但每次僅產出一個 token 的 logits。以 NVIDIA H100 SXM 為例，其 dense FP16 Tensor Core 峰值為 989 TFLOPS (不含 2:4 sparsity 加速)，HBM3 頻寬為 3.35 TB/s，[算術強度](https://en.wikipedia.org/wiki/Roofline_model) (arithmetic intensity) 的平衡點約為 $989 \times 10^{12} / (3.35 \times 10^{12}) \approx 295$ FLOP/byte。然而 autoregressive decoding 的 attention 計算中，每個 FP16 KV 元素 (2 bytes) 從 HBM 讀入後僅參與一次乘加 (2 FLOP)，算術強度僅約 $2 / 2 = 1$ FLOP/byte，遠低於平衡點，GPU 算力利用率不到 0.5%。這正是 [roofline model](https://en.wikipedia.org/wiki/Roofline_model) 所描述的 memory-bound 區域：效能完全受限於 HBM 至 SRAM 的資料搬運速度，而非計算單元的吞吐量。KV 快取存於 HBM，每次 attention 計算都需將其載入 SRAM，將精度從 16-bit 降至 3-bit 可使搬運的資料量縮減至約 $1/5$，在此 memory-bound 場景下直接轉化為等比例的延遲降低。 延續以 CPU 運算換取記憶體頻寬的主題，Linux 核心同樣採用積極的壓縮策略，以減緩記憶體 swap 至磁碟時的極端延遲。Zswap 與 Zram 皆壓縮本應被 swap 至實體磁碟的記憶體 page，以相對廉價的 CPU 週期換取大幅降低的磁碟存取延遲。但二者的底層架構代表根本不同的記憶體壓力處理方法。 [zram](https://docs.kernel.org/admin-guide/blockdev/zram.html) 是壓縮 RAM 區塊裝置，作為完全包含在實體 RAM 中的獨立 swap partition 運作。對無磁碟嵌入式系統或傳統 swap 不可用的高度記憶體受限環境極有助益。較新的核心提供 `CONFIG_ZRAM_WRITEBACK` 選項，允許將不可壓縮或閒置的 page 寫回後端磁碟，但此功能預設關閉且需手動設定 backing device。在預設組態下，Zram 與次要實體磁碟 swap 配對時仍存在 LRU Inversion 風險：當 Zram 達到容量上限時，缺乏自動逐出至後端磁碟的整合機制，核心可能被迫從系統其餘部分回收活躍的熱 file-backed page，而非回收困在 Zram 中的過時 anonymous page，造成效能劣化。 Zswap 則是輕量的 write-behind 壓縮快取，無縫位於實際磁碟 swap 裝置之前。它透過 frontswap API 直接掛入核心記憶體管理子系統。當系統嘗試將 page swap 至磁碟時，Zswap 攔截該 page、嘗試壓縮、並儲存於動態配置的 RAM pool 中。 關鍵結構差異在於 Zswap 與核心逐出邏輯的深度整合。Zswap 維護索引樹並透過 `zswap_entry` 結構追蹤元資料 (含 allocation handle、offset 與 length)。當 Zswap 記憶體池達到最大閾值時，內建的 pool-full 逐出機制會將最舊的壓縮 page 解壓縮並寫回後端磁碟 swap，避免鎖死。此外，可選的 shrinker worker (`queue_work(shrink_wq, &zswap_shrink_work)`) 提供主動式回收，在記憶體壓力升高時提前逐出冷 page (此功能預設關閉，需明確啟用)。二者共同形成在壓力下優雅退化的分層系統，不破壞系統整體的 LRU 邏輯。 | 特性 | Zswap | Zram | |---|---|---| | 主要功能 | 磁碟 swap 前的 write-back 快取 | 獨立壓縮區塊裝置 | | 整合方式 | 透過 frontswap API | 格式化為獨立 swap 空間 | | 逐出機制 | 透過 shrinker 自動 LRU 逐出至磁碟 | 硬性上限；無自動逐出至磁碟 | | 失效模式 | 優雅分層至磁碟儲存 | 潛在 LRU inversion 與系統 thrashing | 此動態壓縮機制與 TurboQuant 的設計原則一致：在運算資源充裕而記憶體/儲存資源受限時，以確定性的壓縮轉換交換容量。TurboQuant 以隨機旋轉與位元打包繞過 GPU HBM 容量瓶頸，Zswap 以 CPU 週期繞過 NAND 儲存延遲。 既有 VQ 方法面臨兩難： ``` Offline (Product Quant.) Online (RabitQ etc.) ┌───────────────────────┐ ┌──────────────────────┐ │ ✚ low distortion │ │ ✚ no preprocessing │ │ ✖ needs codebook │ │ ✖ loose bounds │ │ ✖ data-dependent │ │ ✖ not GPU-friendly │ │ ✖ slow (494 s, d=3072)│ │ │ └───────────┬───────────┘ └──────────┬───────────┘ │ │ └──────────┐ ┌───────────────┘ ▼ ▼ ┌────────────────────┐ │ TurboQuant │ ├────────────────────┤ │ ✚ data-oblivious │ │ ✚ online │ │ ✚ near Shannon LB │ │ ✚ accelerator- │ │ friendly │ │ ✚ ~0 s (0.002 s, │ │ d=3072) │ └────────────────────┘ ``` TurboQuant 的設計強調 accelerator-friendly 的程式碼結構。在使用者空間，AVX-512 等 SIMD (Single Instruction, Multiple Data) 指令可自由用於處理大量浮點資料。但在 Linux 核心中，浮點運算單元 (FPU) 與 SIMD 暫存器的使用受嚴格管控。 context switch 是核心中極頻繁的操作。若核心不加限制地使用 AVX/ZMM 暫存器 (涵蓋數百位元組的狀態)，每次 context switch、中斷或系統呼叫都需儲存與還原此狀態，效能將嚴重劣化。因此標準核心程式碼以 `-mno-avx` 等旗標編譯，明確禁止編譯器產生 SIMD 指令。若編譯器在核心程式碼中自行產出 AVX 指令，會在使用者空間的浮點變數尚未儲存前將其靜默覆寫，後果不堪設想。 然而，對極端運算密集的任務，核心允許隔離的 SIMD 臨界區段。RAID6 同位元組計算是典型案例。RAID6 需產生二個同位元組區塊 (P 與 Q) 以抵禦二個同時的磁碟故障。P 同位元組是簡單的 bitwise XOR，但 Q 同位元組需要在有限伽羅瓦體 (Galois field) $GF(2^8)$ 上進行複雜的乘法運算。以標準純量整數指令逐位元組計算，在計算上極為昂貴，成為儲存吞吐量的瓶頸。 為達極致吞吐量，核心在 `lib/raid6` 架構樹中提供特化實作。安全執行 SIMD 程式碼的流程如下： 1. 儲存裝置驅動程式呼叫 `kernel_fpu_begin()`：此函式主動儲存目前使用者空間的 FPU 暫存器狀態並停用核心 preemption，防止行程在持有 FPU 狀態期間被排程切換。 2. 以 inline assembly 使用寬 `ymm` 或 `zmm` 暫存器處理資料。演算法針對特定微架構嚴格最佳化，例如 LoongArch LSX/LASX 實作將 伽羅瓦體處理迴圈明確展開至每次操作 64 位元組，精確對齊CPU core 的 L1 cache line 大小，並避免分支以維持 SIMD pipeline 的連續資料流。演算法同時避開 null page 處理，確認 SIMD pipeline 不受稀疏資料干擾。 3. 計算完成後呼叫 `kernel_fpu_end()` 還原原始狀態並重新啟用 preemption。 此案例與 TurboQuant 的向量化距離計算直接對照：二者皆須確保運算對映至硬體的向量執行單元，刻意避免分支以維持 pipeline 吞吐量，同時遵守作業系統或加速器要求的嚴格執行協定。 TurboQuant 要解決的根本問題可形式化為：設計量化映射 $Q : \mathbb{R}^d \to \{0,1\}^B$ (其中 $B = b \cdot d$) 與反量化映射 $Q^{-1} : \{0,1\}^B \to \mathbb{R}^d$，使以下二個失真指標最小化。MSE 失真衡量的是 $\ell_2$ 空間中原始向量與重建向量的距離平方；inner product 失真衡量的是以量化向量近似原始內積 $\langle y, x \rangle$ 時的誤差平方，此指標直接對應 attention 機制中 query-key 相似度計算的精度： $$D_{\text{mse}} := \mathbb{E}_Q\left[\|x - Q^{-1}(Q(x))\|_2^2\right] \quad \text{(MSE 失真)}$$ $$D_{\text{prod}} := \mathbb{E}_Q\left[|\langle y, x \rangle - \langle y, Q^{-1}(Q(x)) \rangle|^2\right] \quad \text{(inner product 失真)}$$ 對內積量化器，TurboQuant 額外要求 unbiasedness：$\mathbb{E}_Q[\langle y, Q^{-1}(Q(x)) \rangle] = \langle y, x \rangle$。此性質確保量化後的 attention score 在期望值上等於原始值，不引入系統性偏差。 TurboQuant 提出二個演算法，分別最佳化 MSE 與內積失真。注意：TurboQuant 不使用極座標 (polar coordinates) 轉換，亦不將資料搬移至頻域。論文中作為比較對象的 [PolarQuant](https://arxiv.org/abs/2502.02617) 才是以極座標 (半徑 + 角度) 編碼的方法。PolarQuant 將向量兩兩配對轉為極座標 $(r, \theta)$，再對半徑遞迴配對，最終僅剩一個總距離和一組角度；角度範圍固定，因此不需額外的 normalization constant。TurboQuant 的做法截然不同，以正交轉換去相關後在旋轉座標系中逐座標量化，類似 JPEG 以 DCT 去相關後逐係數量化。二者的本質差異在於：(1) JPEG 的 DCT 是固定轉換，TurboQuant 的旋轉矩陣 $\Pi$ 是隨機產生的；(2) JPEG 對不同頻率係數分配不同精度 (低頻精、高頻粗)，TurboQuant 對所有座標使用相同的 codebook (因為旋轉後各座標的統計分布相同)。網路上流傳的部分科普文章誤將 PolarQuant 的遞迴極座標轉換描述為 TurboQuant 的第一步，這是張冠李戴。 第 1 階段：隨機旋轉 + Lloyd-Max 純量量化 (Algorithm 1, TurboQuant_mse) ``` input: x ∈ ℝᵈ │ ▼ ┌─────────┐ ┌─────────────────┐ ┌───────────┐ ┌──────────┐ │ L2 norm │ │ random rotation │ │ scalar │ │ bit-pack │ │ ‖x‖ │───▶│ y = Π·(x/‖x‖) │───▶ │ quantize │───▶│ b-bit │ └─────────┘ └─────────────────┘ │ per coord │ │ indices │ │ │ └───────────┘ └──────────┘ ▼ ▼ │ │ norm (FP32) Lemma 1: ▼ ▼ │ y_j ~ Beta idx[j] ∈ [0, 2ᵇ) packed bytes │ → N(0, 1/d) for each j ∈ [d] │ (coords ~indep.) │ codebook: {c₁, …, c_{2ᵇ}} │ (Lloyd-Max centroids) │ │ └───────▶ stored together ◀──────────────┘ in block_tq3 {norm, indices[]} ``` * 隨機旋轉 (Lemma 1)：先對隨機矩陣 $G \in \mathbb{R}^{d \times d}$ (各元素 i.i.d. $\mathcal{N}(0,1)$) 施行 [QR 分解](https://en.wikipedia.org/wiki/QR_decomposition) $G = QR$，再以 $\Pi = Q \cdot \text{diag}(\text{sign}(R_{ii}))$ 校正符號，確保 $\Pi$ 為 [Haar 測度](https://en.wikipedia.org/wiki/Haar_measure)下均勻分布於正交群 $O(d)$ 上的隨機正交矩陣。QR 分解是線性代數的基礎工具，將任意矩陣分解為正交矩陣 $Q$ ($Q^\top Q = I$) 與上三角矩陣 $R$ 的乘積；單獨取 $Q$ 因子並不保證 Haar 均勻性 (因為 QR 分解的符號約定使 $R$ 對角元素為正，引入偏差)，乘上 $\text{diag}(\text{sign}(R_{ii}))$ 才消除此偏差。旋轉後的座標 $y_j = (\Pi \cdot \hat{x})_j$ (其中 $\hat{x} = x/\|x\|_2$ 為單位向量) 服從 scaled Beta 分布 $f_X(x) = \frac{\Gamma(d/2)}{\sqrt{\pi} \cdot \Gamma((d-1)/2)} (1 - x^2)^{(d-3)/2}$。此分布隨維度 $d$ 增大而趨近 $\mathcal{N}(0, 1/d)$ (中央極限定理的推論)，且各座標間並非獨立但恰好不相關 ($\mathbb{E}[x_i x_j] = 0$ 對 $i \neq j$)，相依性僅表現在高階約束 (如單位範數條件 $\sum x_i^2 = 1$) 而非成對統計量。直觀理解：單位球面 $\mathbb{S}^{d-1}$ 上均勻分布的向量，其各座標投影集中於零附近且漸近 Gaussian，這是 concentration of measure 現象的具體展現。此旋轉將座標間的相關性打散，使 $d$ 維問題近似分解為 $d$ 個獨立的一維量化問題。 * Lloyd-Max codebook：旋轉後各座標服從相同的已知分布，可以單一 codebook 處理所有座標。對此分布求解一維 continuous k-means 最佳化 (Eq. 4)，得到 $2^b$ 個最佳 centroid。以 $b = 1, 2$ 為例：$b = 1$ 時 centroid 為 $\{\pm\sqrt{2/\pi} / \sqrt{d}\}$；$b = 2$ 時為 $\{\pm 0.453/\sqrt{d},\ \pm 1.510/\sqrt{d}\}$。codebook 僅依賴維度 $d$ 和位元寬度 $b$，可預計算後儲存，不需要訓練資料。 * 逐座標量化：對每個 $y_j$ 找最近 centroid 並記錄 $b$-bit 索引。反量化時以索引查表還原 centroid 值，再乘以 $\Pi^\top$ 旋轉回原始基底。 第 2 階段：1-bit QJL 殘差校正 (Algorithm 2, TurboQuant_prod) 第 1 階段的 MSE 量化器雖然重建誤差最小，但用於估計內積 $\langle y, x \rangle$ 時會產生系統性偏差。$b = 1$ 時乘法偏差為 $2/\pi \approx 0.637$ (論文 Section 3.2)，意味著 attention score 被系統性縮減約 36%；$b$ 增大時偏差遞減但不為零。如同一把校準不良的尺，每次量測都偏向同一方向，累積後會扭曲 attention score 的排序。 ``` 原始向量 x ∈ ℝᵈ │ ├───▶ Q_mse (b−1 bits) ───▶ idx (第 1 階段: MSE 量化) │ │ │ x̃ = DeQuant(idx) (反量化重建) │ │ └───────▶ r = x − x̃ (殘差向量: 第 1 階段的量化誤差) │ ├───▶ sign(S·r) ───▶ qjl (第 2 階段: QJL 1-bit sign hash) │ 每個座標僅用 1 bit: +1 或 −1 └───▶ ‖r‖ ───▶ gamma (殘差 L2 norm) output: (idx, qjl, gamma) 反量化: x̂ = x̃_mse + (√(π/2) / d) · γ · Sᵀ · qjl ``` * QJL 的角色：QJL (Quantized Johnson-Lindenstrauss) 的數學基礎是 [Johnson-Lindenstrauss 引理](https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)，該引理指出將 $n$ 個高維點以隨機線性映射 $S \in \mathbb{R}^{m \times d}$ 投影至 $m = O(\varepsilon^{-2} \log n)$ 維子空間時，所有成對距離以 $(1 \pm \varepsilon)$ 倍率保持。QJL 更進一步：對殘差 $r = x - \tilde{x}_{\text{mse}}$ 計算隨機投影 $Sr$ 後僅取 sign，每個座標只花 1 bit 記錄正負號 ($+1$ 或 $-1$)。反量化時以 $\sqrt{\pi/2}$ 為 scale factor，補償 sign 函式丟失幅值的效應 (因為 $\mathbb{E}[|Z|] = \sqrt{2/\pi}$ 對 $Z \sim \mathcal{N}(0,1)$)。Lemma 4 證明組合後的內積估計器是 unbiased 的：$\mathbb{E}[\langle y, \hat{x} \rangle] = \langle y, x \rangle$。 偏差消除的數學推導 (論文 Theorem 2 證明的關鍵，以條件期望展開)： ``` 僅用 MSE 量化器估計內積 (biased, 含偏差)： ┌──────────────────────────────────────────────────────────┐ │ E[⟨y, x̃_mse⟩] = (2/π) · ⟨y, x⟩ (b=1 時) │ │ ~~~~~~ │ │ 乘法偏差：內積被系統性縮減至 63.7% │ └──────────────────────────────────────────────────────────┘ 加入 QJL 殘差校正後 (unbiased, 不含偏差)： E[⟨y, x̃⟩] = E[⟨y, x̃_mse + x̃_qjl⟩] = E[⟨y, x̃_mse⟩] + E[⟨y, x̃_qjl⟩] ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~ 含偏差的 MSE 項 QJL 殘差校正項 其中 QJL 校正項： E[⟨y, x̃_qjl⟩ | x̃_mse] = ⟨y, r⟩ (Lemma 4: QJL unbiased) = ⟨y, x - x̃_mse⟩ (殘差定義) = ⟨y, x⟩ - ⟨y, x̃_mse⟩ 合計：E[⟨y, x̃⟩] = E[⟨y, x̃_mse⟩] + ⟨y, x⟩ - E[⟨y, x̃_mse⟩] = ⟨y, x⟩ ✓ 完美消除偏差 ``` 此推導是 Theorem 2 (p13) 的關鍵：無論 MSE 量化器引入多少偏差，QJL 對殘差的無偏估計恰好補上缺口，此性質不依賴 $b$ 值或 codebook 選擇。注意：無偏性嚴格成立的前提是 $S$ 的元素為 i.i.d. $\mathcal{N}(0,1)$ (Definition 1、Lemma 4)。後續 Problem C 改用確定性 Rademacher 投影 ($\pm 1$) 以簡化實作，犧牲嚴格無偏性但在高維度下漸近等價 (詳見 Problem C 的驗證說明)。 $Q_{\text{prod}}$ 的量化映射定義為 (論文 Algorithm 2)： $$ Q_{\text{prod}}(x) = \left[Q_{\text{mse}}(x),\ \text{sign}(S \cdot r),\ \|r\|_2\right], \quad r = x - Q_{\text{mse}}^{-1}(Q_{\text{mse}}(x)) $$ 反量化映射為： $$ Q_{\text{prod}}^{-1}(\text{idx}, \text{qjl}, \gamma) = Q_{\text{mse}}^{-1}(\text{idx}) + \frac{\sqrt{\pi/2}}{d} \cdot \gamma \cdot S^\top \cdot \text{qjl} $$ * Theorem 2 (論文 p12-13) 證明此內積量化器滿足：(1) 無偏性 $\mathbb{E}[\langle y, \tilde{x} \rangle] = \langle y, x \rangle$；(2) 內積失真上界 $D_{\text{prod}} \leq \frac{\sqrt{3}\pi^2 \cdot \|y\|_2^2}{d} \cdot \frac{1}{4^b}$。具體數值：$b = 1, 2, 3, 4$ 時 $D_{\text{prod}} \approx \frac{1.57}{d}, \frac{0.56}{d}, \frac{0.18}{d}, \frac{0.047}{d}$。 * 品質保證：論文在 Needle-In-A-Haystack 測試 (Figure 4) 中展示 $4\times$ 壓縮達到與 full-precision 相同的 recall score (0.997)，在 LongBench-V1 (Table 1) 上以 2.5-bit 量化達到與 16-bit full cache 相當的平均分數 (49.44 vs 50.06)。損失極低的原因在於內積估計的 unbiasedness：個別估計有 variance，但不會系統性偏向特定方向，在大量 attention head 與 layer 的統計平均下，整體品質趨近無損。 * Theorem 1 證明 MSE 失真上界為 $D_{\text{mse}} \leq \frac{\sqrt{3}\pi}{2} \cdot \frac{1}{4^b}$，具體數值如下： | $b$ (bits) | $D_{\text{mse}}$ (上界) | $D_{\text{mse}}$ (下界 $1/4^b$) | 倍率 | |---|---|---|---| | 1 | 0.36 | 0.25 | 1.44 | | 2 | 0.117 | 0.0625 | 1.87 | | 3 | 0.03 | 0.0156 | 1.92 | | 4 | 0.009 | 0.0039 | 2.31 | 以下三題分別探討此管線中的關鍵環節：FP32/FP16 轉換 (Problem A)、位元打包與 codebook 量化 (Problem B)、sign hash 與內積估計 (Problem C)。 --- ## Problem A: 浮點格式轉換與 denormalized 捨入 > 延伸 CS:APP 2.87 / Practice Problem 2.52 / Figure 2.32 / Figure 2.35 題目設計要點： * 核心在於把 Figure 2.32 與 Figure 2.35 轉成可執行的位元操作，而不是背誦 FP16 規格。 * 學員只要掌握 normalized / denormalized、bias、hidden bit 與 round-to-even，即可完整作答。 * 延伸閱讀刻意連到 Linux 核心中的浮點模擬與格式轉換，讓同一組規則落到真實程式碼。 - [ ] Part 1: Half-Precision 編碼 IEEE 754-2008 的 16 位元 half-precision 格式由 1 個 sign bit、$k = 5$ 個 exponent bits、$n = 10$ 個 fraction bits 組成，exponent bias 為 $2^{5-1} - 1 = 15$。CS:APP Practice Problem 2.52 要求在不同浮點格式間轉換位元樣式，並在必要時套用 round-to-even 規則。 本題真正會用到的規格常數： | 格式 | Exponent Bits ($k$) | Fraction Bits ($n$) | Bias | |---|---:|---:|---:| | FP32 | 8 | 23 | 127 | | FP16 | 5 | 10 | 15 | CS:APP Figure 2.32 定義 IEEE 754 浮點數由三個欄位組成：sign bit `s`、$k$-bit exponent field `exp`、$n$-bit fraction field `frac`。以下圖示對照二種格式的欄位配置： ``` FP32 (single precision, k=8, n=23): 31 30 23 22 0 ┌──┬─────────────┬──────────────────────────────────┐ │ s│ exp │ frac │ │ │ (8 bit) │ (23 bit) │ └──┴─────────────┴──────────────────────────────────┘ FP16 (half precision, k=5, n=10): 15 14 10 9 0 ┌──┬───────┬───────────────┐ │ s│ exp │ frac │ │ │(5 bit)│ (10 bit) │ └──┴───────┴───────────────┘ ``` FP32 → FP16 轉換需將 8-bit exponent 轉為 5-bit (調整 bias)，23-bit fraction 截斷為 10-bit (捨入)。Figure 2.33 進一步將浮點值分為四類： * normalized ($\text{exp} \neq 0$ 且 $\text{exp} \neq 2^k - 1$)：significand $M = 1 + f$，exponent $E = e - \text{Bias}$ * denormalized ($\text{exp} = 0$)：significand $M = f$，exponent $E = 1 - \text{Bias}$ * infinity ($\text{exp} = 2^k - 1, \text{frac} = 0$) * NaN ($\text{exp} = 2^k - 1, \text{frac} \neq 0$) Figure 2.35 以 8-bit 浮點格式 ($k = 4, n = 3, \text{bias} = 7$) 列出所有非負可表示值。注意 denormalized 與 normalized 的交界處：最大 denormalized value $= 7/512$ 與最小 normalized value $= 8/512 = 1/64$ 之間的平滑銜接，歸功於 denormalized 使用 $E = 1 - \text{Bias}$ 而非 $E = -\text{Bias}$。 CS:APP 2.87 (homework problem) 要求填寫 half-precision 的 hex/M/E/V/D 表格，包含 $-0$、最小正 denormalized、$512$、最大 denormalized、$-\infty$ 以及 $0\text{x3BB0}$ 所代表的值。此表格驗證學員對 exponent bias、hidden bit、denormalized 編碼規則的理解。 - [ ] Part 2: 向量量化中的 FP32 → FP16 轉換 (含 denormalized 捨入) 大型語言模型的 key/value 快取在推論期間持續膨脹，記憶體用量隨 context length 與 attention head 數量線性成長。TurboQuant 等向量量化方法會把高維浮點向量壓縮成低位元整數索引，但每個量化區塊仍要保存一些輔助資訊，例如 scale 與 offset。若這些輔助資訊仍用 FP32 儲存，壓縮收益會被吃掉一部分；改用 FP16 儲存，才能把整體空間再往下壓。換言之，本題不是孤立的格式轉換練習，而是量化系統中真實會遇到的空間成本問題。 Linux 核心的 MIPS FPU 軟體模擬器 ([`arch/mips/math-emu/`](https://github.com/torvalds/linux/tree/master/arch/mips/math-emu)) 在不具備硬體 FPU 的嵌入式處理器上以純整數運算模擬浮點計算。其 double → single 轉換 ([`sp_fdp.c`](https://github.com/torvalds/linux/blob/master/arch/mips/math-emu/sp_fdp.c)) 與本題的 single → half 轉換邏輯相同：擷取 sign/exponent/fraction 欄位 → 轉換 bias → 處理 denormalized/overflow/underflow → round-to-even 捨入。Linux 核心以 `union` 結構體對映 IEEE 754 欄位： ```c /* arch/mips/math-emu/ieee754.h (節錄，經簡化) */ union ieee754sp { struct { unsigned sign:1; unsigned bexp:8; unsigned mant:23; }; u32 bits; }; ``` 此 `union` 型別雙關受 GCC/Clang 明確支援，Linux 核心廣泛依賴此慣例。C99 本文對透過 `union` 讀取非最後寫入成員的行為未明確定義 (附註 82 為非規範性)，WG14 Defect Report 283 (TC3 腳註) 後續澄清位元組以新型別重新詮釋，但結果依賴底層表示 (representation)，當存取產生 trap representation 時為未定義行為，其餘情況屬 implementation-defined behavior。反之，若以指標強制轉型 `*(uint32_t *)&v` 取代 `union`，則違反 C99 6.5 §7 的 strict aliasing rule，屬未定義行為。本題及後續 Problem B、C 皆以 `union` 實作型別雙關。 以下 FP32 → FP16 轉換函式取自向量量化實作，處理完整的 normalized、denormalized 與 special value 路徑，包含 CS:APP Section 2.4.4 定義的 round-to-even 捨入。讀這段程式碼時，建議先把它分成三件事看：先拆欄位，再依 exponent 決定走哪條路，最後才做捨入。這樣較不容易在細節中迷失。 偏移量轉換可一步完成：$\text{hexp} = e_{\text{FP32}} - (\text{Bias}_{\text{FP32}} - \text{Bias}_{\text{FP16}})$。填空 __ A01 __ 為此淨偏移量。學員須依 CS:APP Figure 2.32 查閱 single precision 的 $k$ 值 (8) 與 half-precision 的 $k$ 值 (5)，分別以 $2^{k-1} - 1$ 計算各格式的 bias 後求差。 注意 `int hexp = (int)exp - __A01__` 的 `(int)` 強制轉型。`exp` 的型別為 `unsigned`，若省略 `(int)` 而寫 `exp - 112`，依 C99 6.3.1.8 的 usual arithmetic conversions，`112` 先轉為 `unsigned` 再進行減法，當 `exp < 112` 時無號減法 wrap around 產生大正數 (例如 `exp = 0` 時結果為 $2^{32} - 112$)。此 unsigned 值賦予 `int hexp` 時，依 C99 6.3.1.3 §3 屬 implementation-defined behavior。在 two's complement 實作上 `hexp` 取得負值，`hexp <= 0` 成立，但 `shift = 14 - hexp` 會產生極大的右移量，導致結果錯誤。加上 `(int)` 強制轉型後，減法以 signed 算術執行，`hexp` 正確取得負值且量值合理，後續邏輯才能正確分流。此 signed/unsigned 轉換陷阱見 CS:APP Section 2.2.4。 當 $\text{hexp} \leq 0$ 時結果落入 FP16 denormalized 區間。此時 FP32 的 normalized mantissa ($1.f_{22}f_{21}\ldots f_0$，含 hidden bit) 須右移以對齊 denormalized 的固定指數。依 CS:APP Section 2.4.2，denormalized 的 exponent 為 $E = 1 - \text{Bias}$，因此 FP16 的 denormalized exponent 為 $1 - 15 = -14$。右移量的基底為 $\text{Bias}_{\text{FP16}} - 1$，填空 __ A02 __。 Normalized 路徑截斷 FP32 fraction 的低位元以符合 FP16 的 $n$-bit fraction。學員須依 CS:APP Figure 2.32 查閱兩格式的 $n$ 值差 ($23 - 10 = 13$)，截斷時以 round-to-even 判斷：低 13 位元的中點值為 $2^{12}$。填空 __ A03 __ 為此中點位移量。 ```c #include #include typedef uint32_t u32; typedef uint16_t u16; #define FP32_EXP_SHIFT 23 #define FP16_EXP_SHIFT 10 #define FP16_EXP_MAX 31 #define FP32_MANT_WIDTH 24 #define FP32_SIGN_MASK 0x80000000u #define FP32_EXP_MASK 0x7F800000u #define FP32_FRAC_MASK 0x007FFFFFu #define FP16_SIGN_MASK 0x8000u #define FP16_EXP_MASK 0x7C00u #define FP16_QNAN 0x7E00u #define unlikely(x) __builtin_expect(!!(x), 0) u16 fp32_to_fp16(float v) { union { float f; u32 u; } bits; bits.f = v; unsigned sign = (bits.u & FP32_SIGN_MASK) >> 16; unsigned exp = (bits.u & FP32_EXP_MASK) >> FP32_EXP_SHIFT; unsigned frac = bits.u & FP32_FRAC_MASK; unsigned hsign = sign; if (exp == 0xFF) { if (frac == 0) return (u16)(hsign | FP16_EXP_MASK); /* ±∞ */ /* 簡化實作：統一回傳 canonical quiet NaN，不保留原本 payload */ return (u16)(hsign | FP16_QNAN); /* NaN */ } if (exp == 0) return (u16)hsign; /* FP32 denorm → FP16 ±0，保留 -0 的 sign bit */ int hexp = (int)exp - __A01__; if (unlikely(hexp >= FP16_EXP_MAX)) return (u16)(hsign | FP16_EXP_MASK); /* overflow → ±∞ */ if (hexp <= 0) { /* denormalized 路徑：還原 hidden bit 後右移 */ unsigned mant = frac | 0x800000; int shift = __A02__ - hexp; if (unlikely(shift > FP32_MANT_WIDTH)) return (u16)hsign; unsigned val = mant >> shift; unsigned lost = mant & ((1u << shift) - 1); unsigned half = 1u << (shift - 1); /* round-to-even */ if (lost > half || (lost == half && (val & 1))) val++; return (u16)(hsign | val); } /* normalized 路徑：截斷 fraction 並捨入 */ unsigned hfrac = frac >> 13; unsigned lost = frac & 0x1FFF; unsigned half = 1u << __A03__; if (lost > half || (lost == half && (hfrac & 1))) { hfrac++; if (hfrac == 0x400) { /* fraction 進位溢至 exponent */ hfrac = 0; hexp++; if (unlikely(hexp >= FP16_EXP_MAX)) return (u16)(hsign | FP16_EXP_MASK); } } return (u16)(hsign | ((unsigned)hexp << FP16_EXP_SHIFT) | hfrac); } ``` 若想快速自我檢查，可用最小測試程式驗證 `1.0f` 是否轉成 FP16 的 `3C00`： ```c int main(void) { u16 h = fp32_to_fp16(1.0f); /* 預期輸出 3C00 */ printf("%04X\n", h); return 0; } ``` 驗證 (normalized)：`float v = 1.0f` 的 FP32 為 `0x3F800000` (exp=127, frac=0)。hexp $= 127 - 112 = 15$，hfrac=0，結果 `0x3C00`。查 CS:APP Figure 2.36，value 1.0 的 exp 欄位 = Bias，$E = 0, M = 1$，符合 FP16 `0x3C00` 的 $e = 15, E = 0, M = 1$。 驗證 (denormalized 邊界)：FP32 `0x387FE000` (exp=112, frac=`0x7FE000`) 轉換時 hexp $= 112 - 112 = 0$，進入 denormalized 路徑。mant $= \text{0x7FE000} | \text{0x800000} = \text{0xFFE000}$，shift $= 14 - 0 = 14$，右移後 val $= \text{0x3FF}$。lost $= \text{0x2000}$ 恰等於 half $= \text{0x2000}$，且 val 末位為 1，觸發 round-to-even 進位，val $= \text{0x400}$。結果 `0x0400` 恰為 FP16 最小 normalized 值 ($e = 1, f = 0, M = 1, E = 1 - 15 = -14$)，越過 denormalized/normalized 邊界，正是 CS:APP Section 2.4.2 強調的平滑銜接。 驗證 (round-to-even 截斷)：FP32 `0x` __ A04 __ 代表值 $1.0 + 2^{-11}$。其 frac = `0x001000` (第 12 位元為 1，其餘為 0)。學員須依 CS:APP Figure 2.32 的 single precision 欄位配置，驗證 $1.0 + 2^{-11}$ 的 frac 欄位：fraction 的第 $i$ 位元 (從 MSB，$i = 0$ 起) 代表 $2^{-(i+1)}$，故 $2^{-11}$ 對應 frac 的第 $i = 10$ 位元，即 bit 位置 $22 - 10 = 12$，hex 為 `0x001000`。hexp = 15，hfrac $= 0x001000 >> 13 = 0$，lost $= 0x1000$，half $= 0x1000$。lost == half 且 hfrac 末位為 0 (偶數)，不進位。FP16 結果為 `0x3C00` (value 1.0)，精度損失 $= 2^{-11} \approx 0.049\%$。此行為與 CS:APP Section 2.4.4 的 round-to-even 規則一致：中點處向偶數方向捨入。 驗證 (overflow 路徑)：FP16 最大 normalized 值的 biased exponent 為 $2^5 - 2 = 30$，fraction 全 1 ($10$ 個 1)，significand $M = 2 - 2^{-10}$，$E = 30 - 15 = 15$，值為 $(2 - 2^{-10}) \times 2^{15} = 65504$。此值的 FP32 表示為 `0x` __ A05 __。學員須依 CS:APP Figure 2.32 建構 FP32 位元樣式：$65504 = 1.1111111111_2 \times 2^{15}$，故 FP32 exp $= 15 + 127 = 142$，frac 高 10 位元全 1，低 13 位元全 0。介於 65504 與 65536 之間的 FP32 值 (hexp = 30) 在 normalized 路徑中截斷或捨入至 `0x7BFF` (65504)；但若捨入使 fraction 進位溢位 (hfrac 從 `0x3FF` 進位至 `0x400`)，hexp 遞增至 31，進入 overflow 路徑回傳 `0x7C00` ($+\infty$)。FP32 exp $\geq 143$ (即 hexp $\geq 31$，值 $\geq 2^{16}$) 則直接 overflow。 延伸閱讀：數值截斷屬 [CWE-197](https://cwe.mitre.org/data/definitions/197.html) (Numeric Truncation Error)。[CVE-2021-33200](https://nvd.nist.gov/vuln/detail/CVE-2021-33200) 中 BPF verifier 的 pointer arithmetic limit 追蹤 (`aux->alu_limit`) 存在值域精度不足的 corner case，允許攻擊者繞過安全檢查，存取越界記憶體。Linux 核心雖禁止在一般路徑使用浮點運算，但 MIPS FPU 軟體模擬器與 BPF verifier 的數值截斷邏輯仍需嚴格處理精度損失。CS:APP Practice Problem 2.49 指出 $n$-bit fraction 浮點格式無法精確表示的最小正整數為 $2^{n+1} + 1$。在 FP16 ($n = 10$) 下此值為 $2^{11} + 1 = 2049$。量化系統中以 FP16 儲存的 codebook centroid 精度同樣受此限制。 除 MIPS FPU 外，GPU 裝置驅動程式亦涉及 FP16 轉換。DRM/AMDGPU 的色彩管理子系統 ([`drivers/gpu/drm/amd/display/dc/basics/`](https://github.com/torvalds/linux/tree/master/drivers/gpu/drm/amd/display/dc/basics)) 以定點數實作 gamma 校正與色彩空間轉換，內部使用的查表值 (LUT) 常以 FP16 格式儲存。若 round-to-even 處理有誤，會在色彩梯度上產生 banding 瑕疵 (量化雜訊)，使用者可在螢幕上直接觀察到精度損失的後果。 ### 延伸問題 * MIPS FPU 軟體模擬器的 double → single 轉換 (Section 2.4.4 round-to-even) 與 Part 2 的 `fp32_to_fp16` 捨入邏輯直接對應。以此為出發點： * (a) 閱讀 [`arch/mips/math-emu/sp_fdp.c`](https://github.com/torvalds/linux/blob/master/arch/mips/math-emu/sp_fdp.c) 的 `ieee754sp_fdp()`，追蹤 52-bit fraction 截斷至 23-bit 時的 guard ($G$) / round ($R$) / sticky ($S$) bit 計算。以 $G$、$R$、$S$ 與截斷後最低位元 $L$ 推導 round-to-even 進位條件 $G \land (R \lor S \lor L)$，驗證其與 Part 2 的 `lost > half || (lost == half && (val & 1))` 等價。對照 Section 2.4.4 Figure 2.37 的四種捨入模式，說明 round-to-even 在 discarded bits 均勻分布假設下期望捨入誤差為零的數學依據 * (b) Practice Problem 2.49 指出 $n$-bit fraction 浮點格式無法精確表示的最小正整數為 $2^{n+1}+1$，FP16 ($n=10$) 為 2049。閱讀 [`kernel/time/clocksource.c`](https://github.com/torvalds/linux/blob/master/kernel/time/clocksource.c) 的 `clocks_calc_mult_shift()`，此函式以 $t_{\text{ns}} = (\text{cycles} \times \text{mult}) \gg \text{shift}$ 將 TSC 週期轉為奈秒，須在 64 位元溢位約束下最大化 `shift`。推導 `shift` 與相對轉換誤差 ($\leq 2^{-\text{shift}}$) 的關係，並類比 IEEE 754 的精度/範圍權衡：定點的 `shift` 對應 fraction 寬度 $n$，增大 $n$ 提升精度但壓縮動態範圍 * \(c) [CVE-2021-33200](https://nvd.nist.gov/vuln/detail/CVE-2021-33200) 中 BPF verifier 的 `aux->alu_limit` 在計算指標算術邊界時，對 masking 方向的處理存在 corner case，使攻擊者可繞過範圍檢查存取越界記憶體。閱讀 [`kernel/bpf/verifier.c`](https://github.com/torvalds/linux/blob/master/kernel/bpf/verifier.c) 的修補差異，追蹤 `sanitize_ptr_alu()` 如何修正 `alu_limit` 在負偏移時的值域追蹤。更廣泛地，BPF verifier 的 `coerce_reg_to_size()` 在 64→32 位元截斷時亦曾因未同步更新有號值域 (`smin_value`/`smax_value`) 而被利用。此類漏洞與 Part 2 的 FP32→FP16 轉換在概念上對應：二者皆為寬精度到窄精度的截斷，若未正確追蹤截斷後的值域，下游邏輯會基於錯誤假設做出不安全決策 * Part 2 的 `(int)exp - 112` 涉及 Section 2.2.6 的 usual arithmetic conversions (C99 6.3.1.8)。以此為出發點： * (a) 若省略 `(int)` 而寫 `exp - 112`，當 `exp < 112` 時無號減法 wrap around 產生大正數 (Section 2.3.1)。以 GCC `-O2` 編譯有/無 `(int)` 轉型兩版，比較 x86-64 組合語言的分支指令差異 (`jle` vs `jbe`)。[CVE-2017-16995](https://nvd.nist.gov/vuln/detail/CVE-2017-16995) 的 BPF verifier `check_alu_op()` 正是因相同的 signed/unsigned 混用陷阱而被利用，攻擊者得以用負值繞過範圍檢查 * (b) 閱讀 [`arch/x86/kernel/fpu/core.c`](https://github.com/torvalds/linux/blob/master/arch/x86/kernel/fpu/core.c)，追蹤 `kernel_fpu_begin()` 如何以 `fpregs_lock()` 停用 preemption 並儲存 FPU 狀態 (現代 x86 以 `TIF_NEED_FPU_LOAD` 管理)。說明核心為何禁止一般路徑使用浮點：若 SIMD 區段中允許 context switch，被切入行程的浮點狀態會被靜默破壞。閱讀 [`lib/raid6/avx2.c`](https://github.com/torvalds/linux/blob/master/lib/raid6/avx2.c)，追蹤 RAID6 如何以 `vpshufb` 實作 $GF(2^8)$ 的 4-bit 查表乘法 (Section 2.1.3 的位元操作在 SIMD 層級的擴充)； * \(c) DRM/AMDGPU 的 [`drivers/gpu/drm/amd/display/dc/basics/conversion.c`](https://github.com/torvalds/linux/blob/master/drivers/gpu/drm/amd/display/dc/basics/conversion.c) 以純整數位元操作轉換 FP16 色彩值。在 HDR 內容中，FP16 denormalized 區間 ($[2^{-24}, 2^{-14})$) 對應暗部畫素，Figure 2.35 顯示 denormalized 為等差數列；若 round-to-even 有誤，會在暗部梯度產生 banding 瑕疵。設計一組落在 FP16 denormalized 邊界的 FP32 輸入，至少涵蓋 tie case 與非 tie case，比較 round-to-even 與 round-towards-zero 的輸出差異 --- ## Problem B: 位元打包、codebook 量化與反量化迴路 > 延伸 CS:APP Section 2.1.3 (Bit-Level Operations) / Problem 2.67 / Practice Problem 2.49 / Figure 2.35 題目設計要點： * 表面主題是 TurboQuant，實際驗證的是固定寬度欄位的打包、解包與位元安全性 * `pack_indices` / `unpack_indices` 可視為手動實作一個極小型 bitstream format， * 延伸問題把 shift/mask、節點打包與走訪安全性連到 Linux 核心內部資料結構設計 - [ ] Part 1: 位元操作與量化的對應 CS:APP Section 2.1.3 介紹 C 語言的 bitwise 運算子 (`&`, `|`, `~`, `^`)。Figure 2.35 的 8-bit 浮點格式與本題的 codebook 量化，雖然表面形式不同，但都在回答同一件事：位元數有限時，如何用少量離散值去近似連續世界。差別只在於 Figure 2.35 討論的是浮點格式本身，本題討論的是量化後索引如何儲存。 TurboQuant 的關鍵觀察是：若先把高維向量旋轉到較合適的座標系，每個座標就能近似視為一個獨立的一維隨機變數。這樣一來，高維量化問題就能拆成很多個簡單的一維量化問題。對本題而言，學員不需要完整重建論文證明，只要理解 codebook 是把連續值映到少數代表值，索引則是代表值的編號即可。 論文 (p10) 指出，在足夠高的維度 $d$ 下，旋轉後座標的 Beta 分布趨近 $\mathcal{N}(0, 1/d)$，最佳 Lloyd-Max centroid 以 $1/\sqrt{d}$ 縮放。以標準 $\mathcal{N}(0, 1)$ 分布為參照 (實際 centroid 為以下值除以 $\sqrt{d}$)，1-bit 與 2-bit 最佳 centroid 分別為： * 1-bit ($b = 1$, 2 個 centroid)：$\{\pm\sqrt{2/\pi}\} \approx \{-0.7979, +0.7979\}$，縮放後 $\{\pm\sqrt{2/\pi}/\sqrt{d}\}$ * 2-bit ($b = 2$, 4 個 centroid)：$\{-1.510, -0.453, +0.453, +1.510\}$，縮放後各除以 $\sqrt{d}$ CS:APP Problem 2.67 揭示位移量等於型別寬度時的未定義行為 (`1 << 32`)。此問題在位元打包中尤為相關：當 `bits` 等於或超過 `int` 寬度時，`1 << bits` 觸發 C99 6.5.7 §3 的未定義行為。 - [ ] Part 2: 完整的量化-反量化迴路 以下程式碼實作完整的 TurboQuant MSE 量化-反量化迴路 (簡化版)，結合 codebook 查表、3-bit 位元打包、L2 norm 保存與反量化重建。若只看控制流程，可以把它拆成先把浮點值對映到索引，再把索引塞進位元組陣列，最後再把索引還原回代表值三步。 Linux 核心的位元操作巨集定義於 [`include/linux/bitops.h`](https://github.com/torvalds/linux/blob/master/include/linux/bitops.h) 與 [`include/vdso/bits.h`](https://github.com/torvalds/linux/blob/master/include/vdso/bits.h)。`BIT(nr)` 巨集以 `UL(1) << (nr)` 取代 `1 << (nr)`，避免有號左移的未定義行為： ```c /* include/vdso/bits.h (節錄) */ #define BIT(nr) (UL(1) << (nr)) /* include/linux/bitops.h (節錄，經簡化) */ static inline void set_bit(int nr, volatile unsigned long *addr) { unsigned long mask = BIT(nr % BITS_PER_LONG); addr[nr / BITS_PER_LONG] |= mask; } static inline int test_bit(int nr, const volatile unsigned long *addr) { return 1UL & (addr[nr / BITS_PER_LONG] >> (nr % BITS_PER_LONG)); } ``` `set_bit` 和 `test_bit` 的邏輯與本題 `pack_indices` / `unpack_indices` 的逐位元操作完全對應：`nr / BITS_PER_LONG` 等同 `bp >> 3` (選取位元組)，`nr % BITS_PER_LONG` 等同 `bp & 7` (位元組內偏移)。差別在於 Linux 核心操作 `unsigned long` 陣列 (每元素 32 或 64 位元)，量化系統操作 `u8` 陣列 (每元素 8 位元)。本題刻意在 `pack_indices` 保留一處 `__B05__ << b`，讓學員直接面對「位移起點應為哪種型別」這個核心問題；`unpack_indices` 的 `(1 << bits)` 則保留作為遮罩推導題，讓位移風險與遮罩邏輯分開觀察。 量化流程 (Algorithm 1 of TurboQuant)： 1. 計算輸入向量的 L2 norm 並正規化 2. 以預計算的隨機正交矩陣旋轉 (此處簡化為 identity) 3. 對每個座標找最近的 codebook centroid，記錄索引 4. 將索引以 $b$-bit 打包至位元組陣列 其中第 3 步可視為把連續值換成離它最近的桶子編號，第 4 步則是把這些編號緊密排進位元流。Problem B 的填空主要都落在這兩步。 ```c #include #include #include typedef uint8_t u8; #define HEAD_DIM 128 #define BITS 3 /* 注意：論文的 codebook 是對 Beta 分布 f_X (Lemma 1) 求解 * Lloyd-Max 最佳化 (Eq. 4) 而得，centroid 值域在 [-1, 1] 且 * 隨維度 d 縮放 (近似 N(0, 1/d) 的 centroid)。以下值為 * 標準 N(0,1) 的近似 3-bit centroid，未經 1/sqrt(d) 縮放， * 僅作為位元打包教學範例使用。填空答案不受此簡化影響。 */ static const float CODEBOOK_3[8] = { -1.748f, -1.050f, -0.500f, -0.069f, 0.069f, 0.500f, 1.050f, 1.748f }; typedef struct { float norm; /* L2 norm (FP32) */ u8 indices[(HEAD_DIM*BITS+7)/8]; /* packed 3-bit indices */ } block_tq3; /* 打包：將 n 個 b-bit 索引寫入位元組陣列 */ static void pack_indices(const u8 *idx, u8 *packed, int n, int bits) { memset(packed, 0, (n * bits + 7) / 8); int bp = 0; for (int i = 0; i < n; i++) { for (int b = 0; b < bits; b++) { if (idx[i] & (__B05__ << b)) packed[bp >> 3] |= (1u << (bp & __B01__)); bp++; } } } /* 解包：從位元組陣列讀出 n 個 b-bit 索引 */ static void unpack_indices(const u8 *packed, u8 *idx, int n, int bits) { int bp = 0; u8 mask = (1 << bits) - __B02__; for (int i = 0; i < n; i++) { u8 val = 0; for (int b = 0; b < bits; b++) { if (packed[bp >> 3] & (1u << (bp & 7))) val |= (1u << b); bp++; } idx[i] = val & mask; } } void tq3_quantize(const float *src, block_tq3 *blk) { /* Step 1: L2 norm */ float norm_sq = 0.0f; for (int i = 0; i < HEAD_DIM; i++) norm_sq += src[i] * src[i]; float norm = sqrtf(norm_sq); blk->norm = norm; float inv_norm = (norm > 1e-15f) ? 1.0f / norm : 0.0f; /* Step 2: 正規化 + 最近 centroid 查表 */ u8 idx[HEAD_DIM]; for (int i = 0; i < HEAD_DIM; i++) { float y = src[i] * inv_norm; float best_dist = __builtin_huge_valf(); u8 best = 0; for (int c = 0; c < (1 << BITS); c++) { float d = (y - CODEBOOK_3[c]); d *= d; if (d < best_dist) { best_dist = d; best = (u8)c; } } idx[i] = best; } /* Step 3: 打包 */ pack_indices(idx, blk->indices, HEAD_DIM, BITS); } void tq3_dequantize(const block_tq3 *blk, float *dst) { u8 idx[HEAD_DIM]; unpack_indices(blk->indices, idx, HEAD_DIM, BITS); for (int i = 0; i < HEAD_DIM; i++) dst[i] = blk->norm * CODEBOOK_3[__B03__]; } ``` 填空說明： 打包的 `bp & __B01__` 計算位元在位元組內的偏移量。`bp >> 3` 選取目標位元組 (等同 `bp / 8`)，`bp & __B01__` 取得位元組內偏移 (等同 `bp % 8`)。學員須依 CS:APP Section 2.1.3 的位元遮罩性質推導：$x \bmod 2^k = x\ \&\ (2^k - 1)$，此處 $k = 3$。 解包的 `mask = (1 << bits) - __B02__`。$b$-bit 索引的有效值域為 $[0, 2^b - 1]$，遮罩須涵蓋低 $b$ 位元全為 1 的樣式。學員須依 CS:APP Section 2.1.3 推導 $(1 \ll b) - 1$ 產生 $b$ 個 1 位元的遮罩。 反量化的 `CODEBOOK_3[__B03__]` 以索引查表還原 centroid 值，再乘以 `norm` 還原尺度。此處 __ B03 __ 為第 $i$ 個座標的 codebook 索引變數。 `pack_indices` 中的 `__B05__ << b` 是本題刻意保留的風險點。若直接寫成 `1 << b`，會以有號 `int` 型別的 `1` 參與運算。本題 `bits = 3`，`b` 至多為 2，實際上不會溢位；但若泛化至 `bits = 31`，`1 << 31` 使 $1 \times 2^{31}$ 超出 32 位元 `int` 的可表示範圍 $[-2^{31}, 2^{31}-1]$，依 C99 6.5.7 §4 屬未定義行為 (CS:APP Problem 2.67)。因此 __ B05 __ 應填入無號常數，使左移在無號型別上執行。`unpack_indices` 的 `mask = (1 << bits) - __B02__` 則保留原貌，因為該處要先驗證學員是否能從 $(1 \ll b) - 1$ 正確推得低位元遮罩。 驗證 (打包/解包對稱性)：令 `idx = {5, 3, 7}`，bits $= 3$。以二進位表示：$5 = 101_2, 3 = 011_2, 7 = 111_2$。打包順序為 LSB-first per index，位元串依 `bit_pos` 遞增排列： ```text Index packing visualization (3-bit, LSB-first): [ MSB <------------------- Byte 0 ------------------- LSB ] Bit weight: 7 6 5 4 3 2 1 0 Byte 0 content: I2b1 I2b0 I1b2 I1b1 I1b0 I0b2 I0b1 I0b0 [ MSB <------------------- Byte 1 ------------------- LSB ] Bit weight: 7 6 5 4 3 2 1 0 Byte 1 content: 0 0 0 0 0 0 I2b2 - Index 0 = 5 = 101b -> bit positions 0,1,2 Index 1 = 3 = 011b -> bit positions 3,4,5 Index 2 = 7 = 111b -> bit positions 6,7,8 ``` | bit_pos | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---|---|---|---|---|---|---|---|---|---| | 來源 | 5 bit0 | 5 bit1 | 5 bit2 | 3 bit0 | 3 bit1 | 3 bit2 | 7 bit0 | 7 bit1 | 7 bit2 | | 值 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | * packed[0]：位元 [7:0] = `11011101` = `0x` __ B04 __ * packed[1]：位元 [8] = `00000001` = `0x01` 解包後應還原 `{5, 3, 7}`。此打包/解包構成 bijection (一對一映射)，每個 $3 \times \text{HEAD\_DIM} = 384$ 位元的位元串恰好對映一組 128 個 3-bit 索引，無歧義。 驗證 (量化誤差)：假設某座標正規化後 $y = 0.3$。最近 centroid 為 `CODEBOOK_3[5]` $= 0.500$，量化誤差 $= |0.3 - 0.5| = 0.2$。此誤差乘以 norm 後回到原始尺度：$\Delta = 0.2 \times \text{norm}$。TurboQuant 論文 Theorem 1 證明，3-bit MSE 量化的期望失真上界為 $D_{\text{mse}} \approx 0.03$。 驗證 (壓縮率)：原始向量 $128 \times 4 = 512$ 位元組。量化區塊：$4$ (norm) $+ 48$ (indices) $= 52$ 位元組。壓縮比 $= 512 / 52 \approx 9.8\times$。 延伸閱讀：位元操作錯誤屬 [CWE-682](https://cwe.mitre.org/data/definitions/682.html) (Incorrect Calculation)。Linux 核心自 2017 年起大規模將裝置驅動程式中的 `1 << N` 改為 `BIT(N)`，消除數百處有號位移未定義行為。UBSan 與 Coverity 持續偵測此類缺陷。[`include/linux/bitmap.h`](https://github.com/torvalds/linux/blob/master/include/linux/bitmap.h) 的 `bitmap_read()` / `bitmap_write()` 是本題 `pack_indices` / `unpack_indices` 在 Linux 核心中最直接的對應，處理跨 word 邊界的任意位元寬度讀寫。 位元寬度不足的風險同樣適用於引用計數。[CVE-2016-0728](https://nvd.nist.gov/vuln/detail/CVE-2016-0728) 是經典案例：`security/keys/keyring.c` 中 keyring 的引用計數以 `atomic_t` (本質為 `int`) 儲存，攻擊者透過反覆呼叫 `keyctl()` 系統呼叫使計數溢位歸零，觸發 premature free，進而達成 local privilege escalation。 此漏洞促使核心引入 [`include/linux/refcount.h`](https://github.com/torvalds/linux/blob/master/include/linux/refcount.h) 的 `refcount_t` 型別，取代裸 `atomic_t` 用於引用計數： ```c /* include/linux/refcount.h (節錄，經簡化) */ typedef struct refcount_struct { atomic_t refs; } refcount_t; static inline void refcount_inc(refcount_t *r) { int old = atomic_fetch_add_relaxed(1, &r->refs); if (unlikely(old < 0 || old + 1 < 0)) refcount_warn_saturate(r, REFCOUNT_ADD_OT_OVERFLOW); } ``` `refcount_t` 在每次增減時檢查溢位與 underflow，若偵測到異常則觸發 `WARN` 並將計數飽和 (saturate) 至安全值。此設計以明確的邊界檢查取代隱式假設，自 2016 年起核心中數千處 `atomic_inc` / `atomic_dec_and_test` 已轉換為 `refcount_inc` / `refcount_dec_and_test`，顯著降低 use-after-free 類漏洞的攻擊面。此案例直接延伸 CS:APP Section 2.3 的整數算術溢位討論。 HID (Human Interface Device) 子系統提供另一個經典案例。[`drivers/hid/hid-core.c`](https://github.com/torvalds/linux/blob/master/drivers/hid/hid-core.c) 的 `extract()` 函式從 HID report 中擷取任意位元寬度的欄位 (例如 3-bit 按鍵狀態接著 5-bit 填充)，手動處理位元組邊界的跨越，邏輯與本題的 `unpack_indices` 幾乎相同。HID 規範允許欄位以任意位元偏移排列，因此不能使用 C 的 bit-field (其記憶體配置為 implementation-defined)，必須如 CS:APP Section 2.1.3 所述以 shift/mask 手動操作。 Problem B 的 `pack_indices` / `unpack_indices` 以手動 shift/mask 操作位元，而非使用 C 語言的 bit-field。Linux 核心在網路協定標頭與硬體暫存器定義中採取相同策略，原因是 C 語言 bit-field 的記憶體配置為 implementation-defined (C99 6.7.2.1 §11)： * bit-field 在配置單元 (allocation unit) 中的排列方向 (高位元優先或低位元優先) 由實作決定 * 相鄰 bit-field 是否跨越配置單元邊界由實作決定 * 配置單元的大小由實作決定 [`include/uapi/linux/ip.h`](https://github.com/torvalds/linux/blob/master/include/uapi/linux/ip.h) 的 `struct iphdr` 是經典案例，以條件編譯處理 bit-field 順序： ```c struct iphdr { #if defined(__LITTLE_ENDIAN_BITFIELD) __u8 ihl:4, version:4; #elif defined(__BIG_ENDIAN_BITFIELD) __u8 version:4, ihl:4; #endif __u8 tos; __be16 tot_len; /* ... */ }; ``` 此做法的代價是每個含 bit-field 的結構都需要兩份定義。更現代的核心程式碼傾向完全避免 bit-field，改用明確的型別標記 (`__be16`、`__le32`) 搭配位元組序轉換巨集 (`cpu_to_be32()`、`le16_to_cpu()` 等，定義於 [`include/linux/byteorder/generic.h`](https://github.com/torvalds/linux/blob/master/include/linux/byteorder/generic.h))。Sparse 靜態分析工具 (`__CHECK_ENDIAN__`) 可在編譯時期偵測位元組序混用錯誤。 Problem B 的 `pack_indices` 採用 LSB-first 排列並以 `uint8_t` 為最小單元，天然為 endian-neutral：無論主機位元組序為何，`packed[bp >> 3]` 的語義不變。這與 Linux 核心 [`include/linux/bitmap.h`](https://github.com/torvalds/linux/blob/master/include/linux/bitmap.h) 的 `bitmap_read()` / `bitmap_write()` 不同，後者操作 `unsigned long` 陣列，在 big-endian 架構上需額外處理 word 內的位元組序。 C/C++ 標準將 bit-field 的記憶體配置、對齊與排列順序定義為 implementation-defined。依 Application Binary Interface 不同 (如 x86-64 的 System V ABI 與 AArch64 的 AAPCS)，編譯器可能從高位元或低位元開始填充，導致與硬體暫存器或網路協定互動時產生 endianness 不匹配。更嚴重的是，若二個 bit-field 共用同一個自然對齊的 word，從不同 CPU core 同時修改相鄰欄位可能引發 read-modify-write tearing，破壞並行安全性。因此 Linux 核心大量採用明確的 bitwise 操作搭配標準化 API。 `cpumask` 子系統追蹤各種拓撲下的 CPU core 狀態 (`cpu_online_mask`、`cpu_possible_mask`、`cpu_active_mask`)： ```c /* include/linux/cpumask.h (節錄) */ typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t; ``` `DECLARE_BITMAP` 巨集展開為精確以 `BITS_TO_LONGS` 除法 (向上取整至最近的 word 邊界) 計算大小的 `unsigned long` 陣列。對這些 mask 的操作使用 `set_bit()`、`clear_bit()`、`test_bit()` 等 atomic 或 non-atomic bitwise 函式，在並行 SMP 環境中提供跨平台的一致性與 atomics。此邏輯與 Problem B 的 `pack_indices` / `unpack_indices` 逐位元操作完全對應。 `struct page` 則展示核心中最極端的位元打包案例。實體記憶體被分割為個別 page，每個 page 以一個 `struct page` 描述子表示。由於典型系統中存在數百萬個 page，`struct page` 每增加一個位元組就會浪費數 GiB 的 RAM。核心將大量狀態資訊塞入結構頂端的單一 `unsigned long flags;` 欄位，此 word 被多工 (multiplex) 以容納： * Page 狀態旗標 > 個別位元指示 page 是否 dirty、locked、處於 writeback、或正參與 LRU 串列。 * Zone 與 Node ID > Non-Uniform Memory Access (NUMA) 節點與記憶體 zone 資訊。 * Section 細節 > 啟用特定功能時，資料透過 inline 函式與位移操作動態對映至既有結構空間，在不破壞 ABI 的前提下擷取精確的 mask。 核心提供 [`include/linux/packing.h`](https://github.com/torvalds/linux/blob/master/include/linux/packing.h) API，讓開發者穩健地擷取與打包自訂位元欄位，避免編譯器特定的填充與對齊假設。此 API 與 Problem B 的 `pack_indices` / `unpack_indices` 在概念上直接對應，皆以手動 shift/mask 操作確保位元配置的可預測性。 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)實作 ([`include/linux/rbtree_types.h`](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_types.h)) 展示另一種位元打包策略，將指標與旗標欄位合併至單一 word，與本題量化索引打包在概念上相通。以下程式碼取自 Linux 核心，以填空形式測驗學員對位元打包、指標對齊與 C 語言規格的理解： ```c /* include/linux/rbtree_types.h (節錄) */ struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); #define RB_RED 0 #define RB_BLACK 1 ``` `__rb_parent_color` 將 parent 指標與節點顏色 (紅/黑) 打包至一個 `unsigned long`。`__attribute__((aligned(sizeof(long))))` 強制每個 `rb_node` 對齊至 `sizeof(long)` 邊界 (32 位元系統為 4 位元組、64 位元系統為 8 位元組)，確保任何合法 `rb_node *` 位址的低 2 位元恆為零。Linux 核心利用 bit 0 儲存顏色，高位元儲存 parent 指標： ``` __rb_parent_color 的位元配置: MSB 2 1 0 ┌────────────────────────────────────────────┬───┬───┐ │ parent pointer (高位元) │ 0 │ C │ └────────────────────────────────────────────┴───┴───┘ bit 2 以上：parent 指標 ▲ (對齊保證低 2 位元為 0) color: 0=RED, 1=BLACK ``` 擷取 parent 指標與設定 parent/color 的操作 ([`include/linux/rbtree.h`](https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h)、[`include/linux/rbtree_augmented.h`](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_augmented.h))： ```c /* 擷取 parent 指標：清除低 2 位元 */ #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & __B06__)) /* 設定 parent 與 color */ static inline void rb_set_parent_color(struct rb_node *rb, struct rb_node *p, int color) { rb->__rb_parent_color = (unsigned long)p + color; } /* 新節點連結 (隱含初始顏色為紅色，因為對齊指標 bit 0 = 0 = RB_RED) */ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) { node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL; *rb_link = node; } ``` 填空 __ B06 __ 為 `rb_parent()` 的遮罩，須清除 bit 0 和 bit 1 以還原對齊指標。學員須依 CS:APP Section 2.1.3 推導：`~3` 在 C 語言中以 `int` 型別表示為 `...11111100`，但在與 `unsigned long` 做 `&` 運算時，依 C99 6.3.1.8 的 usual arithmetic conversions 隱式轉為 `unsigned long`，所有高位元補 1。填空仍以最精簡的 C 運算式作答，canonical form 為 `~3`。若從核心實作習慣出發，`~3UL` 更能直接表達「此遮罩工作在 unsigned long 寬度」；本題刻意保留 `~3` 作答，是為了先驗證學員是否理解 usual arithmetic conversions 的補寬過程。 `rb_set_parent_color` 使用 `+` 而非 `|`。二者在此等價，因為對齊指標低位元為零，加上 0 或 1 不會進位至 bit 2。這是 CS:APP Section 2.3 的無號算術性質：當加數的非零位元不重疊時，加法與 OR 結果相同。 `rb_link_node` 中 `node->__rb_parent_color = (unsigned long)parent` 將新節點隱式著色為紅色 (RED=0)，因為對齊指標的 bit 0 恆為 0，不需額外設定顏色。此設計呼應紅黑樹插入時新節點預設為紅色的性質。 驗證：令 `parent = (struct rb_node *)0x7FFE0040` (低 2 位元為 0，符合對齊)，`color = RB_BLACK (1)`。呼叫 `rb_set_parent_color(node, parent, 1)` 後，`node->__rb_parent_color = 0x7FFE0040 + 1 =` `0x` __ B07 __。隨後 `rb_parent(node)` 回傳 `(struct rb_node *)(0x7FFE0041 & ~3) = (struct rb_node *)0x7FFE0040`，正確還原 parent 指標。 此技巧涉及的 C 語言規格與效能議題： * 指標與整數的轉換 (C11 6.3.2.3 §5-6) 屬 implementation-defined behavior。C 標準僅保證 `uintptr_t` (C11 7.20.1.4) 可無損保存指標值，不保證 `unsigned long` 亦可。Linux 核心在其支援的平面位址空間 (flat address space) 架構上額外假設 `(unsigned long)ptr` 可保留並還原位址資訊，此假設由 GCC 與 Linux 核心的型別系統共同保證 (`sizeof(unsigned long) == sizeof(void *)`) * `__attribute__((aligned(sizeof(long))))` 是 GCC 擴展 (extension)，強化結構體的對齊需求。C 標準 (C11 6.2.8) 僅規定對齊值為 implementation-defined 的 2 的冪，不保證特定值。Linux 核心原始碼的註解指出，CRIS 架構是最初促使加入此強制對齊的原因 * `__rb_change_child()` 以 `WRITE_ONCE()` 更新子節點指標，防止編譯器將指標寫入拆分為多次 store 或最佳化消除。此巨集在 [`include/asm-generic/rwonce.h`](https://github.com/torvalds/linux/blob/master/include/asm-generic/rwonce.h) 以 `volatile` 語義實作，約束編譯器對該存取產生單次 C 語言層級的寫入，對自然對齊且大小在架構支援範圍內的存取可防止 store tearing，確保與 RCU (Read-Copy-Update) 讀取端的正確配對。ISO C 的 `volatile` 語義 (C11 6.7.3 §7) 僅保證對 volatile 物件的存取不被最佳化消除，但不保證存取的 atomics 或排序。Linux 核心的 `WRITE_ONCE` / `READ_ONCE` 在此基礎上搭配編譯器屏障 (`barrier()`)，提供比 ISO C `volatile` 更精確的語義 除了在低位元塞入顏色旗標，核心也把錯誤碼編進不可能為合法指標的位址區段。[`include/linux/err.h`](https://github.com/torvalds/linux/blob/master/include/linux/err.h) 定義的 `ERR_PTR` / `IS_ERR` / `PTR_ERR` 三件組將 errno 值編碼在指標的高位元區段。 ```c /* include/linux/err.h (節錄，經簡化) */ #define MAX_ERRNO 4095 #define IS_ERR_VALUE(x) unlikely((unsigned long)(void *)(x) >= (unsigned long)-MAX_ERRNO) static inline void * ERR_PTR(long error) { return (void *) error; } static inline long PTR_ERR(const void *ptr) { return (long) ptr; } static inline bool IS_ERR(const void *ptr) { return IS_ERR_VALUE((unsigned long)ptr); } ``` 此設計利用 Linux 核心虛擬位址空間的頂端 4095 位元組 ($-1$ 至 $-4095$) 在所有支援的架構上永遠不會是合法的核心指標 (此區域為保留位址範圍)，因此可安全地將這些值重新詮釋為錯誤碼。`IS_ERR` 的判斷以無號比較 `>= (unsigned long)-MAX_ERRNO` 實作，等同檢查指標值是否落在 `[0xFFFFF001, 0xFFFFFFFF]` (32 位元) 或對應的 64 位元區間。這與 Problem B 的 `rb_parent()` 遮罩在概念上對稱：後者從低位元擷取額外資訊 (顏色)，前者從高位元區段擷取額外資訊 (errno)。 此機制使核心函式以單一指標回傳值同時傳遞成功結果 (合法指標) 與失敗原因 (錯誤碼)，避免額外的 out-parameter 或全域 `errno` 變數。呼叫端的典型模式為： ```c struct inode *inode = iget_locked(sb, ino); if (IS_ERR(inode)) return PTR_ERR(inode); /* 傳播錯誤碼 */ ``` 若未檢查 `IS_ERR` 而直接解參考回傳的指標，會觸發 kernel oops (存取非法位址)。Sparse 靜態分析工具以 `__must_check` 標註強制呼叫端檢查回傳值。此模式與 CS:APP Section 2.2.4 的 signed/unsigned 轉換直接相關：`ERR_PTR(-ENOMEM)` 將負的 `long` 轉為 `void *`，`PTR_ERR` 再轉回 `long`，整個迴路依賴 two's complement 表示法在 signed/unsigned 間的位元保持性質。 快取與記憶體配置：相較於將 `parent`、`left`、`right`、`color` 分開儲存 (4 欄位，64 位元系統需 32 位元組含填充)，打包後僅 3 欄位 (24 位元組)，每個節點省 8 位元組 (25%)。在 64 位元組的 cache line 上，packed 版可容納 2 個節點加部分第 3 個 ($24 \times 2 = 48$，剩 16 位元組放第 3 個節點的 `__rb_parent_color` 與 `rb_right`)。CFS 排程器的每個 task 的 `sched_entity` 內嵌 `rb_node`，伺服器或容器化環境中 $n$ 可達數千至數萬，$n = 10000$ 時省下 80 KB；加上 netfilter 規則集 ([`nft_set_rbtree`](https://github.com/torvalds/linux/blob/master/net/netfilter/nft_set_rbtree.c))、I/O 排程器、`procfs` ([`fs/proc/generic.c`](https://github.com/torvalds/linux/blob/master/fs/proc/generic.c)) 等使用處，節省量與系統複雜度成正比。歷史上 VMA 管理亦以 augmented rbtree 追蹤位址區間，Linux v6.1 起已改用 maple tree 取代。 Linux 核心以 augmented 紅黑樹搭配雙向鏈結串列管理每個行程的虛擬定址空間 (`vm_area_struct`)。紅黑樹提供 $O(\log n)$ 的搜尋、插入與刪除，核心實作以侵入式設計 (`rb_node` 內嵌於資料結構) 消除一層指標間接存取，改善 CPU 快取局部性。為對映至 order-4 B-tree 表示，紅黑樹強制 black height 一致與相鄰連結顏色交替的不變式，確保最長路徑不超過最短路徑的兩倍。 然而，隨著 CPU core 數量指數成長，紅黑樹設計暴露出記憶體管理子系統的嚴重可擴充性瓶頸： * 快取效率不足 > 紅黑樹為二元樹，樹高相對較深，走訪過程中產生大量 cache line miss。 * lock contention > 依序走訪節點需透過紅黑樹與輔助鏈結串列，須以寫入模式持有高度爭搶的 `mmap_sem` (現為 `mmap_lock`)。 Linux v6.1 引入 [Maple Tree](https://docs.kernel.org/core-api/maple_tree.html) 取代紅黑樹，這是種 RCU-safe (Read-Copy-Update) 的 range-based B-tree 變體，專為現代處理器快取架構設計： * 分支因子與密度 > VMA 管理使用的 allocation node (`maple_arange_64`) 非葉節點分支因子為 10，葉節點為 16。一般 Maple 節點的葉節點與非葉節點分支因子皆為 16。相較二元樹，樹高大幅降低，CPU 可將大量連續索引資料拉入 L1/L2 快取，有效減少 cache miss。 * 無鎖走訪 > Maple Tree 為 RCU-safe，特定讀取端路徑 (如 page fault 處理中的 VMA 查詢) 無需取得 `mmap_lock` 即可走訪結構。此無鎖特性適用於 RCU 讀取端臨界區段內的唯讀走訪，寫入端仍需持有適當的鎖。 * 消除輔助結構 > Maple Tree 淘汰並移除 augmented 紅黑樹、雙向鏈結串列 (`vm_next` 與 `vm_prev`)、以及 VMA 快取。迭代改以狀態機 (`struct ma_state`) 與 `vma_iterator` API 實作。 此架構轉換並非毫無風險。過渡期間引入 "StackRot" 漏洞 ([CVE-2023-3269](https://nvd.nist.gov/vuln/detail/CVE-2023-3269)，影響 Linux 6.1 至 6.4)，這是一個 Use-After-Free-By-RCU (UAFBR) 缺陷：在 stack 擴充期間，Maple Tree 可能在未正確取得 MM write lock 的情況下進行節點替換。由於 Maple 節點以 RCU callback 釋放記憶體，實際解除配置延遲至 RCU grace period 之後，使精心設計的 local privilege escalation exploit 得以操縱記憶體管理子系統。 此案例展示硬體特性如何主導軟體資料結構設計：Maple Tree 以高分支因子換取快取效率，與 TurboQuant 以 data-oblivious codebook 換取 accelerator-friendly 執行路徑的思路一致。非同步記憶體釋放 (RCU) 引入的新型安全風險亦值得關注。 [CVE-2023-53566](https://nvd.nist.gov/vuln/detail/CVE-2023-53566) 涉及 `nft_set_rbtree` 的節點插入與 garbage collection 路徑：插入時可能觸發 null dereference，GC 走訪時未正確快取下一節點導致 use-after-free，說明紅黑樹操作的正確性對系統安全至關重要。 Problem B 的紅黑樹將 `rb_node` 內嵌於 `sched_entity` 等結構，核心透過 [`container_of`](https://github.com/torvalds/linux/blob/master/include/linux/container_of.h) 巨集從 `rb_node *` 反推外層結構位址。此巨集仰賴 `offsetof` (C99 7.17)： ```c /* include/linux/container_of.h (節錄，經簡化) */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ ((type *)(__mptr - offsetof(type, member))); }) ``` `offsetof` 產生編譯時期常數，計算成員在結構中的位元組偏移。此技巧與 Problem B 的位元打包概念互補：後者在單一 word 中塞入額外資訊 (指標 + 顏色)，前者從嵌入的子結構還原外層容器。二者皆依賴對記憶體配置的精確控制。 侵入式設計的優勢在於零額外記憶體配置：`rb_node` 直接佔用外層結構的空間，不需另行 `kmalloc` 節點容器。缺點是物件生命週期管理更困難：若內嵌節點所屬的外層結構已被釋放，殘留的指標透過 `container_of` 會計算出指向已釋放記憶體的位址，導致 use-after-free。前述 [CVE-2023-53566](https://nvd.nist.gov/vuln/detail/CVE-2023-53566) 即屬此類：`nft_set_rbtree` 的 garbage collection 路徑在走訪期間呼叫 `rb_prev()` 可能回傳 `NULL`，且未在釋放目前節點前快取下一個節點，導致 null dereference 或 use-after-free。修正方式為在 GC 迴圈中先以 `rb_prev()` 取得前一節點並快取，再對目前節點執行移除操作，確保迭代器不指向已釋放的記憶體。 Linux 核心的所有侵入式資料結構 (`list_head`、`hlist_node`、`rb_node`、`maple_node`) 皆依賴此模式，約有數千處 `container_of` 呼叫。與 C++ 的 `std::set` 等外部容器相比，侵入式設計避免每次插入的額外 heap allocation，降低記憶體碎片化並改善快取局部性。 紅黑樹的高度上界 $h \leq 2\log_2(n+1)$ 保證 $n$ 個節點的搜尋、插入、刪除皆為 $O(\log n)$，且插入至多 2 次旋轉、刪除至多 3 次旋轉。此確定性旋轉次數上界使 worst-case 延遲可預測，是 Linux 核心選擇紅黑樹 (而非高度更緊的 AVL 樹，$h \leq 1.44\log_2(n+2)$) 的考量之一。紅黑樹與 TurboQuant 的共同設計哲學在於可證明的上界：前者以 $2\log_2(n+1)$ 控制動態資料結構的更新成本，後者以 $D_{\text{mse}} \leq \frac{\sqrt{3}\pi}{2} \cdot \frac{1}{4^b}$ (Theorem 1) 控制量化誤差。二者皆透過數學分析給出確定性的品質保證，而非依賴啟發式 (heuristic) 的平均表現。 對 TurboQuant 的典型 codebook ($2^b$ 個 centroid，$b \in \{2, 3, 4\}$)，最佳資料結構不是紅黑樹，而是固定大小陣列搭配 branchless 線性掃描。在 $2^b \leq 16$ 的場景下，陣列查表充分利用 CPU 快取與 SIMD 向量化，符合 TurboQuant 論文強調的 accelerator-friendly 設計。 ### 延伸問題 * `pack_indices` 的逐位元操作對應 Section 2.1.3 的 bitwise operations，`rb_parent()` 的遮罩 `~3` 對應 $x\ \&\ (2^k - 1)$ 的位元遮罩性質。以此為出發點： * (a) 閱讀 [`include/linux/bitmap.h`](https://github.com/torvalds/linux/blob/master/include/linux/bitmap.h) 的 `bitmap_read()`/`bitmap_write()`，追蹤跨 `unsigned long` word 邊界的讀寫邏輯。與 `pack_indices` 比較：後者逐位元迭代 ($128 \times 3 = 384$ 次分支)，`bitmap_read()` 以 word 為單位操作 ($\approx 6$ 次 word 存取)。閱讀 [`drivers/hid/hid-core.c`](https://github.com/torvalds/linux/blob/master/drivers/hid/hid-core.c) 的 `extract()`，比較 HID report 欄位擷取的跨位元組邊界處理 * (b) 若 `BITS` 恰為 2、4 或 8，索引欄位可整齊切分位元組。設計一版以 byte 或 word 為單位搬移的 `pack_indices`，比較其與逐位元版本在分支數、記憶體存取次數與可讀性上的差異，並說明為何核心在 hot path 常偏好 aligned access * \(c) `struct page` 的 `flags` 將 node ID、zone ID、page flags 以 shift/mask 打包至一個 `unsigned long`。閱讀 [`include/linux/page-flags-layout.h`](https://github.com/torvalds/linux/blob/master/include/linux/page-flags-layout.h)，追蹤 `NODES_SHIFT`、`ZONES_SHIFT` 如何依 `CONFIG_*` 在編譯時期計算位元配置。從 C99 6.7.2.1 §11 (bit-field 配置為 implementation-defined) 說明核心為何不用 bit-field。此固定位元預算與 `block_tq3` 的空間約束相同 * (d) `rb_set_parent_color` 以 `+` 而非 `|` 合併指標與顏色 (Section 2.3 的無號算術)。從 $\mathbb{Z}/2^{64}\mathbb{Z}$ 證明：$a$ 低 $k$ 位元為零且 $b < 2^k$ 時 $a + b = a \lor b$。閱讀 [`include/linux/rbtree_augmented.h`](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_augmented.h) 的 `__rb_rotate_set_parents()`，追蹤旋轉中 parent/color 的更新。對比 [`include/linux/err.h`](https://github.com/torvalds/linux/blob/master/include/linux/err.h) 的 `ERR_PTR`：前者在低位元夾帶資訊 (對齊保證)，後者在高位元夾帶 errno (保留位址範圍)。分析若 slab corruption 破壞 `rb_node` 對齊，`+` 產生進位如何破壞 parent 指標 * [CVE-2023-3269](https://nvd.nist.gov/vuln/detail/CVE-2023-3269) (StackRot) 與 [CVE-2023-53566](https://nvd.nist.gov/vuln/detail/CVE-2023-53566) (`nft_set_rbtree`) 展示紅黑樹與 Maple Tree 的並行安全風險。以此為出發點： * (a) 閱讀 [`include/linux/maple_tree.h`](https://github.com/torvalds/linux/blob/master/include/linux/maple_tree.h) 的 `maple_arange_64` 節點結構。VMA 管理使用分支因子 10 (非葉) / 16 (葉) 的 Maple Tree，$n = 10000$ 時樹高 $\leq 4$，紅黑樹 $\leq 2\log_2(10001) \approx 27$。以 L2 miss penalty $\approx 10$ ns 估算此差異對 page fault VMA 查詢延遲的影響，並說明此估算隱含每層至少一次指標追逐與一次快取未命中的假設 * (b) StackRot 的根因：`expand_stack()` 未持有 MM write lock 即修改 Maple Tree，舊節點以 `call_rcu()` 延遲釋放，RCU grace period 結束後殘留指標成為 dangling pointer。閱讀 [`include/linux/rcupdate.h`](https://github.com/torvalds/linux/blob/master/include/linux/rcupdate.h)，說明 RCU 不變式如何被違反。此 UAFBR 比傳統 UAF 更難偵測：物件存活狀態依全域 grace period 時序而定，非局部可判定 * \(c) CVE-2023-53566 中 `nft_set_rbtree` GC 走訪時未在 `kfree` 前快取 `rb_prev()`，致 `container_of` 推算出無效位址。侵入式資料結構的 `container_of` 前提是 `rb_node` 所屬物件仍存活，這點可與 `unpack_indices` 的 bijection 類比：底層記憶體無效時，解碼仍可能成功，但結果無意義。設計正確的 GC 走訪虛擬碼，明確寫出先快取迭代器、再 unlink、最後釋放節點的順序 --- ## Problem C: 型別雙關、sign hash 與浮點算術性質 > 延伸 CS:APP Practice Problem 2.54 / Section 2.4.5 (Floating-Point Operations) / Section 2.2.6 / Figure 2.33 題目設計要點： * 本題把三類常見陷阱放在同一條線上看：浮點非結合性、有號/無號混算，及 sign hash 的幅值補償 * 作答時不需重建 QJL 全部證明，只要掌握先投影、再保留正負號、最後按比例補回幅值的流程 * 延伸問題刻意導向 RTT 平滑、EWMA、`jiffies` 與雜湊等核心內部設計，讓數值性質對應到核心程式碼 - [ ] Part 1: 浮點算術性質與量化 CS:APP Section 2.4.5 指出浮點算術不滿足結合律。以 single-precision 為例： ``` (3.14 + 1e10) - 1e10 → 0.0 3.14 + (1e10 - 1e10) → 3.14 ``` Practice Problem 2.54 要求判斷以下運算式是否恆成立 (假設 `x` 為 `int`，`f` 為 `float`，`d` 為 `double`，且 `f`, `d` 非 NaN/∞)： * `x == (int)(double) x`：恆真，因為 32-bit int 可精確表示為 `double` 的 52-bit fraction * `x == (int)(float) x`：非恆真，反例為 $x = 2^{24} + 1$，`float` 的 23-bit fraction 不足以精確表示 * `d == (double)(float) d`：非恆真，`float` 精度低於 `double` * `f == -(-f)`：恆真，IEEE 754 的 negation 僅翻轉 sign bit，不損失精度 * `(f+d) - f == d`：非恆真，浮點加法不滿足結合律，cancellation 損失精度 CS:APP Section 2.2.6 討論有號與無號整數的轉換規則。C99 6.3.1.8 定義的 usual arithmetic conversions 規定：當 `int` 與 `unsigned` 運算元出現在同一運算式中，`int` 先轉換為 `unsigned` 再進行運算。此規則在混合型別的位元操作中尤為重要。 這些性質直接影響向量量化的正確性： * quantize-dequantize 迴路的往返誤差 (round-trip error) 類似 `x == (int)(float) x` 的精度損失 * 浮點加法的非結合性意味著內積 $\sum x_i y_i$ 的累加順序會影響結果精度 * TurboQuant 的 QJL 以 $\sqrt{\pi/2}$ scale factor 補償 sign 函式的幅值損失，使內積估計滿足無偏性 $\mathbb{E}[\langle y, \hat{x} \rangle] = \langle y, x \rangle$ (Lemma 4) - [ ] Part 2: QJL sign hash 量化與內積估計 TurboQuant 的 inner product quantizer (Algorithm 2) 採兩階段壓縮。第一階段先用 $(b-1)$-bit MSE quantizer (Problem B) 壓縮向量的大致形狀；第二階段再對剩下的誤差，也就是殘差 (residual)，施加 1-bit QJL sign hash。直觀上，可把它理解成先做一個粗略版本，再用很便宜的額外資訊補回內積估計最在意的部分。反量化時把兩部分相加，就能得到 inner product estimator。完整的 Algorithm 2 管線已在前述背景中以圖示呈現。 以下程式碼單獨實作 QJL 的 sign hash 與內積估計環節 (Algorithm 2 的第二階段)，不包含 MSE 量化部分 (已在 Problem B 實作)。hash 函式以確定性 Rademacher 投影避免儲存完整的 $d \times d$ 投影矩陣，僅需 $O(1)$ 額外空間。讀程式碼時，建議把它拆成兩段：`qjl_quantize()` 負責把每個投影方向壓成一個 sign bit，`qjl_inner_product()` 則把這些 sign bit 重新解讀成對內積的近似。 Linux 核心中與此型別雙關技巧相關的實作見 [`include/linux/swab.h`](https://github.com/torvalds/linux/blob/master/include/linux/swab.h)，其 `__swab32` 在早期版本以 `union` 在 `__u32` 與 4 個 `__u8` 之間轉換位元組序，現代核心已改用 `__builtin_bswap32` 或輔助函式實作。Linux 核心的 [`include/linux/average.h`](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 定義的 `DECLARE_EWMA` 巨集則展示另一種數值壓縮策略，以無號定點數搭配明確精度參數儲存指數加權移動平均值，用於 TCP RTT 平滑與無線訊號強度估計。 此技巧在 TCP RTT 估計中扮演關鍵角色。Jacobson/Karels 演算法 (1988, [RFC 6298](https://datatracker.ietf.org/doc/html/rfc6298)) 以定點右移取代浮點乘法： ```c /* net/ipv4/tcp_input.c (節錄，經簡化) */ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us) { struct tcp_sock *tp = tcp_sk(sk); long m = mrtt_us; long srtt = tp->srtt_us; if (srtt != 0) { m -= (srtt >> 3); /* m = 量測值 - srtt/8 */ srtt += m; /* srtt = srtt + (量測值 - srtt)/8 */ /* = 7/8 * srtt + 1/8 * 量測值 */ /* ... mdev (mean deviation) 計算省略 ... */ } else { srtt = m << 3; /* 首次量測：srtt = 量測值 * 8 */ } tp->srtt_us = max(1U, srtt); } ``` `srtt_us` 以 8 倍放大儲存 (即 3 位元定點小數)，避免浮點除法。`>> 3` 等同乘以 $1/8$，平滑因子 $\alpha = 1/8$ 為 2 的冪，使指數平滑完全以整數位移實作。此設計與 TurboQuant 的 $\sqrt{\pi/2}$ scale factor 概念相通：二者皆以確定性的數學轉換補償資訊壓縮帶來的幅值偏差，前者補償定點截斷損失，後者補償 sign 函式對幅值的損失。 [`include/linux/average.h`](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 的 `DECLARE_EWMA` 巨集將此模式泛化： ```c /* include/linux/average.h (節錄，經簡化) */ #define DECLARE_EWMA(name, _precision, _weight_rcp) \ struct ewma_##name { \ unsigned long internal; \ }; \ static inline void ewma_##name##_add( \ struct ewma_##name *e, unsigned long val) { \ unsigned long internal = READ_ONCE(e->internal); \ unsigned long weight_rcp = ilog2(_weight_rcp); \ unsigned long precision = _precision; \ if (internal) { \ internal = internal - \ (internal >> weight_rcp) + \ (val << precision >> weight_rcp); \ } else { \ internal = val << precision; \ } \ WRITE_ONCE(e->internal, internal); \ } ``` `_precision` 指定定點小數位元數 (類似 `srtt_us` 的 3 位元)，`_weight_rcp` 為平滑因子的倒數 (必須為 2 的冪)。無線訊號強度 (RSSI) 估計 ([`net/mac80211/rx.c`](https://github.com/torvalds/linux/blob/master/net/mac80211/rx.c)) 以 `DECLARE_EWMA(rssi, 10, 16)` 定義 10 位元精度、$\alpha = 1/16$ 的平滑器，用於判斷漫遊 (roaming) 時機。磁碟 I/O 延遲統計 ([`block/blk-wbt.c`](https://github.com/torvalds/linux/blob/master/block/blk-wbt.c)) 以類似的 EWMA 追蹤寫入延遲，當延遲超過閾值時啟動寫入節流 (write-back throttling)，防止 buffered write 淹沒儲存裝置。 定點數算術的風險在於精度累積誤差。若 `_precision` 不足，長期執行的 EWMA 會因反覆右移截斷而趨向零 (定點 underflow)。`DECLARE_EWMA` 以 `unsigned long` 儲存，在 64 位元系統上提供 64 位元寬度，但若 `val` 的有效位元數與 `_precision` 之和超過型別寬度，`val << precision` 仍可能溢位。此限制與 Problem A 的 FP16 精度上限 ($2^{11} + 1 = 2049$ 為不可精確表示的最小正整數) 呼應：有限位元寬度下，數值表示的精度與範圍互相制約。 TurboQuant 論文 Definition 1 定義 QJL 使用 i.i.d. Gaussian 投影矩陣 $S_{i,j} \sim \mathcal{N}(0,1)$： $$Q_{\text{qjl}}(x) := \text{sign}(S \cdot x), \quad Q_{\text{qjl}}^{-1}(z) := \frac{\sqrt{\pi/2}}{d} \cdot S^\top \cdot z$$ Lemma 4 在 Gaussian $S$ 的假設下證明此估計器是 unbiased 的：$\mathbb{E}[\langle y, Q_{\text{qjl}}^{-1}(Q_{\text{qjl}}(x))\rangle] = \langle y, x \rangle$。以下實作以確定性 Rademacher 投影 ($\pm 1$) 近似 Gaussian $S$，犧牲嚴格的無偏性保證以換取 $O(1)$ 空間 (不需儲存完整的投影矩陣)。此近似在高維度下表現良好，因為 Rademacher 與 Gaussian 投影的 [Johnson-Lindenstrauss 性質](https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) 漸近等價。scale factor $\sqrt{\pi/2}$ 仍用於補償 sign 函式對幅值的損失。 ```c #include #include #include typedef uint32_t u32; typedef uint8_t u8; #define BIT(nr) (1u << (nr)) #define DIM 128 #define SDIM 256 /* sketch 維度，可大於 DIM 以降低 variance */ /* 確定性 Rademacher 投影：以 Knuth's multiplicative hash 常數 * 2654435761u 混合索引；此值近似 2^32 / phi，與 2^32 互質， * 在 32-bit 空間上能提供良好的均勻分布與 bit diffusion。 * 注意：這裡混合了 signed/unsigned 運算，需留意隱式型別轉換。 */ static float rademacher(int dim, int sketch) { u32 h = (u32)(dim * 2654435761u + sketch * 340573321u); h ^= h >> 16; h *= 0x45d9f3b; h ^= h >> 16; return (h & 1) ? 1.0f : -1.0f; } /* 量化：計算 sign hash */ void qjl_quantize(const float *x, u8 *hash, int d) { memset(hash, 0, SDIM / 8); for (int s = 0; s < SDIM; s++) { float proj = 0.0f; for (int i = 0; i < d; i++) proj += x[i] * rademacher(i, s); if (proj >= 0.0f) hash[s >> 3] |= BIT(s & 7); } } /* 以 sign hash 估計 內積 */ float qjl_inner_product(const float *query, const u8 *key_hash, float key_norm, int d) { /* QJL scale = 1 / E[|Z|] / SDIM, where E[|Z|] = sqrt(2/pi) for Z ~ N(0,1) */ float scale = key_norm / (sqrtf((float)M_2_PI) * (float)SDIM); float sum = 0.0f; for (int s = 0; s < SDIM; s++) { /* 將 key 的 sign bit 還原為 ±1 */ float key_sign = (key_hash[s >> 3] & BIT(s & 7)) ? 1.0f : __C01__; /* 計算 query 在第 s 個投影方向上的分量 */ float q_proj = 0.0f; for (int i = 0; i < d; i++) q_proj += query[i] * rademacher(i, s); sum += q_proj * key_sign; } return scale * sum; } ``` 填空說明： QJL 的反量化 scale factor 為 $\sqrt{\pi/2}$，用於補償 sign 函式丟失幅值資訊的效應。此因子的來源是 half-normal 分布：對 $Z \sim \mathcal{N}(0,1)$，$\mathbb{E}[|Z|] = \sqrt{2/\pi}$。sign 函式將幅值壓為 $\pm 1$，平均損失 $\mathbb{E}[|Z|]$ 倍的幅值。反量化時需除以此期望值以補償，即乘以 $1/\mathbb{E}[|Z|] = 1/\sqrt{2/\pi} = \sqrt{\pi/2}$。程式碼以 `key_norm / (sqrtf((float)M_2_PI) * (float)SDIM)` 實作此補償，其中 `M_2_PI` 是 `` 定義的常數 $2/\pi$，`sqrtf((float)M_2_PI)` 即 $\sqrt{2/\pi} = \mathbb{E}[|Z|]$。 key 的 sign bit 為 0 時對應 $-1$ (QJL 以 $\{-1, +1\}$ 而非 $\{0, 1\}$ 編碼方向)。__ C01 __ 為此負值的浮點常數。 `rademacher()` 中的 `dim * 2654435761u`：`dim` 為 `int`，`2654435761u` 為 `unsigned` 常數。此常數來自 Knuth 的 multiplicative hash，可視為 $2^{32}/\varphi$ 的整數近似，目的不是隨機亂選，而是利用黃金比例乘法在有限字寬下提供良好的 bit diffusion。依 C99 6.3.1.8 的 usual arithmetic conversions (CS:APP Section 2.2.6)，`dim` 先轉為 __ C02 __ 型別再進行乘法，結果亦為該型別 (填空以最短型別拼寫作答：`unsigned`；`unsigned int` 為同義詞，亦可接受)。此隱式轉換將有號值以模 $2^{32}$ 算術重新詮釋為無號值。當 `dim` 為非負值時數值不變，但當 `dim` 為負值時，轉換後會先變成一個很大的無號值，再參與乘法與 XOR-shift 混合。`d` 與 `SDIM` 在本題語境都應是非負且小於陣列長度的維度參數；若上游誤把負值傳入維度參數，這段程式未必立刻 crash，卻會產生型別正確但語義錯誤的 hash，正是 signed/unsigned 混算最危險的地方。 驗證 (內積估計)：令 $x = (1, 0, 0, \ldots)$，$y = (1, 0, 0, \ldots)$，真實內積 $\langle x, y \rangle = 1$。在此退化情況下，每個 sketch 維度的 `q_proj` $= \text{rademacher}(0, s)$，`key_sign` $= \text{sign}(\text{rademacher}(0, s))$。因為 $\text{rademacher} \in \{-1, +1\}$，乘積恆為 1，sum $= \text{SDIM}$，估計值 $= \sqrt{\pi/2} \approx 1.253$。此系統性偏差源於 Rademacher 投影與 Lemma 4 假設的 Gaussian 投影之差異：Gaussian $S_{i,j}$ 的幅值服從 half-normal 分布，期望值恰為 $\sqrt{2/\pi}$，使 $\sqrt{\pi/2}$ 的 scale factor 精確補償；Rademacher 投影的幅值恆為 1，無法被同一常數精確補償。在高維度且向量分量均勻分散 (非退化) 的場景下，中央極限定理使 `proj` 的分布趨近 Gaussian，此偏差大幅縮減。實務上以大量 sketch 維度 (SDIM) 降低 variance，內積估計的相對誤差隨 $1/\sqrt{\text{SDIM}}$ 衰減。 驗證 (C 語言型別安全)：`hash[s >> 3]` 的索引型別為 `int` (因 `s` 為 `int`，右移結果為 `int`)。C99 6.5.7 §5 規定有號整數右移的行為屬 implementation-defined (算術右移或邏輯右移，見 CS:APP Section 2.1.8)，但 `s` 為非負整數，二者結果相同。`qjl_quantize` 中的 `1u << (s & 7)` 使用 `1u` (無號) 避免有號左移溢位，與 Problem B 討論的 `BIT()` 巨集同理。 驗證 (浮點累加順序)：`sum += q_proj * key_sign` 逐項累加，其精度受浮點加法非結合性影響 (CS:APP Section 2.4.5)。當 SDIM 很大時，累加的中間結果幅值可能遠大於個別項，導致 cancellation。實務上以 Kahan summation 或分組累加可改善此問題，但 QJL 的 unbiased 性質是在數學期望 (而非有限精度算術) 下成立的。浮點累加引入的 round-off error 是額外的雜訊來源，不影響無偏性但增加 variance。 延伸問題 (非填空)：CS:APP Practice Problem 2.54 的 `f == -(-f)` 恆真 (sign bit 翻轉兩次)。在 QJL 語境中，若 key 向量取負 $x' = -x$，其 sign hash 的每個位元都翻轉：`hash'[s] = 1 - hash[s]`。因此 $\langle y, Q^{-1}(Q(-x)) \rangle = -\langle y, Q^{-1}(Q(x)) \rangle$，內積估計值取負。sign hash 完美保留向量的正負號資訊，與 IEEE 754 的 sign bit 語義一致。此性質對 attention score 的正確性至關重要：key 向量的方向翻轉必須忠實反映在內積估計中。 延伸閱讀：混合有號/無號運算屬 [CWE-195](https://cwe.mitre.org/data/definitions/195.html) (Signed to Unsigned Conversion Error)。Linux 核心的 [`include/linux/compiler.h`](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 定義 `__same_type()` 巨集以 `__builtin_types_compatible_p` 在編譯時期檢查型別一致性，防止隱式轉換引入的非預期行為。`-Wsign-conversion` 編譯旗標可偵測此類問題，但 Linux 核心基於歷史相容性尚未全面啟用。 核心處理時間先後時也面臨相同的無號算術陷阱。CS:APP Section 2.2.4 討論有號與無號整數的比較陷阱。Linux 核心的 `jiffies` 計數器是此議題最直接的實務案例。`jiffies` 為全域 `unsigned long` 變數，每次 timer interrupt 遞增 1，在 32 位元系統上以 `HZ=1000` 約 49.7 天後環繞 (wrap around) 回零。 若以直覺的 `jiffies > saved_jiffies` 判斷時間先後，環繞時會產生錯誤結果。核心以 [`include/linux/jiffies.h`](https://github.com/torvalds/linux/blob/master/include/linux/jiffies.h) 的 `time_after()` 巨集正確處理： ```c /* include/linux/jiffies.h (節錄) */ #define time_after(a,b) (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ ((long)((b) - (a)) < 0)) ``` 此巨集將無號減法結果強制轉為有號 `long` 再與 0 比較。當 `a` 在時間上晚於 `b` 時 (即使 `a` 的數值因環繞而小於 `b`)，`b - a` 在無號算術下產生大值，轉為 `long` 後為負數，`< 0` 成立。此技巧依賴 C99 6.3.1.3 的 implementation-defined 有號/無號轉換行為：在 two's complement 架構上，無號值的高位元被重新詮釋為符號位元。Linux 核心假設所有目標架構皆為 two's complement (此假設在 C23 中已成為標準要求)。 `typecheck()` 巨集以指標相等比較 (`&__dummy == &__dummy2`，其中 `__dummy` 與 `__dummy2` 分別宣告為目標型別與實際型別) 觸發編譯時期型別不匹配警告，確保二個運算元型別相同，防止不同寬度的無號型別在比較時因隱式提升產生非預期行為。此防禦性設計與 Problem C 討論的 `dim * 2654435761u` 型別提升陷阱直接對應。 歷史上，不使用 `time_after()` 而直接比較 jiffies 的驅動程式在系統連續執行數十天後出現 timer 失效的 bug，是 unsigned wrap-around 在實務中造成嚴重後果的經典案例。 BPF verifier 是此類問題的經典教訓。[CVE-2017-16995](https://nvd.nist.gov/vuln/detail/CVE-2017-16995) 中 [`kernel/bpf/verifier.c`](https://github.com/torvalds/linux/blob/master/kernel/bpf/verifier.c) 的 `check_alu_op()` 在處理 ALU 運算時未正確處理 sign extension，使負的 32-bit `int` 被詮釋為大的 `unsigned` 值，攻擊者藉此繞過範圍檢查存取越界記憶體。此漏洞直接對應 CS:APP Section 2.2.4 的 signed/unsigned 比較陷阱與 Section 2.2.6 的 integer promotion 規則。類似地，[CVE-2024-58017](https://nvd.nist.gov/vuln/detail/CVE-2024-58017) 中 `kernel/printk/printk.c` 的 `LOG_BUF_LEN_MAX` 計算以有號 `1 << N` 觸發溢位，修正方式為將 `1` 轉型為 `u32` 後再進行位移，消除有號左移的未定義行為，與本卷 Problem B 的 B05 填空同理。 ### 延伸問題 * `rademacher()` 的 `dim * 2654435761u` 與 `time_after()` 的 `(long)((b)-(a)) < 0` 皆依賴 Section 2.3 的無號算術環繞性質。以此為出發點： * (a) 閱讀 [`include/linux/seqlock.h`](https://github.com/torvalds/linux/blob/master/include/linux/seqlock.h) 的 `read_seqcount_retry()`：sequence counter 以 LSB 奇偶性標記寫入進行中 (與 Problem B `rb_node` 的 bit 0 編碼顏色相同手法)。`seqcount` 環繞不影響正確性 (判斷僅用奇偶與等值)，但 `jiffies` 環繞需 `time_after()` 的有號重新詮釋 (Section 2.2.4)。從 $\mathbb{Z}/2^{32}\mathbb{Z}$ 證明等值比較在環繞後仍正確，大小比較則失效 * (b) `rademacher()` 使用 Knuth 黃金比例常數 ($2654435761 \approx 2^{32}/\phi$)。$\gcd(2654435761, 2^{32}) = 1$，故乘法構成 $\mathbb{Z}/2^{32}\mathbb{Z}$ 上的雙射。閱讀 [`include/linux/hash.h`](https://github.com/torvalds/linux/blob/master/include/linux/hash.h) 的 `hash_long()`，說明其以 `(val * GOLDEN_RATIO_PRIME) >> (BITS_PER_LONG - bits)` 提取高位元的原因 (高位元 avalanche 品質優於低位元)。再追蹤 Linux 核心 2016 年對 32-bit 黃金比例常數的調整脈絡：早期常數 `0x9e370001UL` 在低位元混合品質不佳，後續改用 `0x61C88647` 以改善 avalanche。若從模運算的對稱性看，`0x61C88647` 最著名的性質其實是 `0x9e3779b9` 的加法逆元，也就是兩者相加在模 $2^{32}$ 下回到 0；這也提醒學員區分 additive inverse 與 multiplicative inverse，不要把二種對稱性混為一談。對照本題 `rademacher()`：QJL 最終取 `h & 1`，因此不能只靠單次乘法，還需要後續三輪 XOR-shift-multiply 混合來補強低位元品質 * \(c) TCP SRTT 以 `>> 3` 實現 $\alpha = 1/8$ 的 EWMA (Section 2.3.7 的整數除以 2 的冪)。閱讀 [`net/ipv4/tcp_input.c`](https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_input.c) 的 `tcp_rtt_estimator()`，追蹤 `srtt_us` 的 8 倍放大定點更新。此截斷偏差 (towards zero) 與 Section 2.4.4 的 round-to-even 不同。計算 RTT 從 $100\ \mu\text{s}$ 跳變至 $200\ \mu\text{s}$ 時，收斂至 95% 新穩態需 $n_{95} = \lceil \log(0.05) / \log(7/8) \rceil = 23$ 個樣本。對比 QJL 的無偏性保證：EWMA 截斷偏差有界 ($\leq 1\ \mu\text{s}$) 但不為零，QJL 的偏差在高維度統計平均下趨近零 * Section 2.4.5 指出浮點加法不滿足結合律 (Practice Problem 2.54 的 `(f+d)-f == d` 非恆真)，QJL 的 `sum` 逐項累加受此影響。以此為出發點： * (a) 對 $d = 128$, $\text{SDIM} = 256$，樸素累加的 round-off error $\approx \sqrt{\text{SDIM}} \cdot 2^{-24} \approx 10^{-6}$，QJL 本身 variance $\approx 1/\sqrt{\text{SDIM}} \approx 0.063$，差距約 4 個數量級。閱讀 [`lib/math/reciprocal_div.c`](https://github.com/torvalds/linux/blob/master/lib/math/reciprocal_div.c)，此模組以 `(a * m) >> 32` 取代除法 (CFS `inv_weight` 同理)，截斷誤差至多 1 且確定性有界；核心選擇定點而非浮點除法的原因，除了停用 FPU 的限制，還在於定點誤差可靜態分析 * (b) 閱讀 [`include/linux/average.h`](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 的 `DECLARE_EWMA`。`ewma_add()` 以 `val << precision >> weight_rcp` 更新，其中區域變數 `weight_rcp = ilog2(_weight_rcp)` 是實際右移量。以 cfg80211 RSSI (`precision=10`, `_weight_rcp=16`) 為例：`weight_rcp = 4`，故 `val << 10 >> 4 = val << 6`，無精度損失。推導避免退化的必要條件應寫為 `precision ≥ ilog2(_weight_rcp)`，並說明此約束如何呼應 IEEE 754 在固定位元預算下對 fraction 與 exponent 的權衡 (Figure 2.32) * \(c) 閱讀 [`include/linux/hash.h`](https://github.com/torvalds/linux/blob/master/include/linux/hash.h)，`hash_long()` 與 `rademacher()` 皆以乘法雜湊產生偽隨機位元。核心的 [`net/core/flow_dissector.c`](https://github.com/torvalds/linux/blob/master/net/core/flow_dissector.c) 以 `jhash` 將封包分類至 RSS 佇列，對 hash 品質的要求 (低碰撞，負載均衡) 與 QJL 的投影品質需求 (低相關，低 variance) 互為映照。設計測試：計算 `rademacher(i, s)` 對 $i \in [0, 127]$, $s \in [0, 255]$ 的 $128 \times 256$ 矩陣行列相關係數，並說明你會用哪些統計量判斷其是否趨近零 --- ## 參考題解 :::spoiler * A01: ==112== * A02: ==14== * A03: ==12== * A04: ==3F801000== * A05: ==477FE000== * B01: ==7== * B02: ==1== * B03: ==idx[i]== * B04: ==DD== * B05: ==1u== * B06: ==~3== * B07: ==7FFE0041== * C01: ==-1.0f== * C02: ==unsigned== :::