## 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

~project/
 ├──Project1/
 │  ├── src/
 │  │   ├── main.c           # 負責初始化矩陣、建立執行緒、匯總結果
 │  │   ├── worker.c         
 │  │   └── utils.h          # 定義對齊用的結構體
 │  ├── scripts/
 │  │   └── run_bench.sh     # 自動測試 1, 2, 4, 8, 16 執行緒的腳本
 │  ├── Makefile             # 需包含 -O3 與 -pthread
 │  └── report.md   
 │  
 ├──Project1_affinity/
    ├── src/
    │   ├── main.c           
    │   ├── worker.c         # 核心計算邏輯 (含 Affinity 設定)
    │   └── utils.h          
    ├── scripts/
    │   └── run_bench.sh     
    ├── Makefile             
    └── 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)

#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;

---
### Step 1 : Structure
建立一個 $16384 \times 16384$ 的單精度浮點數 (float) 矩陣 $M$。
單精度浮點數佔用 4 Bytes(32 bits)。
* 總大小：
$$16384 * 16384 * 4 Bytes = 1,073,741,824 Bytes = 1 GB$$

1. 絕對不能宣告在 Stack 上
如果你寫 `float matrix[16384][16384]`，程式一執行就會立刻發生 Stack Overflow (堆疊溢位)，因為作業系統預設給每個執行緒的 Stack 大小通常只有 8 MB
> use `ulimit -s` to check default stack

2. 必須使用 Heap (堆積)
我們必須使用 malloc 或 calloc 來動態配置這 1 GB 的記憶體。

3. 使用一維陣列模擬二維陣列
為了極致的效能，我們不使用 `(float **)`來建立二維陣列，因為那會讓記憶體變得破碎。我們應該宣告一個巨大的一維陣列，這樣記憶體才是連續的 (Contiguous)。連續的記憶體對 CPU Cache 絕對友善，能大幅降低 Cache Miss。

> 這裡請複習Stack / Heap 的差異

#### `(float **)`

##### 1. 指標陣列層次（第一層）
當你宣告一個 `float **ptr` 並為其分配空間時（例如模擬二維陣列），你通常會先分配一個存放「指標」的空間：

float **ptr = malloc(rows * sizeof(float *));

在這個階段，`ptr` 指向的是一個連續的記憶體區塊，裡面存放著多個 `float *`（指標）。**在這個區塊內，指標與指標之間是連續的。**

##### 2. 實際資料層次（第二層）
問題通常出在這裡。當你為每一列分配空間時：

for (int i = 0; i < rows; i++) {
    ptr[i] = malloc(cols * sizeof(float));
}

* **指標之間不連續：** 每次呼叫 `malloc` 分配的 `ptr[i]` 區塊，在記憶體中的位置是由作業系統動態決定的。`ptr[0]` 的結尾與 `ptr[1]` 的開頭通常**不相鄰**。
* **區塊內部連續：** 在同一個 `ptr[i]` 所指向的 `cols` 個 `float` 之間，記憶體是連續的。
##### 比較表：`float **` vs. 二維陣列 `float[R][C]`

| 特性 | `float **ptr` (動態分配) | `float arr[R][C]` (靜態陣列) |
| :--- | :--- | :--- |
| **記憶體佈局** | **非線性**。每一列可能散落在記憶體各處。 | **線性**。所有資料都在一個完整的連續區塊。 |
| **存取效率** | 較慢。需要兩次記憶體尋址 (Dereference)。 | 較快。編譯器可直接計算偏移量。 |
| **彈性** | 高。每一列的長度可以不同（鋸齒陣列）。 | 低。每一列長度必須相同。 |

---

##### 如何讓 `float **` 的記憶體完全連續？
如果你需要使用 `ptr[i][j]` 的語法，又希望記憶體完全連續（為了效能或傳輸需求），你可以使用「一次性分配」技巧：

float **ptr = malloc(rows * sizeof(float *));
float *data = malloc(rows * cols * sizeof(float)); // 分配一整塊連續空間

for (int i = 0; i < rows; i++) {
    ptr[i] = &data[i * cols]; // 將指標指向連續空間的對應位置
}

#### Header : utils.h

/*
 *  utils.h
 *  version 1.0
 *  Created on: 2025/3/27
 *  Author: Jimmy
 */
