# 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 差別是什麼?
![image](https://hackmd.io/_uploads/B1g93K2MR.png)
以 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):
![截圖 2024-05-11 下午3.07.31](https://hackmd.io/_uploads/HkmvF52MC.png)
這邊要注意的是 exponent 全為 0 或是全為 1 的情況:
全為 1 會被用來表示 `INF`
![image](https://hackmd.io/_uploads/HJyN_9nG0.png)
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}$
![image](https://hackmd.io/_uploads/rJBG1snfA.png)
| 表示範圍 | 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)。
```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