---
# System prepended metadata

title: 'Programming Assignment I: SIMD Programming'
tags: [Parallel Programming, NYCU]

---

# Programming Assignment I: SIMD Programming
[ToC]

## Part 1 : Vectorizing Code Using Fake SIMD Intrinsics

:::info
++***Q1-1***++: 
**Does the vector utilization increase, decrease or stay the same as `VECTOR_WIDTH` changes? Why?**
:::

++***ans:***++

Run `./myexp -s 10000` and sweep the vector width from 2, 4, 8, to 16

* `VECTOR_WIDTH` = 2
```=
Results matched with answer!
****************** Printing Vector Unit Statistics *******************
Vector Width:              2
Total Vector Instructions: 167727
Vector Utilization:        90.1%
Utilized Vector Lanes:     302405
Total Vector Lanes:        335454
************************ Result Verification *************************
ClampedExp Passed!!!
```

* `VECTOR_WIDTH` = 4
```=
Results matched with answer!
****************** Printing Vector Unit Statistics *******************
Vector Width:              4
Total Vector Instructions: 97075
Vector Utilization:        88.1%
Utilized Vector Lanes:     342041
Total Vector Lanes:        388300
************************ Result Verification *************************
ClampedExp Passed!!!
```
* `VECTOR_WIDTH` = 8
```=
Results matched with answer!
****************** Printing Vector Unit Statistics *******************
Vector Width:              8
Total Vector Instructions: 52877
Vector Utilization:        87.0%
Utilized Vector Lanes:     368081
Total Vector Lanes:        423016
************************ Result Verification *************************
ClampedExp Passed!!!
```
* `VECTOR_WIDTH` = 16
```=
Results matched with answer!
****************** Printing Vector Unit Statistics *******************
Vector Width:              16
Total Vector Instructions: 27592
Vector Utilization:        86.5%
Utilized Vector Lanes:     381929
Total Vector Lanes:        441472
************************ Result Verification *************************
ClampedExp Passed!!!
```

結果顯示，當`VECTOR_WIDTH`增加時，<font color=#FF0000>vector utilization</font>會降低。

++***why?***++

主要影響vector utilization的因素是mask的使用，而有以下兩個情況會需要透過mask來確保結果正確：
* **vector內各元素需要的運算量不同**
因為<font color=#FF0000>**每個元素要計算的指數是隨機給予的**</font>，在平行計算時會面臨到vector內的元素不會同時運算完畢的情況。此時便需要透過mask將較早運算完的結果保留下來，造成在有元素已經運算完畢，而其他元素尚未完成的情況下，vector utilization降低。
* **超過9.999999的結果要設為9.999999**
當結果都運算完後，便需要<font color=#FF0000>透過mask來將超過門檻的結果設為9.999999</font>。因此取決於此vector內的運算結果超過門檻的數量，也會使vector utilization降低。

結合以上兩點，**隨著vector長度上升，需要考慮的元素變多，互相等待、遮罩的情況會更嚴重，使得vector utilization更容易下降**。

:warning:但這是建立於通常情況，在某些例子下的結果可能會不一樣:warning:

## Part 2 : Vectorizing Code with Automatic Vectorization Optimizations

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

++***observation***++: 
從生成的assembly code中可以發現：
```=49
...
vmovups	(%rbx,%rcx,4), %ymm0
vmovups	32(%rbx,%rcx,4), %ymm1
vmovups	64(%rbx,%rcx,4), %ymm2
vmovups	96(%rbx,%rcx,4), %ymm3
...
```
AVX2指令集中的registers **ymm**的對齊單位為**32 bits**，因此要透過`__builtin_assume_aligned()`函式告訴編譯器`a`，`b`，和`C`對齊的單位為32 bits。
因此在`test1.cpp`中加入以下程式碼：
```cpp=6
...
a = (float *)__builtin_assume_aligned(a, 32);
b = (float *)__builtin_assume_aligned(b, 32);
c = (float *)__builtin_assume_aligned(c, 32);
...
```
++***result***++: 