#ifndef UTILS_H
#define UTILS_H
#define _GNU_SOURCE
#include <stdalign.h> // 用於 alignas
# define MATRIX_SIZE 16384
# define rows 16384
# define cols 16384
# define CACHE_LINE_SIZE 64
# define EXIT_FAILURE 1
typedef struct  {
    alignas(CACHE_LINE_SIZE) long long final_count;
} thread_data_t;
// 等價於
// typedef struct {
//     double local_sum;
//     char padding[CACHELINE_SIZE - sizeof(double)]; 
// } __attribute__((aligned(CACHELINE_SIZE))) thread_data_t;
// ---------------------------------------------------------
// typedef struct {
//     double local_sum;
//     char padding[CACHELINE_SIZE - sizeof(double)];
// } alignas(CACHELINE_SIZE) thread_data_t;


#endif // UTILS_H

#### main.c (ver. matrix default)

/*
 *  main.c
 *  version 1.0
 *  Created on: 2025/3/27
 *  Author: Jimmy 
*/
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>
#include "utils.h"



int main () {
    printf("Default\n");
    // size_t : unsigned integer type, auto-adjusted to the size of the platform (32-bit or 64-bit)
    size_t total_element = (size_t)rows * cols;
    // number of elements in the matrix = rows * cols
    printf("Total elements: %zu\n", total_element);

    // single precision float: 4 bytes
    // malloc return void* , float* can trasform void* to float*
    float *matrix = (float *)malloc(total_element * sizeof(float));
    // float **ptr = malloc(rows * sizeof(float *));
    // float *data = malloc(rows * cols * sizeof(float)); // 分配一整塊連續空間

    // for (int i = 0; i < rows; i++) {
    //     ptr[i] = &data[i * cols]; // 將指標指向連續空間的對應位置
    // }
    if (matrix == NULL) {
        // log error message to a file name "stderr"
        fprintf(stderr, "Memory allocation failed\n");
        return EXIT_FAILURE;
    }
    // time_t time(time_t *tloc);
    // time return the current calendar time as 
    // a value of type time_t. 
    // If tloc is non-NULL, 
    // the return value is also stored 
    // in the memory pointed to by tloc.
    srand (time(NULL)); // seed the random number generator with current time
    for (size_t i = 0; i < total_element; i++) {
        // RAND_MAX is a constant defined in stdlib.h,
        // which represents the maximum value returned by the rand function
        matrix[i] = (float)rand() / RAND_MAX; // Initialize with some values, e.g., 0.0, 1.0, ..., 99.0, then repeat
    }

    printf ("Matrix initialization completed.\n");
    free (matrix);
 
    return 0;
}

