---
tags: 平行程式設計
---
# SIMD Programming
<style>
img {
border: 1px solid #ddd;
border-radius: 4px;
padding: 5px;
width: 85%
}
</style>
Part1
---
* Q1-1
>Implement a vectorized version of clampedExpSerial in clampedExpVector (using fake vector intrinsics). Your implementation should work with any combination of input array size (N) and vector width (VECTOR_WIDTH), achieve a vector utilization higher than 60%, and of course pass the verification. (You can assume the array size is much bigger than the vector width.)
>Run ./myexp -s 10000 and sweep the vector width from 2, 4, 8, to 16. Record the resulting vector utilization. You can do this by changing the #define VECTOR_WIDTH value in def.h. Q1-1: Does the vector utilization increase, decrease or stay the same as VECTOR_WIDTH changes? Why?
在N=10000時，各個Vector Width的執行結果如下
* Vector Width: 2
Vector Utilization: 86.5%
* Vector Width: 4
Vector Utilization: 82.4%
* Vector Width: 8
Vector Utilization: 80.4%
* Vector Width: 16
Vector Utilization: 79.4%
Vector Utilization會隨著Vector Width的上升而**下降**。
下降的原因分為**兩種**:
1. **切割資料**
```cpp
for (int i = 0; i < N; i += VECTOR_WIDTH)
```
以上的迴圈計算為例，
若:
* VECTOR_WIDTH = 4,
* N = 13
則計算的時候會切割資料為以下幾組(數字代表index)
[0 ~ 3], [4 ~7], [8 ~ 11], [12]
在最後一組中只有一個資料被利用到，但VECTOR_WIDTH是切割為4的空間，所以有3個空間在計算上沒被使用到，造成浪費。
當N被放大時，只要不是VECTOR_WIDTH的倍數就會造成空間浪費，且當VECTOR_WIDTH放大數倍後(如: VECTOR_WIDTH = 12, N = 13)在切割上勢必會比較小的VECTOR_WIDTH造成更多的空間浪費，也因此降低了Vector Utilization。
2. **指數運算**
在指數運算時需要將exponents為0的lane做mask，因為只剩下exponents還有值的value需要計算，其他的都已計算完畢，所以會造成空間浪費。
以下圖為例:
| Index |0 |1 |2 |3 |
| ----- |-- |-- |-- |-- |
| Value |1.1|1.2|1.3|1.4|
| Exponents| 1 | 0 | 0 | 0 |
VECTOR_WIDTH = 4
Index為 1, 2, 3的資料exponents為0，所以不需要進入指數運算相乘的環節，而Index為0的資料需要經過1次的乘法。
因為VECTOR_WIDTH = 4，所以每次計算時都是4個4個一起，mask會設定為
| Index |0 |1 |2 |3 |
| ----- |-- |-- |-- |-- |
| Mask | 1 | 0 | 0 | 0 |
因為Index為 1, 2, 3的資料不須計算所以Mask設定為0。從Mask可以看出這這次的計算中浪費了3個計算空間，若當VECTOR_WIDTH擴大時，則最後一次的指數計算所造成的空間浪費以機率而言會比小的VECTOR_WIDTH還大(最多會浪費掉VECTOR_WIDTH - 1的計算空間)。
舉個簡單的例子:
***以下簡稱VECTOR_WIDTH=16的Vector為V16，VECTOR_WIDTH=4的Vector為V4。***
1個V16的大小等於4個V4。
4個V4都在最壞的指數數值分配的結果為1個9配3個0
如:
```
第一個V4 第二個V4 第三個V4 第四個V4
9000 0900 0090 00009
#註: 數字代表該位置的數值所對應的Exponents
```
而一個V16最壞的結果為1個9配15個0，所以以機率來看V16有機會比4個V4的Vector Utilization還要差。
若以相同的指數分配來做比較
如:
```
V16
9000 0000 0000 0000 需要進行9次的指數運算，浪費了15*9的計算空間
一樣的結果轉為V4
第一個V4 第二個V4 第三個V4 第四個V4
9000 0000 0000 0000 只有第一個V4需要進行9次指數運算
相對於V16只浪費了3*9的計算空間
```
V4, V16都是分配相同的指數數值，但V4的Vector Utilization顯著比V16還要有效率。
Part 2
---
* Q2-1
> Fix the code to make sure it uses aligned moves for the best performance.
將
```cpp
__builtin_assume_aligned(*, 16);
```
改為
```cpp
__builtin_assume_aligned(*, 32);
```
即可看見vmovaps 而不是vmovups
* Q2-2
> What speedup does the vectorized code achieve over the unvectorized code? What additional speedup does using -mavx2 give (AVX2=1 in the Makefile)? You may wish to run this experiment several times and take median elapsed times; you can report answers to the nearest 100% (e.g., 2×, 3×, etc). What can you infer about the bit width of the default vector registers on the PP machines? What about the bit width of the AVX2 vector registers.
執行
* case 1
```cpp
$ make clean && make && ./test_auto_vectorize -t 1
```
結果為
| 次數| 執行時間(秒)|
| --- | -------- |
|1 | 8.17017 |
|2 | 8.171 |
|3 | 8.17114 |
|4 | 8.17046 |
|5 | 8.17089 |
執行時間約為: 8.17秒
* case 2
```cpp
$ make clean && make VECTORIZE=1 && ./test_auto_vectorize -t 1
```
結果為
| 次數| 執行時間(秒)|
| --- | -------- |
|1 | 2.60918 |
|2 | 2.60964 |
|3 | 2.61055 |
|4 | 2.61045 |
|5 | 2.61019 |
執行時間約為: 2.61秒
* case 3
```cpp
$ make clean && make VECTORIZE=1 AVX2=1 && ./test_auto_vectorize -t 1
```
結果為
| 次數| 執行時間(秒)|
| --- | -------- |
|1 | 1.35531 |
|2 | 1.35359 |
|3 | 1.35392 |
|4 | 1.35336 |
|5 | 1.35409 |
執行時間約為: 1.35秒
case2 與 case3的時間差異約為兩倍的時間，而AVX2的vector registers為256bits(來源:https://en.wikipedia.org/wiki/Advanced_Vector_Extensions)，因此推測原本PP machines預設的vector registers為128bits(與AVX2時間差距約為大小差距)。
作業的內容也提到，*clang has used packed SSE instructions to add 16 bytes at a time*，SSE一次處理正好為以上所推論的128bits(16bytes)。
* Q2-3
> Provide a theory for why the compiler is generating dramatically different assembly.
:::info
推測:
:::
原本的寫法
```cpp
for (int j = 0; j < N; j++)
{
c[j] = a[j];
if (b[j] > a[j])
c[j] = b[j];
}
```
在迴圈內還未做判斷時就已經有一次assign ```c[j] = a[j];```，所以在compilation階段compiler需要先做完這一步assign才進入判斷，讓向量化的處理被中斷。
修改後的寫法
```cpp
for (int j = 0; j < N; j++)
{
if (b[j] > a[j]) c[j] = b[j];
else c[j] = a[j];
}
```
在迴圈內判斷完後才做assign，因此compiler可以利用向量化的優勢對if-else去做等效的處理。
:::success
理由:
:::
會這樣推斷的理由為，若將原本的程式碼改為
* 第一點
```cpp
for (int j = 0; j < N; j++)
{
if (b[j] > a[j])
c[j] = b[j];
c[j] = a[j];
}
```
雖然結果並不是我們要的，但在組合語言的部分卻可以明顯地看到**有向量化**的指令出現。
* 第二點
或是將改寫後的程式碼之前再加入assign的程式
```cpp
for (int j = 0; j < N; j++)
{
c[j] = a[j];
if (b[j] > a[j]) c[j] = b[j];
else c[j] = a[j];
}
```
儘管有點多此一舉，但在編譯成組合語言後得到的結果會發現原本平行化的指令"movaps"會被別的指令取代掉，**失去了原本向量化的功能**。
因此推斷出，若將assign的語句置於for迴圈內的第一行會破壞掉原本向量化的功能。
Sign in with Wallet
Connect another wallet