---
tags: parallel_programming
---
# Parallel programming HW5
> 學號：311551173 姓名：黃牧恩

## Q1
**What are the pros and cons of the three methods? Give an assumption about their performances.**
- Method 1
- Pros: 每一個thread只需要處理一個pixel
- Cons: 有些計算量小的thread只被使用一下，只有部分的thread會因為計算量較大而被使用較久，導致整體thread utilization較低
- Method 2
- Pros: 在資料是2D的情況下，確保存放的時候有對齊，由於CUDA在一次讀取256 bits的資料會比較快，因此提高取資料的時候的效率
- Cons: 如果資料不足256的倍數，就需要額外宣告補齊的空間
- Method 3
- Pros: 每個thread一次可以處理比較多個pixels，較省運算資源
- Cons: 節省運算資源但使得每個thread的負擔加重，會因為負擔分配不均而拖慢運算時間，導致效能降低

## Q2
**How are the performances of the three methods? Plot a chart to show the differences among the three methods.**
- 效率排名: Method 1 > Method 2 > Method 3
1. view 1 running time:

| maxIteration | $10^3$ | $10^4$ | $10^5$ |
|:------------:|:------:|:------:|:-------:|
| Method 1 | 32.159 | 33.232 | 282.309 |
| Method 2 | 33.613 | 34.859 | 283.715 |
| Method 3 | 32.865 | 43.619 | 378.341 |


2. view 2 running time:

| maxIteration | $10^3$ | $10^4$ | $10^5$ |
|:------------:|:------:|:------:|:------:|
| Method 1 | 15.737 | 25.416 | 30.527 |
| Method 2 | 17.604 | 27.479 | 31.999 |
| Method 3 | 22.656 | 31.055 | 49.069 |


## Q3
**Explain the performance differences thoroughly based on your experimental results. Does the results match your assumption? Why or why not.**

- Method 1跟Method 2這兩種方法都是一個thread一個pixels，每個block裡面因為loading分布不均的情況比較輕微，所以執行時間會比Method 3還快
- Method 3當中，每個thread的負擔較重，加上block之間和thread之間負擔分布不均的情形比較嚴重，可能一個thread連續被分到好幾個高運算量的pixel，但同一個block當中另一個thread卻都被分到運算量低的pixel，導致同一個block之內的thread負擔分配不均，每個block需要等待的時間 $t_{block}$ = $max(t_{thread_1},t_{thread_2},...,t_{thread_n})$，加上每個thread處理的pixel本來就比Method 1和Method 2還要多，每個thread需要的時間更長，因此Method 3比Method 1和Method 2慢。
- 從Q2的View 1 running time圖可以發現Method 3都花了最多的時間，根據Q1的回答所推測，有可能是每個thread被分到很多個pixels，加上圖案上的pixel計算量分布不均，導致有一些block當中的thread被分到比較多計算的pixel，使得thread的負擔變高，因此有一部分的thread需要花費較長的時間計算，其他thread也要等這些thread完成。
- 由於Q2的View 2 running time圖也可以發現Method 3花較多時間的現象，但因為view 2的圖相較view 1比較少高計算量的pixel聚集在一起，所以在分配pixel的時候，每個block比較不會一次被分到幾乎都是高計算量的pixel，但Method 3的running time依然比其他兩者高，所以可以合理推斷是因為一個block一次算多個pixel導致loading分佈不均的現象。
- 例如下面這張示意圖(view 1)中黃色的部分，這幾塊block整個都是需要大量計算的pixel，整個block內的thread都要花比其他block當中的thread還久的時間計算，使得運算時間比一個thread處理一個pixel還要久
- 但如果是下面這張示意圖(view 2)，因為沒有整塊block都被分到大量計算的pixel，所以整個計算時間會比view 1短

## Q4
**Can we do even better? Think a better approach and explain it.**
- 不需在host額外配置一塊空間，直接將device上的值透過cudaMemcpy複製到img當中
- 可以省去配置、複製及刪除的時間
- 這個方法會比Method 1、2、3來得快，下面兩張是四種方法的running time比較圖