##### Take out
* **size_t** : auto-adjusted to the size of the platform (32-bit or 64-bit)
* **time(NULL)**: 代表不使用指標接收時間，只取回傳值。
* **RAND_MAX**: 是標準庫定義的固定數字，不是函式。
* **(float)**: 強制轉型很重要，如果沒加，整數除法（例如 10 / 32767）會直接變成 0
* **($float^*$)**: 轉malloc (default return void*) 成float
* **fprint**(log's name, message)

#### Makefile

# Makefile for Project 1: Parallel Matrix Extraction

# 1. 定義變數 (Variables)
CC = gcc
# CFLAGS 是一連串的編譯選項：
#   -Wall -Wextra: 開啟所有常見的警告。工程師最喜歡警告了，它能幫我們抓出潛在的 Bug。
#   -O3: 最高等級的編譯器最佳化。因為我們要測效能，這個參數絕對不能少。
#   -pthread: 告訴編譯器我們要連結 POSIX Thread 函式庫，這是多執行緒的靈魂。
#   -g: 加入除錯資訊，萬一程式當掉 (Segmentation fault)，我們可以用 gdb 追蹤。
CFLAGS = -Wall -Wextra -O3 -pthread -g

# exe file name
TARGET = extractor

# 所有的 .c 原始碼檔案
SRCS = src/main.c src/worker.c

# 預設目標
# make = 執行第一個 Target（通常就是 all）。
# make all = 明確指定執行名為 all 的 Target。
all: $(TARGET)

# 編譯規則：告訴 Make 如何把 SRCS 編譯成 TARGET
$(TARGET): $(SRCS)
	$(CC) $(CFLAGS) -o $(TARGET) $(SRCS)

# 清理編譯出來的檔案 (方便重新編譯)
clean:
	rm -f $(TARGET)

### Step 2 Workload & Threads Lifecycle
依照threads數量分配，如
* Thread 0 負責 Row 0 ~ 4095
* Thread 1 負責 Row 4096 ~ 8191

以達成記憶體連續存取對齊
#### utils.h (modify ver 2)

// utils.h
// below the thread_data_t
typedef struct {
    int thread_id;                 // 執行緒的編號 (0, 1, 2...)
    size_t start_row;              // 負責計算的起始行
    size_t end_row;                // 負責計算的結束行 (不包含此行)
    float *matrix;                 // 整個矩陣的指標
    thread_data_t *thread_results; // 指向我們防 False Sharing 的結果陣列
} thread_args_t;

void* worker_task(void* arg);

#### worker.c

#include "utils.h"

void* worker_task(void* arg) {
    // 1. transform void* arg to thread struct, pointer to the struct we defined in utils.h 
    thread_args_t *args = (thread_args_t*)arg;
    // here we can access the fields of the struct, e.g., args->thread_id, args->start_row, etc.
    int tid = args->thread_id;
    
    double sum = 0.0; // 暫存用的局部變數，放在 CPU Register 裡最快！

    // 2. Start work：只跑自己的 Rows
    for (size_t i = args->start_row; i < args->end_row; i++) {
        // Columns
        for (size_t j = 0; j < MATRIX_SIZE; j++) {
            // 一維陣列模擬二維陣列的公式： 索引 = (行號 * 總列數) + 列號
            sum += args->matrix[i * MATRIX_SIZE + j];
        }
    }

    // 3. 計算完畢，把結果寫入專屬的記憶體位置 (已 Padding 過，不會有 False Sharing)
    args->thread_results[tid].local_sum = sum;

    // print log to console
    printf("[Thread %d] 完成計算 Rows %zu ~ %zu，局部總和: %f\n", 
           tid, args->start_row, args->end_row - 1, sum);

    return NULL; // 執行緒結束
}

#### main.c version 2
這裡就該宣告的宣告，該設置的設置
> 這裡的NUM_THREADS是先用#define

for 在這裡其實可以手動展開如join，但僅限於define下，理想還是直接用openmp自動展開

// ... after random init matrix
    // ==========================================
    // Benchmark 開始：記錄起始時間
    // ==========================================
    struct timespec start_time, end_time;
    clock_gettime(CLOCK_MONOTONIC, &start_time);
    // ==========================================
    pthread_t threads[num_threads];
    thread_args_t thread_args[num_threads];
    thread_data_t thread_results[num_threads]; 
   
    // check if thread_results is correctly allocated
    float *row_max_array = malloc(MATRIX_SIZE * sizeof(float));

    size_t rows_per_thread = MATRIX_SIZE / num_threads;
    printf("\n %d 個thread開始作業...\n", num_threads);
    for (int i = 0; i < num_threads; i++) {
        thread_args[i].thread_id = i;
        thread_args[i].start_row = i * rows_per_thread;
        
        // 如果是最後一個執行緒，就包辦剩下的所有行數 (避免無法整除的問題)
        thread_args[i].end_row = (i == num_threads - 1) ? MATRIX_SIZE : (i + 1) * rows_per_thread;
        thread_args[i].matrix = matrix;
        thread_args[i].thread_results = thread_results;
        thread_args[i].row_max_array = row_max_array;

        // 建立執行緒並執行 worker_task
        pthread_create(&threads[i], NULL, worker_task, &thread_args[i]);
    }

    
 
    for (int i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL); 
    }
    double global_sum = 0.0;
    for (int i = 0; i < num_threads; i++) {
        global_sum += thread_results[i].local_sum;
    }
    // ==========================================
    // Benchmark 結束：記錄結束時間並計算差值
    // ==========================================
    clock_gettime(CLOCK_MONOTONIC, &end_time);
    double elapsed_time = (end_time.tv_sec - start_time.tv_sec) + 
                          (end_time.tv_nsec - start_time.tv_nsec) / 1e9;
    printf("\n>>> 最終全局總和 (Global Sum): %f <<<\n", global_sum);
    printf(">>> 核心計算耗時: %f 秒 <<<\n", elapsed_time);

    printf("\n所有執行緒完成計算，矩陣總和: %f\n", global_sum);
    
    



    // ==========================================
    // 結果驗證階段 (Sequential Verification)
    // ==========================================
    printf("\n>>> 啟動結果驗證 (計算單執行緒基準值以供核對)... <<<\n");
    double expected_global_sum = 0.0;
    int validation_passed = 1;

    for (size_t i = 0; i < MATRIX_SIZE; i++) {
        // 先預設該行的第一個元素是最大值
        float expected_row_max = matrix[i * MATRIX_SIZE]; 
        
        for (size_t j = 0; j < MATRIX_SIZE; j++) {
            float val = matrix[i * MATRIX_SIZE + j];
            expected_global_sum += val; // 計算單執行緒總和
            
            // 計算單執行緒極值
            if (val > expected_row_max) {
                expected_row_max = val;
            }
        }

        // 1. 驗證行極值：將單執行緒算出的極值，與多執行緒陣列中的結果比對
        if (row_max_array[i] != expected_row_max) {
            printf(" error：Row %zu 的極值不吻合！預期: %f, 實際: %f\n", 
                   i, expected_row_max, row_max_array[i]);
            validation_passed = 0;
            break; // 錯一個就不用比了，直接中斷
        }
    }

    // 2. 驗證全局總和
    // 浮點數運算會有微小的精度誤差 (Epsilon)，尤其是加法順序不同的時候。
    // 所以我們不能用 == 來比對浮點數，必須取相減的絕對值，確認誤差小於一個極小值。
    double diff = expected_global_sum - global_sum;
    if (diff < 0) diff = -diff; // 簡單的絕對值處理

    if (diff > 1e-2) { // 容許 0.01 的浮點數累加誤差
        printf("error：全局總和不吻合！預期: %f, 實際: %f\n", 
               expected_global_sum, global_sum);
        validation_passed = 0;
    }

    // 最終宣判
    if (validation_passed) {
        printf("Pass\n");
    } else {
        printf("Fail\n");
    }
    // ==========================================
    // release memory
  

    free(threads);
    free(thread_args);
    free(thread_results);
    free(row_max_array); 
    free(matrix);
    printf("Matrix memory freed.\n");
    return 0;
}

