1. 왜 멀쩡한 Decode를 두 개로 쪼갰을까? (The Problem)

기존의 단순한 순차 실행(In-order execution) 파이프라인에서는 Decode 단계에서 명령어를 해석하고 데이터를 읽어옵니다.
근데 여기서 치명적인 문제가 발생합니다. 만약 앞 명령어가 데이터를 아직 안 줘서(RAW Hazard) 뒷 명령어가 데이터를 못 읽는다면?

• 뒷 명령어는 Decode 단계에 멈춰 서서 파이프라인 전체를 꽉 막아버립니다 (Pipeline Stall). 뒤에 아무리 데이터가 준비된 착한 명령어들이 줄을 서 있어도, 맨 앞놈이 길을 막고 있으니 아무도 못 지나갑니다.

• 이 끔찍한 병목 현상을 뚫기 위해 설계자들은 기가 막힌 아이디어를 냅니다.
  "야! 당장 계산 못 하는 놈들은 일단 길막하지 말고 '대기실(Buffer)'로 빼버려! 그리고 뒤에 줄 서 있는 놈들 중에 재료(Data) 다 모인 놈들부터 먼저 계산기(ALU)로 던져!"

• 이것이 바로 Decode를 쪼갠 이유이자, 순차 실행(In-order)을 비순차 실행(Out-of-order)으로 바꾸는 마법의 시작점입니다.

---

Dynamic Scheduling (Out-of-Order Execution)

• DIVD (1번 손님): 칠면조 통구이를 주문했습니다. 요리하는 데 30분 걸립니다. (Long-running)
• ADDD (2번 손님): 1번 손님의 칠면조 고기를 조금 떼어서 샌드위치를 만들어 달라고 합니다. 당연히 1번 요리가 끝날 때까지 하염없이 기다려야 합니다. (Depends on DIVD / Data Hazard)
• SUBD (3번 손님): 그냥 콜라 한 잔 주문했습니다. 10초면 나옵니다. (Independent of both)

기존 방식 (In-order execution):
주문 들어온 순서대로만 일합니다. 1번 손님 요리(30분)가 안 끝났다고, 2번 손님이 멈춰 서서 길을 막고(Stall), 그 뒤에 있는 3번 손님(콜라)까지 30분을 꼬박 기다려야 합니다. 진짜 답답하죠?

새로운 방식 (Dynamic Scheduling / Out-of-order execution):
어차피 콜라(SUBD)는 앞사람 요리랑 아무 상관 없잖아요? 길 막고 있는 2번 손님은 옆에서 대기하라고 하고, 콜라를 주문한 3번 손님부터 먼저 빨리 처리해서 내보냅니다. 순서를 뒤죽박죽으로 섞어서 독립적인 명령어들부터 쫙쫙 뽑아내는 것, 이것이 바로 Out-of-order execution의 핵심입니다.

Splitting Instruction Decode

이런 융통성 있는 가게를 만들려다 보니, 기존의 단순한 계산대(Instruction Decode) 방식으로는 감당이 안 됩니다. 그래서 계산대 작업을 두 단계로 찢어버렸습니다(Splitting).

① 단계: Instruction Issue 또는 Dispatch

(주문받기 & 번호표 뽑기)

• 특징: 여기는 무조건 손님이 들어온 순서대로 (In-order) 처리합니다.
• 역할:
  "무슨 요리 주문하셨죠? (Determine instruction type)",
  "오븐 자리 있나요? (Check for structural hazards)"
  확인만 딱 하고, 번호표를 쥐여준 뒤 손님을 옆 대기실로 빼버립니다.
• 공대식 해석: 아직 요리 재료(Data)를 받거나 계산하지 않습니다. 명령어들을 순서대로 쭉쭉 읽어서 대기실로 밀어 넣기만 하니까 여기서 막힐 일이 없습니다.

② 대기실: Queue 또는 Buffer

(진동벨 들고 기다리는 곳)

• 명령어들이 자신의 재료(Operands)가 준비될 때까지 머무는 공간입니다. (나중에 배울 Reservation Station이 바로 여깁니다!)

③ 단계: Read Operands

(재료 들어오면 낚아채서 요리 시작)

• 특징: 여기서부터는 순서가 개판이 됩니다. (Out-of-order)
• 역할: 대기실에 앉아있는 명령어들 중에서, 앞사람 요리가 다 끝나서 자기가 쓸 재료가 방금 도착한 녀석(no data hazards)이 있으면! 그 순간 재료를 확 낚아채서(Read operands) 바로 실행 유닛(Execution)으로 튀어나갑니다.
• 공대식 해석: 늦게 들어온 명령어라도 재료가 먼저 준비되면(operands are ready) 새치기해서 먼저 실행하러 가는 겁니다.

---

Scoreboarding

방금 전 질문에서 Decode를 두 개로 쪼갰다고 했죠? 그 쪼개진 파이프라인들을 누군가 중앙에서 교통정리를 해줘야 명령어가 뒤죽박죽으로 실행되면서도 에러가 나지 않습니다. 그 거대한 '중앙 통제실' 역할을 하는 하드웨어가 바로 Scoreboarding (스코어보딩)입니다.

1. 전제 조건: 여러 개의 Functional Units (연산기)

• 배경: 비순차 실행(Out-of-order execution)을 하면 여러 명령어가 동시에 EX (실행) 단계에 진입할 수 있습니다.

• 해결: 연산기가 하나면 어차피 병목이 생기므로, 종류별로 여러 개의 연산기(Multiple functional units)를 둡니다. (예: 곱셈기 2개, 덧셈기 1개, 나눗셈기 1개, 정수 처리기 1개). 즉, 주방에 튀김기, 오븐, 화구를 여러 대 놔두는 것과 같습니다.

2. Pipeline with Scoreboarding (스코어보드 파이프라인 5단계)

기존 5단계와 이름은 비슷하지만, 내부에서 해저드(Hazards)를 검사하는 타이밍이 완전히 다릅니다. 이 타이밍이 시험 문제의 핵심입니다.

1. Fetch (명령어 가져오기)

• 메모리(Instruction cache)에서 명령어를 가져옵니다. 여기까진 평범합니다.

2. ID: Issue (명령어 발행) [WAW 검사]

• 조건 1: 명령어를 처리할 빈 연산기(Functional unit)가 있어야 합니다. (오븐이 비어있어야 함)
• 조건 2: 다른 앞선 명령어와 목적지 레지스터(Destination register)가 겹치면 안 됩니다. 즉, WAW (Write-After-Write) Hazard를 여기서 막습니다.

왜? 나중에 들어온 명령어가 먼저 계산을 끝내고 값을 덮어써 버리면, 최종적으로 쓰레기 값이 남기 때문입니다.
조건을 통과하면 명령어를 연산기로 보냅니다. 통과 못 하면 멈춥니다(Stall).

3. ID: Read Operands (재료 읽기) [RAW 검사]

• 조건: 내 명령어에 필요한 재료(Source operand)를 앞선 명령어가 쓰고 있는 중이라면(Write 할 예정이라면) 대기해야 합니다. 즉, RAW (Read-After-Write) Hazard를 여기서 기다리며 해결합니다.

• 왜? 앞사람이 계산해서 값을 넘겨줄 때까지 기다려야 정확한 값을 읽을 수 있으니까요. 재료가 다 모이면 비로소 연산기에서 실행을 시작합니다.

4. EX: Execute (실행)

• 각자의 연산기에서 열심히 계산(Compute)을 수행합니다. 연산 종류(덧셈, 나눗셈 등)에 따라 걸리는 클럭(Clock) 수가 다릅니다.

5. WB: Write Results (결과 쓰기) [WAR 검사]

• 조건: 계산이 끝났다고 바로 레지스터에 결과값을 덮어쓰면 안 됩니다! 스코어보드가 WAR (Write-After-Read) Hazard가 있는지 확인합니다.
• 왜? 내 앞 순서에 있던 어떤 명령어가 "아직 옛날 값을 못 읽어간 상태"일 수 있습니다. 내가 너무 빨리 계산을 끝내고 새 값을 덮어써 버리면(Write), 앞사람이 엉뚱한 새 값을 읽어가게(Read) 됩니다.
• 앞사람들이 옛날 값을 무사히 다 읽어갈 때까지 쓰기 작업을 멈추고 기다립니다(Stall write back). 안전해지면 값을 쓰고 스코어보드에 "나 끝났다!"라고 보고(Notifies)합니다.

스코어보딩의 치명적 한계: "포워딩(Forwarding) 금지 구역"

문제점: 현대의 파이프라인은 계산이 끝나면 그 결과값을 레지스터에 쓰기 전에, 뒤따라오는 명령어에게 공중에서 바로 던져주는 마법(Forwarding 또는 Bypassing)을 씁니다. 하지만 Scoreboard 구조에서는 이게 불가능합니다.

이유: "Operands are always read from register file"
무조건 계산이 끝나고 결과를 레지스터 파일에 완전히 기록(Write)한 뒤에만, 다음 명령어가 그 레지스터에서 값을 읽어갈 수(Read) 있습니다.

변명 (No large penalty?): 슬라이드에서는 "어차피 MEM 단계(메모리 접근) 없이 EX 끝나자마자 바로 Write 하니까 페널티가 크지 않다"라고 변명합니다.

