## Thread Affinity
如何從作業系統手中奪回「排程主導權」，解決在多核心環境下，執行緒在不同 CPU 核心間「遷移（Migration）」所造成的效能損失。
### Miss Table
| 現象 | 發生原因 | 對效能的影響 |
| :--- | :--- | :--- |
| **Cache Miss** | 數據不在新核心的快取裡 | 增加數百個週期的延遲。 |
| **TLB Miss** | 記憶體映射不在新核心裡 | 觸發 Page Walk，代價極高。 |
| **CPU Migration** | 排程器為了負載平衡強行搬家 | 導致上述兩者同時發生。 |
### Why Affinity
排程器為了負載平衡（Load Balancing），可能會將一個執行緒從 CPU 0 移到 CPU 2。
但只要一搬移，就會帶來兩個嚴重的研究課題：
1. **Cache Cold Start (快取冷啟動)**
原本在 CPU 0 的 L1/L2 快取數據，在 CPU 2 必須重新從 L3 或記憶體抓取。
> 當一個執行緒原本在 Core 0 跑，後來被作業系統遷移（Migrate）到 Core 1 時，Core 1 的 L1/L2 快取裡完全沒有這個執行緒剛才運算的數據。核心必須去 L3 快取甚至實體記憶體（RAM）把數據重新抓回來。這就是所謂的 Cache Invalidation（快取失效），而之所以是去L3，是因為On-demand策略，走L3比copy有效率
* Cache 失效：數據的「冷啟動」問題
每個 CPU 核心都有自己私有的 **L1 和 L2 Cache**。
* **發生了什麼事？** 當一個執行緒原本在 Core 0 跑，後來被作業系統遷移（Migrate）到 Core 1 時，Core 1 的 L1/L2 快取裡完全沒有這個執行緒剛才運算的數據。
* **代價：** 核心必須去 L3 快取甚至實體記憶體（RAM）把數據重新抓回來。這就是所謂的 **Cache Invalidation（快取失效）**。
2. **TLB Flush (Translation Lookaside Buffer, used to map VM to phy mem)**
分頁表快取失效，增加虛擬地址轉換的成本。
* TLB 重構
這是比 Cache 失效更重大的開銷。**TLB (Translation Lookaside Buffer)** 是 CPU 內部的一個小快取，專門用來存放「**虛擬地址到實體地址的轉換表**」。
* **為什麼要重構？**
1. 虛擬記憶體是「假的」，CPU 必須透過頁表（Page Table）才能找到實體 RAM。
2. 查表（Page Walk）很慢，所以 CPU 會把最近查過的結果存進 **TLB**。
3. **TLB 通常是核心私有的**。當執行緒從 Core 0 搬到 Core 1，Core 1 的 TLB 裡沒有該執行緒的地址轉換記錄。
* **代價：** CPU 必須重新去走訪記憶體裡的「多級頁表」來填滿 Core 1 的 TLB。
#### 但為什麼核心之間不能同時將TLB和CACHE搬過去?
* SRAM
Cache 在硬體上的位置。L1 和 L2 Cache 不是放在記憶體條上，而是直接蝕刻在 CPU 核心的電路裡面（SRAM）。這使他無法移動，只能複製，所以數據不是「搬」過去，而是要透過 CPU 內部總線或 Mesh Network從 Core A **複製**一份到 Core B。
* 能量
另外，大規模搬移數據是非常耗電且會產生高熱的動作。如果每次執行緒切換都要搬幾百 KB 的數據，CPU 會變得很燙。
> 能量我不熟，所以忽略，注重考慮的是從L3搬資料跟走Copy誰比較快
2. CPU Interconnect Occupied
* 數據量龐大
現代 CPU 的 L2 Cache 可能有 1MB 或更多。如果作業系統每秒進行數千次執行緒遷移，總線會滿載
* 優先權問題
總線連接太多東西了，這條路還要用來處理記憶體讀寫、核心間的通訊（如 MESI 協定）。如果被「搬家公司」佔滿了，其他的運算指令就會卡住。
> 那如果是cluster? core之間塞獨立的interconnect，每個core對外都有自己的線路?
> -> Area Problem?
3. **TLB跟 CPU 內部的 MMU（記憶體管理單元） 緊密結合**
所以不同狀況與不同經歷的CPU中的TLB架構會不一樣，直接拿過去會導致錯亂
#### 缺點1 負載不均（Load Imbalance）
如果你把 4 個重度運算的執行緒都綁在 Core 0，而 Core 1 到 Core 3 都在閒逛，你的程式會比沒設 Affinity 還慢。作業系統的排程器原本想幫你「平衡」，但被你禁用了。
#### 缺點2 核心拓撲（Topology）
現代 CPU 有 **超執行緒 (Hyper-threading)**。
* 如果你把兩個互相競爭 Cache 的執行緒綁在同一個實體核心的兩個邏輯核心上，它們會更擠。
* 如果你把需要大量通訊的執行緒綁在不同的 **NUMA Node**（不同插槽的 CPU），通訊延遲會炸掉。
### Affinity Code
```c
// ~/pthreads/affinity.c
// 執行時tmux或直接多開一個terminal，輸入htops，F2 setup-> Display option-> CPU detail
#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sched.h>
#include <stdbool.h>
#include <stdalign.h>
#define CORE 16
// -O3，編譯器會進行「暫存器優化」。
// 在這個執行緒的視角裡，沒有人會動這個變數，
// 所以不需要每次都去記憶體讀取，
// 直接把它放在 CPU 暫存器裡跑就好。
// 結果就是：就算主程式把 keep_running 改成 false 了，
// 子執行緒還是在看自己暫存器裡的舊值（true），永遠停不下來。
// 加上 volatile 是強制 CPU 每次都要回記憶體看最新的值。
volatile bool keep_running = true;
// 儲存每個執行緒的結果
typedef struct {
alignas(64) unsigned long long final_count;
int thread_id;
int bound_core;
} ThreadResult;
void* heavy_worker(void* arg) {
ThreadResult* result = (ThreadResult*)arg;
int core_to_bind = result->bound_core;
// 1. 設定執行緒親和性 (Affinity)
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(core_to_bind, &cpuset);
pthread_t current_thread = pthread_self();
if (pthread_setaffinity_np(current_thread, sizeof(cpu_set_t), &cpuset) != 0) {
perror("pthread_setaffinity_np");
return NULL;
}
// 2. 密集運算迴圈
unsigned long long local_count = 0;
while (keep_running) {
local_count++; // 單純的加法運算
}
result->final_count = local_count;
return NULL;
}
int main() {
int num_cores = sysconf(_SC_NPROCESSORS_ONLN);
printf("=== P-core vs E-core 算力競賽 ===\n");
printf("系統偵測到核心數: %d\n", num_cores);
printf("將啟動 %d 個執行緒，分別綁定到核心 0-%d\n", CORE, CORE-1);
printf("...\n\n");
pthread_t threads[CORE];
ThreadResult results[CORE];
// 3. 啟動執行緒，每個執行緒綁定到對應編號的核心
for (int i = 0; i < CORE; i++) {
results[i].thread_id = i;
results[i].bound_core = i; // 這裡你可以手動更改，例如只測 0 和 12
results[i].final_count = 0;
pthread_create(&threads[i], NULL, heavy_worker, &results[i]);
}
// 4. 固定測試時間
printf("正在運算中，請查看 htop...\n");
fflush(stdout);
getchar(); // 等待使用者按下 Enter 鍵來結束測試
keep_running = false; // 停止所有執行緒
// 5. 等待回收並打印結果
for (int i = 0; i < CORE; i++) {
pthread_join(threads[i], NULL);
}
printf("\n--- 實驗結果 (5秒總算力) ---\n");
printf("%-10s | %-10s | %-20s\n", "Thread ID", "Core ID", "Total Increments");
printf("--------------------------------------------------\n");
for (int i = 0; i < CORE; i++) {
printf("Thread %-2d | Core %-2d | %-20llu\n",
results[i].thread_id, results[i].bound_core, results[i].final_count);
}
return 0;
}
```
## Final Project (Phase 1)
Include : **Thread Lifecycle**、**Synchronization**、**False Sharing**、**Affinity**。
### 專案題目
多核心異構環境下的矩陣特徵提取器 **(Parallel Matrix Feature Extractor)**
### Spec
給定一個巨大的二維矩陣 $M$ ($16384 \times 16384$，單精度浮點數)，你需要撰寫一個平行程式來計算：
1. **全局總和 (Global Sum)**：矩陣所有元素的累加。
2. **行極值 (Row-wise Maxima)**：每一行最大的數值，存入一個陣列。
3. **效能報告**：量化在不同核心綁定策略下的執行效率。
#### Requirement 1 : Domain Decomposition
* **任務**：將矩陣按「行 (Rows)」平均分配給 $N$ 個執行緒。
* **OS 連結**：利用 **Thread Affinity** 將每個執行緒固定在不同的 CPU 核心上，觀察 P-core 與 E-core 的計算速度落差。
#### Requirement 2 : Reduction Optimization
* **禁忌**：嚴禁多個執行緒直接對一個全域變數加鎖（會產生嚴重的 Contention）。
* **要求**：每個執行緒必須先計算其分配區域的「局部總和 (Local Sum)」，最後再彙整。
#### Requirement 3 : False Sharing Preventing
* **挑戰**：如果你建立一個儲存每個執行緒局部結果的陣列 `float results[NUM_THREADS]`，會觸發 False Sharing。
* **要求**：使用 **Padding** 或 **Thread-local Storage** 確保各核心的 L1 Cache 不會互相打架。
---
### File Structure
```text
parallel-project-01/
├── src/
│ ├── main.c # 負責初始化矩陣、建立執行緒、匯總結果
│ ├── worker.c # 核心計算邏輯 (含 Affinity 設定)
│ └── utils.h # 定義對齊用的結構體
├── scripts/
│ └── run_bench.sh # 自動測試 1, 2, 4, 8, 16 執行緒的腳本
├── Makefile # 需包含 -O3 與 -pthread
└── report.md # 你的研究發現 (核心數據分析)
```
---
### report
`report.md` 必須包含以下量化分析：
1. **加速比曲線 (Speedup Curve)**：
* 計算 $S = T_1 / T_n$。
* **分析**：當執行緒數量超過實體核心（Physical Cores）進入超執行緒（Hyper-threading）時，加速比是否趨於平緩？為什麼？
2. **硬體異構性分析 (Heterogeneity)**：
* 分別測試「只綁定 P-cores」與「只綁定 E-cores」的執行時間。
* **量化**：計算兩者的 **效能功耗比估算**（若有工具可測）或單純的運算速度倍率。
3. **Cache Miss 驗證**：
* 使用 `perf stat -e L1-dcache-load-misses` 比較「有 Padding」與「無 Padding」版本的數據差異。
### 啟動代碼片段 (Data Structure)
為了幫你起步，這裡提供一個符合研究所規範的記憶體對齊結構建議：
```c
#define CACHELINE_SIZE 64
typedef struct {
double local_sum;
// Padding 確保每個 struct 佔用整倍數的 Cache Line
char padding[CACHELINE_SIZE - sizeof(double)];
} __attribute__((aligned(CACHELINE_SIZE))) thread_data_t;
```
Project
https://hackmd.io/@1p0_VOUHTXGcHlBU9A0OEA/S1VgDyViWg
LAB 4 (Phase 2)
https://hackmd.io/@1p0_VOUHTXGcHlBU9A0OEA/ryUEZv55bx
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet