循序 SEQ 實作 (Sequential SEQ Implementation)

Overview Table

4.3.1 將處理組織成六個階段 (p.420-431)

SEQ 在每個 clock cycle 完成一整條指令的所有處理。為了讓差異極大的指令共用最少硬體(硬體複製成本遠高於軟體複製),把每條指令的處理統一切成六個階段,所有指令走同一條均勻流程 (uniform flow),以最少硬體單元(單一 ALU、單一 register file)涵蓋全部指令 (p.421)。

        +--------+   +--------+   +---------+   +--------+   +------------+   +-----------+
 PC --> | Fetch  |-->| Decode |-->| Execute |-->| Memory |-->| Write back |-->| PC update |--+
        +--------+   +--------+   +---------+   +--------+   +------------+   +-----------+  |
            ^                                                                                 |
            +------------------------------ 新 PC (下一條指令) -------------------------------+

各指令的階段計算表(Figures 4.18–4.21 精華)

表中 M1[x] 表示存取位址 x 的 1 byte,M8[x] 表示存取 8 bytes;← 表示賦值,概念上由上而下依序讀(實際硬體不必嚴格循序,見 4.3.3)。

運算類指令(OPq / rrmovq / irmovq)— 結果寫回暫存器 (p.423)

記憶體存取指令(rmmovq / mrmovq)— ALU 當位址加法器 (p.425)

堆疊指令(pushq / popq)— 最難實作:同時動記憶體與 %rsp (p.425-428)

• pushq:寫入位址用 valE(先減 8 再寫)符合 Y86-64/x86-64 慣例,但 %rsp 實際更新要到 clock 上升時才發生。
• popq 讀兩份 %rsp 看似冗餘,實為讓流程與其他指令一致、提升設計均勻性 (p.425);記憶體位址用未遞增的 valA,符合「先讀記憶體、再遞增指標」的慣例。
• pushq %rsp 推入的是 %rsp 的原值(valA 在 decode 讀取,早於更新);popq %rsp 使 %rsp 得到從記憶體讀出的值(Practice 4.15/4.16)。

控制轉移指令(jXX / call / ret)— push/pop 的是 PC 值 (p.428-431)

x ? a : b 語意同 C 的條件運算式。call/ret 與 pushq/popq 極相似,只是推入/彈出的是 PC 值(valP / 返回位址)(p.430)。

4.3.2 SEQ 硬體結構 (p.432-436)

抽象視圖(Figure 4.22):PC 暫存器在左下角,資訊沿線路由下而上再繞回右側(順時針);右側回饋路徑帶回要寫入 register file 的值(valE, valM)與新 PC。所有處理在單一 clock cycle 內完成。由下而上畫圖的理由留待 pipeline 設計時說明 (p.432)。

  PC update      newPC <--------------------------+
                                                  |
  Write back     valE, valM ----------------------+  (回饋路徑)
                      ^ valM
  Memory        [ Data memory ]   <- Addr, Data
                      ^ valE
  Execute       [CC]--[ ALU ]--> Cnd    <- aluA, aluB
                      ^ valA, valB
  Decode        [ Register file ]  讀埠 A,B / 寫埠 E,M   <- srcA,srcB / dstE,dstM
                      ^ icode, ifun, rA, rB, valC, valP
  Fetch         [ Instruction memory ]  [ PC increment ]
                      ^
                    [ PC ]   (SEQ 唯一的時鐘暫存器)

各階段硬體單元 (p.432-434):

• Fetch:instruction memory(唯讀)以 PC 為位址讀出指令 + PC incrementer 產生 valP。
• Decode:register file 具兩個讀取埠 A、B,同時讀出 valA、valB。
• Execute:單一 ALU 身兼多職——整數運算、有效位址加法、%rsp ±8、「加 0」傳遞;CC 暫存器存 3 個 condition code bits,由 ALU 計算新值;Cnd 由 CC 與 ifun 算出,供 cmovXX 與 jXX 用。
• Memory:data memory 讀/寫一個 word;instruction memory 與 data memory 存取同一記憶體空間,只是用途不同。
• Write back:register file 的兩個寫入埠——E port 寫 ALU 結果 valE,M port 寫記憶體讀出值 valM。
• PC update:新 PC 從 valP / valC / valM 中選出。

繪圖慣例(Figure 4.23, p.434):白色矩形 = 時鐘暫存器(SEQ 只有 PC)、淺藍方塊 = 硬體單元(視為黑盒)、灰色圓角框 = 控制邏輯區塊(需寫 HCL 的部分)、白圈 = 線路名稱、中粗線 = 64-bit word(64 條並聯導線)、細線 = 4/8-bit、虛線 = 1-bit 控制訊號。