##### return

所有執行緒完成計算，矩陣總和: 134211673.527968

>>> 啟動結果驗證 (計算單執行緒基準值以供核對)... <<<
Pass
double free or corruption (out)
Aborted (core dumped)

這裡是源自於記憶體對齊 (Memory Alignment)引發了堆積 (Heap) 結構破壞

呼叫` malloc() `或 `calloc() `時，作業系統不僅僅會給你一塊記憶體，它還會在這塊記憶體前塞入一些管理資料 **(Heap Metadata)**，用來記錄這塊記憶體有多大。當你呼叫 free() 時，系統會去讀取這些隱藏的資料來決定要回收多少空間。

// utils.h內，這裡要求了需要對齊64
typedef struct  {
    double local_sum;
    alignas(CACHE_LINE_SIZE) long long final_count;
} thread_data_t;

但` malloc() calloc()`卻不會指定起始位置，只會給你正確的大小，這就導致了汙染，雖然不影響計算數值，但最終的free讀到汙染後會讓OS給出 corruption 並強制 Abortion

這裡可以改用`posix_memalign`取代calloc

thread_data_t *results = NULL;
    if (posix_memalign((void **)&results, CACHELINE_SIZE, num_threads * sizeof(thread_data_t)) != 0) {
        fprintf(stderr, "錯誤：對齊記憶體配置失敗！\n");
        return 1;
    }

或直接把下方的`free`註解掉，不過這是有風險的，stack空間小，如果今天照原樣，而宣告過多，則有塞滿的風險，故可以考慮改放heap

    // ========== stack version ==========
    pthread_t threads[num_threads];
    thread_args_t thread_args[num_threads];
    thread_data_t thread_results[num_threads]; 
    // check if thread_results is correctly allocated
    float *row_max_array = malloc(MATRIX_SIZE * sizeof(float)); 
    
    // ========== heap version ==========
    // pthread_t *threads = malloc(num_threads * sizeof(pthread_t));
    // thread_args_t *thread_args = malloc(num_threads * sizeof(thread_args_t));
    // thread_data_t *thread_results = NULL;
    // posix_memalign((void **)&thread_results, 64, num_threads * sizeof(thread_data_t));

### Step 3 bash and plot
建立自動測試腳本與繪圖

# ~/scripts/run_bench.sh
#!/bin/bash
cd "$(dirname "$0")/.." || exit 1
echo "==============================================="
echo "  Parallel Matrix Extractor Benchmark Script  "
echo "==============================================="

