2025q1 Homework1 (ideas)

contributed by: <Beethovenjoker> (章元豪) Github

Linux 排程器研究

vax-r

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

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

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

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

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 ，然後各自做部分相乘。

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」寫法可讓三重迴圈的存取更有序，提升資料區域性與快取效率。

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 指令。

typedef float v4sf __attribute__((vector_size (16)));  // 128-bit
typedef float v8sf __attribute__((vector_size (32)));  // 256-bit

編譯器會將這些向量型態轉成目標架構的 SIMD 指令。

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];
        }
    }
}

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。

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推理速度的因素

• 矩陣相乘。
• 模型量化。
  • 將 16-bit 或 32-bit 浮點數壓縮為 8-bit，能節省記憶體並提升運算速度。
  • 量化後模型精度會下降，正確率或推理品質也可能略有影響。。
  • 量化技術對硬體支援要求不一，需要依照實際需求取捨。

Reference

• 2025年Linux核心設計課程作業––lab0(A)
• 2024 年 Linux 核心設計/實作課程期末專題
• 2024 年 Linux 核心設計/實作課程期末展示(上)
• 2024 年 Linux 核心設計/實作課程期末展示(下)