# HW2 陳克盈 112062205

## Implementation

### A.

#### Load balancing
設定兩個變數 `batch_x, batch_y`，代表 `x, y` 軸的 batch size，並依照 `iters` 參數分成兩種情況：
1. `iters > 10000`：每個像素點會進行多次迭代，但因為有些點會在還沒有迭代到指定步數就跳出（x^2 + y^2 >= 4），會造成多個點計算量的不平均。在這個情況下，將 `batch_x` 設定為 `max(1, (int)(width / num_threads / 4))`，並將 `batch _y` 設定為 `1`，利用更小的 batch size 來提升 load balancing 的效果
2. `iters <= 10000`：將 `batch_x` 設定為 `width / num_threads`, `batch_y` 設定為 `width / num_threads / 12`，也就是平均每個 thread 會分到 `num_threads * 12` 塊區域。

#### 分配工作
首先宣告以下物件：
- `std::pair<int, int> tasks[24][64005]`：每個 threads 的預設工作
- `int tasks_sz[24]`：每個 threads 預設分配幾個工作
- `std::atomic_int nxt_task[24]`：每個 threads 下一個要做的工作是什麼，因為可能會有多個執行緒存取這個變數，因此使用 atomic 的方式宣告

接著利用 pthreads 開出 12 個 threads，呼叫 `calculate` 函式。在函式最一開始，將每個 threads 的預設工作放進陣列裡：（`y, x` 代表著從 `(x, y)` 這個點開始，計算 `(x, y), (x, y + batch_y), (x + batch_x, y), (x + batch_x, y + batch_y)` 這個矩形範圍內的像素點）

int ystep = num_threads * batch_y;
for (int y = id * batch_y; y < height; y += ystep) {
    for (int x = 0; x < width; x += batch_x) {
        tasks[id][tasks_sz[id]++] = std::make_pair(y, x);
    }
}

然後每個 threads 從自己的預設工作開始做起，當 thread $i$ 的預設工作做完後，從 $i + 1, i + 2, \dots$ 開始檢查，看其他 thread 有沒有還沒完成的工作，如果有就把它搶過來並更新該 thread 下一個要做的工作 index。

#### 計算
計算的部分由於像素點之間沒有依賴性，因此可以直接使用 AVX512，每次操作 8 個 double 來增加速度，使用了以下幾種 AVX512 function 來進行運算：
- `_mm512_fmadd_pd(a, x, y)`：計算 `ax + y`
- `_mm512_set1_pd(x)`：設定一個由 8 個 `x` 組成的 AVX512 double
- `_mm512_add_pd(x, y)`：相加兩數
- `_mm512_sub_pd(x, y)`：相減兩數
- `_mm512_mul_pd(x, y)`：相乘兩數
- `_mm512_setzero_pd`：設定變數 0
- `_mm512_mask_add_epi32(x, masks, y, z)`：將 `masks = 1` 的位置進行 `x = y + z` 的操作（`masks` 是一個 8-bit 變數，代表著 AVX512 變數內的每個位置）
- `_mm512_cmplt_pd_mask(x, y)`：對於變數內每個位置的值，進行 `x < y` 的比較，並將每個位的比較結果生成出一個 8-bit mask
- `_mm512_mask_storeu_epi32(ptr, mask, x)`：從 `ptr` 開始，將 `mask = 1` 的對應位置設定為 `x`

利用以上函式，便可將 sequential 的程式碼轉成 AVX512 的格式，最後再將不滿 8 個的部分用 sequential 程式碼額外計算即可。

#### 儲存結果
首先，將 png 的壓縮等級調為 0，減少壓縮所佔的時間，接著將範例程式碼中的 `p % 16 * 16` 改寫為 `(p << 28) >> 24`，利用位元運算加速，最後將計算每個像素點的過程利用 AVX512 加速，搭配其他範例程式碼原有的 function call，便完成了 `write_png` 的加速

### B.
直接將 height 切成長度幾乎一致的 chunk，並分配到各個 Process 運算，搭配原有的 pthreads 就是我的實作。

## Experiment & Analysis

### Methodology
我的實驗都是在 QCT 的機器上進行的，我利用 `gettimeofday()` 這個 function 得出毫秒級別的時間，並將運算過程分成三個階段：Input, Computing, Output。

