CA 心智地圖

1.問：PC 為什麼通常加 4？

答：每條指令是一個 word = 4 bytes，Mem 是 byte-addressable。所以下一條指令的位址是 PC + 4。

2.問：Mem 裡的一個 word 是指令還是資料，由誰決定？

答：由誰去存取它決定。PC 指到它，CPU 就把它當指令執行；lw、sw 的位址指到它，就把它當資料讀寫。bit 本身不分指令和資料。

1.問：目的地 register 為什麼有時在 rd，有時在 rt？

答：軸 1 決定欄位的切法。I-type 把 rd 的位置拿去放 imm，所以目的地只能放在 rt（表頭：R-type 有 rd，I-type 沒有）。這就是第 4 章的 reg_dst mux：R-type 選 rd，I-type 選 rt。（你推出來的）

2.問：rt 什麼時候被寫，什麼時候被讀？

答：rt 被寫 ⇔ I-type 而且 LHS 是 Reg（addi、lw、lui）。其他指令的 rt 都是被讀的，包括 sw 要存的值和 beq、bne 要比較的值（表的 Reg 那一列，I-type 那一格）。（你推出來的）

3.問：四種定址從哪裡來？

答：都是「常數（軸 1）拿來做什麼（軸 2）」。表裡常數的顏色，就是這四種用法。

• addi：常數就是值，= sign_extend(imm)。
• lw、sw：常數加到 Reg[rs] 上，當作 Mem 的位址。
• beq、bne：常數是 PC 的位移，目標 = PC + 4 + sign_extend(imm) × 4（imm 以 word 為單位）。
• j、jal：26 bit 的 address 換掉 PC 的低 28 bit：{(PC + 4)[31:28], address, 00}。
• jr 沒有常數：PC = Reg[rs]。

lw、sw 的 imm 以 byte 為單位，不乘 4。

4.問：control 看哪些欄位，決定一條指令做什麼？

答：看 op；R-type 再加看 funct。兩個軸都由它們決定。

5.問：MIPS 的哪些設計，各對應 P&H 的哪一條設計原則？

答：

• Simplicity favors regularity：三種格式都是 32 bit，op 都在 [31:26]，rs、rt 在 R-type 和 I-type 的位置也一樣。所以 control 看 op 就知道格式，Reg 可以先讀 rs、rt，不用等解碼完。
• Smaller is faster：Reg 只有 32 個 register，所以一個 cycle 內讀得完。memory 階層（memory hierarchy，第 7 章）越往下越大，也越慢。所以資料放在小而快的 register 裡，少碰大而慢的 memory。
• Make the common case fast：常數很常見，所以直接放進 16-bit immediate（addi、lw、sw 都用這個欄位），不用另外 load。branch 只做最常見的 beq、bne。
• Good design demands good compromise：每種指令都想要更多 bit，但總長固定 32 bit。所以 immediate 只有 16 bit，大常數用 lui（load upper immediate）+ ori（or immediate）分兩步。j 的 address 只有 26 bit，高 4 bit 抄 PC。三種格式本身也是妥協。

6.問：j 能跳到任何位址嗎？

答：不能。j 只換低 28 bit，高 4 bit 照抄 PC。memory 依位址的高 4 bit 切成 16 塊，每塊 256 MB。所以 j 只能跳到同一塊裡。P&H 抄的其實是 PC + 4 的高 4 bit；只在 256 MB 的邊界上才有差別。

7.問：追蹤一段組合語言時，寫進 $0 的值、剛 sw 進 Mem 的值，之後會讀到什麼？

答：$0 永遠是 0，寫進去的值會被丟掉。sw 之後再 lw 同一個位址，會讀到剛寫進去的值。因為每條指令都是一次狀態轉移（第 0 章），sw 已經改了 Mem。

1.問：n-bit 二補數能表示哪些整數？

答：−2^(n−1) ~ 2^(n−1) − 1，負的比正的多一個。例：16 bit 的 0xFFFC，最高位 bit 是 1，所以是負數。絕對值 = 0x10000 − 0xFFFC = 4，值是 −4。P&H §2.4 用 32 bit 的同一個數當例子。

2.問：單精度的 fraction 欄位只有 23 bit。有效位數為什麼是 24 bit？

答：normalized 數的開頭一定是 1，所以不存。這個不存的 1 是 hidden bit。所以有效位數比 fraction 欄位多 1 bit。