`vmovups`變成`vmovaps`：
```=49
...
vmovaps	(%rbx,%rcx,4), %ymm0
vmovaps	32(%rbx,%rcx,4), %ymm1
vmovaps	64(%rbx,%rcx,4), %ymm2
vmovaps	96(%rbx,%rcx,4), %ymm3
...
```
---
:::info
++***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`)? 
* 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?
:::

++***speedup experiment (N: 1024, I: 20000000)***++ :

|   **round** | **Unvectorized** | **Vectorized** | **Vectorized + AVX2** |
| -----------:| ----------------:| --------------:| ---------------------:|
|           1 |          8.42196 |        2.67959 |               1.42745 |
|           2 |          8.56017 |        2.67295 |               1.42949 |
|           3 |          8.43915 |         2.7005 |               1.42868 |
|           4 |          8.40761 |        2.66324 |               1.43153 |
|           5 |          8.40766 |        2.71379 |               1.43363 |
|           6 |          8.57744 |        2.83703 |               1.42635 |
|           7 |          8.45745 |        2.67869 |               1.42816 |
|           8 |          8.39355 |        2.68008 |               1.43499 |
|           9 |          8.50639 |        2.67706 |               1.43428 |
|          10 |          8.40772 |        2.69791 |               1.43311 |
|          11 |          8.41674 |        2.67807 |               1.43306 |
|          12 |             8.38 |         2.6795 |               1.43202 |
|             |                  |                |                       |
|  **Median** |          8.41935 |       2.679545 |              1.431775 |
| **Speedup** |           **1x** |  **3.142082x** |         **5.880358x** |

++***bit width***++ :

* **Default Machine :**
	在只做`VECTORIZE=1`時，由生成出的Assembly code可以發現以下段落：
	```=
		...
		movups	16(%rbx,%rcx,4), %xmm0
		movups	16(%r15,%rcx,4), %xmm1
		addps	%xmm0, %xmm1
		movups	%xmm1, 16(%r14,%rcx,4)
		movups	32(%rbx,%rcx,4), %xmm0
		movups	32(%r15,%rcx,4), %xmm1
		addps	%xmm0, %xmm1
		...
	```
	可以發現在將資料搬移進register `xmm0`、`xmm1`時，搬移資料的間隔為**16 bytes**，也就是**128 bits**。

* **AVX2**
	將`VECTORIZE=1 AVX2=1`加入後，觀察同樣一段Assembly code會發現變成：
	```=
		...
		vmovups	(%rbx,%rdx,4), %ymm0
		vmovups	32(%rbx,%rdx,4), %ymm1
		vmovups	64(%rbx,%rdx,4), %ymm2
		vmovups	96(%rbx,%rdx,4), %ymm3
		vaddps	(%r15,%rdx,4), %ymm0, %ymm0
		vaddps	32(%r15,%rdx,4), %ymm1, %ymm1
		vaddps	64(%r15,%rdx,4), %ymm2, %ymm2
		vaddps	96(%r15,%rdx,4), %ymm3, %ymm3
		...
	```
	可以得知AVX2指令集使用的registers `ymm0`、`ymm1`系列，大小為**32 bytes**，也就是**256 bits**。

---
:::info
++***Q2-3***++:
* Provide a theory for why the compiler is generating dramatically different assembly.
:::

++***observation***++:

* instructions
    * `movaps`：將src 的資料搬進dst
    * `maxps` : 比較src和dst的資料，把大的放入dst
* task
    `test2.cpp`要做的事情是 ++*比較`a`和`b`裡面的值大小，並將大的放入`c`中*++

先看==修改之後==，`if (b[j] > a[j]) c[j] = b[j]; else c[j] = a[j];`的部分可以用兩個`movaps`和`maxps`達成，不會有同一vector內要進行不同運算的問題，因此編譯器認定可以被向量化：
```asm=47
...
.LBB0_3:                                #   Parent Loop BB0_2 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
        movaps  (%r15,%rcx,4), %xmm0
        movaps  16(%r15,%rcx,4), %xmm1
        maxps   (%rbx,%rcx,4), %xmm0
        maxps   16(%rbx,%rcx,4), %xmm1
        movaps  %xmm0, (%r14,%rcx,4)
        movaps  %xmm1, 16(%r14,%rcx,4)
        movaps  32(%r15,%rcx,4), %xmm0
        movaps  48(%r15,%rcx,4), %xmm1
        maxps   32(%rbx,%rcx,4), %xmm0
        maxps   48(%rbx,%rcx,4), %xmm1
        movaps  %xmm0, 32(%r14,%rcx,4)
        movaps  %xmm1, 48(%r14,%rcx,4)
        addq    $16, %rcx
        cmpq    $1024, %rcx                     # imm = 0x400
        jne     .LBB0_3
...
```

而在==未修改==的版本中，可以看到：
```cpp=14
...
    for (int j = 0; j < N; j++)
    {
        /* max() */
        c[j] = a[j];
        if (b[j] > a[j])
        c[j] = b[j];
    }
...
```
因為`c`先被assign，而比較的是`a`和`b`，編譯器無法得知兩個指令之間的關聯性，因此不會使用`maxps`來進行這段工作。當一個向量內的元素中，有一部分比較的結果是`b>a`，另一部分是`a<=b`，便會出現不同的分支，導致此向量無法統一繼續進行相同的運算。故編譯器判定無法向量化。
由assembly code也可看出其並非vectorize後的結果，而是以sequence的方式進行運算：
```asm=53
...
.LBB0_11:                               #   in Loop: Header=BB0_3 Depth=2
        addq    $4, %rcx
        cmpq    $1024, %rcx                     # imm = 0x400
        je      .LBB0_12
.LBB0_3:                                #   Parent Loop BB0_2 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
        movaps  (%r15,%rcx,4), %xmm1
        movaps  %xmm1, (%rbx,%rcx,4)
        movaps  (%r14,%rcx,4), %xmm0
        ucomiss %xmm1, %xmm0
        ja      .LBB0_4
...
```
---


