109 年 國立中正大學通訊工程學系碩士班通訊乙組《線性代數與計算機組織》

核心觀念

本題主要考查：

1. Gaussian–Jordan elimination：將矩陣化為最簡列梯形式（RREF）。
2. 樞紐欄與欄空間基底：RREF 的樞紐欄位置，對應到原矩陣中的欄向量；注意不能直接取 RREF 的欄向量作為原矩陣欄空間基底。
3. 線性組合與生成空間：判斷向量是否能由矩陣的列向量或欄向量線性組合而成。
4. 座標向量：若 $C$ 是某向量空間的基底，必須先確認目標向量屬於該向量空間，座標向量才存在。

---

(a) 求 $A$ 的最簡列梯形式

給定

$$A= \begin{bmatrix} 1&2&3&4\\ 4&3&2&1\\ 1&3&5&7\\ 7&5&3&1 \end{bmatrix}.$$

先以第一列消去第一欄以下元素：

$$R_2\leftarrow R_2-4R_1,\qquad R_3\leftarrow R_3-R_1,\qquad R_4\leftarrow R_4-7R_1.$$

得到

$$\begin{bmatrix} 1&2&3&4\\ 0&-5&-10&-15\\ 0&1&2&3\\ 0&-9&-18&-27 \end{bmatrix}.$$

交換第二、三列：

$$R_2\leftrightarrow R_3,$$

得

$$\begin{bmatrix} 1&2&3&4\\ 0&1&2&3\\ 0&-5&-10&-15\\ 0&-9&-18&-27 \end{bmatrix}.$$

利用第二列消去其餘元素：

$$R_1\leftarrow R_1-2R_2,$$ $$R_3\leftarrow R_3+5R_2,$$ $$R_4\leftarrow R_4+9R_2.$$

因此

$$\begin{bmatrix} 1&0&-1&-2\\ 0&1&2&3\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}.$$

所以

$$\boxed{ \operatorname{rref}(A)= \begin{bmatrix} 1&0&-1&-2\\ 0&1&2&3\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}}$$

其中樞紐欄為第 $1$ 欄與第 $2$ 欄，因此

$$\operatorname{rank}(A)=2.$$

---

(b) 求 $A$ 的欄空間基底 $C$

RREF 的樞紐欄是第 $1$ 欄與第 $2$ 欄，所以必須取原矩陣 $A$ 的第 $1$、第 $2$ 欄：

$$\boldsymbol a_1= \begin{bmatrix} 1\\4\\1\\7 \end{bmatrix}, \qquad \boldsymbol a_2= \begin{bmatrix} 2\\3\\3\\5 \end{bmatrix}.$$

因此欄空間的一組基底為

$$\boxed{ C= \left\{ \begin{bmatrix}1\\4\\1\\7\end{bmatrix}, \begin{bmatrix}2\\3\\3\\5\end{bmatrix} \right\}}$$

也就是

$$\operatorname{Col}(A) = \operatorname{span} \left\{ \begin{bmatrix}1\\4\\1\\7\end{bmatrix}, \begin{bmatrix}2\\3\\3\\5\end{bmatrix} \right\}.$$

解題技巧

樞紐欄的位置要由 RREF 判斷，但基底向量要回到原矩陣取得。直接使用 RREF 的欄向量，通常只能得到與原欄空間不同的向量組。

---

(c) 判斷 $v$ 是否能表示為列向量的線性組合，並求 $(v)_C$

給定

$$v= \begin{bmatrix} 0\\-5\\1\\9 \end{bmatrix}.$$

以 $A$ 的列向量作線性組合

由 RREF 可知，$A$ 的列空間由

核心觀念

本題考查：

• 齊次方程組 $B\mathbf{x}=\mathbf{0}$ 的解集合，即矩陣 $B$ 的零空間。

• 零空間的維度與秩—零度定理：

  $\dim(\operatorname{Null}(B))+\operatorname{rank}(B)=3$

• 特徵值與特徵向量的定義：

  $B\mathbf{v}=\lambda\mathbf{v},\qquad \mathbf{v}\ne\mathbf{0}$

  等價於求解：

  $\det(B-\lambda I)=0$

---

解題方法

矩陣為

$$B= \begin{bmatrix} 1&0&3\\ 0&5&0\\ 7&0&9 \end{bmatrix}$$

其中第二列、第二行與其他變數分離，因此可先處理 $x,z$ 的二元部分，再處理 $y$。

---

(a) 求 $B$ 的零空間與其維度

令

$$\mathbf{x}= \begin{bmatrix} x\\y\\z \end{bmatrix}$$

零空間中的向量必須滿足

$$B\mathbf{x}=\mathbf{0}$$

因此

$$\begin{bmatrix} 1&0&3\\ 0&5&0\\ 7&0&9 \end{bmatrix} \begin{bmatrix} x\\y\\z \end{bmatrix} = \begin{bmatrix} 0\\0\\0 \end{bmatrix}$$

得到聯立方程式：

$$\begin{cases} x+3z=0,\\ 5y=0,\\ 7x+9z=0. \end{cases}$$

由第二式得

$$y=0$$

由第一式得

$$x=-3z$$

代入第三式：

$$7(-3z)+9z=0$$ $$-21z+9z=0$$ $$-12z=0$$

故

$$z=0,\qquad x=0$$

所以唯一解為零向量：

$$\operatorname{Null}(B) = \left\{ \begin{bmatrix} 0\\0\\0 \end{bmatrix} \right\}$$

因此零空間的維度為

$$\boxed{\dim(\operatorname{Null}(B))=0}$$

快速驗算

矩陣的行列式為

$$\det(B) = 5 \begin{vmatrix} 1&3\\ 7&9 \end{vmatrix} = 5(9-21) =-60\ne 0$$

所以 $B$ 可逆，齊次方程組必只有零解，與上述結果一致。

---

(b) 求特徵值與特徵向量

第一步：求特徵多項式

計算

$$\det(B-\lambda I) = \begin{vmatrix} 1-\lambda&0&3\\ 0&5-\lambda&0\\ 7&0&9-\lambda \end{vmatrix}$$

沿著第二列展開：

$$\det(B-\lambda I) = (5-\lambda) \begin{vmatrix} 1-\lambda&3\\ 7&9-\lambda \end{vmatrix}$$

因此

$$\det(B-\lambda I) = (5-\lambda)\left[(1-\lambda)(9-\lambda)-21\right]$$

展開括號內的部分：

$$(1-\lambda)(9-\lambda)-21 = 9-10\lambda+\lambda^2-21$$ $$= \lambda^2-10\lambda-12$$

故特徵方程為

$$(5-\lambda)(\lambda^2-10\lambda-12)=0$$

由此得到一個特徵值：

$$\lambda_1=5$$

另外兩個特徵值由

$$\lambda^2-10\lambda-12=0$$

求得：

$$\lambda = \frac{10\pm\sqrt{100+48}}{2} = \frac{10\pm\sqrt{148}}{2} = 5\pm\sqrt{37}$$

所以全部特徵值為

$$\boxed{\lambda=5,\quad 5+\sqrt{37},\quad 5-\sqrt{37}}$$

---

第二步：求 $\lambda=5$ 時的特徵向量

解

$$(B-5I)\mathbf{v}=\mathbf{0}$$

其中

$$B-5I= \begin{bmatrix} -4&0&3\\ 0&0&0\\ 7&0&4 \end{bmatrix}$$

第 3 題　名詞解釋

a. Von Neumann bottleneck

核心觀念

Von Neumann bottleneck（馮紐曼瓶頸）是指：在馮紐曼架構中，指令與資料共用同一個主記憶體及匯流排，處理器與記憶體之間的傳輸頻寬成為系統效能瓶頸。

CPU 的執行速度通常遠高於主記憶體的存取速度，因此 CPU 必須持續等待：

1. 從記憶體擷取指令；
2. 從記憶體讀取運算資料；
3. 將運算結果寫回記憶體。

即使 CPU 本身具備很高的運算能力，整體效能仍會受限於記憶體的延遲與匯流排頻寬。

解題方法

判斷此名詞時，掌握兩個關鍵即可：

• 指令與資料共用記憶體；
• CPU 與記憶體之間的傳輸能力不足以配合 CPU 速度。

這種限制稱為 Von Neumann bottleneck。

解題技巧

答案中應同時寫出「指令與資料共用」及「記憶體頻寬／速度限制」兩項。只寫「CPU 很慢」並不正確，瓶頸主要位於 CPU 與記憶體之間的資料傳輸。

常見改善方法包括：

• 使用快取記憶體與多層記憶體階層；
• 使用預取（prefetching）；
• 增加匯流排寬度或傳輸頻寬；
• 採用指令與資料分離的 Harvard architecture；
• 使用非同步執行及平行化技術。

---

b. Write-through vs. write-back

核心觀念

這兩者都是快取記憶體（cache）的寫入策略，關鍵差異在於：CPU 修改 cache 中的資料時，何時同步更新下一層記憶體。

Write-through

Write-through（直寫式）在 CPU 寫入 cache 後，會立即將相同資料寫入下一層記憶體，通常是主記憶體。

流程為：

$$\text{CPU} \rightarrow \text{Cache}$$

同時：

$$\text{Cache} \rightarrow \text{Main Memory}$$

特性：

• cache 與主記憶體內容隨時保持一致；
• 實作簡單；
• 每次寫入都會產生下層記憶體流量；
• 寫入速度受下層記憶體影響；
• 通常搭配 write buffer 降低 CPU 等待時間；
• 不需要 dirty bit 來記錄 cache line 是否被修改。

Write-back

Write-back（回寫式）在 CPU 寫入 cache 時，只先修改 cache，不立即更新主記憶體。等到該 cache block 被替換出去時，若其內容曾被修改，才將資料寫回下一層記憶體。

流程為：

$$\text{CPU} \rightarrow \text{Cache}$$

在 cache block 被替換且資料已修改時：

$$\text{Cache} \rightarrow \text{Main Memory}$$

Write-back 必須使用 dirty bit：

• dirty bit = 0：cache 內容與主記憶體一致；
• dirty bit = 1：cache 內容已被修改，替換前必須寫回主記憶體。

比較

比較項目	Write-through	Write-back
主記憶體更新時機	每次寫入立即更新	cache block 被替換時更新
寫入流量	較大	較小
實作複雜度	較低	較高
是否需要 dirty bit	不需要	需要
主記憶體與 cache 的一致性	易於維持	必須管理
寫入效能	較容易受主記憶體影響	通常較快
系統設計	簡單、可靠	複雜但節省頻寬

解題方法

回答時先指出兩者都是 cache 的寫入政策，再以「何時更新主記憶體」作為比較主軸，最後補充效能與 dirty bit 的差異，即可完整作答。

要注意 write-through／write-back 與 write-allocate／no-write-allocate 是兩組不同的政策：

• write-through／write-back：討論寫入命中時，何時更新下層記憶體；
• write-allocate／no-write-allocate：討論寫入未命中時，是否先將資料載入 cache。

解題技巧

快速判斷方式：

• 「每次寫入都同步寫主記憶體」是 write-through；
• 「先只改 cache，替換時才寫回」是 write-back；
• 看到 dirty bit，通常就是 write-back 的特徵。

---

c. Memory mapped I/O vs. I/O mapped I/O

核心觀念

這兩種方式都是 CPU 存取輸入／輸出裝置暫存器的設計方法，差別在於 I/O 裝置是否與一般記憶體共用同一個位址空間。

Memory mapped I/O

Memory mapped I/O（記憶體映射輸入／輸出）將 I/O 裝置的控制暫存器、狀態暫存器及資料暫存器配置在一般記憶體位址空間中。

CPU 可以使用一般的記憶體存取指令，例如 load、store：

$$\text{讀取 I/O 暫存器}：\quad \text{LOAD } R_1,\,[\text{I/O address}]$$ $$\text{寫入 I/O 暫存器}：\quad \text{STORE } R_1,\,[\text{I/O address}]$$

這些位址雖然形式上屬於記憶體位址，實際上會由硬體解碼後送往 I/O 裝置。

優點：

• 使用一般的 load/store 指令即可；
• 可使用一般記憶體的定址模式；
• 程式設計介面較一致；
• 不需要額外設計專用的 I/O 指令。

缺點：

• 會佔用記憶體位址空間；
• I/O 暫存器不可任意快取，必須設定為 non-cacheable；
• 記憶體保護與 I/O 權限必須妥善管理。

I/O mapped I/O

I/O mapped I/O（I/O 映射輸入／輸出），又稱 port-mapped I/O，為 I/O 裝置建立獨立的 I/O 位址空間，與一般記憶體位址空間分開。

核心觀念

