## 指令級平行與編譯器自動化 (OpenMP)
首先，需要理解 OpenMP 如何在編譯時期（Compile-time）將簡單的指令轉換為複雜的執行緒管理邏輯，並掌握數據在並行區域間的流動

## Fork-Join
>當你在 C 語言中加入 #pragma omp parallel 時，編譯器背後到底做了什麼？

1. Fork-Join 執行流程
* Fork：
當主執行緒(Master)遇到並行指令時，會Fork出一組執行緒團隊（Team of Threads）。
* Parallel Region：
所有執行緒同時執行大括號內的程式碼。
* Join：
在並行區域結束處有一個「隱含的同步點（Implicit Barrier）」，所有執行緒匯合後銷毀，只剩下主執行緒繼續執行。

2. Data Sharing
> pthread時，我們總需要一個`void* arg`，(worker wrap)

在 Pthreads 中，我們必須手動處理 `void* arg`；在 OpenMP 中，我們透過 Clauses 來定義變數的歸屬：

* **shared**
預設屬性。所有執行緒存取同一個記憶體位址（需注意 Race Condition）。
* **private**
每個執行緒在自己的 Stack 上建立一個同名變數的複本（初值未定義）。
* **firstprivate**
類似 private，但會繼承主執行緒中該變數的初始值。
* **reduction**
最常用的優化指令。它會為每個執行緒建立私有變數，並在 Join 時自動進行加總、相乘等操作，完全避開了手動加鎖的開銷。

### Sample Code : omp_basic

// omp_basic.c
#include <omp.h>
#include <stdio.h>

#define TEST 0
int main() {
#if !TEST
    int total_sum = 0;
    int data[100];
    for(int i=0; i<100; i++) data[i] = 1;

    // 只需要這一行，編譯器就會幫你完成 Fork, Work-sharing, 與 Reduction
    #pragma omp parallel for reduction(+:total_sum)
    for (int i = 0; i < 100; i++) {
        total_sum += data[i];
    }

    printf("Total Sum: %d\n", total_sum);
    printf("預設執行緒數: %d\n", omp_get_max_threads());
    
#else 
    long long total_sum = 0;

    struct timespec m_start, m_end;
    clock_gettime(CLOCK_MONOTONIC, &m_start);

    // num_threads(THREADS): 強制指定使用 16 個執行緒
    // reduction(+:total_sum): 告訴編譯器幫我們做區域加總與合併
    #pragma omp parallel for num_threads(THREADS) reduction(+:total_sum)
    for (long long i = 1; i <= LIMIT; i++) {
        total_sum += i;
    }

    clock_gettime(CLOCK_MONOTONIC, &m_end);

    printf("計算完成！1 到 %lld 的總和是: %lld\n", LIMIT, total_sum);
    printf("執行時間: %f 秒\n", (m_end.tv_sec - m_start.tv_sec) + (m_end.tv_nsec - m_start.tv_nsec) / 1e9);
    printf("使用的執行緒數: %d\n", THREADS);

#endif
    return 0;
}

> 與~ /src/pthreads/thread_trace.c 做比較

pthread :

    計算完成！1 到 1000000000 的總和是: 500000000500000000

    執行時間: 0.034421 秒

    使用的執行緒數: 16

openmp :

    計算完成！1 到 1000000000 的總和是: 500000000500000000

    執行時間: 0.047312 秒

    使用的執行緒數: 16

### 推測
當下達 `#pragma omp parallel` 時，OpenMP 在底層必須做很多安全檢查：
1. 它要喚醒執行緒池 (Thread Pool )。
> 於補充說明
2. 它要建立一個隱藏的 Barrier (屏障)，確保所有執行緒在迴圈結束時等待。
3. 它要處理 reduction 的記憶體對齊與安全合併機制。

這些是通用與保險所造成的 Overhead
> 不過現實計算更複雜，此處只是用最簡易的加法累計來測量。
#### 觀察

# 可以產出一個，比assemblely好一點的展開code 
# 找到 __builtin_GOMP_parallel 這是fork的位置
gcc -O3 -fopenmp -fdump-tree-ompexp omp_basic.c -o omp_basic

### Tracing code

// omp_trace.c
#include <omp.h>
#include <stdio.h>
#include <unistd.h>

void trace_info(const char* stage) {
    int id = omp_get_thread_num();
    int total = omp_get_num_threads();
    // 使用 printf 觀察執行緒的「分身」與「匯合」
    printf("[Thread %d/%d] Stage: %s\n", id, total, stage);
}

