2024q1 Homework5 (assessment)

contributed by < vestata >

測驗題改進

選擇三題進行改進。

1. 第四周測驗題 Q2

預計：

• 補完之前缺失的 lab0-c 之 ttt
  • 完成 coroutine 並行
  • 鍵盤事件
• 第四周測驗題 Q3

2. 第三周測驗題 Q3

詳見 log2
以不同方式實作 log2() 比較效能差距。
預計：

• 分析噪點原因
  • 改為使用 perf 測量，發現不能明顯體現實驗結果
• 更多 linux 應用案例

3. 第一周測驗題 Q2

預計：

• 實作 timsort 中的 insertion sort, galloping mode 部份
• 觀察 list_sort 在 linux 中的使用場景
• 是否 timsort 在這些場景中表現受否會好

閱讀 因為自動飲料機而延畢的那一年

「一項產業進步的速度，很大程度取決於做實驗修正問題的速度。」

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

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

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

屆時剛好做完 NVIDIA GPU System Software Engineer Intern 的 hackerrank 測試。因為最近一直在寫實作的作業自認為對程式的掌握有提高，也很久沒有刷 leetcode 了，前面的基礎題還好，後面的程式題（leetcode 類型）真得是表現欠佳。今年找的暑期實習也都沒什麼好消息，心情多少還是被影響到。但是看到文章中 jserv 老師提到：

「你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望。你可以計算要花多少錢，然後評估自己可以接受多少損失，畢業後慢慢還都好，要錢我也可以借你。但青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」

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

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

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

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

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

簡述想投入的專案

llm.c

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

根據目前的 karpathy 提到的工作重點我想我能貢獻的有：

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

---

紀錄問題

與 jserv 進行一對一討論，紀錄以下問題：

Mon, May 6, 2024 14:00 PM

與 jserv 討論專題，預計在 第九週測驗題 第二題 並行矩陣計算進行延伸，探討是否有可能在 llama.cpp 等專案是否有提升效能的可能性。需要有實質上的提升，並有實驗佐證。

matmul 筆記在 這裡

1. 為何不同大小的方陣不能相乘？參閱 2024-04-16 問答簡記

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

jouae 從什麼是矩陣相乘講述，它從映射關係講起，令

$(UT)(v)$ ，則可以解釋為原本的

$v$ 從原本的空間映射到

$T$ 向量空間，再從

$T$ 向量空間轉換到

$U$ 向量空間。為了完成線性轉換的兩者的基底必須相同。

$A=[T{]}_{\alpha }^{\beta }$ 和

$B=[U{]}_{\beta }^{\gamma }$。則

$AB=[UT{]}_{\alpha }^{\gamma }$

2. llama 的效能瓶頸會是什麼？

目前瓶頸有兩個：

1. Quantization
2. Matrix Multiplication

3. 浮點數跟定點數分別需要多少 memory 空間？會有多少精確度？

假設這邊的定點數為 8 位元整數，fp32 需要 32 位元記憶體空間，8 位元整數 需要 8 位元記憶體空間，記憶體成本是浮點數的四分之一。
精度會依據不同 quantization 手段有不同精確度。
quantization 筆記

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}\ast 2^{exponent-15}\ast 1.fractoin(binary)$

這邊看到另外一種計算方法，認為很有趣，因為 fraction 10 個 bits 最大為

$2^{10}=1024$ 那所以 fraction 的表示都會在這個之中，可以用比例去計算出 fraction 在 十進制的大小。

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

故我們算 fp16 的表示範圍：
最大正數：

$0111101111111111=(-1{)}^0\ast 2^{30-15}\ast (1+\frac{1023}{1024})=65504$
最小正數：

$0000010000000000=(-1{)}^0\ast 2^{1-15}\ast (1+\frac{0}{1024})=0.00006103515625$
（正數負數表示範圍是一樣的，先不考慮 subnormal 的狀態，特殊表示可以在以下 wiki 找到）

範圍我參考 fp16 wiki：

這邊要注意的是 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}\ast 2^{exponent-127}\ast 1.fractoin(binary)$
最大正數為：

$0111111101111111=(-1{)}^0\ast 2^{254-127}\ast (1+\frac{fraction}{128})=3.38953139\times {10}^{38}$
最小正數為：

$0000000010000000=(-1{)}^0\ast 2^{1-127}\ast (1+\frac{0}{128})=1.175494351\times {10}^{-38}$

表示範圍	FP16	BF16
MAX	65504	$3.38953139\times {10}^{38}$
MIN	0.00006103515625	$1.175494351\times {10}^{-38}$

5. 文章中 fortran 的矩陣相乘其中它數字代表什麼？

作者提到了 numpy 模組的使用，其中涉及調用 Fortran 來完成 SGEMM。整體的流程為：Python -> Numpy © -> 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\ast c)$
將乘法的乘積結果和累加器 A 的值相加，再存入累加器。若沒有使用 MAC 指令，上述的程式可能需要二個指令，但 MAC 指令可以使用一個指令完成。他的輸入格式可以為 8 bits, 16 bits 但是經過最後累加器會變成 32 bit。
若一條 MAC 指令在處理浮點數時只有一次的數值修約，則這種指令稱為 FMA。

TODO:
讀懂 LLaMA Now Goes Faster on CPUs 文章

專題問題：
在 筆記 中我對 matmul 使用的資料型態是 float 與 Matrix_Multiply_using_Arm_Neon_and_Avx 進行了測試。我發現，並行程式只在大型矩陣相乘時顯示出其優勢，而在小型矩陣相乘時，其並行成本反而會降低效能。

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

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

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

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

期末專案

方案一
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 (搭配第六次作業提到的效能分析方式，排除系統干擾)
TODO: (bonus) 提出更快的 matmul

llamafile is defived llama.cpp