04. The Processor

chelseey·2024년 11월 27일

컴퓨터아키텍처

Introduction

Instruction Execution (명령어 실행)

명령어 인출:
프로그램 카운터(PC) → 명령어 메모리로 접근하여 명령어를 가져옴.
레지스터 파일 접근:
명령어에 포함된 레지스터 번호 → 레지스터 파일에 매핑하여 해당 레지스터를 읽음.
명령어 종류에 따라 작업 수행:
ALU(산술 논리 연산 장치)를 사용하여 다음을 계산:
• 산술 연산 결과.
• 메모리 참조를 위한 주소 (load/store).
• 분기(branch) 조건 비교.
데이터 메모리 접근:
load 또는 store 명령어를 처리하기 위해 데이터 메모리에 접근.
프로그램 카운터(PC) 업데이트:
분기 명령(branch)일 경우 PC가 목표 주소(target address)로 업데이트되거나, 그렇지 않으면 기본적으로 PC + 4로 증가.

CPU Overview

Multiplexers

CPU 내에서 서로 다른 데이터 경로가 같은 하드웨어 리소스를 공유해야 할 경우, 단순히 선을 연결하면 데이터 충돌이 발생하기 때문에 멀티플렉서(MUX)가 필요.

ex) 여러 입력 중 하나만 선택해서 ALU에 전달하거나, 메모리 주소를 결정할 때.

• 멀티플렉서(MUX)
: 하나의 출력을 만들기 위해 여러 입력 중 하나를 선택하는 장치.

• MUX의 사용 예시
프로그램 카운터(PC): 분기(branch) 명령 시 target address 와 PC + 4 중 하나를 선택.
ALU 입력: ALU가 처리할 두 개의 값 중 올바른 값을 선택.
데이터 메모리: load/store 명령 시 데이터 경로를 선택.

Control

Instruction Memory에서 명령어를 가져오면,
Control Unit이 명령어를 분석하여 각 신호를 설정.

• 제어 신호 :
RegWrite:
레지스터 파일에 데이터를 쓰는 동작을 활성화.
ex) 산술 연산 결과를 특정 레지스터에 저장.
MemWrite:
데이터 메모리에 쓰기 동작을 활성화.
ex) store 명령어 실행 시 사용.
MemRead:
데이터 메모리에서 읽기 동작을 활성화.
ex) load 명령어 실행 시 사용.
ALU Operation:
ALU가 어떤 연산(덧셈, 뺄셈, 논리 연산 등)을 수행해야 하는지를 결정.
ex) 산술 연산(add)이나 비교 연산(beq)을 수행할 때.
Branch:
분기 명령어(beq) 실행 시 사용.
분기 조건이 참인지 확인하고, 참이면 프로그램 카운터(PC)를 목표 주소로 업데이트.
Zero 신호:
ALU의 출력 결과가 0인지 여부를 나타냄. 분기 명령어 조건 평가에 사용.

4.2 Logic Design Conventions

Logic Design Basics

❯ 정보의 이진 표현 (Information encoded in binary)

• 디지털 회로에서 정보는 이진수(0과 1)로 표현:
Low voltage (낮은 전압) = 0
High voltage (높은 전압) = 1

• 한 비트당 한 선(one wire per bit):
각 비트는 하나의 전선으로 표현됨.
예: 8비트 데이터는 8개의 전선으로 표현.

• 멀티 비트 데이터(Multi-bit data):
여러 비트로 이루어진 데이터는 multi-wire buses를 통해 전달됨.

❯ 조합 논리 요소 (Combinational element)
: 데이터 연산을 수행하는 논리 회로.

입력에 따라 즉각적으로 출력이 결정됨.
출력 = function of input
ex) 논리 게이트(AND, OR), 덧셈기

❯ 순차 논리 요소 (State/Sequential elements)
: 정보를 저장하는 역할

순차 논리는 과거 상태를 기반으로 동작하며, 클럭 신호와 함께 작동.
클럭 신호는 순서대로 작업을 동기화하는 데 사용됨.
ex) 레지스터, 플립플롭, 메모리

Combinational Elements

AND 게이트

Y = A & B
: 입력 A와 B가 모두 1일 때 출력 Y가 1이 되는 논리 연산.

Multiplexer (MUX)

Y = S ? I1 : I0
: 선택 신호 S에 따라 I0 또는 I1 중 하나를 출력 Y로 전달.
S = 0이면 I0 선택, S = 1이면 I1 선택.

Adder (덧셈기)

Y = A + B
: 입력 A와 B의 값을 더해 출력 Y로 전달.

Arithmetic/Logic Unit (ALU)

Y = F(A, B)
: 입력 A와 B에 대해 특정 연산(산술/논리 연산)을 수행하고 결과를 출력 Y로 전달.
함수 F는 연산 종류를 정의(예: 덧셈, 뺄셈, AND, OR).

Sequential Elements

❯ Register
: 데이터를 회로 내에 저장하는 장치

클럭 신호(Clock Signal)를 사용하여 저장된 데이터를 업데이트.
저장된 데이터는 클럭 신호가 특정 조건을 만족할 때만 변경.

: 입력 D (Data) → 레지스터에 저장 → 출력 Q.
클럭 신호(Clk)가 레지스터 업데이트 타이밍을 결정.

❯ 클럭 신호(Clk)
: 레지스터가 데이터를 업데이트해야 하는 시점을 결정

에지 트리거(Edge-triggered):
레지스터는 클럭 신호가 0에서 1로 변하는 순간(Rising Edge)에 데이터를 업데이트.

: Clk 신호가 0 → 1로 변할 때만 레지스터가 입력 데이터(D)를 읽어 저장.
출력 데이터(Q)는 저장된 값으로 갱신.

❯ Register with write control

쓰기 제어(Write Control):
클럭 신호(Clk)가 활성화되더라도 쓰기 제어 입력(Write)이 1일 때만 레지스터가 값을 업데이트.

클럭 신호(Clk): 데이터를 업데이트하는 기준 타이밍.
쓰기 신호(Write): 값 저장 여부를 결정.
입력 데이터(D): 레지스터에 저장될 값.
출력 데이터(Q): 레지스터에 저장된 값.

Clocking Methodology

: 클럭 신호를 사용하여 조합 논리와 순차 논리의 상호작용을 제어하는 방식

❯ 조합 논리(Combinational Logic)
: 두 클럭 에지 사이에서 동작.
이전 상태 요소(State Element)에서 데이터를 받아 처리하고, 결과를 다음 상태 요소에 전달

: 클럭 상승 에지(0 → 1): State Element 1에서 데이터를 꺼냄.
클럭 주기 동안: 조합 논리가 데이터를 계산(덧셈, 뺄셈 등).
다음 클럭 상승 에지(0 → 1): 계산된 결과를 State Element 2에 저장.

❯ 상태 요소(State Elements)
: 데이터 저장소의 역할을 하며, 클럭 신호에 동기화되어 동작

❯ 클럭 주기(Clock Period)와 지연 시간

Longest Delay: 조합 논리를 통해 데이터가 처리되기까지 걸리는 최대 지연 시간
→ 클럭 주기는 Longest Delay을 초과할 수 없도록 설정.

Building a Datapath

Building a Datapath

Datapath
: 데이터와 주소를 처리하는 CPU의 구성 요소들로 이루어진 경로
구성 요소) Registers, ALUs, mux’s, memories

Instruction Fetch

PC → 명령어 메모리 → 명령어 읽기 → PC + 4 갱신

PC
: 현재 실행 중인 명령어의 메모리 주소를 나타냅니다.
(명령어가 메모리에서 읽히는 순간, PC는 곧바로 다음 명령어로 업데이트)

Instruction Fetch(명령어 인출) 단계
: PC에 저장된 주소(Read address)를 통해 명령어를 메모리에서 가져옴