除了階段值之外還有四個 register ID 訊號(Figure 4.24, p.434-436):srcA(valA 來源)、srcB(valB 來源)、dstE(valE 寫入目的)、dstM(valM 寫入目的)。

4.3.3 SEQ 時序 (p.436-439)

SEQ = 組合邏輯 + 兩種記憶元件:時鐘暫存器(PC、CC)與 random access memories(register file、instruction memory、data memory)。組合邏輯不需時序控制——輸入變了輸出就跟著變;RAM 的讀取也假設如組合邏輯般運作(小型記憶體合理,大型電路可用特殊時鐘電路模擬);instruction memory 只用來讀,可直接視為組合邏輯 (p.436-437)。

只有 4 個單元需要明確時序控制,全由單一 clock 訊號觸發載入/寫入:

兩個 cycle 的執行追蹤(Figure 4.25, p.438-439;程式:irmovq×2 → addq %rdx,%rbx → je dest,初始 CC=100):

Clock  __|~~~~~~|______|~~~~~~|______
          cycle 3        cycle 4
        (1)     (2)    (3)     (4)

(1) cycle 3 開始:狀態元件 = 前一條 irmovq 更新後的值;PC=0x014 載入
    組合邏輯尚未反應
(2) cycle 3 結束:組合邏輯已依 addq 算出新值
    (新 CC=000、%rbx 新值 0x300、新 PC=0x016) — 但狀態元件仍是舊值!
(3) clock 上升 → cycle 4 開始:PC / CC / register file 同時載入新值
    組合邏輯尚未反應
(4) cycle 4 結束:je 的組合邏輯完成(ZF=0 → 不跳),新 PC=0x01f 待載入

每次 clock 由低變高,處理器就開始執行一條新指令;狀態元件整個 cycle 保持前一條指令的結果,所有狀態更新只在下一個上升沿同時發生。

4.3.4 SEQ 各階段實作(HCL 控制邏輯) (p.440-447)

HCL 常數(Figure 4.26,慣例用大寫命名):

另外 nop 幾乎不做事、只 PC+1;halt 把處理器狀態設為 HLT 而停機 (p.441)。

Fetch 階段 (p.441-442)

   icode ifun    rA  rB      valC          valP
     ^     ^      ^            ^             ^
  [icode] [ifun]  [   Align   ]        [PC increment]
     ^     ^      ^                       ^      ^
   [ Split ]   Bytes 1-9          need_regids  need_valC
     Byte 0                        (1-bit, 由 icode 算出)
     ^_____________^
   [ Instruction memory ] -- imem_error;另產生 instr_valid
             ^
           [ PC ]

• 一次從 PC 讀 10 bytes(byte 0 = 指令位元組);Split 把 byte 0 拆成 icode:ifun;若 imem_error(指令位址越界)則以 nop 的編碼取代。
• 由 icode 算三個 1-bit 訊號:instr_valid(合法指令?偵測非法指令)、need_regids(有 register specifier byte?)、need_valC(有常數字?)。instr_valid 與 imem_error 供 memory 階段產生狀態碼。
• Align 單元:need_regids=1 時 byte 1 拆成 rA:rB,否則兩者皆為 RNONE;valC 取 bytes 1–8(無 regid byte,如 jXX/call)或 bytes 2–9。
• HCL 範例:

bool need_regids =
        icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
                   IIRMOVQ, IRMMOVQ, IMRMOVQ };

• PC incrementer 公式:PC 值 p、need_regids 值 r、need_valC 值 i,則 valP = p + 1 + r + 8i(涵蓋 1/2/9/10 bytes 四種指令長度)。

Decode 與 Write-back 階段 (p.442-444)

兩階段合併實作,因為都存取 register file(四埠:讀 A/B、寫 E/M;每埠有位址線 = register ID 與 64-bit 資料線;位址為 RNONE 即不存取)。四個控制區塊依 icode、rA、rB(dstE 還需 Cnd)產生四個 register ID:

word srcA = [
        icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : rA;
        icode in { IPOPQ, IRET } : RESP;
        1 : RNONE;    # 不需讀暫存器
];

# 警告:此版尚未正確處理 conditional move
word dstE = [
        icode in { IRRMOVQ } : rB;
        icode in { IIRMOVQ, IOPQ } : rB;
        icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RESP;
        1 : RNONE;    # 不寫任何暫存器
];

(srcB、dstM 同理由各指令表歸納:srcB 對 OPq/rmmovq/mrmovq 為 rB、對 push/pop/call/ret 為 RESP;dstM 只在 mrmovq/popq 時為 rA。)