3.問：exponent 欄位為什麼存「實際指數 + bias」？

答：這樣負的指數也能用無號數存。例：0x3F80_0000 = 1.0（exponent 欄位 127，實際指數 0）。normalized scientific notation 寫的是實際指數。寫回 32 bit 時，exponent 欄位才是實際指數 + bias。兩個不要混在一起。

4.問：exponent 欄位有 E bit 時，normalized 數的實際指數最大是多少？

答：exponent 欄位全 0 和全 1 保留給特殊值。所以 normalized 的實際指數是 1 − bias 到 bias，最大實際指數 = bias = 2^(E−1) − 1。要表示到 2^k，就要 2^(E−1) − 1 ≥ k。

5.問：浮點加法怎麼做？誤差從哪裡來？

答：三步：對齊、相加、normalize。對齊時，實際指數小的那個 mantissa 往右移。右移時，數學上的值沒有變。IEEE 754 規定先用無限精度算完，最後只 round 一次。所以誤差只來自最後那次 round。guard、round、sticky bit 是硬體多留的 3 個 bit，讓結果和「最後只 round 一次」一樣。

6.問：exponent 欄位 = 0 時（denormal），0 附近為什麼沒有空洞？最小正 denormal 是多少？

答：denormal 的 hidden bit 變 0，實際指數 = 1 − bias。這個指數和最小 normalized 數的實際指數一樣。所以 denormal 的間距和最小 normalized 那一段的間距相同。fraction 欄位最小的非 0 值是 2^−(fraction 欄位的 bit 數)，所以最小正 denormal = 2^−(fraction 欄位的 bit 數) × 2^(1 − bias)。bias 要用這個格式自己的，不一定是 127。

1.問：這個 1-bit ALU 只有 AND、OR、adder 三個結果。它還能做哪些運算？

答：

• SUB：b_negate = 1，carry_in = 1，所以算的是 a + ¬b + 1 = a − b。這就是二補數的「取反加一」（第 2 章）。
• NOR、NAND 靠 De Morgan's laws：¬a·¬b = ¬(a + b)，¬a + ¬b = ¬(a·b)。NOT 是兩個輸入接同一個數的 NOR。
• XOR 做不到。XOR = a·¬b + ¬a·b，要兩個乘積項再 OR。這個 ALU 每個 bit 只能選一個 gate 的結果，不能再把兩個結果接起來。

2.問：pᵢ 要用 OR 還是 XOR 定義？

答：兩種都讓 cᵢ₊₁ = gᵢ + pᵢ·cᵢ 成立。差別在 gᵢ = 1（aᵢ = bᵢ = 1）時：用 OR 定義，pᵢ = 1；用 XOR 定義，pᵢ = 0。所以題目給 pᵢ = 0、gᵢ = 1 時，只能是 XOR 定義。

3.問：ripple carry adder 為什麼慢？CLA 怎麼變快？代價是什麼？

答：ripple carry adder 的遞迴式，每一位都要等前一位的 carry。CLA 把遞迴式展開，每個 carry 兩層 gate（先 AND，再 OR）就算完。代價是 gate 的 fan-in（輸入個數）隨位數變大。所以切成 4-bit block，再用 block 的 P、G 算 block 之間的 carry（cascaded CLA）。

你推出來的：「ripple = 乖乖算遞迴；CLA = 展開轉移式；cascaded = 給轉移式加底標」

4.問：一個 carry 的 gate delay 怎麼算？

答：gate delay 就是最長路徑。D[x] 是 x 的延遲（幾個 gate delay）。從 c₀ 開始，用圖左下的式子逐位取 max。ripple carry adder 得到 D[cᵢ] = 1 + 2i。cascaded CLA 把 block 的 G、P 先算好當常數，只累加 block 之間的 carry。起算點有兩種慣例：pᵢ、gᵢ 算 1 層，或從 pᵢ、gᵢ 就緒才開始算。

5.問：carry save adder（CSA）為什麼不管幾 bit，都只要 1 個 full adder（FA）的延遲？

答：CSA 是 3:2 compressor：輸入 3 個數，輸出 2 個數（sum 和 carry），兩邊的和相同：a + b + c = sum + (carry << 1)。這裡的 c 是第三個數，不是 carry。carry 不傳給左邊那一位，而是左移 1 位，當成另一個輸出。所以每一位各自算，不用等別的位。

