[Computer Architecture] Processor

"Processor"

[A Basic RISC-V Processor Implementation]

▣ 지원하는 명령어

· Memory 명령어 (ld, sd) / Arithmetic-Logical 명령어 (add, sub, and, or) / Conditional Branch 명령어 (beq)

▣ Processor Execution Procedure

> Step 1

· 매 Cycle마다 Processor는 Program Counter 값을 명령어 메모리에 보내고, 해당 주소에 맞는 명령어를 가져옴(Fetch)

> Step 2

· 명령어의 종류와 피연산자 필드(Ex. rs1, rs2)에 따라 하나 또는 두 개의 Register 값을 Read

> Step 3

· ALU가 명령어를 실행

→ 산술-논리 명령어 : 실제 계산을 수행 / 메모리 명령어 : 주소를 계산(덧셈) / 분기 명령어 : 비교 작업 수행(뺄셈)

> Step 4

· 산술-논리 명령어 : 결과 값을 목적지 Register에 Write

· 메모리 명령어 : 데이터 메모리에 접근하여 데이터를 Load 또는 Store

· 분기 명령어 : Test 결과에 따라 Program Counter 값을 변경 가능 (분기가 일어나지 않으면 다음 PC는 단순히 PC + 4)

[Datapath & Execution Control]

▣ Logic Design Conventions

· Combinational Logic : ALU처럼 현재 입력만 보고 바로 출력을 만드는 회로

· State Element(= Sequential Logic) : Register/Memory처럼 값을 저장하는 회로 (현재 입력 뿐만 아니라 이전 상태를 보유)

▣ Clocks

· Edge-Triggered : 신호 Update는 오직 Clock의 Edge(상승/하강)에서만 발생

· Synchronous System : 입력 신호는 다음 Clock Edge가 오기 전에 안정적인 값에 도달해야 Timing 오류를 피할 수 있음

→ 한 Clock Cycle 내에는 오직 하나의 상태 전이만 허용(상태 전이가 여러 번 일어나면 Race Condition 발생)

▣ Control Signal & Data Bus

· Control Signal : 특정 요소의 동작을 선택하거나 지시 (활성화 : 1 / 비활성화 : 0)

· Data Bus : 여러 Bit로 구성된 신호나 데이터를 함께 실어 나르는 Wire들의 묶음 (Ex. 64-bit Data Bus, Control Bus)

▣ Instruction Fetch

· Instruction Memory : Program Code를 저장하며, Processor는 이곳에서 Read 전용으로만 접근

· Program Counter : 현재 실행 중인 명령어의 주소를 담고 있는 64-bit Register

· Adder : Branch가 발생하지 않는 한, Program Counter 값을 4씩 증가시켜 다음 명령어의 주소를 가리킴

→ 위 3가지 요소로 구성

▣ Register File

· 32개의 RISC-V Register는 "Register File"이라는 데이터 구조로 조직

· Multi-Ported : 한 Cycle 내에 여러 Register에 접근할 수 있도록 Read Port 2개와 Write Port 1개를 보유

→ 한 Cycle에 2개의 Register 값 Read & 1개의 Register 값 Write

