# 2025q1 Homework1 (ideas)
contributed by: <``Beethovenjoker``> (章元豪) [Github](https://github.com/Beethovenjoker)
## Linux 排程器研究
[vax-r](https://hackmd.io/@sysprog/BJdyxvxX0)
:::spoiler Detail
### Core Concept
#### Schedulable Unit
- 在 Linux Kernel 中，CPU 排程的最基本單位是 task，更準確的說法是 sched_entity。
- Task 由 CPU 負責執行，CPU scheduler 需要在適當的時間挑選合適的 task 執行。
#### CPU Scheduler Main Job
- 選擇最適合的 task 在下個時間點執行，最大化 CPU 效率。
- 決定 task 應該在哪個 CPU 上執行，特別是在多核架構下進行負載均衡（Load Balancing）。
### CPU Load Balance
#### Goals
- 將多個 task 平均分配到 CPU 上，避免某些 CPU 過載，而其他 CPU 閒置。
- 提高整體執行效率與系統響應時間。
#### Challenges
- 如何確保 task 在不同 CPU 之間的 migrate 成本不會過高？（考慮 cache locality）
- 在負載較重的 CPU 之間進行合理的負載遷移，以達到最佳效能。
### SCX (Scheduler Extension & Tools)
- eBPF (Extended Berkeley Packet Filter)
- 類似於 javascript 之於 HTML，eBPF 允許開發者將程式碼安全地植入 Kernel 空間，而不需重新編譯 Kernel。
- 與 Kernel module 的差異：
- Kernel module 直接加入 code base，若出錯可能導致 Kernel crash。
- eBPF 則可以動態加入、刪除，並且錯誤時自動退出 Kernel space，避免影響系統穩定性。
- 應用於 CPU 排程器:
- 允許開發者 快速實驗不同的排程策略，避免頻繁修改 Kernel 代碼。
- 可根據特定場景調整排程邏輯，如遊戲運行時提高互動性任務的優先級，降低背景計算任務的影響。
### scx_lavd
- 針對遊戲的排程器。
- 特別寵愛互動性強的任務。
原本在eBPF的環境下編譯檔案邊玩Terreria編譯檔案很卡，但是換成scx_lavd之後遊戲體驗變得非常順暢。
### Import ML into CPU scheduler
- ML 不是直接幫助我們決定哪個 Task 先執行，而是用來最佳化特定決策，例如：
- Task Migration（Task 在 CPU 之間的遷移）：決定是否應該將 Task 從 CPU A 移動到 CPU B。
- Kernel 內建函數 ``can_migrate_task()`` 會評估 Task 是否可以遷移，ML 可以幫助提高這個判斷的準確性。
- <Machine Learning for Load Balancing in the Linux Kernel>論文
- 使用很簡單ANN模型來判斷某個task是否該被migrate到其他CPU。
- 降低遷移次數並不一定能提升效能，重點應該放在 Kernel Compilation Time。
### Create Load Imbalnce
- 同時執行大量 CPU-bound 和 I/O-bound 任務:
- CPU-bound task: Linux Kernel編譯。
- I/O-bound task: 使用 ``fio`` 進行 Disk I/O 測試。
- 主要的評估指標:
- 不是遷移次數（migration count），而是 Kernel 編譯時間。
- 遷移次數上升可能對編譯時間有正面影響，因此不能單純以次數來評估負載均衡策略的好壞。
- EEVDF vs. scx_rusty
- 目前scx排程器都沒有實作load imbalance的機制。
- 只有rusty在user space實作load imbalance。
- scx_rusty過度task migration，對於locality的部分沒有處理很好。
| 排程器 | Task Migration 次數 | Kernel Compilation Time |
|-----------------|-----------------|------------------|
| EEVDF | 51,719 | 6m20s |
| scx_rusty | 265,801 | 7m10s |
| scx_rusty + ML | 61,649 | 5m41s |
### Extra contents
- 計算weight的方式可以再改進，weight太大的任務可能會占用兩個以上的CPU，它的weight很大是沒錯，但是不能一次讓兩個CPU執行。
- 作者並非真的最佳化排程的策略來改善效能，僅是使用lab-0的一些bitwise之類的技巧。要改進很一小部分的效能，當CPU部屬到幾千幾百萬台機器上，累積效能提升將極為可觀。
- 利用ML來知道task migration的哪些feature是重要的。
- 對task做量化提取特徵。
:::
## LLaMA 效能分析
[LIAO-JIAN-PENG](https://hackmd.io/@sysprog/SJCtkQhVA)
:::spoiler Detail
在進行大型語言模型（LLM）推理時，矩陣乘法往往是主要的計算瓶頸之一。以 LLaMA 為例，其運作原理在底層仍然必須進行大量的矩陣運算，因此如何加速矩陣乘法就成了提升 LLaMA 推理速度的關鍵。
### 探討提升矩陣乘法的手法
#### Strassen Algorithm
- 將傳統的矩陣乘法從 $O(n^3)$ 降到約 $O(n^{2.81})$ 的時間複雜度。
- 以 2×2 矩陣為例，傳統演算法需要進行 8 次乘法和 4 次加法；而 Strassen 演算法會先組合部分乘積（product）成中間通用項，再利用這些通用項組合出最終結果，最終只需要 7 次乘法與 18 次加法。
> 補充：近代研究已使矩陣乘法複雜度逐漸逼近 $O(n^{2.37})$ ; 然而，這些演算法通常只有在非常大的矩陣規模下才會展現出優勢，且程式的常數項較大。實際應用仍需權衡。
### 資料平行處理與實作
在硬體支援的前提下，最直接也最有效的方式之一就是「並行化」：無論是 CPU 多核心、SIMD 指令集（如 SSE、AVX），或是 GPU 等專用硬體，都能加速大量的乘加運算。為了探討這些方法，可以比較以下兩個專案：
- matmul：在單執行緒上，比較不同最佳化手段（transposed、sdot、SSE sdot、SSE tiling、OpenBLAS 等）。
- matmul_bench：在多執行緒環境下，比較 outer function、block matrix、SSE、GCC vector type、AVX2、FMA 等不同方式。
#### sdot_8
```c
float sdot_8(int n, const float *x, const float *y)
{
int i, n8 = n>>3<<3;
float s, t[8];
t[0] = t[1] = t[2] = t[3] = t[4] = t[5] = t[6] = t[7] = 0.0f;
for (i = 0; i < n8; i += 8) {
t[0] += x[i+0] * y[i+0];
t[1] += x[i+1] * y[i+1];
t[2] += x[i+2] * y[i+2];
t[3] += x[i+3] * y[i+3];
t[4] += x[i+4] * y[i+4];
t[5] += x[i+5] * y[i+5];
t[6] += x[i+6] * y[i+6];
t[7] += x[i+7] * y[i+7];
}
for (s = 0.0f; i < n; ++i) s += x[i] * y[i];
s += t[0] + t[1] + t[2] + t[3] + t[4] + t[5] + t[6] + t[7];
return s;
}
```
Loop unrolling：將迴圈攤平後，編譯器或組譯器能更容易預測記憶體存取位置，也降低迴圈控制的開銷。不過若迴圈過大，程式碼膨脹嚴重時，編譯器就不一定會自動展開。
#### sdot_sse
```c
float sdot_sse(int n, const float *x, const float *y)
{
int i, n8 = n>>3<<3;
__m128 vs1, vs2;
float s, t[4];
vs1 = _mm_setzero_ps(); // {0.f, 0.f, 0.f, 0.f}
vs2 = _mm_setzero_ps(); // {0.f, 0.f, 0.f, 0.f}
for (i = 0; i < n8; i += 8) {
__m128 vx1, vx2, vy1, vy2;
vx1 = _mm_loadu_ps(&x[i]); // load {x[0], x[1], x[2], x[3]}
vx2 = _mm_loadu_ps(&x[i+4]); // load {x[4], x[5], x[6], x[7]}
vy1 = _mm_loadu_ps(&y[i]); // load {y[0], y[1], y[2], y[3]}
vy2 = _mm_loadu_ps(&y[i+4]); // load {y[4], y[5], y[6], y[7]}
vs1 = _mm_add_ps(vs1, _mm_mul_ps(vx1, vy1)); // vs1 += vx1*vy1
vs2 = _mm_add_ps(vs2, _mm_mul_ps(vx2, vy2));
}
for (s = 0.0f; i < n; ++i) s += x[i] * y[i]; // Complete the remaining (insufficient 8) operations.
_mm_storeu_ps(t, vs1);
s += t[0] + t[1] + t[2] + t[3]; // {t[0], t[1], t[2], t[3]}
_mm_storeu_ps(t, vs2);
s += t[0] + t[1] + t[2] + t[3]; // {t[4], t[5], t[6], t[7]}
return s;
}
```
- SSE(Streaming SIMD Extensions)是Intel CPU的一組指令及擴展，能對多筆資料執行相同運算。
- ``_mm_setzero_ps()`` :載入四個 0 浮點數。
- ``_mm_loadu_ps()`` :從記憶體載入 4 筆浮點數至暫存器。
- ``_mm_add_ps()`` 和 `` _mm_mul_ps()`` :分別進行同時乘法或加法運算。
- 最後同樣需補不足 8 筆的餘數計算。
#### loop tiling
```c
int i, j, ii, jj, x = 16, n_b_rows = n_a_cols;
float **m, **bT;
m = mat_init(n_a_rows, n_b_cols);
bT = mat_transpose(n_b_rows, n_b_cols, b);
for (i = 0; i < n_a_rows; i += x) {
for (j = 0; j < n_b_cols; j += x) {
// loop tiling
int je = n_b_cols < j + x? n_b_cols : j + x;
int ie = n_a_rows < i + x? n_a_rows : i + x;
for (ii = i; ii < ie; ++ii)
for (jj = j; jj < je; ++jj)
m[ii][jj] += sdot_sse(n_a_cols, a[ii], bT[jj]);
}
}
```
- Loop tiling 將大迴圈拆成較小的區塊，以便更有效率地利用 CPU 快取。
- 先轉置其中一個矩陣（例如 bT），可讓讀取時能依序存取連續記憶體，增加快取命中率。
### 多執行緒加速
在「matmul_bench」專案中，進一步利用多執行緒加速：
- 將輸入矩陣切成多區段，並行計算，再將結果合併。
- 下圖為 6 個執行緒計算後的效能測試結果。
以如下程式碼為例，``thread function`` 接收各執行緒需負責處理的起始索引 ``i_start`` 與結束索引 ``i_end`` ，然後各自做部分相乘。
```c
for (unsigned long i=i_start; i<i_end; i++) {
for (unsigned long j=0; j<n; j++) {
float v = 0;
for (unsigned long k=0; k<n; k++) {
v += inL[i*n+k] * inR[k*n+j];
}
out[i*n+j] = v;
}
}
```
#### outer function
以「outer」寫法可讓三重迴圈的存取更有序，提升資料區域性與快取效率。
```c
for (unsigned long i=0; i<n; i++) {
for (int k=0; k<n; k++) {
float lik = inL[i*n+k];
for (int j=0; j<n; j++) {
out[i*n+j] += lik * inR[k*n + j];
}
}
}
```
與一般的轉置做法類似，但不需真的轉置即可達成「對 out 的連續存取」。
### SIMD GCC vector type
GCC 的向量擴展（Vector Extensions） 提供了一種高階語法使用 SIMD 指令。
```c
typedef float v4sf __attribute__((vector_size (16))); // 128-bit
typedef float v8sf __attribute__((vector_size (32))); // 256-bit
```
編譯器會將這些向量型態轉成目標架構的 SIMD 指令。
```c
typedef float v4sf __attribute__((vector_size (16)));
for (unsigned long i=i_start; i<i_end; i++) {
for (int k=0; k<n; k++) {
float lik = inL[i*n+k];
v4sf vlik = {lik,lik,lik,lik};
for (int j=0; j<n; j+=4) {
*(v4sf*)&out[i*n+j] += vlik * *(v4sf*)&inR[k*n + j];
}
}
}
```
```c
typedef float v8sf __attribute__((vector_size (32)));
v8sf vlik = {lik,lik,lik,lik,
lik,lik,lik,lik};
```
一次處理 8 個 float 數值，如果硬體支援 AVX，就能發揮更好的並行運算效率。
### Block Matrix Multiplication
與 loop tiling 類似，但此處是將整個大矩陣拆分成多個小矩陣（block），再進行相乘；同樣是為了增強記憶體的 locality。
```c
for (i0=i_start; i0<i_end; i0+=block_size) {
for (int j0=0; j0<n; j0+=block_size) {
for (int k0=0; k0<n; k0+=block_size) {
for (int bi=0; bi<block_size; bi++) {
int i = i0+bi;
for (int bk=0; bk<block_size; bk++) {
int k = k0+bk;
float lik = inL[i*n + k];
for (int bj=0; bj<block_size; bj++) {
int j = j0+bj;
out[i*n + j] += lik * inR[k*n + j]; // outer function
}
}
}
}
}
}
```
透過調整 ``block_size``，能在不同硬體（CPU、快取大小等）上找到最佳效能點。
### Transfomer
- Non Sequential: 基於 Self-Attention，輸入序列可同時更新多個位置的資訊，比 RNN/LSTM 更具效率。
- Self-Attention: 透過 Query、Key、Value 計算序列中各位置的關聯權重，能更好處理長距離依賴。
- Positional Embeddings: 保留序列中位置關係資訊，不再只依賴時間步長的遞迴。
### RNN/LSTM
- 一次只能處理一個時間步長，難以並行化。
- 反向傳播容易導致梯度消失（vanishing）或爆炸（exploding）。
- LSTM 透過多個 Gate（Input、Forget、Output）設計，減輕梯度消失問題，但依舊難以真正解決超長序列的依賴性。
### CNN
- 常用於影像或短文本特徵抽取。
- Attention 機制某種程度上可被視為「全局化」的卷積操作。
- 若要處理很長序列或大型文本，卷積核尺寸可能會暴增，導致計算與記憶體需求大幅上升，限制應用彈性。
### 影響LLaMA推理速度的因素
- 矩陣相乘。
- [模型量化](https://hackmd.io/waJTKCH5QzmBOoMZijPJxg)。
- 將 16-bit 或 32-bit 浮點數壓縮為 8-bit，能節省記憶體並提升運算速度。
- 量化後模型精度會下降，正確率或推理品質也可能略有影響。。
- 量化技術對硬體支援要求不一，需要依照實際需求取捨。
:::
## Reference
- [2025年Linux核心設計課程作業----lab0(A)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)
- [2024 年 Linux 核心設計/實作課程期末專題](https://hackmd.io/@sysprog/linux2024-projects)
- [2024 年 Linux 核心設計/實作課程期末展示(上)](https://www.youtube.com/watch?v=kwYgfkD1dWA)
- [2024 年 Linux 核心設計/實作課程期末展示(下)](https://www.youtube.com/watch?v=qUd1PtF-R38&t=1s)
Sign in with Wallet
Connect another wallet