6.問：Wallace tree 為什麼是 minimum delay？要幾層 CSA？

答：Wallace tree 每一層把數 3 個一組送進 CSA，每組輸出 2 個，直到剩 2 個。最後用一個 carry propagate adder（CPA，例如 CLA）把 2 個數加起來。CSA 只能 3 → 2，不能 2 → 1。2 → 1 就是 carry 傳播。這一步一定要做，所以放到最後，只做一次。樹裡每層只有 1 個 FA 的延遲。層數 L 的下限：(數的個數) × (2/3)^L ≤ 2。圖右下畫的是 16 個 partial product 的例子。

1.問：datapath 為什麼有 7 個 control signal？轉移式要背嗎？

答：datapath 是合併出來的。同一個位置，不同指令送進的值不一樣 ⇒ 放 mux；有的指令不寫某個 state ⇒ 那個 state 加 write enable。7 個 control signal 就是 4 個 mux 和 3 個 enable（步驟 2 的表）。所以轉移式不用背，只要記得每類指令做什麼。

2.問：為什麼只有一個 alu，前面還要放 alu_src mux？

答：每類指令都剛好用一次 alu：add 算結果，addi 算加法，lw、sw 算位址，beq 相減看 zero。所以只有一個 alu。它的第二個輸入，add、beq 用 read_data_2，addi、lw、sw 用 imm32，所以前面放 alu_src mux。

3.問：給一條指令，怎麼推出它的 control signal？

答：

1. 寫出這條指令那一列（步驟 1 的表）。
2. mux 的選擇訊號：要送出哪個輸入，就填它的編號。
3. mux 的選擇訊號是 X（don't care）⇔ 這個 mux 的輸出沒有寫進任何 state。
4. write enable、read enable 只能填 0 或 1。

例：reg_write = 0 ⇒ write_reg 和 write_data 都沒有寫進 Reg ⇒ reg_dst = X，mem_to_reg = X。

4.問：不是 load 的指令，mem_read 為什麼填 0，不填 X？

答：mem_read 是 read enable，只能填 0 或 1（定理 3）。Mem 的資料 port 其實是 L1 D-cache（第 7 章）。用沒有意義的位址去讀，可能 cache miss，也可能 page fault。所以只有 load 是 1，其他指令填 0。

5.問：圖上的 datapath 能執行 bne 嗎？

答：不能直接執行。圖上的 pc_src = branch & zero 是給 beq 用的：beq 在 zero = 1 時跳。bne 要在 zero = 0 時跳，要多一條 control 的 wire（例如 branch_ne），讓 pc_src = branch_ne & ~zero。所以推 bne 的 pc_src 時，要看這次跳不跳，不能照抄圖上的 &。

6.問：怎麼把 j 合併進 datapath？

答：下一個 PC 多一種值 jump_target = {pc_plus_4[31:28], inst[25:0], 00}，只要接線，不用 adder。在 pc_src mux 後面再加一個 mux（jump mux）：next_pc = jump ? jump_target : (pc_src ? branch_target : pc_plus_4)。control 多送出 jump。加了 j 以後，pc_src = X ⇔ jump = 1。

1.問：pipeline 裡的 state，都在同一個 clock edge 寫入嗎？

答：pipeline register 也是 state。所有 state 接同一個 clock，在同一個 clock edge 寫入。Reg 例外：它在 cycle 中間寫入（前半寫、後半讀），用的還是同一個 clock。

你問過：「這裏的 state 都是同一個 clock domain 嗎？」

2.問：clock cycle time 怎麼算？

答：clock cycle time = 所有 Time 裡最大的那個。single-cycle 只有一段 ⇒ 各 stage 的時間相加。pipeline 有 5 段 ⇒ 每段 = logic + t_reg，取最大的。

你在 0007 的定義：「Time(x): x 穩定之後，要花多少時間才會使後續所有 signal 穩定」

3.問：register 存資料要的時間（t_reg），要加在哪裡？

答：t_reg 是 setup time + clock-to-Q。pipeline 的每一段都要加：可以當成每個 pipeline register 前面多了一段 logic。single-cycle 沒有 pipeline register；題目只給 pipeline register 的時間時，single-cycle 不加。