PC 값 업데이트
: 명령어를 가져온 후, CPU는 다음 명령어를 가리키기 위해 PC 값을 업데이트(+4).

R-Format Instructions

: CPU가 산술 및 논리 연산을 수행할 때 사용되는 기본적인 명령어 형식

R-Format 명령어의 주요 단계

두 레지스터 피연산자 읽기 (Read two register operands):
명령어에 지정된 두 개의 레지스터에서 값을 읽음.
각각 Read Register 1과 Read Register 2로 나타냄.
산술/논리 연산 수행 (Perform arithmetic/logical operation):
ALU(산술 논리 연산 장치)를 사용해 읽어온 데이터를 기반으로 산술(덧셈, 뺄셈) 또는 논리(AND, OR) 연산을 수행.
ALU Operation 신호가 어떤 연산을 수행할지를 결정.
결과를 레지스터에 저장 (Write register result):
ALU 연산 결과를 Write Register로 지정된 레지스터에 저장.
저장 동작은 RegWrite 신호에 의해 제어됨.

입력:
명령어가 읽을 레지스터의 번호와 데이터를 제공.
5비트 레지스터 번호를 통해 각각 두 개의 레지스터 값을 읽어옴 (Read Register 1, Read Register 2).

출력:
레지스터에서 읽은 데이터는 Read Data 1과 Read Data 2로 ALU에 전달됨.

쓰기 동작:
Write Register와 Write Data는 결과 값을 레지스터에 쓰기 위한 입력.
(RegWrite 신호에 의해 제어)

입력:
Read Data 1과 Read Data 2가 ALU로 입력됨.
ALU Operation 신호가 어떤 연산(예: ADD, SUB, AND, OR)을 수행할지를 결정.

출력:
연산 결과는 ALU Result로 출력되며, 이후 레지스터에 저장됨.

Load/Store Instructions

: 데이터 메모리와 레지스터 간 데이터 전송을 담당

Load/Store 명령어의 주요 단계

레지스터 피연산자 읽기 (Read register operands):
명령어에 지정된 레지스터에서 기본 주소(base address)를 읽음.
주소 계산 (Calculate address using 12-bit offset):
ALU를 사용해 기본 주소와 12비트 오프셋(offset)을 더해 최종 메모리 주소를 계산.
오프셋은 부호 확장(sign-extension)을 통해 12비트에서 64비트로 변환

• 오프셋(Offset):
명령어에 포함된, 기본 주소에서 더하거나 빼는 값.
• 부호 확장:
오프셋의 가장 왼쪽 비트(부호 비트)를 복사하여 64비트를 만듦.
ex)
12비트 오프셋 0000 0000 1010 (10) → 64비트: 000...0000 0000 1010 (10)
12비트 오프셋 1111 1111 1010 (-6) → 64비트: 111...1111 1111 1010 (-6)

Load/Store 작업:
Load: 계산된 주소에서 메모리 값을 읽어 레지스터에 저장.
Store: 레지스터 값을 계산된 주소에 쓰기.

데이터 메모리(Data Memory)

입력:
Address: ALU에서 계산된 메모리 주소.
Write Data: Store 명령어에서 메모리에 저장할 데이터.

제어 신호:
MemRead: 메모리에서 데이터를 읽는 동작을 제어.
MemWrite: 메모리에 데이터를 쓰는 동작을 제어.

출력:
Read Data: Load 명령어에서 메모리에서 읽어온 데이터.

Branch Instructions

Branch 명령어의 주요 단계

레지스터 피연산자 읽기 (Read register operands):
명령어에서 지정된 두 개의 레지스터 값을 읽음.
피연산자 비교 (Compare operands):
ALU를 사용해 두 레지스터 값을 뺀 결과를 확인.
결과가 0 = 두 값이 같음, 이를 통해 branch
조건이 참인지 검사.
Zero ouput:
ALU의 결과가 0인지 나타내는 신호.
목표 주소 계산 (Calculate target address):
분기 명령어는 조건이 참일 경우 점프할 Target Address를 계산.
주소 계산 과정:
• Displacement(변위)를 부호 확장(Sign-Extend):
명령어에 포함된 변위 값을 64비트로 확장.
• 왼쪽으로 1비트 이동(Shift Left 1):
변위를 2배 크기(halfword 단위)로 변경하여 4바이트 단위 주소에 맞춤.
• 현재 PC 값에 추가(Add to PC value):
PC 값과 변위를 더해 최종 목표 주소 생성.

Branch Instructions의 데이터 경로

레지스터 값 읽기: 분기 명령어에 지정된 두 레지스터 값을 읽음.
ALU에서 비교: 두 레지스터 값을 빼서 결과가 0인지 확인.
부호 확장 및 주소 계산:
Immediate 값을 64비트로 확장한 후, 왼쪽으로 1비트 이동.
이를 현재 PC 값과 더해 분기 목표 주소를 계산.

• 분기 오프셋을 왼쪽으로 1비트 이동 : 메모리 주소가 항상 4바이트의 배수가 되도록 하여, 명령어 경계를 정확하게 맞추기 위함.

분기 조건 확인:
조건이 참이면 목표 주소로 이동하고, 거짓이면 다음 명령어로 진행.

Composing the Elements

First-Cut data path의 설계
: 데이터 경로 설계는 기본적으로 하나의 명령어를 한 클록 사이클 안에 수행할 수 있도록 함.

각 data path 요소의 역할
: 각 데이터 경로 요소들은 한 번에 하나의 기능만 수행

명령어와 데이터 메모리의 분리 필요성
: 각 요소가 하나의 작업만 수행할 수 있기 때문에, 명령어 메모리와 데이터 메모리의 분리 필요.
→ 명령어를 가져오는 작업과 데이터 접근 작업을 동시에 수행 가능.

멀티플렉서 사용 (Multiplexers)
: 데이터 경로에서 다른 명령어들이 다른 데이터 소스를 필요로 할 때 사용.

A Simple Implementation Scheme

ALU (Arithmetic Logic Unit) Control

ALU : CPU에서 산술 및 논리 연산을 수행

• ALU가 사용되는 명령어 유형

Load/Store 명령어: 덧셈(add) 연산
Branch 명령어: 뺄셈(subtract) 연산
R-Type 명령어: (AND, OR, ADD, SUBTRACT 등)

• ALU Control 신호
: ALU가 수행할 연산의 종류를 결정

ALU Control 신호는 결합 논리를 통해 생성

combination logic : 입력 값(명령어)에 따라 고정된 출력(ALU Control 신호)을 만드는 논리 회로

결합 논리 회로는 입력된
ALUOp와 Function Code를 사용해 ALU Control 신호를 생성.

ex) "ALUOp가 10이고 Function Code가 100000이면 ALU Control을 0010으로 설정."

The Main Control Unit

: Main Control Unit이 명령어로부터 제어 신호를 어떻게 유도해내는지

ALU Control 신호를 결정하는 논리 테이블

ALUOp1 = 0이고 ALUOp0 = 0인 경우: Load/Store 명령어
→ ADD (0010) 연산 수행.

ALUOp1 = 0이고 ALUOp0 = 1인 경우: Branch 명령어
→ SUBTRACT (0110) 연산 수행.

ALUOp = 10 : R-Type 명령어
→ ALUOp 값과 함께 명령어의 Funct7 및 Funct3 필드의 값이 함께 사용되어 ALU가 수행할 연산이 결정.

Performance Issues

❯ 가장 긴 지연시간이 클록 주기를 결정
Critical Path : 데이터 경로에서 가장 느리게 완료되는 부분

Instruction memory → register file → ALU → data memory → register file의
Load instruction 과정에서 가장 오랜 시간이 걸리는 작업이 clock cycle를 결정