int main() {
    printf("--- 進入主執行緒 (Master Only) ---\n");
    trace_info("Sequential Start");

    printf("\n--- 觸發 #pragma omp parallel (Forking...) ---\n");
    #pragma omp parallel
    {
        // 這裡會印出多行，代表 Fork 成功
        trace_info("Inside Parallel Region");
        
        #pragma omp master
        {
            printf("  > 只有 Master 執行緒 (%d) 會跑這行\n", omp_get_thread_num());
        }
    }

    printf("\n--- 離開並行區域 (Joined) ---\n");
    trace_info("Sequential End");

    return 0;
}

或看環境變數

# env var
export OMP_DISPLAY_ENV=VERBOSE
./omp_basic

# unset env var
unset OMP_DISPLAY_ENV
export OMP_DISPLAY_ENV=FALSE

# extra visualize tool
Intel VTune / Score-P

## Scheduling
> 當**Load Imbalance**，則需要調整，但調整又會出現overhead。

### Scheduling Strategies

OpenMP 提供了四種主要的排程方式，用來處理不同的任務特性：

| 排程類型 | 運作機制 | 適用場景 | 開銷 (Overhead) |
| :--- | :--- | :--- | :--- |
| **`static (default)`** | 在編譯/啟動時就平分好任務。 | 每個迴圈計算量幾乎相等。 | 最低 |
| **`dynamic`** | 執行緒算完一個「區塊」後，再去申請下一個。 | 任務計算量不可預測（如：分形計算、不規則矩陣）。 | 較高 (需同步隊列) |
| **`guided`** | 初始區塊大，隨後逐漸縮小。 | 兼顧 `dynamic` 的靈活與減少申請次數。 | 中等 |
| **`runtime`** | 由環境變數 `OMP_SCHEDULE` 決定。 | 實驗階段，測試哪種最快。 | 視設定而定 |

需要注意的是，`omp_get_max_threads()`可以看使用多少threads，而如果沒有事先

#pragma omp parallel for num_threads(THREADS) reduction(+:total_sum)
或
export OMP_NUM_THREADS=n

openmp會在確認完硬體核心數的情況下直接default = max_core

---

## Sample Code : imbalance

// omp_sched.c
#include <omp.h>
#include <stdio.h>
#include <unistd.h>

void heavy_work(int iterations) {
    // 模擬負載重計算：迴圈次數隨 i 增加
    // 避免優化
    volatile double dummy = 0;
    for (int i = 0; i < iterations * 1000000; i++) {
        dummy += 1.0;
    }
}

int main() {
    int n = 20;
    double start, end;

    // 測試指令：可以手動更換為 dynamic, 1 或 guided
    printf("--- 測試 Static Scheduling ---\n");
    start = omp_get_wtime();
    
    #pragma omp parallel for schedule(static, 1)
    for (int i = 0; i < n; i++) {
        int tid = omp_get_thread_num();
        printf("Thread %d 執行迭代 %2d\n", tid, i);
        heavy_work(i); // 迭代次數越多，計算越重
    }
    
    end = omp_get_wtime();
    printf("Static Time: %f s\n\n", end - start);

    return 0;
}

>　( < type>, <chunk_size>)

* `schedule(static)`
直接平均分配
* `schedule(static,1)`
輪流給，每次**chunk_size**個(Round-robin)
> 注意 False Sharing，task無padding的情況下，64bytes cache會必定會引發false sharing
* `dynamic, 4`

    # recommend ! but only for auto 
    export OMP_SCHEDULE="dynamic,4"
    ./omp_sched

調整 `chunk size` (後面的數字)，觀察這對效能的微小影響。

### static,4

--- 分配結果統計 ---
Thread 0 處理的迭代: [ 0 1 2 3 64 65 66 67 ] (總計: 8 次)
Thread 1 處理的迭代: [ 4 5 6 7 68 69 70 71 ] (總計: 8 次)
Thread 2 處理的迭代: [ 8 9 10 11 72 73 74 75 ] (總計: 8 次)
Thread 3 處理的迭代: [ 12 13 14 15 76 77 78 79 ] (總計: 8 次)
Thread 4 處理的迭代: [ 16 17 18 19 80 81 82 83 ] (總計: 8 次)
Thread 5 處理的迭代: [ 20 21 22 23 84 85 86 87 ] (總計: 8 次)
Thread 6 處理的迭代: [ 24 25 26 27 88 89 90 91 ] (總計: 8 次)
Thread 7 處理的迭代: [ 28 29 30 31 92 93 94 95 ] (總計: 8 次)
Thread 8 處理的迭代: [ 32 33 34 35 96 97 98 99 ] (總計: 8 次)
Thread 9 處理的迭代: [ 36 37 38 39 ] (總計: 4 次)
Thread 10 處理的迭代: [ 40 41 42 43 ] (總計: 4 次)
Thread 11 處理的迭代: [ 44 45 46 47 ] (總計: 4 次)
Thread 12 處理的迭代: [ 48 49 50 51 ] (總計: 4 次)
Thread 13 處理的迭代: [ 52 53 54 55 ] (總計: 4 次)
Thread 14 處理的迭代: [ 56 57 58 59 ] (總計: 4 次)
Thread 15 處理的迭代: [ 60 61 62 63 ] (總計: 4 次)