你問：「5ps store data 應該是 pipeline register 内部，當成在 register 前面多了一個 logic 需要 5ps 才能穩定?」

4.問：pipeline 有 5 個 stage。throughput 會變成 5 倍嗎？一條指令會變快嗎？

答：throughput 不到 5 倍：5 個 stage 的長度不同，cycle 要配合最長的一段；每段還要加 t_reg。一條指令不會變快：latency = 5 × clock cycle time，而 5 × 最長的一段 ≥ 5 段相加 = single-cycle 的 latency。pipeline 讓 throughput 變大，單一條指令反而變慢。例（圖上 P&H 的數字）：single-cycle 的 cycle 是 800 ps，pipeline 是 200 ps + t_reg，所以 throughput 不到 4 倍；latency 是 5 × (200 ps + t_reg)，比 800 ps 長。

5.問：一個 state 在哪個 stage 寫入？

答：pipeline register 在它左邊那個 stage 結束時寫入，例如 EX_MEM 在 EX 結束時寫入。一個 state 的新值，在轉移式 RHS 用到的值全部到齊的第一個 stage 算出來，那個 stage 結束時寫入。所以上面那張 stage 的表不用背。

6.問：beq 在哪個 stage 決定跳不跳？

答：MEM。ID_EX.A == ID_EX.B 由 EX 的 alu 比較。Zero 和 ALUOut1 都在 EX 結束時才寫進 EX_MEM，所以 MEM 才拿得到，MEM 結束時寫入 PC。把比較器和 adder 移到 ID，branch 就能在 ID 結束時決定（第 6 章的 control hazard）。

1.問：沒有 forwarding 時，一個 dependency 要插幾個 no-op？

答：值在 WB 寫進 Reg，後一條指令在 ID 讀；internal forwarding 讓同一個 clock 也可以。所以兩條指令相鄰插 2 個，中間隔一條插 1 個，隔兩條以上不用插。

2.問：有 forwarding 時，哪些 dependency 不用 stall？

答：前提：後一條指令在 EX 用這個值。前一條是 R-type：值在 EX 求出，所以任何距離都不用 stall。相鄰的靠 EX → EX；隔一條的靠 MEM → EX；隔兩條以上的靠 internal forwarding 從 Reg 讀。前一條是 lw、中間至少隔一條：隔一條的靠 MEM → EX，也不用 stall。

3.問：有 forwarding，就能避開所有 data hazard 嗎？

答：不能。下一條指令在 EX 要用 lw 的值時，下一條的 EX 和 lw 的 MEM 在同一個 cycle，所以一定要 stall 1 個 cycle。P&H 叫這種 hazard load-use data hazard。例外：下一條是 sw，而且 lw 的值是 sw 要存的值（rt），這個值在 MEM 才用到。但 P&H 的 hazard detection unit 不分這種情況，照樣 stall。考題問「avoid all data hazards」，意思是一個 stall 都不用插。

4.問：branch 在 MEM 決定時，損失幾個 cycle？移到 ID 呢？

答：在 MEM 決定，損失 3 個：beq 在 cycle 1 做 IF，cycle 4 結束時才寫入 PC，所以下一條最早在 cycle 5 做 IF，本來是 cycle 2。移到 ID，損失 1 個：PC 在 cycle 2 結束時寫入，下一條在 cycle 3 做 IF。

5.問：猜錯時，為什麼 flush 就能讓結果和第 0 章一樣？

答：在 MEM 決定時，拿錯的指令最遠只到 EX，還沒到 MEM（寫 Mem）和 WB（寫 Reg）。把它們的 Ctl 清成 0，它們就不會改 Reg 和 Mem。在 ID 決定時，拿錯的只有 IF 那 1 條。

你推出來的：「只要計算 MEM 和 WB 的時候，必須先確保是猜對的，就可以。否則就不會有任何狀態改變」

6.問：一個迴圈跑 n 圈（n ≥ 2），前 n − 1 圈跳、最後一圈不跳。穩定以後，1-bit 和 2-bit 猜法每次迴圈各猜錯幾次？

答：1-bit 錯 2 次：最後一圈（出口）錯一次，留下「不跳」，下一次迴圈的第 1 圈（入口）又錯一次。2-bit 錯 1 次：出口錯一次，但計數器在 11，出口只降到 10，還是猜跳，所以入口猜對。