測資的部分，我選用測資 `slow01` 這個迭代 174170376 次，圖片大小為 `2549x1439` 的測資作為高迭代的測資代表，並以 `strict34` 這個迭代 10000 次，圖片大小為 `7680x4320` 的測資作為大測資的代表

### Plots & Discussion
#### A.
##### slow01
- 下圖為 `slow01` 在不同 threads 數量下的 IO/Computing 時間比，IO 時間幾乎可以忽略不計
- 下圖為 `slow01` 在不同 threads 數量下的 Speedup，可以發現幾乎是呈現線性成長。會有一部分的效能損失推測是在建立 pthread 並生成 task pool 時的損耗。
- 下圖為 `slow01` 在不同 threads 數量下，threads 完成時間的全距，反應了 load balancing 的效果。能夠觀察到當 thread 數量少的時候，因為切的 chunk size 足夠大，因此較不容易有不平衡的狀況發生。而 thread 數量大的時候，由於切的塊數足夠多，因此相比於切的不夠大，也不夠多的 6 個 threads 比起來，能夠起到更好的 load balancing 效果

##### strict34
- `strict34` 與 `slow01` 一樣，IO 的時間幾乎可以忽略
- 下圖為 `strict34` 在不同 threads 數量下的 Speedup，可以發現比起 `slow01`，`strict34` 呈現的 Speedup 更加線性，這是因為在迭代次數低的情況下，batch size 較大，切出來的塊數也比較少，因此 task pool 對於效能的影響就更小了
- 下圖為 `struct34` 在不同 threads 數量下，threads 完成時間的全距，由於迭代次數較小，因此較不容易出現不同像素的運算量相差較大的情況，因此全距比起 `slow01` 還要低上不少

#### B.
- 下圖為 `strict34` 在 `thread x process` 為定值時的執行時間比例。因為 IO 集中在 process 0 的緣故，因此不同組合之下的 IO time 基本一致，而隨著 process 數下降，雖然每個 Process 的 Computing 時間因為沒有額外 load balancing 的關係沒有顯著提升，但 MPI 時間卻有著明顯的下降，導致最後使用 `12 x 1` 的組合才是最好的。

#### Overall
我認為在這個作業的最大難點在於 load balancing，因為無法事先知道測資到底哪些區塊會需要比較多迭代次數，因此在迭代次數上限越大的時候，loading 不平衡的機率就越高。從 `slow01` 與 `strict34` 的比較中也可以發現，`strict34` 這個迭代次數上限比較小的測資，其 Scalibility 就比 `slow01` 好上不少。

另外，在 MPI 的版本中，礙於時間關係，我用的策略只是粗略地將其分成許多寬度相等的長條區域，並分給不同 Process 運算，導致了在 Process 數提高時，運行時間是不減反增。我認為如果在 MPI 的版本中，也引入了 Pthread 的 task pool，也就是利用兩層 task pool 來分攤運算任務，應該能夠使得效能再往上一層。

### Experience & Conclusion
在這次的作業中我練習實作了一個簡單的 task pool 以及分配機制，並從不同測資的特性中觀察出不同情況下，load balancing 的重要程度，而這也是這次作業的最大難點。因為無法事先知道測資到底哪些區塊會需要比較多迭代次數，因此在迭代次數上限越大的時候，loading 不平衡的機率就越高。從 `slow01` 與 `strict34` 的比較中也可以發現，`strict34` 這個迭代次數上限比較小的測資，其 Scalibility 就比 `slow01` 好上不少。

另外，在 MPI 的版本中，礙於時間關係，我用的策略只是粗略地將其分成許多寬度相等的長條區域，並分給不同 Process 運算，導致了在 Process 數提高時，運行時間是不減反增。我認為如果在 MPI 的版本中，也引入了 Pthread 的 task pool，也就是利用兩層 task pool 來分攤運算任務，應該能夠使得效能再往上一層。

除此之外，這次是我第一次手刻 AVX512 的程式碼，之前看到會覺得很醜很難寫，但實際寫過一遍之後，發現雖然是真的很醜，但他的 functino 都是經過一定的規則去命名的，所以實際寫起來並不會像想象中一樣那麼困難。

最後，我還是很好奇第一名的同學到底是怎麼做到比我快一倍的，希望之後有機會看到他的程式碼。