# 1. 自動重新編譯
echo "Recompiling..."
make clean > /dev/null 2>&1
make > /dev/null 2>&1

if [ $? -ne 0 ]; then
    echo "Compile Error！plz check code。"
    exit 1
fi
OUT_DIR="results"
mkdir -p "$OUT_DIR"
# Make sure the plots directory exists too
mkdir -p "$OUT_DIR/plots"

CSV_FILE="$OUT_DIR/benchmark_results.csv"
PNG_FILE="$OUT_DIR/plots/speedup_curve.png"
# 定義要測試的執行緒數與採樣次數
THREADS=(1 2 4 8 16)
RUNS=1
CSV_FILE="$OUT_DIR/benchmark_results.csv"
PNG_FILE="$OUT_DIR/plots/speedup_curve.png"
# 初始化 CSV 檔案並寫入標題
echo "Threads,AverageTime" > "$CSV_FILE"

echo "Compile Success！Start Benchmarking(Each number of threads will run $RUNS times)..."
echo "------------------------------------------"

# 2. 雙重迴圈：測試不同執行緒數，每次跑 5 遍
for t in "${THREADS[@]}"
do
    echo -n "$t threads... "
    TOTAL_TIME=0

    for ((i=1; i<=RUNS; i++))
    do
        # 執行程式並將結果存入變數 OUTPUT
        OUTPUT=$(./extractor $t)
        
        # 使用 grep 找出含有「耗時」的那一行，並用正則表達式提取出浮點數數字
        TIME=$(echo "$OUTPUT" | grep "核心計算耗時" | grep -oE '[0-9]+\.[0-9]+')
        
        # 萬一抓不到數字的防呆機制
        if [ -z "$TIME" ]; then
            echo "Error：Fetching time error, plz check main.c format"
            exit 1
        fi

        # 使用 awk 進行浮點數累加
        TOTAL_TIME=$(awk "BEGIN {print $TOTAL_TIME + $TIME}")
    done

    # 計算 5 次的平均值
    AVG_TIME=$(awk "BEGIN {print $TOTAL_TIME / $RUNS}")
    echo "Avg Time: $AVG_TIME 秒"

    # 將結果寫入 CSV 檔案
    echo "$t,$AVG_TIME" >> $CSV_FILE
done

echo "------------------------------------------"
echo "Data collected！Save in $CSV_FILE"
echo "Ready to plot (Speedup Curve)..."

# 3. 自動生成 Python 繪圖腳本
cat << 'EOF' > plot_speedup.py
import csv
import sys
import matplotlib.pyplot as plt
input_csv = sys.argv[1]
output_png = sys.argv[2]
try:
    threads = []
    times = []
    # 讀取剛剛 Bash 產生的 CSV
    with open(input_csv, 'r') as f:
        reader = csv.DictReader(f)
        for row in reader:
            threads.append(int(row['Threads']))
            times.append(float(row['AverageTime']))

    # 計算加速比 Speedup = T1 / Tn
    t1_time = times[0]
    speedup = [t1_time / t for t in times]

    # 設定圖表樣式
    plt.figure(figsize=(8, 5))
    
    # 畫出實際加速比 (藍線)
    plt.plot(threads, speedup, marker='o', linestyle='-', color='b', label='Actual Speedup')
    # 畫出理想加速比 (紅虛線：如果 2 個 Thread 快 2 倍，4 個快 4 倍的理論值)
    plt.plot(threads, threads, linestyle='--', color='r', alpha=0.6, label='Ideal Speedup')

    plt.title('Parallel Matrix Extractor - Speedup Curve')
    plt.xlabel('Number of Threads')
    plt.ylabel('Speedup (T1 / Tn)')
    plt.xticks(threads)
    plt.grid(True, linestyle='--', alpha=0.7)
    plt.legend()

    # 儲存圖片
    plt.savefig(output_png, dpi=300)
    print(f"Success！Save as {output_png}")

except ImportError:
    print("Error, lack of python module: matplotlib。")
    print("Solution：Checked if'pip install matplotlib' ,execute 'python3 plot_speedup.py'。")
except Exception as e:
    print(f"plot error: {e}")
EOF

# 4. 呼叫 Python 執行繪圖
python3 plot_speedup.py "$CSV_FILE" "$PNG_FILE"