하지만 1 Cycle 낭비: 읽기(Read)와 쓰기(Write)가 동시에 겹칠 수 없기 때문에, 앞 명령어가 결과를 쓰는 동안 뒷 명령어는 무조건 1 클럭을 멍때리며 대기(1 cycle latency)해야 합니다. (이 답답함을 해결하기 위해 나중에 토마술로 알고리즘이 등장합니다.)

2. 스코어보드의 3대 핵심 구성 요소 (Figure C.58을 읽는 법)

교수님이 외우라고 하신 그 표(Figure C.58)는 크게 3개의 구역으로 나뉩니다. 상황실 전광판이라고 상상해 보세요.

① 명령어 상태 (Instruction status)

• 역할: 현재 칩 안에 들어온 각 명령어들이 4단계(Issue, Read, Exec, Write) 중 어느 위치에 있는지 보여줍니다.
• 예시: "DIVD는 지금 요리 중(Exec), ADDD는 재료 기다리는 중(Read)"

② 연산기 상태 (Functional units status)

[가장 복잡하고 중요함 ⭐]
역할: 각 요리기구(덧셈기, 곱셈기 등)가 지금 무슨 일을 하고 있는지, 재료는 다 모였는지 감시합니다.

• Busy: 이 연산기가 지금 쓰이고 있는가? (Yes/No)
• Op: 지금 무슨 연산(덧셈, 곱셈)을 하는가?
• Fi: 결과값을 저장할 목적지 레지스터 (Destination)
• Fj, Fk: 필요한 두 개의 재료(소스) 레지스터 번호 (Sources)
• Qj, Qk: (아주 중요!) 내 재료(Fj, Fk)를 만들어 줄 앞선 연산기가 누구인지 적어놓습니다. (예: "내 첫 번째 재료는 저쪽 '곱셈기 1번'이 만들고 있어")
• Rj, Rk: 내 재료가 준비되었는지(Ready) 알려주는 깃발(플래그)입니다. (Yes면 재료 도착 완료)

③ 레지스터 결과 상태 (Register result status)

• 역할: 레지스터의 관점에서, "어떤 연산기가 내 안에 값을 채워 넣을 예정인가?"를 적어놓는 예약 장부입니다.
• 활용: 나중에 어떤 명령어가 이 레지스터 값을 읽고 싶을 때, 장부를 보고 "아, 이 값은 아직 안 들어왔고 저쪽 곱셈기가 쓰고 있는 중이구나"하고 파악하게(RAW Hazard 감지) 해줍니다.

표 이해

표의 열(Column)
- Wait until: 다음 단계로 넘어가기 위한 통과 조건 (해저드 검사)
- Bookkeeping: 조건을 통과하면, 장부(전광판)에 내 상태를 업데이트(기록)하는 행동

변수 사전(Dictionary)
- FU (Functional Unit): 지금 이 명령어가 사용하려고 배정받은 연산기 (예: Add1, Mult1)
- D (Destination): 결과를 저장할 목적지 레지스터 번호
- S1, S2 (Source): 재료로 쓸 1번, 2번 레지스터 번호
- op (Operation): 덧셈, 곱셈 등 연산의 종류
- Result[x]: x번 레지스터에 값을 써넣기로 예약한 연산기의 이름

- Busy: 이 연산기가 지금 쓰이고 있는가? (Yes/No)
- Op: 지금 무슨 연산(덧셈, 곱셈)을 하는가?
- Fi: 결과값을 저장할 목적지 레지스터 (Destination)
- Fj, Fk: 필요한 두 개의 재료(소스) 레지스터 번호 (Sources)
- Qj, Qk: (아주 중요!) 내 재료(Fj, Fk)를 만들어 줄 앞선 연산기가 누구인지 적어놓습니다. (예: "내 첫 번째 재료는 저쪽 '곱셈기 1번'이 만들고 있어")
- Rj, Rk: 내 재료가 준비되었는지 알려주는 깃발

1. Issue: Structural & WAW 방지

[Wait until (통과 조건)]

Not busy [FU] and not result [D]

• Not busy [FU]: 내가 쓰려는 연산기(FU)가 현재 아무도 안 쓰고 비어있어야 통과.
• not result [D]: 내 목적지 레지스터(D)를 다른 앞선 명령어가 쓰겠다고 예약(result)해두지 않았어야 통과. (이것이 WAW Hazard를 막는 핵심입니다.)

[Bookkeeping (장부 기록)]

조건을 통과했다면, 전광판(장부)에 내 정보를 등록합니다.