本題採用教科書常見的 MIPS 五級管線，階段如下：

階段	意義
IF	取指令
ID	指令解碼、讀取暫存器
EX	ALU 運算或計算記憶體位址
MEM	存取資料記憶體
WB	將結果寫回暫存器

當多個指令重疊執行時，後面的指令可能需要前面指令尚未完成的結果；若直接使用，便會讀到舊資料，這種因資料相依與時序衝突造成的問題稱為資料危障（data hazard）。

以暫存器 $R$ 為例：

$$I_i: W(R),\qquad I_j: R(R),\qquad i<j$$

其中 $I_i$ 先寫入 $R$，$I_j$ 後讀取 $R$。若 $I_j$ 讀取的時間早於 $I_i$ 產生或寫回正確資料的時間，就會形成危障。

常見資料危障可分為：

• RAW（Read After Write）：後指令讀取前指令即將寫入的資料，是真正的資料相依；五級、循序執行的 MIPS 管線主要處理此類危障。
• WAR（Write After Read）：後指令寫入資料，但前指令尚未完成讀取；循序執行管線通常不會發生。
• WAW（Write After Write）：兩個指令寫入同一目的地，但寫入順序錯亂；循序執行管線通常不會發生。

解題方法

判斷資料危障時，依序完成三件事：

1. 找出前一指令的目的暫存器與後一指令的來源暫存器。
2. 在管線圖中標出資料產生時間與資料使用時間。
3. 若資料已產生且有繞送路徑，使用 forwarding；若資料尚未產生，則讓後指令停頓，並在管線中插入空泡（bubble）。

Forwarding 是將較晚階段的結果直接繞送至目前指令的 ALU 輸入端，不必等待資料完成 WB。Stall 則是暫停後續指令的推進，直到所需資料可用。

---

（a）資料危障的定義

資料危障是指：在管線重疊執行期間，某一指令需要使用前面指令產生的資料，但該資料尚未在指定時間準備完成；若不採取 forwarding 或 stall，後指令便會使用錯誤的舊值，造成計算結果錯誤。

---

（b）以 forwarding 處理資料危障

考慮下列兩個指令：

$$I_1:\ \texttt{ADD R1, R2, R3}$$ $$I_2:\ \texttt{SUB R4, R1, R5}$$

$I_1$ 將結果寫入 $R1$，$I_2$ 隨後讀取 $R1$，因此兩者具有 RAW 資料危障。

管線圖

指令／週期	1	2	3	4	5	6
$I_1:\ \texttt{ADD}$	IF	ID	EX	MEM	WB	—
$I_2:\ \texttt{SUB}$	—	IF	ID	EX	MEM	WB

在第 3 週期：

• $I_1$ 在 EX 階段完成 ALU 運算。
• $I_2$ 在 ID 階段讀取暫存器欄位，但此時 $R1$ 尚未完成 WB。

在第 4 週期：

• $I_1$ 位於 MEM 階段，運算結果已存於 EX/MEM 管線暫存器。
• $I_2$ 進入 EX 階段，必須使用 $R1$。
• 控制電路將 $I_1$ 的 ALU 結果從 EX/MEM 直接繞送至 $I_2$ 的 ALU 輸入端。

資料路徑可表示為：

$$\text{EX/MEM.ALUResult} \longrightarrow \text{$I_2$ 的 EX 階段 ALU 輸入}$$

因此 $I_2$ 不必等待 $I_1$ 到第 5 週期完成 WB，也不需要插入空泡，整體管線沒有額外停頓。

---

核心觀念

這題考「移位加法乘法」：每回合檢查乘數最低位（Multiplier 的 bit 0）。若該位是 $1$，就把被乘數加到乘積；接著將被乘數左移一位、乘數右移一位。流程圖指定重複 4 次，因此共執行 4 回合。

解題方法

表格每列記錄該回合完成加法與移位後的數值。初始乘積為 $0$，初始被乘數為 $6$，乘數為 $0011$。

• 第 1 回合：乘數最低位為 $1$，乘積加上 $6$ 得 $6$；再將乘數右移、被乘數左移。
• 第 2 回合：乘數最低位仍為 $1$，乘積加上 $12$ 得 $18$；再執行移位。
• 第 3、4 回合：乘數最低位皆為 $0$，乘積不變，只執行移位。