2024-04-16 問答簡記

檢討第五次作業

williamS

第五次作業

• EWMA 在 Linux Kernel 中哪邊有用到呢？
  • 可做 CPU sched 的 estimated utilization。

weihsinyeh

第五次作業

• weakly-ordered V.S. strongly-ordered
  • 當 CPU 速度比 Main Memory 快上許多時，在硬體架構設計上，cache 設計讓 CPU load / store 省去每次存取 Main Memory 的成本，但還是受限於 instructions 的 execution orders。
  • store buffer暫存 CPU store 指令，讓 CPU 不須等待 store instruction 完成即可進行下個 instruction ，(帶來什麼優點呢？) 允許 CPU 處理指令可不受限於 execution orders 。然而，在多核處理器系統中，需要處理 Cache Coherence 的問題。所以，還多了廣播給不同 CPU core 上的 cache 以及等待其他 CPU cache 完成對應 cacheline update 的 overhead。
  • invalidate buffer 就沒有聽清楚了。
• rdtsc V.S. C STL gettime()
  • C STL gettime() 量測精準度到 microsecond 等級，執行多次取平均又可能會涵蓋其他不易觀察的 operations，例如：timer interrupt。
• about magic number 0xbfff978 ？
  • debug Linux Kernel 的方式。
    • 西元 2000 年時, 虛擬化 Virtualization 技術還未成熟，需要多一台機器，透過特殊的 cable 來連接要觀察的 Linux 系統。
    • 後來可透過在 Linux Kernel 預先註冊 Exception Handler 來觀察特定事件被觸發時的 CPU 狀態。
    • …

david965154

fork 仍需要時間成本，尤其是在遞迴期間才做 fork ，因此會不斷的進行 fork 直到 fork_count 到達設定值或者 partition 結束。不過剛剛有看到若設定值過大，執行時間會變很長的同時還會導致排序錯誤，但為什麼會導致排序錯誤 ?

invoke mmap(2) to share among forked processes.
sudo sysctl -w kernel.sched_child_runs_first=1，以便要求 Linux 排程器 (CFS) 讓 child process 優先於 parent process 執行

改進 concurrent (fork) merge sort:

1. 避免遞迴，降低 fork 的成本
2. 預先 fork (pre-forking)
3. 實作 workqueue // 參見 案例: Thread Pool 實作和改進

millaker

ioctl
demand paging
page size: 4KB (trade-off)
Arm64: 4KB, 16KB, 64KB
CS:APP Chapter 9 (virtual memory)
https://docs.kernel.org/admin-guide/mm/hugetlbpage.html (HugeTLB)

KPTI dramatically increased this cost: directly, by switching the active page table at each context transition
=> ESCA: Effective System Call Aggregation for Event-Driven Servers

jouae

"The purpose of computing is insight, not numbers." by Richard Hamming, Numerical Methods for Scientists and Engineers (1962).

第 9 週測驗 中提及的矩陣乘法，為何不同大小的方陣不能相乘？簡單歸納兩個結論：

• 矩陣表示式是根據線性轉換而來
• 矩陣相乘是線性轉換間的合成

線性代數(linear algebra) 字面意思是在討論線性性質與代數結構，與一般工程數學或是工程學中的線性代數不同，數學系相關的線性代數出發點是向量空間(vector space)，所謂向量空間其實就是代數中的體(field)的延伸，對於一個體

$(F,+,\times )$ 與一個集合

$V$ 會滿足十個公理。

從向量空間開始接續會討論到線性相依、線性獨立、基底，再來到線性這個性質

• 對兩個體為
  $F$ 的向量空間
  $V,W$ ，函數
  $T:V_1\to V_2$ 為線性轉換，對所有係數
  $c\in F$ 和
  $a,b\in V$ 滿足以下特性：
  • 加法線性：
    $T(a+b)=T(a)+T(b)$
  • 係數乘法：
    $T(ca)=cT(a)$

線性組合、基底等等這些概念都是息息相關。由有序基底

$\beta =\{v_1,v_2,\dots ,v_n\}$ 生成的向量空間

$V$ ，藉由係數

$a_1,a_2,\dots ,a_n$ 對基底元素的線性組合，組合出任意向量

$x\in V$ 表示為

$$x=\sum _{i=1}^n{a}_i{v}_i$$
且每個係數皆唯一。

而以

$\beta$ 為基底的

$x$ 座標向量表示為

$$[x{]}_{\beta }=\left[\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_n\end{array}\right]$$

讓向量空間

$V$ 的有序基底為

$\beta =\{v_1,v_2,\dots ,v_n\}$ 和向量空間

$W$ 的有序基底為

$\gamma =\{w_1,w_2,\dots ,w_m\}$ ，以及一線性轉換

$T:T\to W$ 則對

$1\le j\le n$ 存在唯一係數

$a_{ij}\in F$ 對

$1\le i\le m$ 使得

$$T(v_i)=\sum _{i=1}^m{a}_{ij}{w}_i,\text{for }1\le i\le n.$$

• 藉由上述的表示法，可以得到一藉由基底
  $\beta$ 和
  $\gamma$ 線性轉換
  $T$ 的矩陣表示式
  $A=[T{]}_{\beta }^{\gamma }$

舉書本 p.81 例子 3，對線性轉換

$T:{\mathbb{R}}^2\to {\mathbb{R}}^3$

$$T(a_1,a_2)=(a_1+3a_2,0,2a_1-4a_2).$$
讓

$\beta$ 和

$\gamma$ 為標準有序基底。則

$T$ 由基底

$\beta$ 和基底

$\gamma$ 構成的矩陣表示法為

$$T(1,0)=1e_1+0e_2+3e_3,T(0,1)=3e_1+0e_2-4e_3$$

