# <center>Parallel Programming Hw1
0783404 黃揚
# Part 1
## Q1：run ./myexp -s 10000 and sweep the vector width from 2, 4, 8, to 16
用一萬筆資料去測，不同vector width實驗結果如下：
* **Vector width** = 2
Vector Utilization：80.5%

* **Vector width** = 4
Vector Utilization：72.6%

* **Vector width** = 8
Vector Utilization：68.6%

* **Vector width** = 16
Vector Utilization：66.6%

* **小結：**
可以很明顯觀察到utilization會隨著vector width加大而下降。
1. 不整除的資料會浪費空間
舉例來說，若`width = 8, N = 20`，則在最後一次切割的時候會剩下4筆資料要處理，但是仍舊佔用了`8`的空間。而這樣的現象會隨著vector width變大而更嚴重，例如當`width = 16, N = 20`時，則最後一次切割會剩4筆資料，但是佔用了`16`的空間。
2. while loop裡面的計算過程
* 在找到exp=0者並把output設為1的時候
使用`./myexp -l`觀察使用情形時可以發現，在`_pp_vset_float(result, 1.0f, maskExpIsZero);`這行的active比例極低，因為測資中`exp=0`的筆數相當少。而同第一點所述，vecotr width越大，就越容易包含這樣的情形。
* 在進行指數運算時
以上圖為例。因為在進行指數運算時，會去看哪邊的exp>1再運算。而運算到此處時，16筆資料只有6筆資料是exp>1的，所以這6筆資料會去做result*x、exp減一以及檢察是否有超過上界的情形發生。就會造成其他exp不大於1(即不須運算)的所在空間被浪費掉。
* 每次運算完成後，要再找一次哪邊的exp仍大於1
`_pp_vgt_int(maskNotDone, exp, one, maskNotDone);`算到越後面，exp仍大於1的地方就越少，越容易發生浪費。

# Part 2
## Q2-1
MOVAPS—Move Aligned Packed Single-Precision Floating-Point Values
MOVUPS—Move Unaligned Packed Single-Precision Floating-Point Values

由於avx2中，float是32 bit的([參考的文章](https://zhuanlan.zhihu.com/p/94649418))，所以在code中加入這一段

    a = (float *)__builtin_assume_aligned(a, 32);
    b = (float *)__builtin_assume_aligned(b, 32);
    c = (float *)__builtin_assume_aligned(c, 32);

就可以成功對齊，得到預期的結果`vmovaps`如下圖。

## Q2-2
對於這三個case，都各執行五次，取中位數當作結果
**Case 1:**
`$ make clean && make && ./test_auto_vectorize -t 1`

| 1 | 2 | 3 |4 | 5 |
| -------- | -------- | -------- |-------- |-------- |
| 8.16878s | 8.16874s | 8.16857s | 8.16888s | 8.16862s |

取中位數，case1的執行時間為8.16874秒

**Case 2**
`$ make clean && make VECTORIZE=1 && ./test_auto_vectorize -t 1`
| 1 | 2 | 3 |4 | 5 |
| -------- | -------- | -------- |-------- |-------- |
| 2.60766s | 2.60733s | 2.60773s | 2.60698s | 2.60814s |
取中位數，case2的執行時間為2.60766秒

**Case 3**
`$ make clean && make VECTORIZE=1 AVX2=1 && ./test_auto_vectorize -t 1`
| 1 | 2 | 3 |4 | 5 |
| -------- | -------- | -------- |-------- |-------- |
| 1.35233s | 1.35265s | 1.35261s | 1.3525s| 1.35272s |
取中位數，case3的執行時間為1.35261秒

* **小結：**
* Case1所需時間是Case2的3倍左右，Case2所需時間又是Case3的2倍。
* Case3相比於Case2，多使用了AVX2，而avx2的width是256 bit，而SSE是128bit。這兩者的width差了一倍，所以在做平行運算時一次能運算的長度差了一倍，連帶影響到時間差大約一倍。([參考來源](https://software.intel.com/content/www/us/en/develop/articles/migrating-from-sse2-vector-operations-to-avx2-vector-operations.html))
* Case1沒有使用vetorize計算，所以速度會是最慢的

## Q2-3
用diff指令觀察修改前後的assembly code差異如下圖。左邊是修改後，右邊是修改前
可以看到出現了`movaps`跟`maxps`
* **小結：**
test2.cpp中，這兩種版本的code的主要差異在於，修改前會先預設c[j]=a[j]，然後根據判斷式決定式否要把c[j]改成b[j]。而修改後的版本則是先判斷大小，再決定c[j]應該要等於誰。藉由assembly code可以發現，修改前的版本是使用32bit的register，而修改後的是128bit的，推測是因為修改前的版本會受到判斷式是否成立的影響，導致沒辦法align，而修改後的改本其每次執行的運算步驟都是規律的，不會受影響。

參考資料：
1. https://ithelp.ithome.com.tw/articles/10227112
2. http://blog.luoyuanhang.com/2015/07/07/%E5%87%A0%E7%A7%8D%E5%9F%BA%E6%9C%AC%E6%B1%87%E7%BC%96%E6%8C%87%E4%BB%A4%E8%AF%A6%E8%A7%A3/