Multicycle FSM

Beginner Story

Single-cycle이 모든 요리를 한 번에 끝내는 방식이라면 multicycle은 재료 준비, 조리, 포장, 전달을 순서대로 나누는 방식입니다.

FSM은 주방의 작업표입니다. 지금 Fetch인지 Decode인지, 다음에 Memory로 갈지 Writeback으로 갈지 알려 줍니다.

중간 결과는 다음 단계에서 필요하므로 `IR`, `A`, `B`, `ALUOut`, `MDR` 같은 register에 보관합니다.

Full beginner lecture

Multicycle FSM

Beginner Intuition

Multicycle FSM(Mehrtakt processor)은 instruction 하나를 여러 cycle로 나누어 실행합니다. Single-cycle에서는 lw가 한 cycle 안에 instruction fetch, register read, address calculation, memory read, writeback을 모두 끝내야 했습니다. Multicycle에서는 이 일을 작은 state로 나눕니다. 그래서 clock period를 짧게 잡고 ALU, memory 같은 hardware를 여러 cycle에서 재사용할 수 있습니다.

FSM(Finite-State Machine)은 "지금 processor가 어떤 단계에 있는가"와 "다음 cycle에 어디로 갈 것인가"를 정하는 Steuerwerk입니다. 시험에서는 state 이름을 외우는 것보다 각 state에서 무엇을 계산하고, 어떤 register가 cycle 끝에 갱신되는지를 말하는 것이 중요합니다.

FSM State Sequence Board

Common start:
S0 Fetch
  IR <- Mem[PC]
  PC <- PC + 4

S1 Decode / Register Read
  A <- Reg[rs1]
  B <- Reg[rs2]
  ImmExt <- sign-extended immediate
  next state depends on opcode

lw:
S0 -> S1 -> S2 MemAdr -> S3 MemRead -> S4 MemWB -> S0

sw:
S0 -> S1 -> S2 MemAdr -> S5 MemWrite -> S0

R-Typ:
S0 -> S1 -> S6 ExecuteR -> S7 ALUWB -> S0

beq:
S0 -> S1 -> S10 BranchCompare -> S0

jal:
S0 -> S1 -> S9 JAL/PCUpdate -> link writeback -> S0

Per-State Control Board

Temporary register를 빼먹지 마세요. IR은 instruction bits를 다음 state까지 보관합니다. A와 B는 register file에서 읽은 operand입니다. ALUOut은 ALU result를 다음 cycle에 쓰기 위해 보관합니다. MDR은 memory에서 읽은 load data를 writeback까지 보관합니다.

Worked Example 1: lw t0, 8(sp)

1. S0 Fetch: IR <- Mem[PC], PC <- PC + 4.
2. S1 Decode: A <- Reg[sp], ImmExt <- 8, rd=t0를 파악합니다.
3. S2 MemAdr: ALUOut <- A + ImmExt = Reg[sp] + 8.
4. S3 MemRead: MDR <- Mem[ALUOut].
5. S4 MemWB: Reg[t0] <- MDR.

검산: lw는 data memory read와 register writeback이 둘 다 필요하므로 5-state path가 됩니다.

Worked Example 2: sw t1, 4(s2)

1. S0 Fetch: instruction을 IR에 넣고 PC <- PC + 4.
2. S1 Decode: A <- Reg[s2], B <- Reg[t1], ImmExt <- 4.
3. S2 MemAdr: ALUOut <- Reg[s2] + 4.
4. S5 MemWrite: Mem[ALUOut] <- B, 즉 Mem[Reg[s2]+4] <- Reg[t1].

검산: t1은 address가 아니라 store data입니다. address는 s2 + 4입니다. sw에는 register writeback state가 없습니다.

Worked Example 3: Branch Cycle Count

문제: beq t0, t1, ELSE에서 t0 != t1입니다. state sequence와 PC update를 설명하세요.

S0 Fetch에서 이미 PC <- PC + 4가 됩니다. S1 Decode에서 t0, t1을 읽고 branch immediate를 준비합니다. S10 BranchCompare에서 ALU가 t0 - t1을 계산하고 Zero=0이므로 Branch AND Zero가 false입니다. 따라서 PC는 target으로 바뀌지 않고 fetch 때 준비된 다음 sequential instruction으로 진행합니다.

PC Control

Course-style 표현으로 자주 나오는 핵심은 다음입니다.

PCWrite = (Branch AND Zero) OR PCUpdate

PCUpdate는 fetch의 PC+4나 jal처럼 조건 없이 PC를 쓰는 요청입니다. Branch는 beq처럼 condition이 맞을 때만 target으로 가는 요청입니다. Branch=1이라고 PC가 무조건 바뀌는 것이 아닙니다. 반드시 Zero 같은 comparison result와 함께 봐야 합니다.

Common Mistakes

• Multicycle을 pipeline처럼 여러 instruction이 겹쳐 실행된다고 생각합니다. 여기서는 instruction 하나가 여러 state를 순서대로 지나갑니다.
• 모든 instruction이 Fetch -> Decode -> Execute -> Memory -> Writeback을 그대로 지난다고 외웁니다. sw는 writeback이 없고 beq는 memory/writeback이 없습니다.
• ALUOut, MDR, IR 같은 temporary register를 답안에서 생략합니다. cycle boundary를 넘기는 값은 보관 위치가 필요합니다.
• Single-cycle control table을 그대로 복사합니다. Multicycle에서는 state마다 control signal이 달라집니다.

Active Recall

1. lw와 sw가 갈라지는 state는 어디인가요?
2. IR, MDR, ALUOut은 각각 무엇을 보관하나요?
3. beq not taken일 때 PC가 이미 다음 instruction을 가리킬 수 있는 이유는 무엇인가요?
4. 새 instruction을 FSM에 추가할 때 먼저 확인해야 하는 세 가지는 무엇인가요? memory access, register writeback, PC update 여부를 기준으로 답해 보세요.

Source Grounding

• current:Vorlesung\Rechnerorganisation - Teil 2.pdf: Mehrtakt datapath, main FSM, lw, sw, R-Typ, beq, jal state paths.
• current:Uebung\Übung 7.pdf, current:Uebung\Lösung 7.pdf: single-cycle vs multi-cycle, datapath steps.
• current:Uebung\Übung 8.pdf, current:Uebung\Lösung 8.pdf: FSM Steuerlogik, PCWrite, Branch, PCUpdate, instruction extension.