• Busy[FU] <- yes;: 이 연산기(FU)는 이제 내가 사용 중이라고 표시.
• Op[FU] <- op;: 이 연산기가 무슨 연산(op)을 할 건지 기록.
• Fi[FU] <- D;: 결과값을 저장할 목적지 레지스터(D) 기록.
• Fj[FU] <- S1;: 첫 번째 재료로 쓸 소스 레지스터(S1) 기록.
• Fk[FU] <- S2;: 두 번째 재료로 쓸 소스 레지스터(S2) 기록.
• Qj <- Result[S1];: [매우 중요] 내 첫 번째 재료(S1)를 지금 누가 만들고 있는지(Result[S1]) 확인해서 Qj에 기록. (만약 아무도 안 만들고 레지스터에 원래 값이 들어있다면 Qj는 비어있게 됨).
• Qk <- Result[S2];: 내 두 번째 재료(S2)를 지금 누가 만들고 있는지 확인해서 Qk에 기록.
• Rj <- not Qj;: Qj가 비어있다면(not), 즉 재료를 누군가 만들고 있는 중이 아니라면 내 재료는 즉시 사용 가능 상태(Ready)이므로 Rj를 Yes로 변경.
• Rk <- not Qk;: Qk가 비어있다면 내 두 번째 재료도 사용 가능 상태이므로 Rk를 Yes로 변경.
• Result[D] <- FU;: 마지막으로, 목적지 레지스터(D) 장부에 "이 접시는 나(FU)한테 예약됐음"이라고 서명.

2. Read operands: RAW 방지

목표: 엉뚱한 옛날 값을 읽는 충돌(RAW Hazard) 방지

[Wait until (통과 조건)]

Rj and Rk

• 첫 번째 재료 준비 완료 플래그(Rj)와 두 번째 플래그(Rk)가 모두 Yes가 될 때까지 무한 대기. (이것이 RAW Hazard를 막는 핵심입니다.)

[Bookkeeping (장부 기록)]

• Rj <- No; Rk <- No;: 재료를 무사히 읽어서 연산기로 가져갔으므로, 깃발을 다시 No로 초기화.
• Qj <- 0; Qk <- 0: 재료를 이미 다 받았으므로, 앞선 연산기와의 연결 고리(Q)를 지움(0).

3. Execution complete

• Wait until: Functional unit done
  • 해석: 덧셈은 2클럭, 나눗셈은 40클럭 등 각 연산기가 정해진 요리 시간을 다 채울 때까지 그냥 기다리는 단계입니다. Bookkeeping 할 것도 없습니다.

4. Write result: WAR 방지

목표: 내가 먼저 결과를 덮어써서 뒷사람이 옛날 값을 못 읽게 되는 충돌(WAR Hazard) 방지

[Wait until (통과 조건)]

• $\forall f$: 칩 안에 있는 모든 다른 연산기(f)들의 장부를 하나씩 다 뒤집니다.

• 조건 1: (Fj[f] ≠ Fi[FU] or Rj[f] = No)
  다른 연산기(f)의 첫 번째 재료(Fj)가 내가 덮어쓸 목적지(Fi)와 다르거나(≠)
  같더라도 그 녀석의 준비 깃발이 아직 No 상태(Rj = No)여야 합니다. (준비 깃발이 Yes라는 건 "읽을 준비가 끝났는데 아직 안 읽고 버티는 중"이라는 뜻이므로, 이때 내가 덮어쓰면 대참사가 일어납니다.)

• 조건 2: (Fk[f] ≠ Fi[FU] or Rk[f] = No)
  다른 연산기(f)의 두 번째 재료(Fk)에 대해서도 위와 똑같이 검사합니다.
  즉,

"내가 덮어쓸 레지스터를, 지금 누군가 읽으려고 대기(Yes)하고 있는 상태라면 절대 덮어쓰지 말고 기다려라"는 뜻입니다. (이것이 WAR Hazard 방지입니다.)

[Bookkeeping (장부 기록)]

$ \forall f (\text{if } Qj[f] = FU \text{ then } Rj[f] \leftarrow \text{Yes}) $:

• 다시 모든 장부를 뒤져서, 나(FU)를 애타게 기다리던 다음 명령어들(Qj = FU)을 찾아냅니다. 그리고 그들의 재료 준비 완료 깃발(Rj)을 Yes로 올려줍니다. ("나 끝났으니 이제 값 가져가!")

$ \forall f (\text{if } Qk[f] = FU \text{ then } Rk[f] \leftarrow \text{Yes}) $:

• 두 번째 재료로 나를 기다리던 녀석들에게도 깃발(Rk)을 올려줍니다.

Result[Fi[FU]] <- 0;: 목적지 레지스터 장부에서 내 예약 서명을 지웁니다(0).

Busy[FU] <- No: 드디어 내 연산기(FU)의 작업이 완전히 끝났으므로 다른 명령어가 쓸 수 있게 비워줍니다(No).