· Read : MUX를 사용하여 입력된 Register(rs1 #, rs2 #)에 해당하는 데이터를 선택하여 출력

· Write : Decoder를 사용하여 데이터를 저장할 특정 Register(rd #)를 활성화

▣ ALU Execution

· R-Type : Register File에서 2개의 Source Register(rs)를 읽어 ALU에서 연산

· I/S-Type : 12-bit Immediate 값을 64-bit로 확장하여 ALU에 공급

· SB-Type : 상단 Adder : PC와 주소 Offset을 더해 Branch 목적지 주소를 계산 / 하단 ALU : Branch 조건이 충족되었는지 Test

▣ Data Memory Access

· ALU가 Base Register 값과 Immediate Offset을 더해 메모리 주소를 계산

· ld(Load) : 데이터 메모리에서 읽은 값을 Register(rd)에 저장

· sd(Store) : Register(rs2)에 있는 데이터를 계산된 메모리 주소에 저장

· MUX : Register에 Write 할 데이터가 ALU 결과인지, 메모리에서 읽어온 값인지 선택

▣ Instruction Decode

· 명령어의 Bit Filed를 분석하여 종류를 파악

▣ ALU Control Signal

· 명령어를 ALU가 이해할 수 있는 제어 신호로 변환

· 00 : Load/Store(Add) / 01 : Branch(Sub & Test) / 10 : R-Type(Func3, 7을 추가로 보고 결정)

→ 최종 제어 신호 : ALUop와 Func Filed를 조합하여 실제 ALU 동작을 결정하는 4-bit 신호 생성

▣ Main Control Unit

· 각 명령어 Type에 따라 어떤 HW 부품을 활성화할지 결정

> R-Type (add/sub/and/or)

  · ALU 결과를 Register에 Wirte → RegWrite = 1

  · Immediate 값 사용 X → ALUsrc = 0

  · 메모리 접근 X → MemRead = 0 & MemWrite = 0

  · ALU 결과를 Register에 Write → MemtoReg = 0

> I-Type (ld)

  · Memory에서 Read한 것을 Register에 Wirte → RegWrite = 1

  · Immediate 값 사용 O → ALUsrc = 1

  · Memory에서 Read → MemRead = 1 & MemWrite = 0

  · Memory에서 Read한 것을 Register에 Write → MemtoReg = 1

> S-Type (sd)

  · Register 값을 Memory에 Write → RegWrite = 0

  · Immediate 값 사용 O → ALUsrc = 1

  · Memory에 Write → MemRead = 0 & MemWrite = 1

  · Register에 Write X → MemtoReg = X

> SB-Type (beq)

  · Branch 명령어 → Branch = 1 (조건 T/F와 상관 X)

▣ Single-Cycle Execution

· 각 명령어가 Processor의 모든 자원을 독점적으로 사용

△ 구조가 단순 (한 명령어가 실행되는 동안 모든 HW 자원을 독점적으로 사용하므로 제어가 비교적 쉬움)

▼ Processor의 Clock 속도는 가장 실행 시간이 긴 명령어로 설정

    → 부동 소수점 곱셈 또는 나눗셈처럼 복잡하고 오래 걸리는 명령어가 추가될 경우, 전체 시스템의 Clock 속도가 매우 느림

[Pipelining]

· 각 명령어를 {IF / ID / EX / MEM / WB} 단계로 나누고, 서로 다른 명령어가 서로 다른 단계를 동시에 사용

· Single-Cycle : 한 명령어 전체가 한 Cycle 안에 끝나야 하므로, Clock 주기는 가장 느린 명령어 전체 실행 시간보다 길어야 됨

· Pipeline : 한 Cycle에 한 Stage만 진행하므로, Clock 주기는 가장 느린 Pipeline Stage보다 길면 됨

<각 HW 요소의 Latency 예시>

<ld 명령어 3개 실행>

· Single-Cycle : 가장 느린 ld에 맞춰 800ps Clock을 사용하며, 총 2400ps 소요

· Pipeline : 가장 느린 단계인 200ps를 Clock 주기로 사용하며, 명령어들이 겹쳐서 실행되어 총 1400ps 소요

△ Pipeline 시 빨라지는 것이 아니라 Throughput(처리량) 증가 (∵ 동시에 여러 명령어 처리 → 노는 HW 존재 X)

△ 한 Cycle에 한 Stage만 진행하므로, Clock 주기 감소 가능

▼ Hazard 발생으로 인한 Stall 발생

▼ 개별 명령어 Latency 반드시 감소 X

    → Pipeline 단계 간의 균형이 맞지 않으면, 개별 명령어 하나가 실행되는 시간이 Single-Cycle보다 길어질 수 있음

∴ 모든 Pipeline Stage가 완벽하게 균형을 이룰 때 최대 성능

▣ RISC-V Processor Pipeline

· IF(Instruction Fetch) : 메모리에서 명령어를 가져옴

· ID(Instruction Decode) : 명령어를 해석하고 Register를 Read

· EX(Execution) : ALU 연산 수행

· MEM(Memory Access) : 데이터 메모리 접근

· WB(Write Back) : 결과값을 Register에 Write

▣ Pipeline Datapath

· Processor를 5단계로 나누면 최대 5개의 명령어가 각기 다른 단계에서 동시에 실행

· Data Flow : 왼쪽에서 오른쪽으로 진행

        ** 예외 : WB 단계에서 Register File에 값을 Write / Branch 결과로 PC 값을 변경 → 데이터가 오른쪽에서 왼쪽으로 진행

<add>

· 왼쪽 : Write / 오른쪽 : Read (add 명령어는 데이터 메모리를 사용하지 않으므로 MEM 단계에서 우회)

▣ Pipeline Execution

<Pipeline Execution>

<Pipeline Register(Flip-Flops)>

· 이웃한 단계들을 연결하며, 매 Clock Cycle마다 명령어가 다음 Register로 이동 {IF/ID, ID/EX, EX/MEM, MEM/WB}

> IF(Instruction Fetch) Stage

· PC 주소를 사용하여 명령어 메모리에서 명령어 Read

· PC에 4를 더해 다음 PC 계산

· 현재 PC 값은 나중에 Branch 등을 위해 명령어와 함께 다음 단계로 계속 전달

> ID(Instruction Decode) Stage

· 명령어를 해석하고 Register File에서 2개의 Source Register(rs1, rs2)를 읽고, 1개의 12-bit Immediate Filed를 부호 확장

· 명령어 Type에 상관없이 2개의 Source Register와 1개의 12-bit Immediate 값을 미리 준비하여 제어 Logic을 단순화

> EX(Execution) Stage

· 명령어 Type에 따라 ALU 연산 수행

· MUX가 연산에 필요한 피연산자를 선택하며, 결과 값은 EX/MEM Register로 전달

> MEM(Memory) Stage - Store

· EX 단계에서 계산된 주소에 Register에서 읽어온 데이터를 Write

· 저장할 데이터는 Register File(ID Stage)에서 읽혀 ID/EX, EX/MEM Register를 거쳐 전달

> MEM(Memory) Stage - Load

· EX 단계에서 계산된 주소를 사용하여 메모리에서 데이터를 Read

· 읽어온 데이터는 WB 단계를 위해 MEM/WB Register로 전달

> WB(Write Back) Stage

· WB Stage 앞 MUX를 통해 {ALU 결과, Memory Read Data} 중 선택하여 Register File에 Write

· WB Stage에서 결과를 Register File에 Write하려면 데이터를 어디에 Write 할지 rd 정보 필요

    → 이때 IF/ID Register는 이미 다른 새로운 명령어의 정보로 덮어씌워진 상태

∴ 명령어의 목적지 Register 번호(rd)를 데이터와 함께 Pipeline Register를 통해 끝까지 전달

<"ld" Instruction Datapath>

① IF에서 Instruction Memory를 Read

② ID에서 Register File의 Base Register를 읽고 Immediate를 부호 확장

③ EX에서 Base Register + Immediate로 메모리 주소를 계산

④ MEM에서 Data Memory를 Read

⑤ WB에서 읽어 온 데이터를 목적지 Register에 Write

→ Register File은 ID에서 Read, WB에서 Write

▣ Pipeline Diagram

<Single-Cycle Pipeline Diagram>

· 가장 오른쪽에 있는 명령어가 가장 먼저 들어온 명령어

<Multi-Cycle Pipeline Diagram>

▣ Pipeline Control Signal

· 데이터뿐만 아니라 제어 신호도 Pipeline화 되어야 함

→ 각 단계에서 필요한 제어 신호들을 묶음으로 만들고, 명령어가 전진할 때 이 신호 묶음도 Pipeline Register에 담겨 함께 이동

> IF Stage

· PC와 명령어 메모리를 매 Clock마다 Read → 특별한 제어 신호 없이 매 Cycle마다 다음 동작 수행

① PC가 명령어 메모리에 주소를 전송

② 명령어 메모리가 명령어 출력

③ Adder가 PC + 4 계산

④ 결과를 IF/ID Pipeline Register로 전송

** Branch 또는 Stall이 있으면 PC 갱신 방식이 달라질 수 있지만, 기본 IF 동작 자체는 항상 반복

> ID Stage

· Register File을 읽고 Immediate 값을 부호 확장 & Control Unit이 명령어 Opcode를 보고 Control Signal 생성

→ 생성된 Control Signal은 크게 EX, MEM, WB 단계에서 사용되며 ID/EX Pipeline Register에 저장되어 다음 단계로 이동

    (EX용 신호 : ALUSrc, ALUOp / MEM용 신호 : MemRead, MemWrite, Branch / WB용 신호 : RegWrite, MemtoReg)

> EX Stage

· ID/EX Register에 저장되어 온 Control Signal과 명령어 정보가 사용

· ALU Control은 ALUOp, Func3, Func7 등을 바탕으로 실제 ALU 연산을 결정

→ EX 단계의 결과인 ALU Output과 남은 Control Signal(M, WB)은 EX/MEM Register로 전달

> MEM Stage

· Memory 관련 Control Signal 사용

· ld : MemRead가 Asserted 되어 Data Memory에서 값을 Read

· sd : MemWrite가 Asserted 되어 Data Memory에 값을 Write

· Branch 명령어의 경우 이 단계에서 Branch 결과가 반영될 수 있음(Ex. PC를 Branch Target으로 바꿀지 결정)

→ MEM 단계가 끝나면 Memory Read Data, ALU Result, Control Signal들이 MEM/WB Register로 이동

> WB Stage

· Register에 결과 Write 여부와 데이터 소스를 결정

· RegWrite : Register File에 값을 Write 할지 결정 (0 : Write X / 1 : Write O)

· MemtoReg : 어떤 값을 Write 할지 선택 (0 : ALU 결과 / 1 : Memory Read Data)

→ 목적지 Register를 지정하기 위해 rd가 Register File로 전달

[Pipeline Hazard]

· Pipeline에서 어떤 명령어가 원래 실행되어야 할 Cycle에 제대로 실행되지 못하는 상황 → Pipeline = Stall

· Stall로 인해 비어 있는 단계는 보통 Bubble로 표현

▣ Structural Hazard

· HW 구조상 동시에 필요한 자원을 제공할 수 없을 때 발생

> 메모리 충돌

- 만약 명령어 메모리와 데이터 메모리가 분리되어 있지 않고 하나라면, 명령어 Fetch와 데이터 접근이 동시에 일어날 때 충동 발생

> 연산기 충동

- ALU가 한 번에 하나의 명령어만 처리할 수 있는데, 실행 시간이 매우 긴 연산이 자원을 점유하고 있으면 후속 명령어가 멈춰야 함

∴ HW 자원을 늘리는 것이 해결책 (Ex. Instruction/Data Memory 분리, ALU 여러 개 설치, Buffer 추가) → 비용 증가

▣ Data Hazard

· 필요한 데이터가 아직 준비되지 않아서 발생

· and, or, add, sd 명령어들은 "x2"를 Source Operand로 사용 → But, sub 명령어에서 Cycle 5에 계산이 완료된 값을 "x2"에 Write

∴ and, or : "x2"의 Old Value 사용 / add, sd : "x2"의 New Value 사용

> Data 의존성 감지 Logic

· ID/EX.rs1 == EX/MEM.rd

· ID/EX.rs2 == EX/MEM.rd

· ID/EX.rs1 == MEM/WB.rd

· ID/EX.rs2 == MEM/WB.rd

→ 현재 명령어가 읽으려는 Source Register가 앞선 명령어가 쓰려는 Destination Register와 같으면 의존성 존재

** "x0"은 항상 0으로 고정되어 있고, 실제로 값이 바뀌지 않으므로 Hazard 생성 X

** 모든 명령어가 Register에 Write X (Ex. sd, beq) → 의존성 판단 시 RegWrite가 1인지도 확인 필요

· and : ID/EX.rs1 == EX/MEM.rd (3 Cycle)

· or : ID/EX.rs2 == MEM/WB.rd (4 Cycle)

 - Data Hazard 해결책 1 - Pipeline Stall

· 필요한 데이터가 준비될 때까지 명령어를 ID 단계에 묶어두고 다음 단계로 진행 X

→ 정확성 보장, But, Stall하는 동안 Pipeline Throughput 감소로 인한 성능 저하

** Nop(No Operation) : Stall을 구현하기 위해 Control Unit은 해당 위치에 "nop" 주입 → Diagram에서 Bubble로 표현

 - Data Hazard 해결책 2 - Data Forwarding(= Bypassing)

· Stall만 사용하면 성능 손실 발생

· 결과가 Register File에 WB될 때까지 기다리지 않고, 결과가 만들어지는 즉시 필요한 곳으로 직접 전달

→ Pipeline을 Stall 하지 않고도 의존성 문제 해결 가능

> Data Forwarding 구현

<Data Forwarding 구현>

· ALU 입력 앞에 MUX를 추가하여, ALU 입력으로 사용할 값을 선택

· ID/EX에서 온 원래 Register 값

· EX/MEM에서 온 직전 명령어의 ALU 결과
· MEM/WB에서 온 더 이전 명령어의 결과 또는 Memory Read Data

> Forwarding Unit의 제어 신호

<Forwarding Unit의 제어 신호>

· ALU의 1번째 입력 : ForwardA / ALU의 2번째 입력 : ForwardB

· 00 : rs 값은 원래대로 ID/EX Register 값 사용

· 01 : EX/MEM Register의 이전 ALU 결과 값 사용
· 10 : MEM/WB Register의 더 이전 결과 값 사용

> Data Forwarding을 위한 HW

· 비교 회로 + MUX + Control Signal 전달 HW 필요

> Double Data Hazard

· 3번째 add의 "x1" : 1번째 add 결과 X / 2번째 add 결과 O → 가장 최근에 계산된 값을 Forwarding

> Immediate Operand

· I-Type/Load/Store의 2번째 ALU 입력 : rs2 X / Immediate O

① Forwarding MUX가 rs2 값을 그대로 사용할지, 앞선 명령어 결과를 Forwarding할지 선택

② ALUSrc MUX가 최종적으로 2번째 ALU 입력에 Register 값을 쓸지, Immediate 값을 쓸지 선

> Load-Use Data Hazard

· Load 결과는 ALU 단계 끝에서 나오는 것이 아니라 MEM 단계 끝에서 나옴

→ 바로 다음 명령어가 EX 단계에서 "x2"를 필요로 하면, Forwarding만으로는 시간 부족

 - Load-Use Data Hazard 해결책 1 - Stall

· 바로 다음 명령어에서 사용하려면 무조건 1 Cycle Stall 필요

 - Load-Use Data Hazard 해결책 2 - Stall

· Compiler가 명령어 순서를 바꿔, 바로 다음 명령어에 독립적인 명령어가 들어간다면 Stall 필요 X

▣ Control Hazard(= Branch Hazard)

· Branch 때문에 다음 PC를 확정할 수 없어서 발생

· Branch가 결정될 때까지 Pipeline Stall / 이미 실행한 명령어를 버림

> Early Branch Decision

· Branch 목적지 주소 계산과 비교 연산을 ID Stage로 앞당김

→ Stall은 1 Cycle로 감소, But, HW 비용이 증가하고 Data Hazard 처리가 더 복잡해짐 = HW 투자 대비 효율 낮음

> Branch Prediction(= Speculation)

· 항상 "Taken" / 항상 "Not Taken"으로 가정

· Branch Predictor와 Branch Target Buffer 필요

** 다음 명령어 Fetch를 멈추지 않고 계속 진행하려면 예측이 IF Stage에서 이뤄져야 함

> Branch Predictor Mechanism

· PC 주소별로 주소 일부를 Index로 사용하여 Branch History를 저장

· "PC >> 2" : 명령어가 4-Byte 단위로 정렬되어 있어 하위 2-bit는 보통 의미 X

· 각 Table Entry에는 1-bit Counter 존재 (1 : 지난번에 Taken / 0 : 지난번에 Not Taken)

· 예측 후 실제 결과가 나오면 Table 값 Update

 - Branch Predictor가 효과적인 이유

· 반복문은 대부분의 반복에서 다시 Loop로 회귀 → 처음 예측이 틀려도, 이후에는 같은 PC의 Branch History가 업데이트 됨

· N번 실행 시 대략 "(N - 2) / N" 정도의 정확도를 얻을 수 있음

 - 1-bit Counter의 문제점

· 직전 결과만 기억함

→ Nested Loop(중첩 Loop) : Outer loop의 첫 Branch를 틀림

→ Taken/Not Taken이 번갈아 나오는 if 구문 : 결과가 매번 바뀌어 1-bit Predictor 성능↓

 - 2-bit Saturating Counter

· 4개의 상태{Not Taken / Weakly Not Taken / Weakly Taken / Taken}를 이용하여 상태가 천천히 바뀌어 예측이 크게 흔들리지 않음

> BTB(Branch Target Buffer)

· Branch Prediction은 보통 IF Stage, Branch Target 주소 계산은 보통 ID Stage에서 진행

→ Stall을 없애려면 IF Stage에서 바로 다음 PC를 알아야 함

· 과거에 실행된 Branch Instruction의 PC와 Target Address를 BTB에 저장

→ IF Stage에서 PC로 BTB를 조회하고, Branch가 Taken으로 예측되면 BTB의 Target 주소를 다음 PC로 사용

> Wrong-Path Execution

· Branch Target 주소에 해당하는 ld를 실행해야 하지만 and, or, add를 실행 = Wrong-Path Execution

> Pipeline Flush
· Wrong-Path Execution이 감지되면 잘못 가져온 명령어들을 Pipeline에서 제거 = Pipeline Flush

    → Flush 된 명령어들은 "nop"으로 변경

· 다시 올바른 주소에서 명령어를 가져와야 하므로 Processor 성능의 상당한 손실 발생

▣ ILP(Instruction-Level Parallelism)

· 병렬성을 이용해 여러 명령어를 더 빠르게 실행

> Deeper Pipeline

· Pipeline Stage를 더 잘게 나누면 더 많은 명령어를 겹쳐 실행할 수 있고, Stage 시간이 줄어 Clock Period도 감소 가능

· But, Clock Speed 향상은 전력과 발열 문제 때문에 물리적 한계 존재

> Multi-Issue Pipeline

<2-Way Issue Pipeline>

· 한 Cycle에 명령어 하나만 Issue하는 것이 아니라, 여러 개의 명령어를 동시에 Issue해서 Throughput을 향상

 - Multi-Issue Pipeline 구현

· 한 Cycle에 여러 명령어를 가져와야 함

→ Instruction Memory Datapath 확장

→ 여러 명령어가 동시에 Register File을 R/W 해야 하므로 R/W Port 증가

** Data Memory는 한 Cycle에 한 번만 접근 가능하다고 가정 → Load/Store 명령어를 동시에 여러 개 처리 제한

 - Multi-Issue Pipeline 고려사항

· 가능한 많은 명령어를 동시에 실행해야 성능 향상 가능 → HW가 2개 이상의 명령어를 처리할 수 있는데 빈 Slot이 많으면 자원 낭비

∴ ALU 같은 Backend가 쉬지 않도록 IF, ID 쪽 Frontend가 충분히 명령어를 공급해야 함

→ But, Data Hazard와 Control Hazard가 많으면 동시에 Issue할 수 있는 명령어 수 감소

 - Issue Slot & Issue Packet

· Multi-Issue Pipeline에서는 각 Cycle에 명령어들이 Issue Slot에 들어감

· 같은 Cycle에 동시에 Issue된 명령어 묶음 = Issue Packet

    (Issue Packet 사이에서 Data Hazard가 발견되면, 그 Packet 전체가 Stall될 수 있음)

· 이 방식은 여러 Operation을 하나의 큰 명령어처럼 묶어 실행하는 VLIW(Very Long Instruction Word)와 유사

 - Static Multiple Issue

· Compiler가 Compile Time에 명령어 순서를 미리 조정하는 방식

① ld : 배열 원소를 Load

② add : 값을 더해서 Update

③ sd : 다시 Store

④ addi : Pointer 감소

⑤ blt : Loop Branch 검사

· Compiler는 Stall을 줄이기 위해 독립적인 명령어를 재배치 → Load-Use Data Hazard가 남아 있어 완벽하게 2개씩 Issue 불가

∴ Dual-Issue의 Peak IPC는 2.0이지만, 위 예시에서는 IPC가 1.25(= 5/4)

> Loop Unrolling

· Loop Body를 여러 번 펼쳐서 Branch 횟수를 줄이는 Compiler 최적화

· Branch 명령어 수가 줄고, 서로 독립적인 Add/Load/Store 명령어들이 많아져 Scheduling 가능

∴ 위 예시에서는 Loop Unrolling 후 IPC가 1.75(= 14/8)

> Register Renaming

· Loop를 단순히 Unroll하면 같은 Register 이름을 반복해서 쓰는 문제 발생

· 실제로는 서로 독립적인 계산인데도, Register 이름이 같아서 의존성이 있는 것처럼 보임 (Ex. "x31")

→ Register Renaming을 통해 True Data Dependency가 아닌 Name/Anti Dependence(가짜 의존성)를 제거

> Out-of-Order Execution

· add : ld가 만든 "x31" 값이 필요하므로 대기

· sub : 앞의 ld, add와 데이터 의존성이 없어 먼저 실행 가능

→ Program 순서와 다르게 준비된 명령어부터 실행하는 방식 = Out-of-Order Execution

** Static Multi-Issue : Compiler가 Compile Time에 미리 Scheduling

    (VLIW, EPIC, Compiler Scheduling, Loop Unrolling, Static Register Renaming)

** Dynamic Multi-Issue : HW가 Runtime에 Scheduling

    (Superscalar Processor, OoO Execution, Dynamic Scheduling, HW Register Renaming, Branch Prediction)

> Superscalar Processor

· Dynamic Multi-Issue Pipeline을 구현한 Processor = 실행 중에 HW가 어떤 명령어를 동시에 실행할지 결정

· RS(Reservation Station) : 실행을 기다리는 명령어와 Operand 준비 상태를 저장 → 준비된 명령어를 골라 Out-of-Order로 실행

· ROB(Reorder Buffer) : 실행은 Out-of-Order로 하더라도 Commit/Write Back은 Program Order대로 실행

· RAT & Freelist : Architectural Register를 Physical Register로 Rename 하는 데 사용

· LSQ(Load/Store Queue) : 실행 중인 Load/Store 명령어 정보를 관리

[Reference]

· 4_processor (Computer Architecture) - William J. Song