❯ 명령어마다 서로 다른 클록 주기를 사용하는 것은 비현실적
: 하드웨어 복잡성이 크게 증가하고, 프로세서의 효율성이 떨어짐. 따라서 모든 명령어는 고정된 클록 주기를 사용하도록 설계

but 고정된 클록 주기에서는 모든 명령어가 가장 긴 지연 시간을 기준으로 동작하므로, 짧은 시간이 걸리는 명령어도 그 시간에 맞춰야 해서 비효율적.

❯ 설계 원칙 위배 (Violates design principle)
: 일반적인 상황에서 흔히 발생하는 작업을 더 빠르게 만들어야 한다는 설계 원칙을 위반

→ 성능 문제를 개선하기 위해 파이프라이닝(pipelining)을 사용

An Overview of Pipelining

Pipelining Analogy

: 병렬성(parallelism)을 통해 성능을 높이는 것

두 번째 다이어그램에서 pipelining 적용
: 작업들이 중첩(overlap)되어 실행되며, 병렬성이 생김.

• 속도 향상 계산 (Speedup Calculation)

파이프라인 단계 수 : n
각 단계에서 걸리는 시간 : 0.5n
파이프라인이 초기 단계에서 가동되기 위한 준비 시간 또는 초기 오버헤드 : +1.5

→ 대략적인 성능 향상이 4배

RISC-V Pipeline

RISC-V 파이프라인의 5단계

IF (Instruction Fetch) - 메모리에서 명령어 가져오기
ID (Instruction Decode & Register Read) - 명령어 해석 및 레지스터 읽기
EX (Execute) - 연산 또는 메모리 접근을 위한 주소 계산
MEM (Memory Access) - 메모리 접근
WB (Write Back) - 레지스터에 결과 저장

Pipeline Performance

파이프라인 성능 비교

single-cycle datapath vs. pipelined datapath 실행 성능 비교

❯ Single-cycle Datapath

: 명령어들이 순차적으로 처리되기 때문에, 전체 세 개의 명령어를 실행하는 데 2400ps가 걸림.

❯ Pipelined Datapath

: 각 명령어의 다른 단계가 동시에 실행되므로, 하드웨어 자원을 효율적으로 활용. 전체 프로그램 실행에 1400ps가 걸림.

Pipeline Speedup

If all stages are balanced → 속도 향상
: 모든 파이프라인 단계가 동일한 시간을 소비하는 경우, 이론적으로 파이프라인 성능이 최대화

If not balanced → 속도 향상 제한
: 특정 단계가 병목이 되어 다른 단계들이 기다리게 되는 상황이 생기면, 전체 파이프라인의 속도 향상 효과가 감소

파이프라인의 속도 향상은 처리율이 증가하기 때문. 지연(latency)는 줄어들지 않음.
처리율 : 단위 시간당 처리할 수 있는 명령어 수

Pipelining and ISA Design

RISC-V ISA : 파이프라이닝에 적합하게 설계

모든 명령어가 32비트:
RISC-V의 모든 명령어는 32비트로 고정되어 있기 때문에 명령어를 한 사이클 안에 쉽게 가져오고 해독 가능.
적은 수의 규칙적인 명령어 형식:
RISC-V의 명령어 형식은 일관되고 규칙적. → 명령어 해독(decoding)을 단순화하고, 레지스터를 한 단계에서 읽어낼 수 있음.
Load/Store 주소 지정 방식:
메모리에서 데이터를 가져오거나 저장할 때,
RISC-V 파이프라인에서 이 주소를 3단계(EX 단계)에서 계산하고, 4단계(MEM 단계)에서 메모리 접근을 함.
→ 이렇게 나눔으로써 각 단계에서 명령어의 특정 작업을 수행할 수 있고, 파이프라인의 각 단계를 효율적으로 활용 가능.

Hazards

: 다음 명령어가 파이프라인에 진입하는 것을 방해하는 상황

• Structural Hazard (구조적 위험)
: 필요한 자원이 동시에 사용 중이어서 문제가 발생. (자원 충돌)

• Data Hazard (데이터 위험)
: 이전 명령어가 데이터 처리를 완료하기 전에 다음 명령어가 그 데이터를 사용하려고 할 때 발생.
→ 따라서, 이전 명령어가 데이터를 완료하기 전까지 기다려야 하는 상황.

• Control Hazard (제어 위험)
: 제어 흐름(분기 명령어 등)을 결정하는 데 시간이 걸리는 경우 발생.
branch 명령어가 있는 경우, 결과가 나오기 전까지 어떤 명령어를 다음에 실행할지를 알 수 없음. → 명령어 흐름이 결정되기까지 파이프라인에서 멈추게 됨.

Structural Hazards

• RISC-V 파이프라인이 하나의 메모리만을 사용하는 경우에 구조적 위험 발생

ex) Load/Store 명령어가 데이터 접근을 필요로 하고, 동시에 명령어를 가져오는(fetch) 단계에서 같은 메모리를 사용하려고 할 때
bubble : 파이프라인이 멈추고 해당 단계에서 잠시 대기(stall)하는 현상

• 해결 방법

명령어 메모리와 데이터 메모리를 분리하여 각각의 자원이 독립적으로 사용될 수 있도록 함.
명령어 캐시와 데이터 캐시를 따로 두어 자원 충돌을 방지

Data Hazards

: 파이프라인에서 순차적으로 실행되는 명령어 간 데이터 의존성이 있을 때 발생

add x19, x0, x1
sub x2, x19, x3

두 번째 명령어(sub)는 레지스터 x19에 있는 값을 사용해야 하지만, 이 값은 첫 번째 명령어(add)에서 계산되어야 함. 따라서 sub 명령어는 실행하기 전에 여러 사이클 동안 대기(bubble) 상태에 놓이게 됨.

→ 대기 시간이 파이프라인의 성능을 저하시키고, 효율을 떨어뜨림.

Forwarding (aka Bypassing)

: 파이프라인에서 Data Hazards를 해결하기 위한 방법,
데이터가 완전히 레지스터에 저장되기 전에 다른 명령어가 바로 사용할 수 있도록 함.
→ 파이프라인에서의 bubble을 줄일 수 있음.

결과가 레지스터에 저장될 때까지 기다리지 않고, 계산된 값을 즉시 다음 명령어에 전달.

but 추가적인 데이터 경로 연결이 필요

Load-Use Data Hazard

: 특정 값이 메모리에서 로드되는 동안 그 값을 바로 다음 명령어에서 사용하려고 할 때 발생

ld x1, 0(x2) // 메모리에서 데이터를 읽어서 레지스터 x1에 저장
sub x4, x1, x5

x1에 저장될 값은 아직 메모리 단계에서 읽혀지지 않았기 때문에, 값이 준비되기 전에 sub 명령어가 실행하려고 해서 문제가 발생.

❯ Forwarding으로 해결되지 않는 이유
: Forwarding은 이미 계산된 값을 다음 단계로 전달하는 방식,
load 명령어는 메모리 접근이 끝난 후에야 값을 사용할 수 있기 때문에 아직 준비되지 않은 값을 전달할 수 없음

ld 명령어가 실행되는 동안, sub 명령어는 기다려야 하기 때문에 여러 개의 bubble이 발생

Code Scheduling to Avoid Stalls

: Load-Use Data Hazard을 줄이기 위해 명령어의 순서를 재배열하여 성능을 개선하는 방법

a = b + e; 
c = b + f;

스케줄링 전:
각 명령어가 순서대로 실행되고, add와 같은 명령어가 바로 앞의 로드 명령어로부터 데이터를 필요로 하는 상황이 반복.
→ 각 데이터 의존성마다 스톨이 발생하여 총 13사이클 걸림.

스케줄링 후:
명령어들의 순서를 변경하여 독립적인 명령어들을 로드 명령어 뒤에 배치함으로써 데이터가 준비될 때까지 기다릴 필요가 없음.
→ 스톨이 줄어들고, 총 11사이클 만에 실행이 완료.