執行時間: 2.188987 秒

### dynamic,4

-- 分配結果統計 ---
Thread 0 處理的迭代: [ 60 61 62 63 ] (總計: 4 次)
Thread 1 處理的迭代: [ 8 9 10 11 72 73 74 75 ] (總計: 8 次)
Thread 2 處理的迭代: [ 48 49 50 51 ] (總計: 4 次)
Thread 3 處理的迭代: [ 56 57 58 59 ] (總計: 4 次)
Thread 4 處理的迭代: [ 24 25 26 27 88 89 90 91 ] (總計: 8 次)
Thread 5 處理的迭代: [ 20 21 22 23 84 85 86 87 ] (總計: 8 次)
Thread 6 處理的迭代: [ 36 37 38 39 ] (總計: 4 次)
Thread 7 處理的迭代: [ 32 33 34 35 96 97 98 99 ] (總計: 8 次)
Thread 8 處理的迭代: [ 44 45 46 47 ] (總計: 4 次)
Thread 9 處理的迭代: [ 28 29 30 31 92 93 94 95 ] (總計: 8 次)
Thread 10 處理的迭代: [ 4 5 6 7 68 69 70 71 ] (總計: 8 次)
Thread 11 處理的迭代: [ 16 17 18 19 80 81 82 83 ] (總計: 8 次)
Thread 12 處理的迭代: [ 12 13 14 15 76 77 78 79 ] (總計: 8 次)
Thread 13 處理的迭代: [ 52 53 54 55 ] (總計: 4 次)
Thread 14 處理的迭代: [ 40 41 42 43 ] (總計: 4 次)
Thread 15 處理的迭代: [ 0 1 2 3 64 65 66 67 ] (總計: 8 次)

執行時間: 2.456770 秒

chunk_size = 16 
-> 執行時間: 1.868869 秒

---

### 排程開銷
`dynamic` 需要一個global table，threads每次領任務都要進行一次同步（Lock/Atomic）。如果每個任務本身極短（例如：單純的加法），`dynamic` 的申請時間甚至會比計算時間還長。

## 無法預測的for-loop
這裡是專門處理非線性數據結構（如樹、圖）或遞迴演算法時，在無法提前得知總 loop 次數時需要做的。

#basic
#pragma omp parallel

# Linear
#pragma omp parallel for schedule

# non-Linear
#pragma omp task

### Tasking Parallel
* 任務產生器
通常由 single thread 負責，不斷把任務丟進Work pool。
* Exe
其它 threads 會從pool裡拿出來work出來跑（這叫 Work-stealing）。
* key : `taskwait / taskgroup`
並行任務是 unsync。如果你希望等待再提交，你必須加上 #pragma omp taskwait，否則主執行緒會直接跑掉，導致結果錯誤。
### Task Granularity
建立一個 task 需要配置記憶體、放入隊列、由排程器調度。如果 $n$ 很小（例如 $n=5$），計算只需幾ns，但建立任務要幾百ns。這就是 細粒度開銷Fine-grained Overhead
### Cutoff
> 當問題已經小到不值得分給別人做時，請自己算完

即，當task大於`cutoff`時，才進行平行化;反之則自己搞定。所以這裡，當cutoff = 0後，所有threads一拿到task，又開始分工，沒打算生產，這樣一路往下自爆，直到 **task = cutoff**

1. 全局溢出：任務被擠到 Global Queue
2. 鎖（Lock）的介入：為了保證資料正確（不讓兩個 Thread 搶到同一個任務），全域隊列必須加鎖。
3. 排隊死結

總結 `cutoff` 的角色

| 條件 | 動作 | 執行緒行為 |
| :--- | :--- | :--- |
| **$n > \text{cutoff}$** | **建立 Task** | **分工** |
| **$n \le \text{cutoff}$** | **執行 Serial** | **生產** |

### Code

// omp_task.c
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>


long fib_serial(int n) {
    if (n < 2) return n;
    return fib_serial(n - 1) + fib_serial(n - 2);
}

