Assignment II: Multi-thread Programming

###### tags: `PP` `交大` # Assignment II: Multi-thread Programming ## Q1 ### Produce a graph for VIEW1 and VIEW2 #### View1 ``` $ ./mandelbrot -t 2 [mandelbrot serial]: [460.751] ms Wrote image file mandelbrot-serial.ppm [mandelbrot thread]: [236.919] ms Wrote image file mandelbrot-thread.ppm (1.94x speedup from 2 threads) $ ./mandelbrot -t 3 [mandelbrot thread]: [282.714] ms Wrote image file mandelbrot-thread.ppm (1.63x speedup from 3 threads) $ ./mandelbrot -t 4 [mandelbrot thread]: [193.399] ms Wrote image file mandelbrot-thread.ppm (2.38x speedup from 4 threads) $ ./mandelbrot -t 8 [mandelbrot thread]: [135.141] ms Wrote image file mandelbrot-thread.ppm (3.41x speedup from 8 threads) ``` ![](https://i.imgur.com/GAQmu20.png) #### View2 ``` $ ./mandelbrot -t 2 -v 2 [mandelbrot serial]: [270.723] ms Wrote image file mandelbrot-serial.ppm [mandelbrot thread]: [162.191] ms Wrote image file mandelbrot-thread.ppm (1.67x speedup from 2 threads) $ ./mandelbrot -t 3 -v 2 [mandelbrot thread]: [124.378] ms Wrote image file mandelbrot-thread.ppm (2.18x speedup from 3 threads) $ ./mandelbrot -t 4 -v 2 [mandelbrot thread]: [105.890] ms Wrote image file mandelbrot-thread.ppm (2.56x speedup from 4 threads) $ ./mandelbrot -t 8 -v 2 [mandelbrot thread]: [74.189] ms Wrote image file mandelbrot-thread.ppm (3.65x speedup from 8 threads) ``` ![](https://i.imgur.com/KEyF0VP.png) ### Is speedup linear in the number of threads used? :::info - **在 View1 中，speedup 並沒有成線性成長**，在 thread 數量為 3 時速度下降了。 - 在 View2 中，隨著thread數量上升，speedup 也隨之上升。 ::: ### Why? 推論的過程分成以下 3 步驟： #### 1. 觀察 View1 與 View2 的不同之處 ![](https://i.imgur.com/VBVYjHb.png) 透過前個問題的結論，我們可以推測出 View1 與 View2 的不同之處很可能就是問題核心。在仔細觀察兩張圖片後，可以發現 **View1 的淺色像素遠比 View2 來得多且集中**。在 8 位元灰階圖片中，0 表示黑色，最大值 255 則表示白色，數值越大顏色越淺。因此 View1 顯然比 View2 擁有更多數值較大的像素。為了觀察此相異之處是否就是導致執行速度不同的主因，我進行了下步觀察。 #### 2. 觀察像素值是否與執行速度相關 ``` static inline int mandel(float c_re, float c_im, int count) { int i; for (i = 0; i < count; ++i) { if (z_re * z_re + z_im * z_im > 4.f) break; ... } return i; } ``` 上方程式碼為 `MandelbrotSerial.cpp` 中的 `mandel()` 函數，透過此函數可以看到每個像素被賦值的過程，並從中得出以下幾點： * 像素值是由迴圈執行次數 `i` 來決定。 * `i` 可能為 0~255 中任一數 (因`count`為256)，數值大小決定該像素顏色深淺。 * 綜合以上兩點可知，**一個像素顏色越淺(像素值越大)，迴圈執行次數也越多**。 #### 3. 最終推論 * 我的程式會將圖片由上至下切成不同區塊，並按順序分配給不同 thread 執行，因此無法保證每個 thread 所負責的區域其淺色像素數量平均 * 使用 3 個 thread 時，分配給第 2 個 thread 的中間區塊有非常多的淺色像素，因此導致該 thread 執行速度拖垮整體速度 :::info 每個 thread 的工作量與其負責區域所含有的淺色像素數量有關。因此使用 3 個 thread 進行運算時，其中一個 thread 會被分配到中間白色最集中的區域，也因此導致了整體執行速度不佳。 ::: ## Q2 ### How do your measurements explain the speedup graph you previously created? 以下三張圖片顯示在 thread 數量不同時，程式分配給不同 thread 的區塊各是哪區。 | 2 threads | 3 threads | 4 threads | | :--------: | :--------: | :--------: | | ![](https://i.imgur.com/m7QxxLy.png) | ![](https://i.imgur.com/RQvd0Ww.png) | ![](https://i.imgur.com/cdQvcvM.png) | 以下為使用 timing code 來量測的 thread 平均執行時間 ``` $ ./mandelbrot -t 2 thread 0 : 236.003 ms thread 1 : 237.405 ms [mandelbrot thread]: [236.942] ms (1.94x speedup from 2 threads) $ ./mandelbrot -t 3 thread 0 : 93.448 ms thread 1 : 283.062 ms thread 2 : 93.734 ms [mandelbrot thread]: [282.980] ms (1.63x speedup from 3 threads) $ ./mandelbrot -t 4 thread 0 : 51.610 ms thread 1 : 196.004 ms thread 2 : 197.149 ms thread 3 : 45.948 ms [mandelbrot thread]: [193.496] ms (2.38x speedup from 4 threads) ``` 搭配圖片及各個 thread 實際的執行時間，可以觀察出： * 2 threads : 2 個 thread 的工作量相當，花的時間也相近。 * 3 threads : 分配到中間區域的 thread 1 花了較多的執行時間。 * 4 threads : 分配到中間區域的 thread 1, 2 花了較多的執行時間。實驗結果證實了我們在 Q1 的推測。 :::info 結論 : View1 在不同 thread 數量下的 speedup 之所以沒有成線性成長，是因每個 thread 工作量分配不均的關係。 ::: ## Q3 ### Modify the mapping of work to threads to achieve to improve speedup to at about 3-4x on both views ``` #define ROWNUM 1 void workerThreadStart(WorkerArgs *const args) { unsigned int gap = ROWNUM * args->numThreads; for (unsigned int startRow = args->threadId * ROWNUM; startRow < args->height; startRow += gap) { mandelbrotSerial(args->x0, args->y0, args->x1, args->y1, args->width, args->height, startRow, ROWNUM, args->maxIterations, args->output); } } ``` ### describe your approach to parallelization 由於 View1 與 View2 的淺色區塊多集中，過去直接由上至下切分圖片的方法將會造成工作量不平均，因此重新更改每個 thread 負責的區域。以 3 個 thread 為例，新的分配方式如下圖顯示： ![](https://i.imgur.com/xMzqoAd.jpg) ### report the final 4-thread speedup obtained :::info View 1 : 3.79x speedup from 4 threads View 2 : 3.78x speedup from 4 threads ::: 以下詳細列出在 View1, View2 分別使用 2, 3, 4個 thread 執行所得出的時間： #### View 1 ``` $ ./mandelbrot -t 2 [mandelbrot serial]: [460.828] ms Wrote image file mandelbrot-serial.ppm [mandelbrot thread]: [237.043] ms Wrote image file mandelbrot-thread.ppm (1.94x speedup from 2 threads) $ ./mandelbrot -t 3 [mandelbrot thread]: [159.095] ms Wrote image file mandelbrot-thread.ppm (2.89x speedup from 3 threads) $ ./mandelbrot -t 4 [mandelbrot thread]: [121.462] ms Wrote image file mandelbrot-thread.ppm (3.79x speedup from 4 threads) ``` #### View 2 ``` $ ./mandelbrot -t 2 -v 2 [mandelbrot serial]: [288.194] ms Wrote image file mandelbrot-serial.ppm [mandelbrot thread]: [148.293] ms Wrote image file mandelbrot-thread.ppm (1.94x speedup from 2 threads) $ ./mandelbrot -t 3 -v 2 [mandelbrot thread]: [99.637] ms Wrote image file mandelbrot-thread.ppm (2.89x speedup from 3 threads) $ ./mandelbrot -t 4 -v 2 [mandelbrot thread]: [75.966] ms Wrote image file mandelbrot-thread.ppm (3.80x speedup from 4 threads) ``` ## Q4 ### Is performance with 8 threads greater than with 4 threads? #### View1 ``` $ ./mandelbrot -t 8 [mandelbrot thread]: [126.211] ms Wrote image file mandelbrot-thread.ppm (3.65x speedup from 8 threads) ``` #### View2 ``` $ ./mandelbrot -t 8 -v 2 [mandelbrot thread]: [76.074] ms Wrote image file mandelbrot-thread.ppm (3.79x speedup from 8 threads) ``` * View1 : 3.79x speedup from 4 threads, 3.65x speedup from 8 threads * View2 : 3.78x speedup from 4 threads, 3.79x speedup from 8 threads :::info 在 View 1 和 View 2 實驗中，使用 8 個 threads 得出的結果都會比使用 4 個 threads 略慢一些 ::: ### Why? 在執行 CPU-bound 程式時，thread 的數量應比核心數低才能盡量避免額外的 Context Switch Overhead。但我們卻在 4 核心的 PP Server 上使用了 8 個 thread，因此我認為這便是使用 8 threads 效能沒有顯著提昇的主要原因。為了驗證這個猜想，我將程式執行於自己 8 核心的電腦上。執行結果如下，可以看出 8 threads 的執行效率比 4 threads 好了許多。 ``` $ ./mandelbrot -t 4 [mandelbrot serial]: [383.379] ms [mandelbrot thread]: [96.220] ms (3.98x speedup from 4 threads) $ ./mandelbrot -t 8 [mandelbrot thread]: [53.539] ms (7.16x speedup from 8 threads) ``` :::info 當 thread 數量多於核心數，會造成額外的 context switch overhead。因此使用 8 threads 的效能才會略差於 4 threads。 :::