Control Hazards

: 파이프라인에서 분기(branch) 명령어가 실행될 때 다음에 수행할 명령어가 결정되기 전까지의 상황에서 발생하는 문제

branch 명령어로 인해 다음 명령어의 주소를 빨리 결정하지 못해서 파이프라인은 다음 명령어를 예측하지 못하고, 잘못된 명령어를 fetch하는 경우 발생.
만약 분기 결과가 예측과 다르다면, 잘못 fetch된 명령어를 취소하고 다시 올바른 명령어를 가져와야 함.
→ 파이프라인이 멈추거나 버블이 생겨 성능이 저하.

❯ RISC-V 파이프라인에서의 해결
: 파이프라인의 초기 단계에서 분기 명령어가 어디로 갈지 빠르게 결정하여 파이프라인이 다음 명령어를 정확하게 페치할 수 있도록 함.
→ 파이프라인의 ID(Instruction Decode) 단계에서 추가적인 하드웨어를 사용해 레지스터 비교 및 분기 타겟 주소를 계산하는 작업을 수행

Stall on Branch

: 브랜치의 결과가 결정되기 전까지 다음 명령어를 페치하지 못하는 상황

beq x1, x0, 40 명령어 이후에 바로 실행되어야 할
or x7, x8, x9 명령어는 beq 결과가 나올 때까지 페치되지 못하고 기다려야 함.

Branch Prediction

❯ 파이프라인이 길수록 브랜치 결과 예측이 어려워짐
: 브랜치가 결정될 때까지의 stall penalty(파이프라인이 빈 상태로 기다리는 시간)가 커지게 됨. → 성능저하

브랜치 결과를 예측해서 그에 맞게 명령어를 미리 페치.
예측이 맞으면 파이프라인이 끊기지 않고 순조롭게 진행되지만, 예측이 틀린 경우에만 stall이 발생.
→ 파이프라인을 정정하고 올바른 명령어를 다시 fetch 해야 하기 때문에 비용이 발생

❯ RISC-V 파이프라인에서의 브랜치 예측

RISC-V 파이프라인에서는 기본적으로 브랜치가 취해지지 않을 (jump하지 않을) 것이라고 예측
: 그냥 다음 명령어를 가져와서 진행할 수 있어, 예측이 맞다면 파이프라인이 멈추지 않고 딜레이 없이 빠르게 실행

잘못 예측한 경우,
파이프라인에 잘못 들어간 명령어들을 버리고(flush),
올바른 명령어부터 다시 가져와 일부 시간 손실이 발생.
but 대부분의 경우 예측이 맞을 때 얻는 성능 향상 > 잘못된 예측으로 인한 손실

More-Realistic Branch Prediction

: 정적(Static) / 동적(Dynamic) 브랜치 예측

반복문(Loop): 루프의 경우, 반복문 안의 브랜치 명령어는 일반적으로 조건이 참이 되어 계속 반복되는 경우가 많음.
→ 뒤로 가는(이전 명령어로 돌아가는) 브랜치(Backward Branch)는 실행됨(Taken)으로 예측.

조건문 (If문): if 같은 조건문은 앞으로 가는 브랜치로, 보통은 조건이 맞지 않아서 브랜치가 실행되지 않음(Not Taken)으로 예측

Subject to hazards : Structure, data, control

data hazard는 명령어 간의 데이터 의존성에 초점을,
control hazard는 프로그램의 흐름 제어 결정에 초점을 맞추고 있음.

Pipelined Datapath and Control

Pipeline registers

: 파이프라인에서의 각 단계는 서로 독립적으로 작동하며, 단계 간의 데이터를 저장하고 전달하기 위해 파이프라인 레지스터가 필요.

각 Pipeline register의 기능

IF/ID 레지스터:
Instruction Fetch (IF) 단계에서 가져온 명령어를 Instruction Decode (ID) 단계로 전달.
→ 명령어와 다음 주소 정보를 저장.
ID/EX 레지스터:
ID 단계에서 디코딩된 명령어와 관련된 정보를 Execute (EX) 단계로 전달.
→ 레지스터 파일로부터 읽은 데이터, 연산에 필요한 제어 신호 등을 저장.
EX/MEM 레지스터:
EX 단계에서 수행된 ALU의 결과와 같은 연산 결과를 Memory Access (MEM) 단계로 전달.
→ 계산된 메모리 주소와 연산 결과 등을 저장.
MEM/WB 레지스터:
MEM 단계에서 읽어온 메모리 데이터나 연산 결과를 Write Back (WB) 단계로 전달.
→ 최종적으로 레지스터에 기록해야 할 데이터를 저장.

Pipeline Operation

파이프라인의 동작 방식을 시각적으로 이해하기 위한 두 가지 접근 방식

Single-Clock-Cycle Diagram

ex)

: pipeline의 각 단계에서 어떤 자원이 사용되고, 어떤 데이터가 전달되는지를 시각적으로 강조

Multi-Cycle Pipeline Diagram

Form showing resource usage :
각 클록 사이클(CC 1, CC 2, ...) 동안 여러 명령어들이 어떤 자원을 사용하고 있는지 시각적으로 표현.

Traditional form :
파이프라인의 각 단계가 시간 순서대로 어떻게 진행되는지를 계단식으로 표현.

활용:
자원 사용량이나 경합을 분석할 때
: resource usage 다이어그램이 유용.
전체 프로세스의 진행과 명령어들의 순차적 실행을 분석할 때
: Traditional form 다이어그램이 더 유용.

Data Hazards: Forwarding vs. Stalling

Data Hazards in ALU Instructions

sub x2, x1, x3
and x12, x2, x5
or  x13, x6, x2
add x14, x2, x2
sd  x15, 100(x2)

x2 레지스터가 여러 번 사용되고 있음.
: 각 명령어가 필요한 x2 값을 얻기 전에 결과가 준비되지 않으면 Data Hazard가 발생할 수.

→ Forwarding
: 데이터를 기다리는 대신, Forwarding 기법을 사용하여 데이터가 만들어지자마자 즉시 다음 명령어로 전달 가능.

Dependencies & Forwarding

: Forwarding을 통해 데이터 의존성을 해결

• 빨간색 선: 데이터 의존성을 나타냄.
→ 이 의존성이 해결되지 않으면 파이프라인이 멈춤.

• 파란색 선: 포워딩 경로를 나타냄.
(데이터가 생성되자마자 필요한 명령어로 직접 전달)

Detecting the Need to Forward

Data Hazard가 발생하는 상황 :

포워딩 조건 :

• 포워딩이 필요한 명령어는 레지스터에 값을 기록해야 하며, RegWrite가 활성화되어야 함.
ex) EX/MEM.RegWrite, MEM/WB.RegWrite → 값이 true여야

• 레지스터 Rd가 x0가 아니어야 함.
RegisterRd는 쓰기 목적 레지스터로, 값이 0이면 쓰거나 갱신할 필요가 없음.

Forwarding Conditions

MUX Control 코드의 의미

00: 레지스터 파일(ID/EX)에서 값을 가져오는 것.
즉, 포워딩 없이 현재 명령어의 일반적인 레지스터 값을 ALU로 전달하는 상황입니다.

10: EX/MEM 단계에서 포워딩을 통해 이전 ALU 연산 결과를 가져오는 것.

01: MEM/WB 단계에서 포워딩을 통해 메모리에서 얻은 데이터 또는 이전의 ALU 연산 결과값을 가져오는 것을 의미.

Double Data Hazard

add x1, x1, x2
add x1, x1, x3
add x1, x1, x4

: x1이 중첩되면서 EX 단계와 MEM 단계가 데이터 해저드 동시에 발생

→ 더 최근에 업데이트된 데이터를 사용

