調查局三等申論題
115年
[資訊科學組] 作業系統及系統程式
第 一 題
📖 題組：
三、針對 MIPS 指令及架構的組合語言程式，假設 X 與 Y 均為每個元素占用 4 Bytes 的一維整數陣列，變數 a、b、c、d、e 分別配置於暫存器$s0、$s1、$s2、$s3、$s4，而陣列 X 與 Y 的起始位址分別儲存於暫存器$s6 與$s7。 I1 addi $t0, $s6, 36 I2 lw $t0, 0($t0) I3 sll $t0, $t0, 3 I4 sll $t1, $s4, 2 I5 add $t1, $t1, $s7 I6 lw $t1, 0($t1) I7 add $t0, $t0, $t1 I8 add $s3, $t0, $s2 (一)請說明上述 MIPS 組合語言程式（I1）~（I6）的運作邏輯，並將整個程式轉換為等效的 C 語言程式碼。（10 分） (二)假設上述程式在單一發射、循序執行的典型五階段 MIPS 管線處理器中執行，管線階段依序為 IF、ID、EX、MEM 與 WB。處理器具有由 EX/MEM 與 MEM/WB 管線暫存器至 EX 階段的完整資料轉傳路徑，且 lw 指令載入的資料須至 MEM 階段結束後才能使用。請找出程式中可能發生的資料危障（Data Hazard），指出具有 RAW 資料相依關係的指令及相依暫存器，並說明那些危障可透過資料轉傳解決，以及那些載入使用危障（Load-use Hazard）仍須插入停頓週期（Stall Cycle）。（15 分）
三、針對 MIPS 指令及架構的組合語言程式，假設 X 與 Y 均為每個元素占用 4 Bytes 的一維整數陣列，變數 a、b、c、d、e 分別配置於暫存器$s0、$s1、$s2、$s3、$s4，而陣列 X 與 Y 的起始位址分別儲存於暫存器$s6 與$s7。 I1 addi $t0, $s6, 36 I2 lw $t0, 0($t0) I3 sll $t0, $t0, 3 I4 sll $t1, $s4, 2 I5 add $t1, $t1, $s7 I6 lw $t1, 0($t1) I7 add $t0, $t0, $t1 I8 add $s3, $t0, $s2 (一)請說明上述 MIPS 組合語言程式（I1）~（I6）的運作邏輯，並將整個程式轉換為等效的 C 語言程式碼。（10 分） (二)假設上述程式在單一發射、循序執行的典型五階段 MIPS 管線處理器中執行，管線階段依序為 IF、ID、EX、MEM 與 WB。處理器具有由 EX/MEM 與 MEM/WB 管線暫存器至 EX 階段的完整資料轉傳路徑，且 lw 指令載入的資料須至 MEM 階段結束後才能使用。請找出程式中可能發生的資料危障（Data Hazard），指出具有 RAW 資料相依關係的指令及相依暫存器，並說明那些危障可透過資料轉傳解決，以及那些載入使用危障（Load-use Hazard）仍須插入停頓週期（Stall Cycle）。（15 分）
📝 此題為申論題，共 2 小題
小題 (一)
請說明上述 MIPS 組合語言程式（I1）~（I6）的運作邏輯，並將整個程式轉換為等效的 C 語言程式碼。（10 分）
思路引導 VIP
看到 MIPS 指令，必須逐行翻譯成數學意義。陣列元素佔 4 Bytes，因此位移量 36 代表的是第幾個元素（36/4=9）？sll 左移指令代表乘以 2 的幾次方？逐行解析出 $t0 與 $t1 裝了什麼，最後 I7 和 I8 在做什麼相加？把最終算式整合成 C 語言變數與陣列存取的形式。
小題 (二)
假設上述程式在單一發射、循序執行的典型五階段 MIPS 管線處理器中執行，管線階段依序為 IF、ID、EX、MEM 與 WB。處理器具有由 EX/MEM 與 MEM/WB 管線暫存器至 EX 階段的完整資料轉傳路徑，且 lw 指令載入的資料須至 MEM 階段結束後才能使用。請找出程式中可能發生的資料危障（Data Hazard），指出具有 RAW 資料相依關係的指令及相依暫存器，並說明那些危障可透過資料轉傳解決，以及那些載入使用危障（Load-use Hazard）仍須插入停頓週期（Stall Cycle）。（15 分）
思路引導 VIP
這題考 Pipeline 結構中的 RAW (Read After Write) 相依性。逐行掃描：I2用I1的結果、I3用I2的結果...。把每一對相鄰有相依的指令找出來。接著判斷 Hazard 類型。算術運算（如 addi, sll, add）結果在 EX 結束時就產生，可無縫轉傳給下一行的 EX。但是 lw 的資料必須到 MEM 結束才出來，如果下一行立刻在 EX 階段就要用（Load-use hazard），即使用了轉傳也來不及，必須插入一個 Stall Cycle。將找到的相依性分類即可。