Execute 階段 (p.444-445)

ALU 對 aluA、aluB 依 alufun 執行 add / subtract / and / exclusive-or,輸出即 valE;三個控制區塊產生資料與控制訊號(Figure 4.29):

word aluA = [
        icode in { IRRMOVQ, IOPQ } : valA;
        icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ } : valC;
        icode in { ICALL, IPUSHQ } : -8;
        icode in { IRET, IPOPQ } : 8;
        # 其他指令不需要 ALU
];

word alufun = [
        icode == IOPQ : ifun;    # 只有 OPq 用 ifun 指定的運算
        1 : ALUADD;              # 其餘一律當加法器
];

bool set_cc = icode in { IOPQ };   # 只有 OPq 更新 CC

• 運算元排列 aluB 在前、aluA 在後,確保 subq 算的是 valB − valA(aluB 對 OPq/rmmovq/mrmovq 為 valB,對 push/pop/call/ret 為 valB(%rsp),對 rrmovq/irmovq 為 0)。
• ALU 每次運算都會產生 zero / sign / overflow 三訊號,但 set_cc 只在 OPq 時允許 CC 暫存器載入。
• cond 單元由 CC 與 ifun 產生 Cnd,同時供 cmovXX 的 dstE 條件化與 jXX 的 next-PC 邏輯;其他指令的 Cnd 值可能為 0 或 1 但會被控制邏輯忽略。cmovXX(icode 同 IRRMOVQ)的實作即修改 dstE:條件不成立時把目的地改為 RNONE(Practice 4.24)。

Memory 階段 (p.445-447)

兩個控制區塊選出記憶體位址與寫入資料,另外兩個產生 read / write 控制訊號;讀取結果為 valM(Figure 4.30):

word mem_addr = [
        icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ } : valE;
        icode in { IPOPQ, IRET } : valA;
        # 其他指令不需位址
];

bool mem_read = icode in { IMRMOVQ, IPOPQ, IRET };

• 位址永遠是 valE 或 valA;寫入資料永遠是 valA 或 valP(rmmovq/pushq 寫 valA,call 寫 valP;Practice 4.25);mem_write 只在 IRMMOVQ, IPUSHQ, ICALL 時為真(Practice 4.26)。
• Memory 階段還負責產生狀態碼 Stat:綜合 icode(是否 IHALT)、fetch 階段的 imem_error、instr_valid 與 data memory 的 dmem_error,輸出 SAOK / SADR / SINS / SHLT 之一(Practice 4.27, p.447)。

PC Update 階段 (p.447)

新 PC 依指令型別與分支旗標從 valC / valM / valP 選出(Figure 4.31):

word new_pc = [
        icode == ICALL : valC;          # call:目標位址
        icode == IJXX && Cnd : valC;    # 跳轉成立:目標位址
        icode == IRET : valM;           # ret:從 stack 彈出的返回位址
        1 : valP;                       # 預設:下一條循序指令
];

Surveying SEQ:為什麼還不夠? (p.447-448)

SEQ 以「均勻流程 + 少量硬體單元 + 單一 clock 控制時序」實現了完整 Y86-64 處理器;控制邏輯負責在單元間路由訊號、依指令型別與分支條件產生控制訊號。但 SEQ 唯一的問題是太慢:

• Clock 必須慢到讓訊號在一個 cycle 內傳過所有階段。以 ret 為例:讀 instruction memory → 讀 register file(%rsp)→ ALU 加 8 → 讀 data memory(返回位址)→ 才能決定新 PC——全部須在 cycle 結束前完成,cycle time 由最長路徑決定。
• 每個硬體單元只在整個 cycle 的一小段時間內活動,利用率極差。
• 解法:pipelining(提升 throughput,latency 可能微增)——見 04-Processor-Architecture/04-Pipelining-Principles。

Exam/Test Patterns

Related Notes

• 04-Processor-Architecture/01-Y86-64-ISA — SEQ 所實作的指令集、編碼與 icode/ifun 定義
• 04-Processor-Architecture/02-Logic-Design-and-HCL — 本節 HCL 控制邏輯、組合邏輯與時鐘暫存器的基礎
• 04-Processor-Architecture/04-Pipelining-Principles — 解決 SEQ 時脈過慢問題的下一步
• 04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards — 由 SEQ 演化出的管線化實作
• 03-Machine-Level-Programs/04-Procedures-and-the-Stack — call/ret 與堆疊慣例在 x86-64 的對應
• 08-Exceptional-Control-Flow/01-Exceptions — 完整處理器對例外的處理方式