MEM 해저드 조건을 수정하여 EX Forwarding 조건이 참일 때 (EX 단계 데이터가 더 최신일 때)는 MEM Forwarding이 동작하지 않도록 (전달을 건너뛰게) 설계.

Forwarding : Data Hazard를 줄이기 위해 사용, 값을 빠르게 전달하여 Stall을 방지.

Revised Forwarding Condition

MEM 단계에서의 Forwarding(전달) 조건 :

• MEM/WB 파이프라인 레지스터의 RegWrite 신호가 활성화되어 있음
(RegWrite != 0)
• 대상 레지스터가 0이 아님 (RegisterRd ≠ 0)
• EX 단계의 해저드 조건이 성립되지 않음

if (MEM/WB.RegWrite 
    and (MEM/WB.RegisterRd ≠ 0)
    and not(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
            and (EX/MEM.RegisterRd ≠ ID/EX.RegisterRs1))
    and (MEM/WB.RegisterRd = ID/EX.RegisterRs1)) 
  ForwardA = 01

Load-Use Hazard Detection

: 명령어가 메모리에서 값을 읽어오는 동안 다음 명령어에서 이 값을 사용하려고 할 때 발생

ID/EX.MemRead가 활성화되어 있음 (즉, 메모리에서 값을 읽어오는 작업이 진행 중).
메모리에서 읽은 값이 현재 명령어에서 사용하는 피연산자와 같음:
(ID/EX.RegisterRd = IF/ID.RegisterRs1)

→ 해결책 : Stall and Insert Bubble
해저드가 탐지되면 CPU는 파이프라인을 잠시 멈추고 버블(Bubble)을 삽입

How to Stall the Pipeline

• Stall 구현 방법

ID/EX 레지스터의 제어 신호를 0으로 강제 설정:
EX, MEM, WB 단계에서 해당 명령어를 NOP(No Operation)으로 처리.
→ 다음 명령어가 정상적으로 진행되지 않도록 멈춤
PC(프로그램 카운터)와 IF/ID 레지스터의 업데이트를 차단:
같은 명령어를 ID 단계에서 다시 디코딩.
그다음 명령어는 다시 가져옴(Fetch).
→ 현재 Hazard가 해결될 때까지 멈춘 명령어를 다시 실행
1-cycle 스톨:
MEM 단계가 데이터를 읽을 수 있도록 1 사이클을 대기.
이후, 데이터를 EX 단계로 전달(Forwarding) 가능.
• 1-cycle stall = CPU가 한 클럭 주기 동안 다음 명령어의 실행을 멈추고 기다리는 것
• Forwarding = MEM이나 WB 단계에서 연산 결과가 생성된 데이터를 다음 명령어의 EX 단계에서 바로 사용할 수 있도록 전달

Load-Use Data Hazard

: load 명령어가 메모리에서(MEM 단계) 값을 읽는 작업과 다음 명령어가 그 값을 사용하는 작업 사이에서 발생.

ld x2, 20(x1)   # x2에 메모리에서 값을 로드
add x4, x2, x5  # x2의 값이 필요하지만 아직 준비되지 않음

Datapath with Hazard Detection

Hazard Detection Unit : ID 단계에서 Load-Use Hazard를 탐지.
탐지되면 스톨을 삽입하고, 파이프라인 진행을 잠시 멈춤.

Stalls and Performance

• Stall의 영향 : 파이프라인이 멈추는 상태를 만들어 전체 성능을 저하시키지만, 올바른 결과를 얻기 위해 반드시 필요.

• 컴파일러의 역할 : 컴파일러는 파이프라인 구조를 이해하여 명령어를 재배치함으로써 해저드와 Stall을 최소화.

Control Hazards

Branch Hazards

: 분기 명령어(ex. beq, bne)가 파이프라인에서 처리될 때 발생.
분기 결과를 결정하기 전에 이미 다음 명령어들이 Fetch되고 파이프라인에 들어가게 됨 → 잘못된 명령어들이 실행될 수 있음.

Reducing Branch Delay

: 분기 지연을 줄이기 위해 하드웨어를 개선하여 분기 결과를 MEM 단계까지 기다리지 않고, ID 단계에서 더 빠르게 결정

beq rs, rt, offset

ex) 
40: beq x1, x3, 16 // PC-relative branch
52: add x14, x4, x2
56: sub x15, x6, x7
...
72: ld x4, 50(x7)

PC-Relative Addressing 계산 과정
현재 명령어의 주소(PC) : beq 명령어의 주소는 40
목표 주소 = 현재 명령어의 PC + (offset × 2) = 40 + (16 × 2) =72
→ 목표 주소는 72번 주소로 이동

Example: Branch Taken

Data Hazards for Branches

• ALU 연산 후 Branch Data Hazard

add x1, x2, x3
add x4, x5, x6
beq x1, x4, target

x1과 x4가 이전 ALU 명령어에서 계산되기 때문에, Branch 명령어가 실행될 때 데이터가 준비되지 않을 수 있음.
→ 포워딩(Forwarding) 사용 : 이전 ALU 결과를 직접 Branch 명령어에 전달

• Load 명령 후 Branch Data Hazard

lw x1, addr
add x4, x5, x6
beq x1, x4, target

Load 명령어는 데이터 메모리에서 값을 읽어와야 하므로, Branch 명령어 실행 전에 데이터를 사용할 수 없음.
→ 1 Stall Cycle 사용

• 비교 레지스터가 바로 직전의 Load 명령어에서 값을 가져올 때 발생하는 Data Hazard.

lw x1, addr
beq stalled		// 첫 번째 스톨
beq stalled		// 두 번째 스톨
beq x1, x0, target

→ 2개의 Stall Cycle 사용
첫 번째 스톨: 데이터가 Load 명령어의 MEM 단계에서 준비되기를 기다림.
두 번째 스톨: 데이터를 Branch 명령어에 전달.

Dynamic Branch Prediction

• Branch Prediction Buffer (Branch History Table):
최근 Branch 명령어의 주소를 기반으로 인덱싱.
해당 Branch 명령어가 이전에 Taken인지 Not Taken인지 결과를 저장.

• Branch 처리 과정 :
Table을 참조하여 Taken 또는 Not Taken 예측에 따라 명령어를 미리 가져옴(Fetch).
만약 예측이 틀리면 파이프라인을 Flush, 새로운 예측 결과로 전환.

1-Bit Predictor: Shortcoming

: 전 분기 명령어의 결과(분기 실행 여부)를 기준으로 다음 분기의 결과를 예측합

• Inner 루프 마지막 반복 :
inner 루프가 마지막으로 실행되는 순간, beq는 Not Taken이 됨.
(더 이상 inner로 분기하지 않음).
하지만 1-Bit Predictor는 이전에 분기가 항상 Taken이었다고 학습했으므로, 이번에도 Taken으로 예측.
→ 결과적으로 Misprediction이 발생합니다.

• 다음 Outer 루프가 다시 Inner 루프를 시작 :
inner 루프가 다시 시작되면 첫 beq 명령어는 다시 Taken이어야 함.
그러나 1-Bit Predictor는 바로 이전 상태에서 Not Taken으로 설정되었기 때문에 또 Misprediction이 발생.

2-Bit Predictor

: 분기를 예측하는 데 2비트 상태 머신을 사용하여, 예측 상태를 더 세밀하게 관리

• 4가지 상태:
Strongly Taken: 강하게 Taken 예측.
Weakly Taken: 약하게 Taken 예측.
Weakly Not Taken: 약하게 Not Taken 예측.
Strongly Not Taken: 강하게 Not Taken 예측.

• 상태 전이 규칙:
분기 결과가 현재 예측과 일치하면 상태를 유지.
예측이 잘못되었더라도 첫 번째 오작동에서는 Weak 상태로 전환.
두 번째 연속 오작동이 발생해야 Strong 상태가 바뀝니다.