// 平行任務版本
long fib_task(int n, int cutoff) {
    if (n < 2) return n;
    
    // 當小於 cutoff 時，停止產生 Task，改用序列計算
    if (n < cutoff) {
        return fib_serial(n);
    }

    long x, y;
    #pragma omp task shared(x)
    x = fib_task(n - 1, cutoff);

    #pragma omp task shared(y)
    y = fib_task(n - 2, cutoff);

    #pragma omp taskwait
    return x + y;
}

int main() {
    int n, cutoff;
    printf("請輸入 Fibonacci 項數 (建議 30-40): ");
    if (scanf("%d", &n) != 1) return 1;
    printf("請輸入 Task Cutoff 閾值 (建議 20，輸入 0 代表全平行): ");
    if (scanf("%d", &cutoff) != 1) return 1;

    double start, end;
    long result;

    // --- 1. 測量純序列時間 ---
    printf("\n[1] 執行純序列計算...\n");
    start = omp_get_wtime();
    result = fib_serial(n);
    end = omp_get_wtime();
    printf("序列結果: %ld | 耗時: %f 秒\n", result, end - start);

    // --- 2. 測量平行任務時間 ---
    printf("\n[2] 執行 OpenMP Task 計算 (Cutoff=%d)...\n", cutoff);
    start = omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single
        result = fib_task(n, cutoff);
    }
    end = omp_get_wtime();
    printf("平行結果: %ld | 耗時: %f 秒\n", result, end - start);

    return 0;
}

### Test

htop 

n = 40, cutoff = 0

#### htop 顯示 CPU 使用率很低?
> 大家都在分工，誰在那邊跟你玩計算。

由 **「任務生成的傳遞速度」** 與 **「執行緒等待策略（Wait Policy）」** 共同造成的。

##### 100% core
當你執行 $F_{40}$ 且 `cutoff=0` 時，任務是從一個 **單一入口**（Master Thread）開始產生的。

* **發包者（Generators）**：一開始只有一個 Thread 在執行 `fib(40)`。它會迅速產出 `fib(39)` 和 `fib(38)`。
* **擴散過程**：Thread 2 偷走了 `fib(39)`，Thread 3 偷走了 `fib(38)`。這幾位「先搶到任務」的執行緒，會立刻**狂發包**。
* **為什麼 100%**：這些執行緒正處於「產生任務 -> 嘗試塞進隊列 -> 失敗 -> 旋轉等待（Spinning）-> 成功 -> 產生下一個任務」的無限循環中。對於作業系統來說，這些執行緒一直處於「活動（Active）」狀態，所以顯示 100%。

##### 5% core
> 為什麼其它執行緒不去幫忙？

* **鎖競爭（Lock Contention）崩潰**
OpenMP 的Global Task Queue
* **OS 的介入**
當 Thread 5 想要去偷任務時，發現門口已經擠滿了 Thread 1~4，且鎖被鎖住了。
* **掛起（Suspend）**
如果 Thread 5 嘗試幾次都失敗，作業系統核心（Kernel）會先把它**移出執行隊列**
* **為什麼 5%**
在 `htop` 裡，這代表該執行緒大部分時間都在「睡眠（Sleep/Blocked）」，只有偶爾被喚醒起來看看有沒有機會搶到鎖，搶不到又立刻回去睡。

##### OpenMP 的等待策略：Active vs. Passive

這與 OpenMP 的內部設定 `OMP_WAIT_POLICY` 有關：

* **ACTIVE**：執行緒沒事做時會一直繞圈圈（Spin）等任務。這會讓所有核心都顯示 100%，但效率極低。
* **PASSIVE**：執行緒沒事做時會交回控制權給 OS 去睡覺。這就是你看到的 5% 現象。
* **混合狀態**：現代 OpenMP 通常會先讓你「旋轉一小段時間」，如果還是沒事做，就送你去睡覺。

**所以你看到的 `htop` 景象其實是：**
> 有幾個執行緒運氣好，搶到了發包的權利，忙得不可開交（100%）；而大多數執行緒則被擋在「任務隊列」的鎖外面，被 OS 強制送去休息了（5%）。

## 補充
* Threads Pool
對應到`lifecycle.c`中所談到的create/delete overhead，將刪除(銷毀)改成睡眠，使Threads不會像竹筍一樣。另外，threads的lifecycle是取決於拿到的task何時結束，所以只要在task加while-loop，threads就會不被銷毀。
> 設計條件
> 1. Task Queue
> 2. While-Loop
> 3. Synchronization
> * (Prevent) Mutex
> * (Prevent) Condition Variable

LAB 5
https://hackmd.io/@1p0_VOUHTXGcHlBU9A0OEA/HkMJabKi-l