# 2024q1 Homework5 (assessment)
contributed by < `vestata` >

## 測驗題改進
選擇三題進行改進。
### 1. [第四周測驗題 Q2](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-2)
預計：
- [ ] 補完之前缺失的 `lab0-c` 之 `ttt`
- [x] 完成 coroutine 並行
- [ ] 鍵盤事件
- [ ] 第四周測驗題 Q3

### 2. [第三周測驗題 Q3](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-3)
詳見 [log2](https://hackmd.io/@tony268596/linux2024-homework4#%E6%B8%AC%E9%A9%97%E4%B8%89)
以不同方式實作 `log2()` 比較效能差距。
預計：
- [ ] 分析噪點原因
- 改為使用 perf 測量，發現不能明顯體現實驗結果
- [x] 更多 linux 應用案例

### 3. [第一周測驗題 Q2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)
預計：
- [ ] 實作 timsort 中的 insertion sort, galloping mode 部份
- [ ] 觀察 list_sort 在 linux 中的使用場景
- [ ] 是否 timsort 在這些場景中表現受否會好

## 閱讀 [因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)
>「一項產業進步的速度，很大程度取決於做實驗修正問題的速度。」

對於這段話，在我進行 Linux 核心實作的課程中有了深刻的體會。我發現 Jserv 老師在課堂上有意培養我們這種習慣。課程初期，我對這個觀念還不太熟悉，經常忽略即時修正的重要性。特別是在 `lab0`，我常因為一些細節問題而進度受阻。現在回顧，我確實認識到細節的重要，但一開始我過於害怕失敗，導致進度落後。作為資訊領域的一分子，我應該善用能夠快速修正的優勢！

> 「你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已。」
> 「你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望 … 你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」

沒想到做飲料機的故事也會遇到 jserv 老師的身影，真的是引響力很大。回顧前五周學習 linux 核心實作這堂課，前面的實作對我來說真的是一大考驗，因為可以參考其他人的進度，可以看到許多修習過這堂課或是本身實力過硬的同學，明明自己花了很多時間也認真學習，但是總是落後他人一節。有時候還是會被上述的情緒所影響。不知道是 jserv 有意無意在此刻安排這些作業內容，讓我修正心態。好好補足自己實作較慢與數學理論的基礎再努力前進！

屆時剛好做完 NVIDIA GPU System Software Engineer Intern 的 hackerrank 測試。因為最近一直在寫實作的作業自認為對程式的掌握有提高，也很久沒有刷 leetcode 了，前面的基礎題還好，後面的程式題（leetcode 類型）真得是表現欠佳。今年找的暑期實習也都沒什麼好消息，心情多少還是被影響到。但是看到文章中 jserv 老師提到：
>「你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望。你可以計算要花多少錢，然後評估自己可以接受多少損失，畢業後慢慢還都好，要錢我也可以借你。但青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」

有時很難揣測 Jserv 老師在想什麼，也不清楚老師的原意是什麼，但是還蠻有趣的，也讓我的心態好轉一些。畢竟還是要繼續前進！（開始每天寫一 leetcode）

> 這一連串的問題都是可能的變因，第一眼看到時會覺得頭腦超級混亂，但現實世界就是這麼一回事，解決問題的唯一方法就是冷靜下來分析，做實驗把變因排除掉。

因為自動飲料機而延畢的那一年裡面提到很多自己的心路歷程，雖然所在的領域不一樣，但是心境卻是相通得。常常在螢幕的這一端感受到他的困境。我也回顧我自己當身處在混亂之中，時常腦袋也亂成一團的壞習慣。看到別人提出相同問題，我也深感其中，要修正這壞習慣。

> 儘管世界如此殘酷，但人卻不一樣，當你真心想做到一件事，付出足夠的犧牲，這個世界會聽見並做出回應，周遭的人漸漸願意相信你、花時間幫助你，你的付出並不見得會有結果，但是加上許多人的幫助，可能一切就不一樣了。
對你而言真正重要的事物，會比你想得到的事物更早出現在路邊。

目前的人生之路，我確實是隨心所欲地探索，但途中感到相當開心。我認為我與許多優秀的同學背景大相逕庭，所以也很感謝這堂課提供的平台，讓我能夠遇見不同的人，並對問題提出不同的解決方案。雖然我們背景迥異且素未謀面，能夠相互交流，實在是一個非常好的體驗！

## 簡述想投入的專案

### llm.c

看到老師在社群上分享的 [karpathy/llm.c](https://github.com/karpathy/llm.c) 關於 Andrej Karpathy 使用 C 語言開發的大語言模型訓練程式，比較目前 C 的實作方法對比 Pytorch 的性能差異。如同老師在第一周上課提到的，我們很常用 Pytorch，但是對於他的限制跟底層實作一概不知。

根據目前的 karpathy 提到的工作重點我想我能貢獻的有：
1. 直接在 CUDA 上實作。
- 目前實作只有前向傳播，希望有貢獻反向傳播的機會。
2. 用 SIMD 指令加速 CPU 版本。
- 目前針對 SIMD 沒有任何實作知識，希望可以學習實作。
- 增加對 CPU 的控制
3. 開發更現代的架構，如 Llama2、Gemma 等。

- - -

紀錄問題

與 jserv 進行一對一討論，紀錄以下問題：
> [time=Mon, May 6, 2024 14:00 PM]

與 jserv 討論專題，預計在 [第九週測驗題 第二題](https://hackmd.io/@sysprog/linux2024-quiz9#%E6%B8%AC%E9%A9%97-2) 並行矩陣計算進行延伸，探討是否有可能在 llama.cpp 等專案是否有提升效能的可能性。需要有實質上的提升，並有實驗佐證。

matmul 筆記在 [這裡](https://hackmd.io/@tony268596/Hy4EWvXM0)

#### 1. 為何不同大小的方陣不能相乘？參閱 [2024-04-16 問答簡記](https://hackmd.io/@sysprog/ByhWN5jeR?fbclid=IwZXh0bgNhZW0CMTAAAR2Vhu3uEN_0vijWCZMoM92281SVzcpTgQ1JsOy8qGWchylL958hmIEFgRs_aem_AZDrSvHardf4em77UrgH_vWceu5H-C_XJanSG8le3mW9iOeGPz_429xwqePrVC_ypWg3HJGeGfR4jZGZyvlcxJ7n#jouae)

>矩陣是線性轉換的有序基底間的映射關係，而矩陣乘向量是將一空間的座標向量映射至另一個空間的座標向量

jouae 從什麼是矩陣相乘講述，它從映射關係講起，令 $(UT)(v)$ ，則可以解釋為原本的 $v$ 從原本的空間映射到 $T$ 向量空間，再從 $T$ 向量空間轉換到 $U$ 向量空間。為了完成線性轉換的兩者的基底必須相同。$A=[T]^{\beta}_{\alpha}$ 和 $B=[U]_{\beta}^{\gamma}$。則 $AB=[UT]_{\alpha}^{\gamma}$

#### 2. llama 的效能瓶頸會是什麼？
目前瓶頸有兩個：
1. Quantization
2. Matrix Multiplication
#### 3. 浮點數跟定點數分別需要多少 memory 空間？會有多少精確度？
假設這邊的定點數為 8 位元整數，fp32 需要 32 位元記憶體空間，8 位元整數 需要 8 位元記憶體空間，記憶體成本是浮點數的四分之一。
精度會依據不同 quantization 手段有不同精確度。
[quantization 筆記](https://hackmd.io/@tony268596/HyjsVKBmR)
#### 4. bf16, fp16 差別是什麼？

以 FP16 來說，有 1 個 bit 作為 sign bit，5 bits 作為 exponent，還有 10 bits 的 fraction (significand)。
sign bit 用來設定正負數，0 設定正數，1 設定負數。
Exponent 用來表示浮點數可以表示的範圍，從 00001 到 11110，，offset 設為 15，故其範圍是 $2^{-14}-2^{15}$。
Fraction 用來設定小數點精度，會有 10 個 bits 紀錄，但其實會包含首位第一個預設的 1，所以會紀錄 11 位。

我們得公式如以下：
$(-1)^{sign} * 2^{exponent - 15}*1.fractoin(binary)$

這邊看到另外一種計算方法，認為很有趣，因為 fraction 10 個 bits 最大為 $2^{10}=1024$ 那所以 fraction 的表示都會在這個之中，可以用比例去計算出 fraction 在 十進制的大小。

$(-1)^{sign} * 2^{exponent - 15}*(1+\frac{fraction(decimal)}{1024})$

故我們算 fp16 的表示範圍：
最大正數：$0111101111111111=(-1)^0*2^{30-15}*(1+\frac{1023}{1024})=65504$
最小正數：$0 00001 0000000000=(-1)^0*2^{1-15}*(1+\frac{0}{1024})=0.00006103515625$
（正數負數表示範圍是一樣的，先不考慮 subnormal 的狀態，特殊表示可以在以下 wiki 找到）

範圍我參考 [fp16 wiki](https://en.wikipedia.org/wiki/Half-precision_floating-point_format#Half_precision_examples)：
這邊要注意的是 exponent 全為 0 或是全為 1 的情況：
全為 1 會被用來表示 `INF`


BF16 全名為 brain floating point，為 google brain 所開發。有 1 個 bit 作為 sign bit，8 bits 作為 exponent，還有 7 bits 的 fraction (significand)。offest 設為 127。

其公式為
$(-1)^{sign} * 2^{exponent - 127}*1.fractoin(binary)$
最大正數為：
$0 11111110 1111111=(-1)^0*2^{254-127}*(1+\frac{fraction}{128}) = 3.38953139 × 10^{38}$
最小正數為：
$0 00000001 0000000=(-1)^0*2^{1-127}*(1+\frac{0}{128})=1.175494351 × 10^{−38}$


| 表示範圍 | FP16 | BF16 |
| -------- | ---------------- | ------------------------ |
| MAX | 65504 | $3.38953139 × 10^{38}$ |
| MIN | 0.00006103515625 | $1.175494351 × 10^{−38}$ |

#### 5. [文章]((https://justine.lol/matmul/))中 `fortran` 的矩陣相乘其中它數字代表什麼？
作者提到了 numpy 模組的使用，其中涉及調用 Fortran 來完成 SGEMM。整體的流程為：Python -> Numpy (C) -> BLAS (Basic Linear Algebra Subprograms) -> SGEMM (Fortran)。

      SUBROUTINE SGEMM(TRANSA,TRANSB,M,N,K,ALPHA,A,LDA,B,LDB,BETA,C,LDC)
*     .. Scalar Arguments ..
      REAL ALPHA,BETA
      INTEGER K,LDA,LDB,LDC,M,N
      CHARACTER TRANSA,TRANSB
*     .. Array Arguments ..
      REAL A(LDA,*),B(LDB,*),C(LDC,*)
      [...]
*
*           Form  C := alpha*A*B + beta*C.
*
              DO 90 J = 1,N
                  IF (BETA.EQ.ZERO) THEN
                      DO 50 I = 1,M
                          C(I,J) = ZERO
   50                 CONTINUE
                  ELSE IF (BETA.NE.ONE) THEN
                      DO 60 I = 1,M
                          C(I,J) = BETA*C(I,J)
   60                 CONTINUE
                  END IF
                  DO 80 L = 1,K
                      IF (B(L,J).NE.ZERO) THEN
                          TEMP = ALPHA*B(L,J)
                          DO 70 I = 1,M
                              C(I,J) = C(I,J) + TEMP*A(I,L)
   70                     CONTINUE
                      END IF
   80             CONTINUE
   90         CONTINUE
      [...]
      RETURN
      END

在這個部分，數字可以自訂，代表 for 迴圈內的所有語句。以上述程序為例，`DO 90 J = 1, N` 至 `90 CONTINUE` 構成了此 for 迴圈的語句範圍；在 C 語言中，這對應於使用大括號來界定。

#### 6. multiply-add matrix 是什麼？
$a \leftarrow a+(b*c)$
將乘法的乘積結果和累加器 A 的值相加，再存入累加器。若沒有使用 MAC 指令，上述的程式可能需要二個指令，但 MAC 指令可以使用一個指令完成。他的輸入格式可以為 8 bits, 16 bits 但是經過最後累加器會變成 32 bit。
若一條 MAC 指令在處理浮點數時只有一次的數值修約，則這種指令稱為 FMA。

TODO:
讀懂 [LLaMA Now Goes Faster on CPUs](https://justine.lol/matmul/) 文章

專題問題：
在 [筆記](https://hackmd.io/@tony268596/Hy4EWvXM0) 中我對 [matmul](https://github.com/attractivechaos/matmul) 使用的資料型態是 float 與 [Matrix_Multiply_using_Arm_Neon_and_Avx](https://github.com/ruthreshx/Matrix_Multiply_using_Arm_Neon_and_Avx) 進行了測試。我發現，並行程式只在大型矩陣相乘時顯示出其優勢，而在小型矩陣相乘時，其並行成本反而會降低效能。

<!-- 在不同 quantization 會產生不同的精度，要怎麼測試它對模型準確率的影響？ -->

在測試過程中，我發現 SIMD 對效能提升具有顯著的影響。[matmul](https://github.com/attractivechaos/matmul) 使用了 SSE 技術，而 [Matrix_Multiply_using_Arm_Neon_and_Avx](https://github.com/ruthreshx/Matrix_Multiply_using_Arm_Neon_and_Avx) 則採用了 neon 技術，與文章中提及的 AVX512 相比較。因此，我認為下一步應該是比較不同 quantization 後，使用 SIMD 在核心模組進行效能的比較，並實驗確定在何種矩陣大小下啟用並行計算最為合適。

在 Linux 核心模組使用 SSE/AVX/NEON 等 SIMD 指令集並降低資料存取的延遲，引入 bf16 計算，並適時開啟並行矩陣計算。

[LLaMA Now Goes Faster on CPUs](https://justine.lol/matmul/) 文真中提到關於不同 quantization 所產生的精度差異，我該如何實驗它對模型的影響（訓練速度、推論速、準確率）？

確認 VDPBF16PS 指令怎麼使用在 AVX_VNNI?

<!-- 如果想完成 bf16 的實驗，我的設備 `13th Gen Intel(R) Core(TM) i7-13700` 該怎麼完成 bf16 的運算？從 user space (fp32) 使用核心模組轉為 bf16 進行 V * K * Q 再複製回 user space。 -->

<!-- 謂何 [OpenBLAS](https://github.com/OpenMathLib/OpenBLAS) 的 sgemm 可以這麼快？ -->

期末專案

方案一
Homework5 上次一對一討論的問題紀錄與回覆。

整理 LLaMA Now Goes Faster on CPUs 所學習到的知識，在 筆記

在測試過程中，我發現 SIMD 對效能提升具有顯著的影響。matmul 使用了 SSE 技術，而 Matrix_Multiply_using_Arm_Neon_and_Avx 則採用了 neon 技術，與文章中提及的 AVX512 相比較。目前還在學習怎麼使用使用 SIMD 指令。我認為下一步應該是比較不同 quantization 後，使用 SIMD 在核心模組進行效能的比較，並實驗確定在何種矩陣大小下啟用並行計算最為合適。

quantization 程式實作未看，llamafile 程式未看。
Q: bfloat16, f16, q (fixedpoint)
TODO: 理解 data type 與其精確度和 tok/s 速度的取捨

TODO: 探討 llamafile 相較於 llama.cpp 進行哪些調整，得以加速？ (重現實驗並分析)
TODO: 一旦選定 data type，就聚焦在 matmul 的實作 (w/ SIMD, OpenMP, oneMKL, OpenBLAS, ...) 的效益 => 我們需要有個 wrapper/tester，得以涵蓋現有實作並整合進 llama.cpp，在 Linux 平台驗證，perf (搭配第六次作業提到的[效能分析方式](https://hackmd.io/@sysprog/linux2024-integration/%2F%40sysprog%2Flinux2024-integration-a)，排除系統干擾)
TODO: (bonus) 提出更快的 matmul
> llamafile is defived llama.cpp