Calculating the Branch Target

: Predictor가 분기가 발생할지(Taken) 여부를 예측하더라도, 분기 대상 주소(Target Address)를 계산하는 작업은 여전히 필요.

• Branch Target Buffer (BTB):
분기 명령어의 대상 주소를 캐시에 저장하여, 분기 명령어(예: beq, bne)가 실행될 때 Target Address를 빠르게 Fetch하는데 사용.

• 동작 방식:
명령어가 Fetch 단계에서 BTB를 조회.
BTB에서 Hit하면, 예측된 대상 주소로 바로 이동하여 다음 명령어를 가져옴.
BTB에서 Miss하면, 대상 주소를 새로 계산해야 하므로 추가적인 지연이 발생.

∨ Miss : CPU가 BTB를 조회했을 때, 해당 분기 명령어의 기록이 없거나 잘못된 정보가 저장된 경우

Exceptions and Interrupts

: 현재 프로그램의 흐름을 중단시키므로 성능 저하를 유발

Handling Exceptions

• 문제가 발생한 명령어의 주소 저장
: 예외가 발생한 명령어의 PC(Program Counter)를 저장하여, 나중에 예외가 처리된 후 해당 명령어로 돌아갈 수 있도록 함.

• 문제 원인 저장
: 예외의 원인을 나타내는 정보를 저장.
RISC-V에서는 SCAUSE (Supervisor Exception Cause Register)가 예외의 원인을 저장

• Handler로 점프
: 예외 처리 루틴(Exception Handler)로 이동.
ex. Handler 주소: 0000 0000 1C09 0000_hex

An Alternate Mechanism

Vectored Interrupts
: 예외의 원인에 따라 처리 루틴의 주소를 자동으로 결정하는 방식

• Exception Vector Address
: 예외의 원인에 따라 벡터 테이블에 저장된 주소를 읽어옴.
ex. 정의되지 않은 명령어: 00 0100 0000_2
하드웨어 오류: 01 1000 0000_2

• 처리 방식
: Instruction(명령어)은 다음 중 하나를 수행

인터럽트를 처리 :
작업이 단순하면, Handler로 점프하지 않고 인터럽트를 현재 위치에서 처리
실제 처리 루틴(Handler)로 점프하여 더 복잡한 작업을 수행 :
예외나 인터럽트가 복잡해서 즉석에서 처리할 수 없을 때, Handler 코드를 실행

Handler Actions

• 원인 읽기 및 관련 핸들러로 전환
: 발생한 예외의 원인을 확인하고, 이를 처리할 적절한 핸들러로 전환

• 필요한 작업 결정
: 예외가 복구 가능한지, 혹은 복구 불가능한지를 판단

• 복구 가능한 경우 (If restartable)
: 문제를 수정하고 SEPC 레지스터를 사용해 중단된 명령어로 복귀

• 복구 불가능한 경우
: 프로그램을 종료.
SEPC와 SCAUSE 정보를 사용해 오류를 기록하고, 사용자에게 보고.

Exceptions in a Pipeline

: Control Hazard의 또 다른 형태
(예외가 처리될 때까지 파이프라인의 일부 단계가 Flush되고 제어 흐름이 핸들러로 전환)

• x1 레지스터 손상 방지
: 현재 연산이 잘못된 데이터를 덮어쓰지 않도록 조치.

• 이전 명령어 완료
: 오류가 발생해도, 이미 파이프라인에 들어와 실행 중이던 명령어들은 정상적으로 완료함.

• 현재 명령어와 이후 명령어를 Flush
: 문제를 일으킨 명령어와 이후 명령어들을 파이프라인에서 제거.

• SEPC와 SCAUSE 값 설정
SEPC: 중단된 명령어의 주소 저장.
SCAUSE: 예외 원인 코드 기록.

• 핸들러로 제어 전달
: 예외 처리 핸들러로 이동해 문제를 해결하거나 종료.

Exception Properties

❯ Restartable Exceptions
: 예외 발생 후 복구가 가능하며, 프로그램이 예외 발생 이전 상태로 돌아갈 수 있음.

예외가 발생한 명령어와 이후의 명령어를 Flush
Handler 실행
SEPC에 저장된 명령어를 다시 Fetch하여 처음부터 다시 실행

❯ SEPC 레지스터에 PC 저장
: SEPC에 문제가 발생한 명령어의 주소를 저장하여
예외가 발생한 명령어를 식별, 예외 처리 후 다시 해당 명령어로 복귀.

Exception Example

40  sub x11, x2, x4
44  and x12, x2, x5
48  orr x13, x2, x6
4c  add x1, x2, x1  # 예외 발생 (Exception)
50  sub x15, x6, x7
54  ld x16, 100(x7)

• 예외 발생 시, 해당 명령어(add x1, x2, x1) 이후에 실행 중인 모든 명령어는 파이프라인에서 제거(Flush)됨.
• SEPC: 문제가 발생한 명령어의 PC 주소(4c)를 저장.
• SCAUSE: 예외 원인을 저장.
• Handler로 제어가 전환.

// Handler
1C090000  sd x26, 1000(x10)
1C090004  sd x27, 1008(x10)
...

Multiple Exceptions

• Pipelining과 다중 예외
: 파이프라인에서 여러 명령어가 동시에 처리되기 때문에,
한 번에 여러 예외가 발생할 수 있음.
ex. 한 명령어는 메모리 접근 오류, 다른 명령어는 정의되지 않은 명령어 예외

• 가장 빠른 명령어의 예외 처리
: 파이프라인에서 가장 먼저 예외를 유발한 명령어를 처리한 후,
나머지 명령어를 Flush.
→ Precise Exceptions(정확한 예외 처리)을 유지할 수 있음.

가장 먼저 발생한 예외를 유발한 명령어를 식별.
이후 명령어들을 모두 플러시.
해당 예외를 처리한 뒤, 프로그램 실행을 복구하거나 종료.

Precise Exception : 예외 처리 후, 프로그램 상태가 정확히 복구

• 복잡한 파이프라인에서의 어려움
: Precise Exception을 유지하는 것이 더 어려워짐.

여러 명령어가 한 사이클에서 실행:
Out-of-Order Completion (완료 순서가 다름)
: 명령어들이 순서대로 완료되지 않고, 더 빠르게 완료 가능한 명령어가 먼저 완료될 수 있음.

→ 예외 처리 순서를 정확히 유지하는 것이 어려움.

Imprecise Exceptions

: 정확히 어떤 명령어가 예외를 발생시켰는지 완벽히 구분하지 않는 방식.
하드웨어가 처리 복잡성을 줄이는 대신, Handler 에서 모든 작업을 처리하도록 위임.

• 파이프라인 중지 및 상태 저장
: 파이프라인을 멈추고, 현재 상태(예외 원인 등)를 저장

• 핸들러에서 처리 :

어떤 명령어가 예외를 발생시켰는지 확인.
완료되지 않은 명령어를 처리하거나 플러시.
수동 작업(Manual Completion)이 필요할 수 있음.

→ 복잡한 파이프라인(Multiple-Issue, Out-of-Order)에서는 비효율적

Parallelism via Instructions

Instruction-Level Parallelism

: 한 클럭 주기 내에서 여러 명령어를 동시에 실행하여 성능을 높이는 기술
파이프라인은 ILP를 활용해 명령어의 병렬 처리를 최대화함.

❯ ILP 증가 방법
• Deeper Pipeline
: 각 단계에서 처리할 작업을 줄이고, 클럭 주기를 단축.
ex. 파이프라인 단계를 5단계에서 10단계로 늘리면 각 단계에서 더 적은 작업 수행
→ 속도 증가.