rm plot_speedup.py

#### Result

Threads,AverageTime
1,0.294057
2,0.165808
4,0.084245
8,0.037628
16,0.044957


### Step 4 Thread Affinity
作業系統 (OS) 的排程器容易將task依據core的忙碌狀態做負載平衡，而task遷移時TLB、L1、L2等資料的報廢與更新將造成巨大的開銷

同時，在Intel的處理器中，有不少型號都是有P/E核的配置，這使得核心間的效能有所差距
#### utils.h

typedef struct {
    int thread_id;                 // 執行緒的編號 (0, 1, 2...)
    int core_id;                   // 執行緒綁定的核心編號
    size_t start_row;              // 負責計算的起始行
    size_t end_row;                // 負責計算的結束行 (不包含此行)
    float *matrix;                 // 整個矩陣的指標
    thread_data_t *thread_results; // 指向結果陣列
    float *row_max_array;          // 指向每行最大值的陣列
} thread_args_t;

#### worker.c

/*
 *  worker.c
 *  version 2.0
 *  Modified ver 2.0 on: 2025/4/1 
 *  Modified Content : affinity
 *  Created on: 2025/3/27
 *  Author: Jimmy 
*/
// #define _GNU_SOURCE here or in utils.h (the head of the file)
#include "utils.h"



void* worker_task(void* arg) {
    // 1. transform void* arg to thread struct, pointer to the struct we defined in utils.h 
    thread_args_t *args = (thread_args_t*)arg;
    // here we can access the fields of the struct, e.g., args->thread_id, args->start_row, etc.
    int tid = args->thread_id;
    
    int core_id = args->core_id; // 從參數結構中獲取核心 ID
    
    // ==========================================
    // 執行緒綁核 (Thread Affinity) 邏輯
    // ==========================================
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);          // 1. 清空 CPU 集合
    CPU_SET(core_id, &cpuset);  // 2. 將我們指定的 core_id 加入集合
    // 取得當前執行緒並強制綁定
    pthread_t current_thread = pthread_self();
    int affinity_status = pthread_setaffinity_np(current_thread, sizeof(cpu_set_t), &cpuset);
    if (affinity_status != 0) {
        printf("[Thread %d] 警告：無法綁定到 Core %d\n", tid, core_id);
    } else {
        // 印出來確認有綁定成功
        printf("[Thread %d] 成功綁在 CPU Core %d\n", tid, core_id);
    }
    // ==========================================

    double sum = 0.0; // 暫存用的局部變數，放在 CPU Register 裡最快！

    // 2. Start work：只跑自己的 Rows
    for (size_t i = args->start_row; i < args->end_row; i++) {
        // Columns
        float current_row_max = args->matrix[i * MATRIX_SIZE];
        for (size_t j = 0; j < MATRIX_SIZE; j++) {
            // 一維陣列模擬二維陣列的公式： 索引 = (行號 * 總列數) + 列號
            sum += args->matrix[i * MATRIX_SIZE + j];
            if (args->matrix[i * MATRIX_SIZE + j] > current_row_max) {
                current_row_max = args->matrix[i * MATRIX_SIZE + j];
            }
        }
        args->row_max_array[i] = current_row_max;
    }

    // 3. 計算完畢，把結果寫入專屬的記憶體位置 (已 Padding 過，不會有 False Sharing)
    args->thread_results[tid].local_sum = sum;

    // print log to console
    printf("[Thread %d] 完成計算 Rows %zu ~ %zu，局部總和: %f\n", 
           tid, args->start_row, args->end_row - 1, sum);

    return NULL; // 執行緒結束
}

#### main.c

 size_t rows_per_thread = MATRIX_SIZE / num_threads;
    printf("\n %d 個thread開始作業...\n", num_threads);
    
    for (int i = 0; i < num_threads; i++) {
        thread_args[i].thread_id = i;
        thread_args[i].core_id = i; // <- 先按順序綁
        
        thread_args[i].start_row = i * rows_per_thread;
        // 如果是最後一個執行緒，就包辦剩下的所有行數 (避免無法整除的問題)
        thread_args[i].end_row = (i == num_threads - 1) ? MATRIX_SIZE : (i + 1) * rows_per_thread;
        thread_args[i].matrix = matrix;
        thread_args[i].thread_results = thread_results;
        thread_args[i].row_max_array = row_max_array;

        // 建立執行緒並執行 worker_task
        pthread_create(&threads[i], NULL, worker_task, &thread_args[i]);
    }

