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 都是經過一定的規則去命名的，所以實際寫起來並不會像想象中一樣那麼困難。

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