• Multiple Issue (다중 명령어 발행)
: 한 클럭 주기 동안 여러 명령어를 동시에 시작.
ex.
4GHz, 4-way 파이프라인 → 최대 16억 명령어/초 실행 가능.
이론상 CPI(Cycles Per Instruction) = 0.25, IPC(Instructions Per Cycle) = 4.

Multiple Issue

: 한 클럭 주기 동안 여러 명령어를 동시에 발행(실행)하여 성능을 향상시키는 기술.

• Static Multiple Issue :
컴파일러가 명령어를 그룹으로 묶어 "Issue Slot"에 배치.
컴파일러가 명령어의 Hazard를 감지하고 방지.
실행 전의 명령어 순서가 중요하며, CPU는 이 순서를 따름.

• Dynamic Multiple Issue :
CPU가 실행 중인 명령어를 분석하여, 매 클럭 주기마다 발행할 명령어를 선택.
컴파일러가 명령어 재배치를 통해 도움을 줄 수 있지만, 주된 작업은 CPU가 담당.
고급 기술을 사용하여 runtime에 Hazard를 해결.

Speculation

: 명령어 실행 시, 미리 "추측"하여 실행하고 나중에 결과를 확인하는 기술

❯ 작동 방식

• 명령어를 가능한 한 빨리 실행 시작.
• 추측이 맞았는지 확인 :
맞으면) 결과를 완료.
틀리면) 작업을 Rollback하고 올바른 작업을 실행.

❯ 종류
• Branch Prediction (분기 예측):
분기 명령어(예: if/else)의 실행 경로를 추측.
추측이 틀렸을 경우, Rollback하고 올바른 경로를 다시 실행.

• Load Speculation (로드 추측):
데이터가 메모리에 준비되었는지 추측하여 데이터를 미리 로드.
추측이 틀릴 경우, 메모리 업데이트 이후 데이터를 다시 로드.

Rollback : 오류가 발생했을 때, 현재 진행 중인 작업을 취소하고 시스템을 이전 상태로 복구하는 과정

Compiler/Hardware Speculation (추측 실행)

❯ Compiler에서의 추측 실행

• 컴파일러가 명령어를 재배열(Reorder)
: 실행의 효율성을 높이고 병렬성을 최대화.

• "Fix-up" 명령어 삽입
: 추측이 틀린 경우를 대비해 오류를 복구할 수 있는 명령어를 추가
ex. 분기 예측이 틀렸을 때 Rollback을 위해 상태를 저장하는 명령어.

❯ Hardware에서의 추측 실행

• 명령어를 미리 살펴보고 실행 준비
: 실행 전에 명령어를 분석하여 추측 실행 가능한 작업을 결정.

• 결과 버퍼링(Buffering)
: 추측 실행의 결과를 버퍼에 저장.

• 잘못된 추측 처리
: 추측이 틀렸다면 버퍼의 내용을 제거(Flush)하고, 올바른 작업을 다시 실행.

Speculation and Exceptions (추측 실행 중 예외 발생)

❯ 예외 처리 방식

• Static Speculation (정적 추측)
: ISA(Instruction Set Architecture)에서 예외 처리를 연기(Defer)하는 기능을 제공.
ex. 특정 예외를 나중에 처리하도록 설계.

• Dynamic Speculation (동적 추측)
: 예외를 명령어 완료 시점까지 버퍼링.

Static Multiple Issue

: 컴파일러가 명령어를 미리 분석하고, 한 클럭 주기 동안 병렬로 실행할 명령어 그룹(Issue Packet)을 구성하는 방식.

• Issue Packet :
여러 명령어가 포함된 "패킷" 형태.
패킷 내 명령어들은 동일한 클럭 주기에 실행.
패킷 구성은 파이프라인 resource을 기준으로 결정.

• Very Long Instruction Word (VLIW) :
Issue Packet은 매우 긴 명령어 단어(VLIW)처럼 작동.
여러 동시 작업을 명시적으로 지정하여 병렬 처리를 극대화.

Scheduling Static Multiple Issue

❯ 효율적인 Issue Packet을 구성

• 해저드(Hazard) 제거
: 명령어 간 종속성(dependency)을 분석하고, 종속성이 없는 명령어를 패킷에 배치.

• 명령어 재배열 (Reordering)
: 실행 순서를 조정하여 효율적인 병렬 실행이 가능하도록 구성.

❯ 스케줄링의 규칙

패킷 내 종속성 제거
: Issue Packet 안에 있는 명령어들 간에는 종속성이 없어야 함.
패킷 간 종속성 허용 가능
: ISA(Instruction Set Architecture)에 따라 패킷 간 종속성이 허용되기도 함.
NOP 명령어 padding
: 자원이 충분하지 않을 경우, 빈 슬롯에 NOP (No Operation)을 삽입하여 스케줄링 유지.
(파이프라인이 항상 동일한 방식으로 진행될 수 있도록 빈 공간을 만들어 줌)

RISC-V with Static Dual Issue

: 한 클럭 주기 동안 두 개의 명령어를 병렬로 발행(실행)하는 방식

❯ Static Dual Issue의 구성

• 한 패킷에 포함될 명령어
: ALU/Branch 명령어 연산(ALU) 또는 분기(Branch) 명령어.
Load/Store 명령어: 메모리 접근(Load/Store) 명령어.

• 두 명령어는 64비트 정렬

• 명령어 배치 규칙
: 첫 번째 명령어는 ALU/Branch 명령어.
두 번째 명령어는 Load/Store 명령어.
만약 두 번째 명령어가 없을 경우 NOP (No Operation) 명령어로 채움.

Hazards in the Dual-Issue RISC-V

• EX Data Hazard
: ALU 명령어의 결과를 같은 패킷에 포함된 Load/Store 명령어에서 바로 사용할 수 없음.

add x10, x0, x1
ld x2, 0(x10)

add 명령어에서 x10에 결과가 저장되기 전에 ld 명령어가 실행되려고 하면 데이터 의존성 문제가 발생.

→ 위 두 명령어를 같은 패킷에 배치하지 못하고, 두 개의 패킷으로 분리해야함.

• Load-Use Hazard
: Load 명령어가 데이터를 메모리에서 가져오는 데 시간이 걸리기 때문에, Load 명령어의 결과를 바로 다음 클럭 주기에서 사용할 수 없음

ld x31, 0(x20)
add x31, x31, x21

ld 명령어로 메모리에서 데이터를 읽은 결과를 바로 다음 add 명령어에서 사용할 수 없으므로 Stall이 발생

Scheduling Example

Loop:
    ld x31, 0(x20)       // x31 = array element
    add x31, x31, x21    // add scalar to x31
    sd x31, 0(x20)       // store result
    addi x20, x20, -8    // decrement pointer
    blt x22, x20, Loop   // branch if x22 < x20

• IPC (Instructions Per Cycle)
IPC 계산:
주어진 명령어는 5개이고, 실행된 주기(Cycle)는 4개.
IPC = 5/4 = 1.25

• 최대 IPC와 비교:
듀얼 이슈 시스템에서 최대 IPC는 2.
하지만 해저드와 스케줄링 제약으로 인해 실제 IPC는 이보다 낮음.

Loop Unrolling

: 루프의 본문(body)을 여러 번 복제(replication)하여 병렬 실행을 가능하게 하는 방법.

• 목적
: 루프 제어를 위한 overhead(ex. 조건 검사와 분기)를 줄임.
CPU가 병렬 처리 가능한 명령어들을 인식할 수 있도록 명령어들을 재배열하거나 루프를 펼쳐서 CPU의 자원을 최대한 활용.

• Register Renaming (레지스터 이름 변경)
: 루프 본문을 복제할 때, 다른 레지스터 이름을 사용하여 anti-dependencies 문제를 방지.

anti-dependency : 이전 명령어의 결과가 아직 사용되지 않았는데, 같은 레지스터 이름을 새로운 명령어가 덮어쓰는 상황.

