# HW1 Report (Parallel Programming)

Student ID: 314551138
Name: 曹瀚文

---

## Part 1:

### Run run -- ./myexp -s 10000 and sweep the vector width from 2, 4, 8, to 16. Vector utilization.
Changing `VECTOR_WIDTH` 後記錄 vector utilization：

| VECTOR_WIDTH | Utilization |
|--------------|-------------|
| 2 | 87.6 % |
| 4 | 82.3 % |
| 8 | 79.6 % |
| 16 | 78.3 % |
#### VECTOR_WIDTH = 2

#### VECTOR_WIDTH = 4
#### VECTOR_WIDTH = 8

#### VECTOR_WIDTH = 16

### Q1-1: Does the vector utilization increase, decrease or stay the same as VECTOR_WIDTH changes? Why?

**Answer (Q1-1):**
- Vector utilization decrease as VECTOR_WIDTH increase
- 原因解釋： 因為每個 exponent 大小不同，需要重複乘法的次數也不一樣。當 VECTOR_WIDTH 拉大時，總會有些數據先算完，相較其他數據提早運算停止下來，導致整體utilization隨著VECTOR_WIDTH下降。

---

### Bonus: arraySumVector (Optional)
- 在 arraySumVector 的實作裡，我採用了課程中提到的方式
- 先把每次 VECTOR_WIDTH 記錄
- 接著利用 _pp_hadd_float 把相鄰的 lane 加總
- 再透過 interleave_float 把資料重排
- 重回第一步縮小width
- 重複 log2(VECTOR_WIDTH) 次後，就能得到最終總和
- 以上步驟要處理(N/VECTOR_WIDTH)次，同時內部計算log2(VECTOR_WIDTH)
- 因此時間複雜度$O\!\left(\tfrac{N}{\text{VECTOR_WIDTH}} + \log_2(\text{VECTOR_WIDTH})\right)$
- 並且utilization根據上圖達到80%以上，滿足requirement
---

## Part 2:

### Q2-1: Fix the code to make sure it uses aligned moves for the best performance.

Hint: we want to see vmovaps rather than vmovups.
- 一開始我有加 restrict，讓編譯器知道三個陣列不會互相重疊，接著再_builtin_assume_aligned 提示它資料記憶體是對齊的。不過編譯出來還是看到 vmovups（unaligned），代表編譯器還是不認為陣列真的有對齊。

後來發現從2.2計算performance時發現原因是：

SSE 一次處理 128 bits（16 bytes）

而後面的AVX2 一次處理 256 bits（32 bytes）
如果我要用 AVX2，就得保證指標是 32-byte 對齊，否則它不會改成用 vmovaps。

我把程式改成下面這樣：

void test1(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];
    }
  }
}

以及我們所想要的vmovaps在assembly中

	vmovaps	(%rdi,%rcx,4), %ymm0
	vmovaps	32(%rdi,%rcx,4), %ymm1
	vmovaps	64(%rdi,%rcx,4), %ymm2
	vmovaps	96(%rdi,%rcx,4), %ymm3
	vaddps	(%rsi,%rcx,4), %ymm0, %ymm0
	vaddps	32(%rsi,%rcx,4), %ymm1, %ymm1
	vaddps	64(%rsi,%rcx,4), %ymm2, %ymm2
	vaddps	96(%rsi,%rcx,4), %ymm3, %ymm3
	vmovaps	%ymm0, (%rdx,%rcx,4)
	vmovaps	%ymm1, 32(%rdx,%rcx,4)
	vmovaps	%ymm2, 64(%rdx,%rcx,4)
	vmovaps	%ymm3, 96(%rdx,%rcx,4)
	addq	$32, %rcx
	cmpq	$1024, %rcx                     # imm = 0x400
	jne	.LBB0_2

---

### Q2-2:
- 跑了5次之後取median
- Unvectorized: ~7.08 sec
- Vectorized (SSE): ~1.76 sec
- Vectorized (AVX2): ~0.89 sec

Speedup (SSE vs scalar): ~4×
Speedup (AVX2 vs SSE): ~2×

#### 推論bit width
- pp machine預設 vector registers = 128bits (SSE, 16bytes)
- AVX2 vector registers = 256bits (32bytes)

---

### Q2-3: Provide a theory for why the compiler is generating dramatically different assemblies.
- 為了理解complier的行為，根據題目去觀察original code和patch code編譯出來assembly的差別
- Original code:

  c[j] = a[j];
  if (b[j] > a[j])
      c[j] = b[j];

- Patch code:

    /* max() */
      if (b[j] > a[j]) c[j] = b[j];
      else c[j] = a[j];

- 並且利用diff

diff assembly/test2.vec.s assembly/test2.original.s

- 得到以下

<       xorl    %eax, %eax
---
>       xorl    %r8d, %r8d
>       jmp     .LBB0_1
10a12,15
> .LBB0_7:                                #   in Loop: Header=BB0_1 Depth=1
>       addl    $1, %r8d
>       cmpl    $20000000, %r8d                 # imm = 0x1312D00
>       je      .LBB0_8
13a19
>       jmp     .LBB0_2
14a21,24
> .LBB0_6:                                #   in Loop: Header=BB0_2 Depth=2
>       addq    $2, %rcx
>       cmpq    $1024, %rcx                     # imm = 0x400
>       je      .LBB0_7
17,36c27,45
<       movaps  (%rsi,%rcx,4), %xmm0
<       movaps  16(%rsi,%rcx,4), %xmm1
<       maxps   (%rdi,%rcx,4), %xmm0
<       maxps   16(%rdi,%rcx,4), %xmm1
<       movups  %xmm0, (%rdx,%rcx,4)
<       movups  %xmm1, 16(%rdx,%rcx,4)
<       movaps  32(%rsi,%rcx,4), %xmm0
<       movaps  48(%rsi,%rcx,4), %xmm1
<       maxps   32(%rdi,%rcx,4), %xmm0
<       maxps   48(%rdi,%rcx,4), %xmm1
<       movups  %xmm0, 32(%rdx,%rcx,4)
<       movups  %xmm1, 48(%rdx,%rcx,4)
<       addq    $16, %rcx
<       cmpq    $1024, %rcx                     # imm = 0x400
<       jne     .LBB0_2
< # %bb.3:                                #   in Loop: Header=BB0_1 

- 我們可以觀察以及得到以下結論， patch後的assembly相較於original極少出現branch相關的指令，同一時間可以觀察到許多的平行化指令如movaps甚至出現了平行化的max()相關指令。
- 從這樣的結果我們可以推論不同的程式control branch執行邏輯，會影響到程式是否能被complier平行化，因此我們在未來編寫程式若是想要平行化，也要注意程式是否能被complier理解為能夠平行化的code