$$[T{]}_{\beta }^{\gamma }=\left[\begin{array}{cc}1& 3\\ 0& 0\\ 3& -4\end{array}\right]$$

如果把有序基底的順序改一下變成

${\gamma }^{\prime }=\{e_3,e_1,e_2\}$ 則矩陣表示法為

$$[T{]}_{\beta }^{{\gamma }^{\prime }}=\left[\begin{array}{cc}3& -4\\ 1& 3\\ 0& 0\end{array}\right]$$
再來探討下矩陣乘向量這個操作的數學含意。令

$x=(1,-1{)}^T$ 則

$$[T{]}_{\beta }^{\gamma }x=1\left[\begin{array}{c}1\\ 0\\ 3\end{array}\right]-1\left[\begin{array}{c}3\\ 0\\ -4\end{array}\right]=\left[\begin{array}{c}2\\ 0\\ 7\end{array}\right]$$
可以看到

$[T{]}_{\beta }^{\gamma }$ 的行向量，藉由

$x$ 中的元素為係數做線性組合。

回到線性轉換以函數觀點來思考

$$T(1,-1)=T(1,0)-T(0,1)=(1e_1+0e_2+3e_3)-(3e_1+0e_2-4e_3)$$
其實就是先將基底

$\beta$ 中的元素線性組合出

$x$ 後以線性轉換得到函數映射至

${\mathbb{R}}^3$ 基底元素的線性組合。

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

接續討論矩陣乘矩陣是什麼？先講結論矩陣乘矩陣代表線性轉換的合成，也因為是函數合成，除非特定情況下矩陣相乘不滿足交換律。

• 令
  $T:V\to W$ 和
  $U:W\to Z$ 為線性轉換，其中
  $UT:V\to Z$ 也為線性轉換。讓
  $\alpha =\{v_1,v_2,\dots ,v_n\}$ 、
  $\beta =\{w_1,w_2,\dots ,w_m\}$ 和
  $\gamma =\{z_1,z_2,\dots ,z_p\}$ 為向量空間
  $V,W$ 和
  $Z$ 各自的有序基底且矩陣表示式為
  $A=[T{]}_{\alpha }^{\beta }$ 和
  $B=[U{]}_{\beta }^{\gamma }$。則
  $AB=[UT{]}_{\alpha }^{\gamma }$ 對
  $1\le j\le n$
  
  $$\begin{array}{rl}(UT)(v_j)& =U(T(v_j))=U\left(\sum _{k=1}^m{B}_{kj}{w}_k\right)\\ & =\sum _{k=1}^m{B}_{kj}U(w_k)=\sum _{k=1}^m{B}_{kj}\left(\sum _{i=1}^p{A}_{ik}{z}_i\right)\\ & =\sum _{i=1}^p\left(\sum _{k=1}^m{A}_{ik}{B}_{kj}\right)z_i=\sum _{i=1}^p{C}_{ij}{z}_i.\end{array}$$

其中

$C=AB$ 為矩陣相乘的結果，也是線性轉換

$UT$ 的矩陣表示式。至此我們可以瞭解矩陣乘矩陣和線性轉換合成之間的關聯。

而關於行列式的部分，強烈建議看看 行列式 | 線性代數的本質 第五章 by 3Blue1Brown 從幾何座標的角度講解

$2\times 2$ 和

$3\times 3$ 行列式值在幾何上的意義。

其中很重要的一個部分

$\text{det}(A)=0$ 也就是矩陣

$A$ 中的行或列向量並非線性獨立，這告訴我們矩陣的

$\text{rank}(A)\ne \text{dim}(A)$。換言之

$A$ 並非以有序基底映射的矩陣表示式，也因為並非基底所以無法生成(span)原本線性轉換定義域的全空間。

在影片 3:05 處 可以看到兩向量張開的面積被壓縮成一條線，就是在告訴我們這個矩陣中的行或是列向量有線性相依的情況，無法生成原本的全空間，並非一組基底形成的矩陣表示式。

最後討論下影片最後的問題：
行列式

$\text{det}(AB)$ 與

$\text{det}(A)$ 和

$\text{det}(B)$ 的關係，其中

$\text{det}(A)$ 和

$\text{det}(B)$ 不為零，且

$A$ 和

$B$ 為大小相同的方陣可以寫成

$$\text{det}(AB)=\text{det}(A)\text{det}(B)$$
從計算可以證明這件事情，但從線性轉換跟幾何的角度思考，這件事情解釋起來就很簡單。由於皆為方陣，定義域和對應域的向量空間大小皆相同，

$AB=[UT{]}_{\alpha }^{\gamma }$ 以線性轉換角度來看只是把一個有序基底

$\alpha$ 換成另一個有序基底

$\gamma$。將上述行列式的等號改以基底變換呈現為

$$\text{det}([UT{]}_{\alpha }^{\gamma })=\text{det}([T{]}_{\alpha }^{\beta })\text{det}([U{]}_{\beta }^{\gamma })$$
等式右邊

$\text{det}([T{]}_{\alpha }^{\beta })$ 是將面/體積從有序基底

$\alpha$ 映射至

$\beta$ 伸縮的係數，同理

$\text{det}([T{]}_{\beta }^{\gamma })$。則兩個行列式相乘的過程就是，從

$\alpha$ 映射至

$\beta$ 做一次伸縮後得到的面/體積變化係數，乘上以基底

$\beta$ 為坐標系做一次映射至

$\gamma$ 坐標系的面/體積變化係數。

• 參考資料

• Linear Algebra S. Friedberg A. Insel L. Spence Fourth Edition
• 行列式 | 線性代數的本質 第五章 by 3Blue1Brown