# 查看CPU狀況
lscpu -e 

# return
CPU NODE SOCKET CORE L1d:L1i:L2:L3 ONLINE
  0    0      0    0 0:0:0:0          yes
  1    0      0    0 0:0:0:0          yes
  2    0      0    1 1:1:1:0          yes
  3    0      0    1 1:1:1:0          yes
  4    0      0    2 2:2:2:0          yes
  5    0      0    2 2:2:2:0          yes
  6    0      0    3 3:3:3:0          yes
  7    0      0    3 3:3:3:0          yes

依照cache，core0 由CPU0和1組成，而我並沒有P/E核的問題

這個core的切割，依賴於**Hyper-Threading**

### Step 5 exetreme condition
* 策略 A：資源獨享 (最佳效能)
把 4 個執行緒分配到完全不同的實體核心上。
* 綁核目標：CPU 0, 2, 4, 6。
* 優勢：每個人都有自己獨立的 L1/L2 Cache，計算單元完全不用跟別人擠。

* 策略 B：資源互卡 (最差效能)

* 把threads塞進同一個實體核心裡。
綁核目標：CPU 0, 1, 2, 3。
* 劣勢：Thread 0 和 Thread 1 被迫擠在 CORE 0 裡面，它們必須搶同一個 L1 Cache 和 ALU（算術邏輯單元），效能絕對會互相拖累