sd x1, 0(x2)   // x1 저장
ld x1, 0(x2)   // 같은 x1 사용, 데이터 손실 가능

• 루프 제어 감소
: 루프 반복 횟수를 줄이고, 불필요한 조건 검사와 분기 명령어의 실행 빈도를 낮추는 것

Loop Unrolling Example

루프 펼치기 전 : IPC = 명령어 수 / 사이클 수 = 5/4 = 1.25.

Loop:
    addi x20, x20, -32    // 포인터 이동
    ld x31, 0(x20)        // 데이터 로드
    add x31, x31, x21     // 연산
    sd x31, 0(x20)        // 데이터 저장
    blt x22, x20, Loop    // 조건 검사 및 분기

루프 펼친 후 : IPC = 14/8 = 1.75.

Dynamic Multiple Issue

: Superscalar 아키텍처를 사용하는 CPU에서 명령어 발행을 동적으로 처리하는 방식.
CPU가 실행할 명령어를 스스로 선택하고, 종속성이나 구조적 제약에 따라 매 사이클마다 0개, 1개, 또는 여러 개의 명령어를 발행할 수 있음.

❯ 특징
• structural and data 해저드 방지
: CPU는 명령어 간의 종속성을 확인하고, 충돌(해저드)을 피할 수 있는 명령어만 발행

• 컴파일러 의존성 감소
: 컴파일러가 명령어 스케줄링을 직접 하지 않아도 됨.

Dynamic Pipeline Scheduling

: CPU가 명령어를 Out-of-Order(순서 무관) 방식으로 실행하여 Stall을 줄이는 기법.
결과(commit)는 반드시 프로그램 순서대로 레지스터에 기록.

ld x31, 20(x21)    # 메모리에서 x31로 데이터 로드
add x1, x31, x2    # x31과 x2를 더해 x1에 저장
sub x23, x23, x3   # x23에서 x3을 빼기
andi x5, x23, 20   # x23과 20의 AND 결과를 x5에 저장

• 문제
: add x1, x31, x2는 ld x31, 20(x21)의 결과를 기다려야 함(데이터 종속성).
만약 순서대로 실행하면 add 때문에 스톨 발생.
• 해결
: sub x23, x23, x3와 andi x5, x23, 20은 독립적인 명령어이므로 Out-of-Order 실행.
ld 명령어가 완료되기 전에 독립적인 명령어를 실행하여 CPU의 유휴 시간을 줄임.

Dynamically Scheduled CPU

❯ 구조

• Instruction Fetch and Decode Unit
: 명령어를 가져오고 순서를 유지하며 실행.

• Reservation Stations (예약 스테이션)
: 각 기능 유닛(integer, floating point 연산, ld/sd 등)에 연결된 대기 영역.
명령어의 operand(연산에 필요한 값)가 준비될 때까지 명령어를 대기시킴.
operand가 준비되면 Out-of-Order(순서 무관 실행)로 실행됨.

• Reorder Buffer
: 실행 결과를 임시로 저장하고, In-Order Commit(레지스터에 순서대로 결과 저장)을 보장.

• Commit Unit
: 리오더 버퍼에 저장된 값을 확인한 뒤, 명령어 실행 결과를 최종적으로 레지스터에 기록.

Register Renaming

❯ 필요한 이유
anti-dependency 문제 : 동일한 레지스터 이름을 여러 명령어에서 사용할 경우, 실제로는 연관이 없는 명령어 간에 종속성이 생긴 것처럼 보임.

❯ 작동 과정
명령어가 reservation station에 발행될 때:

• operand가 준비된 경우:
레지스터 파일 또는 리오더 버퍼에서 값을 복사하여 reservation station으로 전달.
값이 레지스터 파일에서 필요 없어질 수 있으므로, 해당 레지스터를 다른 명령어가 덮어써도 무방.

ex.

add x1, x2, x3   # x1 = x2 + x3
sub x1, x4, x5   # x1 = x4 - x5

첫 번째 명령어(add x1, x2, x3)가 실행되면:
x1에 결과를 저장하지 않고, reservation station(임시 저장 공간)에 결과를 보관.
두 번째 명령어(sub x1, x4, x5)는:
x1을 덮어쓰지만, 첫 번째 명령어의 결과는 이미 reservation station에 있으므로 영향을 받지 않음.

• operand가 준비되지 않은 경우:
reservation station은 실행 유닛(Function Unit)에서 값을 받을 때까지 대기.
필요 시, 레지스터 업데이트 없이 reservation station으로 값 전달.

Speculation

: CPU가 명령어 실행 결과를 정확히 알기 전에, 예상되는 결과를 바탕으로 작업을 미리 진행하는 기법.

• Branch Speculation
: CPU는 분기(Branch) 명령어의 결과를 미리 추측해 명령어를 발행.
하지만 결과가 확인되기 전까지 commit하지 않음.

• Load Speculation
: 로드 명령어의 주소와 값을 예측하여 cache miss를 최소화.
아직 저장이 완료되지 않은 값(Outstanding Stores)이 있어도 load 작업을 미리 진행.
스토어가 load unit을 우회하도록 하여 로드가 빠르게 이루어질 수 있도록 함.
하지만 결과가 확인되기 전까지 commit하지 않음.

Why Do Dynamic Scheduling?

: 컴파일러 스케줄링만으로는 한계가 있음.
→ 명령어 실행을 CPU가 실시간으로 최적화하도록 하는 동적 스케줄링 필요.

• 컴파일러 스케줄링의 한계
: 컴파일러가 실행 전에 모든 명령어를 최적으로 스케줄링할 수 있다고 가정할 수 없음.
ex. Cache Miss는 실행 중에 발생하며 예측하기 어려움.

• Branch Handling
: Branch의 결과는 실행 중에 동적으로 결정, 예측하기 어려움.

• ISA 구현의 다양성
: 동일한 ISA를 사용하는 프로세서라도 구현 방식에 따라 Latency나 Hazard가 다름.
→ 동적 스케줄링은 이러한 차이를 실시간으로 보완.

Does Multiple Issue Work?

Multiple Issue : 한 사이클에 여러 명령어를 실행하여 성능을 향상시키는 방법

❯ 한계점

• Real Dependencies :
프로그램은 데이터 간의 종속성을 가지며, 이는 ILP(Instruction-Level Parallelism)를 제한함.
ex. 한 명령어의 결과가 다음 명령어의 입력으로 사용될 경우 종속성 때문에 병렬 실행이 어려움.

• Hard-to-Eliminate Dependencies :
ex. Pointer Aliasing처럼 데이터 참조가 모호할 때 최적화가 어려움.

• Hard-to-Expose Parallelism :
명령어 발행 시 CPU가 분석할 수 있는 명령어 수가 제한적이어서 병렬성을 최대한 활용하기 어려움.
메모리 지연이나 대역폭 한계 때문에 파이프라인을 항상 가득 채우기 어려움.

Power Efficiency

Dynamic scheduling과 speculation은 복잡한 하드웨어를 필요로 하며, 이는 전력 소모를 증가시킴.

→ 복잡한 코어 하나를 사용하는 것보다 단순한 코어 여러 개를 사용하는 방식이 더 효율적일 수 있음.
ex. 멀티코어 CPU

Fallacies and Pitfalls

Fallacies (오해)

• Pipelining is easy
파이프라이닝의 기본 아이디어는 명령어를 여러 단계로 나눠 동시에 처리하는 방식으로 간단하지만,

데이터 해저드(Data Hazards) 탐지 및 해결.
병렬성 극대화를 위한 복잡한 하드웨어 설계가 필요.

Pitfalls (함정)

ISA 설계가 복잡하면 파이프라이닝 구현이 어려워짐.

chelseey

이전 포스트

Channel Coding (Block Codes)

다음 포스트