# HW1
###### tags: `Parallel Programming 2020`
# Part1
## Q1-1
A: the vector utilization **decreases** as `VECTOR_WIDTH` changes from 2, 4, 8, 16.
The reason is following:
首先我們可以推導出 vector utilization 的公式為 (不考慮其他的向量操作下)
$$
\frac{\Sigma_{i=1}^{N} e_i}{L*\Sigma_{k=0}^{\frac{N}{L}}max(e_{k*L+1}, e_{k*L+2}, ... ,e_{k*L+L})} \\
$$
其中 L 為 `VECTOR_LENGTH`，$e$ 代表 `exponents[i]`
假設我們整理式子成為下面的樣子：
$$
\Sigma_{i=1}^{N} e_i * \frac{1}{\Sigma_{k=0}^{\frac{N}{L}}L *max(e_{k+1}, e_{k+2}, ... ,e_{k+L})} \\
$$
如果 `exponents[i]` 是平均分佈的亂數，那麼可以當作$\Sigma_{1}^{N} e_i$在 N 固定的情況都是相同的。
那對於 $\Sigma_{k=0}^{\frac{N}{L}}L * max(e_{k*L+1}, e_{k*L+2}, ... ,e_{k*L+L})$ 來說，只要 L 越大，數值分佈的範圍越廣，因此 $\Sigma_{k=0}^{\frac{N}{L}}L * max(e_{k*L+1}, e_{k*L+2}, ... ,e_{k*L+L})$ 也會越大。
所以可以推論出 L 越大，即 **`VECTOR_LENGTH` 的值越大**，**vector utilization 越低**，與實驗結果相符。
# Part2
## Q2-1
Since the prefix of instructions is `v*` and we can confirm we have turned on AVX2 instructions successfully.
Moreover, the type of registers in the generated assembly code is `YMM*`, indicating the width of registers are 256 bits rather than 128 bits (e.g, `XMM*`)
According to the documentation of `MOVAPS` in https://www.felixcloutier.com/x86/movaps
> This instruction can be used to load a YMM register from a 256-bit memory location, to store the contents of a YMM register into a 256-bit memory location, or to move data between two YMM registers. When the source or destination operand is a memory operand, the operand must be aligned on a 32-byte boundary
Therefore, we need to align the variable to a 32-byte boundary to generate `vmovaps` instruction.
After we adjusted the alignment from 16 bytes to 32 bytes, we can see the compiler generate `vmovaps` instructions successfully.
```cpp=
void test(float* __restrict a, float* __restrict b, float* __restrict c, int N) {
__builtin_assume(N == 1024);
a = (float *)__builtin_assume_aligned(a, 32);
b = (float *)__builtin_assume_aligned(b, 32);
c = (float *)__builtin_assume_aligned(c, 32);
for (int i=0; i<I; i++) {
for (int j=0; j<N; j++) {
c[j] = a[j] + b[j];
}
}
}
```
```cpp=
17,20c17,20
< vmovups (%rdi,%rcx,4), %ymm0
< vmovups 32(%rdi,%rcx,4), %ymm1
< vmovups 64(%rdi,%rcx,4), %ymm2
< vmovups 96(%rdi,%rcx,4), %ymm3
---
> vmovaps (%rdi,%rcx,4), %ymm0
> vmovaps 32(%rdi,%rcx,4), %ymm1
> vmovaps 64(%rdi,%rcx,4), %ymm2
> vmovaps 96(%rdi,%rcx,4), %ymm3
25,28c25,28
< vmovups %ymm0, (%rdx,%rcx,4)
< vmovups %ymm1, 32(%rdx,%rcx,4)
< vmovups %ymm2, 64(%rdx,%rcx,4)
< vmovups %ymm3, 96(%rdx,%rcx,4)
---
> vmovaps %ymm0, (%rdx,%rcx,4)
> vmovaps %ymm1, 32(%rdx,%rcx,4)
> vmovaps %ymm2, 64(%rdx,%rcx,4)
> vmovaps %ymm3, 96(%rdx,%rcx,4)
```
## Q2-2
根據不同參數實驗的結果：
| Optimization | 1st | 2nd | 3rd | median |
|:---------------- | ----- | ----- |:----- |:------:|
| naive | 8.309 | 8.169 | 8.176 | 8.169 |
| vectorize | 2.621 | 2.609 | 2.607 | 2.609 |
| vectorize & AVX2 | 1.353 | 1.352 | 1.352 | 1.352 |
可以看出沒開任何參數 與 vectorize 的程式執行時間比為 3.13 倍，
而開啟 vectorize 和 vectorize with AVX2 後的程式執行時間比為 2 倍。
這是因為 vectorize 和 AVX2 讓 registers 的大小變大了，因此可以一次載入多個 value 來提高程式執行的效率。
雖然開啟 vectorize 後的執行時間與沒開的時間比為 3.13 ，但是我推論 bit width of default vector registers 大小是 4 個 float，也就是 4 * 32 = 128bits。
我認為不是剛好 4 倍的原因 CPU 執行的 vector 運算還是會比 scalar 還要慢，所以速度不會那麼快。
而 AXV2 可以推論 bit width of default vector registers 就是 4 * 32 * 2 = 256bits
## Q2-3
### 觀察
節錄並簡化原本 test2.cpp 的 assembly code：
```asm=
.LBB0_6: # in Loop: Header=BB0_2 Depth=2
add rcx, 2
cmp rcx, 1024
je .LBB0_7
.LBB0_2: # Parent Loop BB0_1 Depth=1
mov eax, dword ptr [rdi + 4*rcx]
mov dword ptr [rdx + 4*rcx], eax
movss xmm0, dword ptr [rsi + 4*rcx] # xmm0 = mem[0],zero,zero,zero
movd xmm1, eax
ucomiss xmm0, xmm1
jbe .LBB0_4
movss dword ptr [rdx + 4*rcx], xmm0
.LBB0_4: # in Loop: Header=BB0_2 Depth=2
mov eax, dword ptr [rdi + 4*rcx + 4]
mov dword ptr [rdx + 4*rcx + 4], eax
movss xmm0, dword ptr [rsi + 4*rcx + 4] # xmm0 = mem[0],zero,zero,zero
movd xmm1, eax
ucomiss xmm0, xmm1
jbe .LBB0_6
movss dword ptr [rdx + 4*rcx + 4], xmm0
jmp .LBB0_6
```
並從編譯的訊息來看：
remark: loop not vectorized: unsafe dependent memory operations in loop.
可以發現到 test2.cpp 並沒有做到 vectorized 的動作， 而是把 **單個
4-byte** 的 float 載入到 xmm\* 的 register 做運算， 即
`movss xmm0, dword ptr [rsi + r*rcx + 4]` 等行，
因此並沒有成功提高程式的效率
反觀，上了 patch 後的 test2.cpp 產出的 assembly code:
```asm=
.LBB0_2: # Parent Loop BB0_1 Depth=1
movaps xmm0, xmmword ptr [rsi + 4*rcx]
movaps xmm1, xmmword ptr [rsi + 4*rcx + 16]
maxps xmm0, xmmword ptr [rdi + 4*rcx]
maxps xmm1, xmmword ptr [rdi + 4*rcx + 16]
movaps xmmword ptr [rdx + 4*rcx], xmm0
movaps xmmword ptr [rdx + 4*rcx + 16], xmm1
movaps xmm0, xmmword ptr [rsi + 4*rcx + 32]
movaps xmm1, xmmword ptr [rsi + 4*rcx + 48]
maxps xmm0, xmmword ptr [rdi + 4*rcx + 32]
maxps xmm1, xmmword ptr [rdi + 4*rcx + 48]
movaps xmmword ptr [rdx + 4*rcx + 32], xmm0
movaps xmmword ptr [rdx + 4*rcx + 48], xmm1
add rcx, 16
cmp rcx, 1024
jne .LBB0_2
```
並從編譯給出的訊息：
remark: vectorized loop (vectorization width: 4, interleaved count: 2)
可以知道 patch 過後的 test2.cpp 有成功的被 vectorized。
與原本的 test2.cpp 不同的是， patch 過後出現了
`movaps xmm0, xmmword ptr [rsi + 4*rcx + 16 * n]`，表示CPU 是一次載入多個
（在這個範例中, vectorization width = 4, 所以是 4 個）value 並進行運算
除此之外，我們可以根據編譯時出現的訊息: `interleaved count: 2` 來知道
compiler 還幫我們做了 loop unrolling, 而 unrolling factor 為 2。
結合上面兩項優化，程式的效率得以大幅提昇。
### 原因
而為什麼會導致兩份看似相同的程式碼，經過 compiler 產生的 assembly code
會相異如此巨大呢？
origin test2.cpp:
```cpp=
for (int j = 0; j < N; j++)
{
c[j] = a[j];
if (b[j] > a[j])
c[j] = b[j];
}
```
patched test2.cpp:
```cpp=
for (int j = 0; j < N; j++)
{
if (b[j] > a[j]) c[j] = b[j];
else c[j] = a[j];
}
```
這是因為在 origin 的 test2.cpp 中，`c[j]` 先被 assign 了 `a[j]` 的值，
然後使 `a[j]` 與 `b[j]` 比較，有可能再次更新了 `c[j]` 的值
可以得出兩個結論
1. `c[j]` 必須先被 assign `a[j]` ，然後才會被 assgin `b[j]` （如果
`b[j] > a[j]`)，因此兩個**對 memory 的 instruction 存在 dependence 關係**
2. `a[j]` 與 `b[j]` 的值無法先被 predict ，因此無法 做進一步的優化
而 patched 過後的 test2.cpp ，因為有 `if else` block
，所以一次只可能走向其中一個 branch ，因此沒有 dependent 的關係存在；
加上有 `maxps` 指令的支援，可以一次完成多個 values 的 assignment
，因而達成 *vectorize* 等優化
Google Drive
Gist
Clipboard
Sign in with Wallet