size_t rows_per_thread = MATRIX_SIZE / num_threads;
    printf("\n %d 個thread開始作業...\n", num_threads);
    // ================= Affinity =========================


    // section 2
    // int core_map[] = {0, 2, 4, 6, 8, 10, 12, 14};
    
    // section 3 
    int core_map[] = {0, 1};
    
    
    int map_size = sizeof(core_map) / sizeof(core_map[0]);
    // ====================================================
        
    for (int i = 0; i < num_threads; i++) {
        thread_args[i].thread_id = i;
        // section 1
        // thread_args[i].core_id = i;
        // section 2 & 3
        thread_args[i].core_id = core_map[i % map_size];
        
// 下方照舊

#### return (2 core, 8 threads)

 8 個thread開始作業...
[Thread 0] 成功綁在 CPU Core 0
[Thread 1] 成功綁在 CPU Core 1
[Thread 3] 成功綁在 CPU Core 1
[Thread 2] 成功綁在 CPU Core 0
[Thread 5] 成功綁在 CPU Core 1
[Thread 6] 成功綁在 CPU Core 0
[Thread 4] 成功綁在 CPU Core 0
[Thread 7] 成功綁在 CPU Core 1

>>> 核心計算耗時: 0.140819 秒 <<<

#### return (8 core, 8 threads)

 8 個thread開始作業...
[Thread 0] 成功綁在 CPU Core 0
[Thread 2] 成功綁在 CPU Core 4
[Thread 3] 成功綁在 CPU Core 6
[Thread 7] 成功綁在 CPU Core 14
[Thread 6] 成功綁在 CPU Core 12
[Thread 4] 成功綁在 CPU Core 8
[Thread 5] 成功綁在 CPU Core 10
[Thread 1] 成功綁在 CPU Core 2

>>> 核心計算耗時: 0.071867 秒 <<<

#### return (16 core, 8 threads)

[Thread 1] 成功綁在 CPU Core 1
[Thread 5] 成功綁在 CPU Core 5
[Thread 6] 成功綁在 CPU Core 6
[Thread 3] 成功綁在 CPU Core 3
[Thread 4] 成功綁在 CPU Core 4
[Thread 2] 成功綁在 CPU Core 2
[Thread 0] 成功綁在 CPU Core 0
[Thread 7] 成功綁在 CPU Core 7

>>> 核心計算耗時: 0.059652 秒 <<<

### Step 6 without padding
最後要做 False Sharing Defense 與 Cache Miss 驗證，若無padding
* Thread 0 的 local_sum 和 Thread 1 的 local_sum 會被塞進同一個 64 Bytes 的 Cache Line 裡。
* 當 Thread 0 更新自己的總和時，CPU 會為了保證資料一致性，強制把 Thread 1 核心裡的同一個 Cache Line 標記為「失效 (Invalid)」。
* Thread 1 下一次要寫入時，就發生了 Cache Miss，必須重新去主記憶體抓資料。

最後最慘就變成pingpong，OS介入
#### utils.h 增加

# define USE_PADDING 1 // 1: 有防禦，0: 無防禦

# if USE_PADDING
    // [有防禦] 在 local_sum 後面加上足夠的 padding，確保每個 thread_data_t 都獨占一個 Cache Line，避免 False Sharing
typedef struct  {
    double local_sum;
    alignas(CACHE_LINE_SIZE) long long final_count;
} thread_data_t;
#else
    // [無防禦] 乾淨溜溜的結構體，多個 local_sum 會擠在同一個 Cache Line 裡互相傷害
    typedef struct {
        double local_sum;
    } thread_data_t;
#endif

#### worker.c

/*
 *  worker.c
 *  version 3.0
 *  Modified ver 3.0 on: 2025/4/1 
 *  Modified Content : affinity, padding
 *  Created on: 2025/3/27
 *  Author: Jimmy 
*/
// #define _GNU_SOURCE here or in utils.h (the head of the file)
#include "utils.h"



void* worker_task(void* arg) {
    // 1. transform void* arg to thread struct, pointer to the struct we defined in utils.h 
    thread_args_t *args = (thread_args_t*)arg;
    // here we can access the fields of the struct, e.g., args->thread_id, args->start_row, etc.
    int tid = args->thread_id;
    
    int core_id = args->core_id; // 從參數結構中獲取核心 ID
    
    // ==========================================
    // 執行緒綁核 (Thread Affinity) 邏輯
    // ==========================================
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);          // 1. 清空 CPU 集合
    CPU_SET(core_id, &cpuset);  // 2. 將我們指定的 core_id 加入集合
    // 取得當前執行緒並強制綁定
    pthread_t current_thread = pthread_self();
    int affinity_status = pthread_setaffinity_np(current_thread, sizeof(cpu_set_t), &cpuset);
    if (affinity_status != 0) {
        printf("[Thread %d] 警告：無法綁定到 Core %d\n", tid, core_id);
    } else {
        // 印出來確認有綁定成功
        printf("[Thread %d] 成功綁在 CPU Core %d\n", tid, core_id);
    }
    // ==========================================

    #if USE_PADDING_WORKER
    double sum = 0.0; // 暫存用的局部變數，放在 CPU Register 裡最快！
    #else 
    args->thread_results[tid].local_sum = 0.0;
    #endif
    // 2. Start work：只跑自己的 Rows
    for (size_t i = args->start_row; i < args->end_row; i++) {
        // Columns
        float current_row_max = args->matrix[i * MATRIX_SIZE];
        for (size_t j = 0; j < MATRIX_SIZE; j++) {
            // 一維陣列模擬二維陣列的公式： 索引 = (行號 * 總列數) + 列號
            #if USE_PADDING_WORKER
            sum += args->matrix[i * MATRIX_SIZE + j];
            # else 
            args->thread_results[tid].local_sum += args->matrix[i * MATRIX_SIZE + j];
            #endif
            if (args->matrix[i * MATRIX_SIZE + j] > current_row_max) {
                current_row_max = args->matrix[i * MATRIX_SIZE + j];
            }
        }
        args->row_max_array[i] = current_row_max;
    }

    // 3. 計算完畢，把結果寫入專屬的記憶體位置 (已 Padding 過，不會有 False Sharing)
    #if USE_PADDING_WORKER
    args->thread_results[tid].local_sum = sum;
    printf("[Thread %d] 完成計算 Rows %zu ~ %zu，局部總和: %f\n", 
           tid, args->start_row, args->end_row - 1, sum);
    #else
    printf("[Thread %d] 完成計算 Rows %zu ~ %zu，局部總和: %f\n", 
           tid, args->start_row, args->end_row - 1, args->thread_results[tid].local_sum);
    #endif

    // print log to console

    

    return NULL; // 執行緒結束
}

結果其實不會差到太多，Compiler的優化有一定的影響，加上無法看到L1 miss
所以在utils.h內加上`volatile`

# if USE_PADDING
typedef struct  {
    double local_sum;
    alignas(CACHE_LINE_SIZE) long long final_count;
} thread_data_t;
#else
    typedef struct {
        volatile  double local_sum;
    } thread_data_t;
#endif

# padding
>>> 核心計算耗時: 0.037044 秒 <<<

# without padding
>>> 核心計算耗時: 0.193459 秒 <<<

END