반응형

파이프라이닝

  • 실행을 겹쳐서 빠르게 처리, 병렬처리는 성능을 향상시킴, throughput을 증가시킴
  • overlapping

스크린샷 2023-05-08 오후 11 55 14


processor의 5단계

  1. IF: Instruction fetch from memory(명령어 메모리에서 읽기)
  2. ID: Instruction decode & register read(명령어 해석 및 레지스터 읽기)
  3. EX: Execute operation or calculate address(명령어 실행 또는 주소값 계산 - ALU)
  4. MEM: Access memory operand(메모리 연산 - data memory)
  5. WB: Write result back to register(결과값을 레지스터에 쓰기)

가정

스크린샷 2023-05-08 오후 11 56 55

  • 100ps for register read or write
  • 200ps for other stages
    • single-cycle = 800ps
    • 한 lw는 800ps

Pipeline Performance

스크린샷 2023-05-09 오전 11 13 06

pipelined

  • 가장 오래 걸리는 단일 작업이 200ps이기에 100ps걸리는 작업도 200ps가 걸림
    • 따라서 모든 작업단위를 200ps로 통일
  • register write를 200ps의 앞쪽 100ps에서 동작하게 하고 read를 뒤 100ps에 동작하게 해서 서로 독립적으로 동작하도록 유도(지연시간이 생기게됨)
  • 현재는 5단계로 나눴지만 더 파이프라이닝하여 퍼포먼스를 올리려면 해당 단계를을 다시 refine하여 더 쪼개면 됨.(실제 핸드폰은 23개?의 파이프라이닝 스텝으로 나뉨)

Speedup due to increased throughput

  • Latency (time for each instruction) does not decrease

명령어 사이의 시간 (파이프라인) = 명령어 사이의 시간 (파이프라이닝 되지 않음) / 파이프 단계 수


Balanced 하게 단계가 일어날 경우

  • 파이프라인 기법을 적용했을 때 명령어 하나를 실행하는 데 걸리는 시간은 파이프라인 기법을 적용하지 않을 때와 동일
  • 처리속도가 증가하지 않음
  • but 여러 개의 명령어를 동시에 처리할 수 있으므로, 단위 시간당 처리할 수 있는 명령어의 수가 증가하여 처리량이 증가
    • 즉 파이프라이닝이 균형있게 잘 일어나면 처리속도가 증가

Unbalanced 하게 단계가 일어나는 경우

  • hazard같은게 일어나면 처리 속도 향상이 예상보다 미미할 수 있음
    • 가장 오래 걸리는 단계가 다른 모든 단계보다 더 느리게 수행되므로, 처리 시간이 가장 오래 걸리는 단계에 의해 전체 처리 시간이 결정되기 때문
    • 파이프라인 기법을 적용하더라도 전체 처리 시간이 크게 감소하지 않을 수 있음

- n(실행 명령어 개수), T(시간), k(파이프라인 개수)

파이프라이닝을 하지 않았을 때, 걸리는 시간 : TS = n x T
파이프라이닝을 했을 때, 걸리는 시간 : TP = (n+k-1) x T/k


파이프라이닝 버블

위 기준 5단계로 진행되는데 특정 조건(hazard)같은 것에 의해 작업했던것이 없던것과 다름없어졌을때 없어진 공간을 버블이라 함.

beq x1 x2 EX2
add x5 x6 x7
sub x5 x6 x7
...


EX2 : ~
  • beq의 IF, ID, EX과정동안 add도 IF, ID가 진행되고, sub도 IF가 진행되는데 beq에 의해 EX2로 이동하게 되면 add와 sub연산은 의미가 없기에 롤백(없었던 취급)
    • 버블이 됨

그림으로 확인

스크린샷 2023-05-09 오전 12 03 53

  • initial delay이후 완료된 작업이 쏟아져 나옴(위의 경우 intial delay = 4 cycle)
  • steady state = t5(모든 단계가 동작중)
    • 버블도 steady state 계산시 포함
    • 즉, t5전에 버블이 있었어도 t5가 steady state였음
  • beq라도 if id ex에서 멈추는게 아니라 mem wb까지 가야함(이게 파이프라이닝 머신이기 때문)

🤔 추가 정리
MIPS ISA는 파이프라인 기법에 적합하도록 설계된 것으로, 모든 명령어가 32비트로 고정되어 있어 한 사이클에서 효과적으로 가져와 디코딩하기 쉬워졌습니다. 반면 x86 아키텍처는 명령어가 1~17바이트로 크기가 다양하며, 이는 명령어 가져오기 및 디코딩 과정에서 복잡성을 증가시킬 수 있습니다. MIPS ISA는 몇 가지 규칙적인 명령어 형식을 가지고 있어 디코딩 및 레지스터 읽기를 한 번에 처리할 수 있습니다. 또한, 로드 및 스토어 주소 지정을 위한 기능을 가지고 있어 메모리 주소 계산은 파이프라인의 세 번째 단계에서, 메모리 접근은 네 번째 단계에서 수행됩니다. 또한, 메모리 연산에 필요한 데이터는 정렬되어 있어 메모리 접근이 단일 사이클에 이루어질 수 있습니다. 이를 통해 MIPS ISA는 파이프라인 기법을 효과적으로 활용하여 처리 속도를 높일 수 있으며, 높은 처리량을 유지하면서도 낮은 지연 시간을 유지할 수 있습니다.





Hazards

다음 주기에서 다음 명령어를 시작하는 것을 방해하는 상황들입니다.


Structure hazard

접근하고자 하는 자원이 사용중일때
자원의 사용 충돌로 인해 다음 명령어를 시작하는 것을 방해하는 상황을 의미
load, store

  • RISC-V 파이프라인에서는 단일 메모리를 사용하는데, 로드/스토어 명령어는 데이터 액세스를 필요
  • 이 경우, 명령어 가져오기는 해당 사이클에 대기해야 하며, 이로 인해 파이프라인에 "버블"이 생길 수 있음
  • 구조적으로 메모리는 하나인데 읽고 쓰기를 동시에 할수 없기에 클럭 싸이클 내에서 반으로 쪼개 읽고 쓰기를 진행

해결법

  • instruction/data caches를 나누기
  • 파이프라인 데이터 패스에서는 별도의 명령어 및 데이터 메모리 또는 캐시가 필요
    • 명령어 및 데이터 액세스 간 충돌을 피하고, 파이프라인을 효율적으로 수행
  • time division
    • 200ms라면 앞쪽 100ms에는 쓰기작업만, 뒤쪽 100ms를 읽기 작업만 진행함으로서 쓰여진값(최신화된 값)을 읽을 수 있게함으로써 해결

data hazard

이전 명령어의 데이터 액세스 완료에 따라 다음 명령어가 의존하는 경우

add x19 x0 x1
sub x2 x19 x3
//x3의 값이 쓰여지기 전까지 대기해야함
  • 이라면 add의 연산결과가 x3에 저장될때까지 sub 연산을 대기
스크린샷 2023-05-09 오전 10 26 05
  • "add x19, x0, x1" 명령어가 실행된 후 "sub x2, x19, x3" 명령어가 실행되어야 하는 경우, "add" 명령어의 실행 결과가 "sub" 명령어에서 사용되므로, "add" 명령어가 완전히 실행되기 전까지 "sub" 명령어는 실행될 수 없습니다.
  • 2 클럭싸이클 손해가 발생(위 그림에서 2 클럭싸이클 이후 sub의 IF실행)

해결법

  • Forwarding(aka Bypassing)
    • 계산이 끝나자 마자 레지스터에 저장하는 것을 기다리는 것이 아니라 값을 바로 받아와서 사용
    • 추가 연결 datapath가 필요해짐
    • 클럭싸이클 손해가 없어짐
    • ALU의 끝부분을 레지스터의 입력값쪽으로 피드백
      • ALU 위쪽은 3to1 mux(rs1, alu연산결과, 메모리 연산결과)
      • 아래쪽은 4to1 mux(rs2, alu연산결과, 메모리 연산결과, offset)
      • mux를 연결해 생성된 값을 바로 사용해야하는 경우 바로 쓰게함

스크린샷 2023-05-09 오전 10 29 49
  • Forwarding의 문제점
    • Load-Use Data Hazard
    • Load는 버블이 발생 가능
      • 값이 필요한 시점에 계산되지 않은 경우 전달을 할 수 없으며, 이전으로 시간을 되돌려서 전달할 수는 없기 때문
      • 이를 해결하기 위해 스탤링을 사용하여 이전 명령어의 실행이 완료될 때까지 기다렸다가 다음 명령어를 실행할 수 있도록 합니다. 그러나 스탤링은 성능에 부정적인 영향을 미치므로 최소한으로 사용하는 것이 좋습
      • load이후 연산은 2bubble발생
      • mem연산이 끝난 이후 다음 클럭에서 ALU연산이 일어나야함

스크린샷 2023-05-09 오전 10 44 50
  • code scheduling은 첫번째 data hazard를 피하기 위한 해결책
    • 명령의 순서를 바꿔 bubble이 안일어 나도록 유도
    • add x3 x1 x2
    • sub x4 x3 x1
      • 두 명령어 사이에 몇개의 명령어가 있어야 data hazard가 안일어 날까?
      • 적어도 2개의 명령어는 있어야함
      • 컴파일러가 명령어를 리스케쥴할때 hazard가 발생할 수 있는 상황이 있다면 적어도 문장 사이 3문장이 있다면 어떤 forwarding과 같은 실행을 하지 않아도 hazard가 발생하지 않음

스크린샷 2023-05-09 오전 10 54 34
  • forwarding이 사용되었다면 13 clock cycle이 필요했지만 리스케쥴링까지 더한다면 11 clock cycle이 필요해짐
  • initial

control hazard

branch
  • 만약 작업이 끝나야 다음 명령어 어떤 명령인지 알 수 있다면
  • 일단 다음줄 명령어를 실행시키고 작업이 완료되기전 해당 명령어가 실행되는게 아니라면 rollback시키기(버블이 발생)
  • branch는 flow of control을 결정(어떤 문장을 결정할지 설정)
    • branch의 결과에 따라 다음 명령어를 fetching
    • 파이프라이닝은 항상 옳은 명령어만 fetch할 수 없음
      • 브랜치가 ID명령을 동작할때까지는 어떤것이 옳은지 모름
  • 아직 RISC-V 파이프라인에서 분기의 ID(stage) 단계를 처리 중입니다. 파이프라인 초기 단계에서 레지스터를 비교하고 목표(target)를 계산해야합니다. 이를 수행하기 위해 ID(stage) 단계에서 하드웨어를 추가해야합니다.

해결법

  • 분기(branch)에 대한 스톨(stall)
  • 다음 명령어를 가져오기 전에 분기 결과가 결정될 때까지 기다립니다.
  • branch outcome을 기다림
  • 1 cycle의 버블이 발생

스크린샷 2023-05-09 오전 11 38 02

분기 예측(Branch Prediction)

  • 더 긴 파이프라인에서는 분기 결과를 미리 결정하기가 어렵습니다.
  • 스톨 벌칙(stall penalty)이 허용할 수 없는 수준이 됩니다.

분기의 결과를 예측합니다.

  • 예측이 잘못되었을 경우에만 스톨(stall)합니다.
    • IF ID EX까지는 레지스터에 값을 쓰거나 메모리에 값의 변경이 없기에 rollback에 문제가 되지 않음

RISC-V 파이프라인에서

  • 분기가 되지 않을 것으로 예측할 수 있습니다.
  • 분기 이후에 지연(delay)없이 명령어를 가져올 수 있습니다.

스크린샷 2023-05-09 오전 11 42 17

예측을 더 잘하기 위해선?


더 현실적인 분기 예측(More-Realistic Branch Prediction).

  • 정적(static) 분기 예측

    • 일반적인 분기 동작을 기반으로합니다.
    • 예: 반복문. 및 if문 분기
      • Predict backward branches taken (반복문 분기 예측)
      • Predict forward branches not taken (if문 분기 예측)

  • 동적(dynamic) 분기 예측

  • 하드웨어는 실제 분기 동작을 측정합니다.

  • 예: 각 분기의 최근 이력 기록

    • 미래 동작이 이전 동작을 따를 것으로 가정합니다.
    • 잘못된 경우, 재검색하면서 스톨하고 이력을 업데이트합니다.

장점은 static보다는 더 잘 예측함
단점은 더 많은 하드웨어를 사용하게 되고 power 소비가 더 심해짐




MIPS 명령어 파이프라인의 5단계


  1. IF(Instruction fetch) : 명령어 인출
  2. ID(Istruction decode) : 명령어 해독 및 레지스터 파일 읽기
  3. EX(Execution) : 실행 및 주소 계산
  4. MEM(memory) : 데이터 멤리 접근
  5. WB(Write back) : 레지스터에 쓰기


단일 사이클 데이터패스의 분할


앞서 보았듯이 일반적으로 정보 흐름은 왼쪽에서 오른쪽으로 진행된다. 하지만, 이 흐름중 두가지 예외가 있다.

  1. WB단계 : 결과를 Reg파일에 쓰기(역류) => 데이터 해저드 유발
  2. PC의 다음 값 선정 : 증가된 PC값(IF서 처리) 과 MEM단계의 분기 주소 중에서 선택 => 제어 해저드 유발

파이프라인 데이터패스


데이터패스를 위에서 나눈 5단계 기준으로 분리하려 한다.

  • 파이프라인 레지스터 : 파이프라인 단계를 분리하는 역할 / 후속 파이프라인 단계에서 필요한 정보를 필요단계까지 전달


파란부분이 파이프라인 레지스터


분리된 데이터패스 시간 흐름 순서대로 보기


lw 명령어가 데이터패스에서 사용하는 부분(파란영역)


  1. Iw명령어 시간 흐름 별 수행 과정
    1) IF 단계 : Mux, PC, Adder, Instruction memory 활성화
    2) ID 단계 : Register의 Read data1, 2, Sign-extend 활성화
    3) EX 단계 : Mux, ALU 활성화
    4) MEM 단계 : Data Memory, Read data 활성화
    5) WB 단계 : Mux와 Register의 Write Reg, data 활성화 => 데이터 해저드 유발

  1. sw명령어 시간 흐름 별 수행 과정

    : lw와 유사, 하지만 MEM단계에서 Data Memory의 왼쪽부분만 작동 (WB단계에선 수행하는 것 없음)


그림으로 표현하는 파이프라인

두가지 방식의 표현법

  1. 시간별로 명령어마다 작동하는 부분을 칠하는 방식 : but, 그리기 번거로움
  2. 그냥 각 시간별로 수행되는 단계 작성
    좌(1), 우(2)



단일 클럭 사이클 파이프라인 다이어그램


파이프라인 제어신호


단일방식에선 10개의 신호 동시에 발사했지만, 파이프라인 도입으로 인해 이제는 부분별로 제어신호 발사해야한다.



각 단계별 제어 신호(제어신호를 제어하는 제어신호)

  1. IF : 제어신호 없음 : 항상 같은 작업 수행하기때문에 필요없다
  2. ID : 제어신호 없음 : 이하동
  3. EX : RegDst(rt, rd 구분) , ALUOP(수행연산종류), ALUSrc(Read data2, extended16bit 중 어느걸 피연산자?)
  4. MEM : Branch(beq), MemRead(lw), MemWrite(sw)
  5. WB : MemtoReg, RegWrite (rw, lw일때만 활성화)

스크린샷 2023-05-09 오후 9 48 09


각 단계에서 명령어에 따라 각 제어신호들에게 내보내주는 신호


스크린샷 2023-05-09 오후 9 50 32

파이프라인 레지스터를 통한 제어신호의 전달


제어신호가 Ex -> MEM -> WB 거치면서 각자에 필요한 정보는 쓰고 나머지는 다음꺼에 전달 하는방식



완성된 MIPS 파이프라인





Forward의 필요성 찾는 법

파이프 라인(pipeline)에서 데이터 해저드(data hazard)를 방지하기 위한 방법 중 하나인 "전달 필요성 감지(Detecting the Need to Forward)"

  • 데이터 해저드란 레지스터에 저장된 값이 다음 명령어에서 사용될 때, 이전 명령어로부터 값이 로드(load)되는 시간차로 인해 오류가 발생하는 상황을 말합니다. 이를 방지하기 위해서는 이전 명령어로부터 값이 로드되기 전에 다음 명령어에서 필요한 값을 미리 전달해 주는 것이 필요합니다.
  • 전달 필요성 감지는 파이프 라인에서 이전 명령어에서 필요한 값을 다음 명령어로 빠르게 전달하기 위해, ID/EX 파이프 라인 레지스터에 저장된 레지스터 번호(register number)를 사용합니다.
    • 예를 들어, ID/EX.RegisterRs1은 ID/EX 파이프 라인 레지스터에 저장된 Rs1 레지스터의 번호를 나타냅니다.
    • EX 단계에서 사용되는 ALU 오퍼랜드(ALU operand) 레지스터 번호는 ID/EX.RegisterRs1과 ID/EX.RegisterRs2에서 제공됩니다.
  • 데이터 해저드가 발생하는 경우, 전달 필요성 감지
    • EX/MEM 파이프 라인 레지스터
    • MEM/WB 파이프 라인 레지스터
    • 필요한 값을 가져와 다음 명령어에서 사용될 값을 미리 전달합니다.
      • 이 때, 데이터가 전달되는 파이프 라인 레지스터는 EX/MEM 레지스터 또는 MEM/WB 레지스터 중 하나입니다.

스크린샷 2023-05-14 오후 10 57 15

빨간 부분 = EX/MEM 파이프 라인 레지스터, MEM/WB 파이프 라인 레지스터


forwarding 동작 과정

값을 전달하기 위해 EX/MEM 파이프 라인 레지스터 또는 MEM/WB 파이프 라인 레지스터에서 값을 가져옵니다. 그러나 이 값은 다음 명령어에서 실제로 레지스터에 쓰여질 필요가 있는 값이어야 합니다.

  • 따라서 전달이 필요한 값이 있는지 확인하기 위해, forwarding instruction(전달하는 명령어)가 레지스터에 쓰기(write)를 수행하는지 여부를 확인합니다.
  • 이를 위해 EX/MEM.RegWrite와 MEM/WB.RegWrite 두 개의 레지스터가 사용됩니다.
    • 만약 forwarding instruction이 레지스터에 쓰기를 수행하지 않는다면, 전달이 필요하지 않습니다.
  • 또한, forwarding instruction이 레지스터 0(x0)에 쓰기를 수행하는 경우 전달이 필요하지 않습니다.
  • 따라서 EX/MEM.RegisterRd와 MEM/WB.RegisterRd가 0이 아닌 경우에만 전달이 필요합니다.

스크린샷 2023-05-09 오후 10 18 12

스크린샷 2023-05-09 오후 10 18 45


EX hazard(Execute stage hazard)


  • EX/MEM 레지스터에 쓰기가 발생하고(EX/MEM.RegWrite), 전달할 레지스터 번호(EX/MEM.RegisterRd)가 0이 아니고(ID/EX.RegisterRs1), 이전 명령어에서 사용하는 레지스터 번호(ID/EX.RegisterRs1)와 같은 경우, ForwardA 값에 10을 할당합니다.
  • EX/MEM 레지스터에 쓰기가 발생하고(EX/MEM.RegWrite), 전달할 레지스터 번호(EX/MEM.RegisterRd)가 0이 아니고(ID/EX.RegisterRs2), 이전 명령어에서 사용하는 레지스터 번호(ID/EX.RegisterRs2)와 같은 경우, ForwardB 값에 10을 할당합니다.

MEM hazard(Memory stage hazard)


  • MEM/WB 레지스터에 쓰기가 발생하고(MEM/WB.RegWrite), 전달할 레지스터 번호(MEM/WB.RegisterRd)가 0이 아니고(ID/EX.RegisterRs1), 이전 명령어에서 사용하는 레지스터 번호(ID/EX.RegisterRs1)와 같은 경우, ForwardA 값에 01을 할당합니다.
  • MEM/WB 레지스터에 쓰기가 발생하고(MEM/WB.RegWrite), 전달할 레지스터 번호(MEM/WB.RegisterRd)가 0이 아니고(ID/EX.RegisterRs2), 이전 명령어에서 사용하는 레지스터 번호(ID/EX.RegisterRs2)와 같은 경우, ForwardB 값에 01을 할당합니다.

이러한 전달 조건을 통해, 데이터 해저드가 발생했을 때 필요한 값을 레지스터에서 가져오지 않고, 파이프라인의 이전 단계에서 바로 전달하여 문제를 해결할 수 있습니다.


Double Data Hazard

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


더블 데이터 하자드(Double Data Hazard)란 하나의 레지스터에 여러 개의 명령어가 접근할 때 발생하는 데이터 위험 상황을 말합니다. 위의 명령어 시퀀스(add x1,x1,x2, add x1,x1,x3, add x1,x1,x4)의 경우, 이전의 명령어가 다음 명령어에 영향을 주는 데이터 위험 상황이 두 번 발생합니다. 이런 경우 더 최근의 명령어의 결과를 사용해야 합니다.


이를 위해 MEM stage의 forwarding 조건을 수정합니다. 이 조건은, EX stage의 forwarding 조건이 만족하지 않는 경우에만 수행됩니다.


수정된 forwarding 조건은 다음과 같습니다.


  • MEM hazard:
    • 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
    • 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.RegisterRs2)) and (MEM/WB.RegisterRd = ID/EX.RegisterRs2)) ForwardB = 01

Load-Use Hazard Detection (로드-유스 하저드 검출)

스크린샷 2023-05-14 오후 11 03 23


이 부분에서는 Load 명령과 이후에 그 값을 사용하는 명령어들 간의 데이터 위험을 검출하는 내용입니다. Load 명령이 수행되기 전까지는 해당 메모리 주소의 값을 알 수 없기 때문에, Load 명령 다음에 그 값을 사용하는 명령어들이 수행될 때 문제가 발생할 수 있습니다.


검출하는 방법은, ID(해독) 단계에서 사용하는 레지스터 번호(IF/ID.RegisterRs1, IF/ID.RegisterRs2)와 이전 명령어의 실행 결과로 레지스터가 업데이트 되는지 여부(ID/EX.MemRead, ID/EX.RegisterRd)를 비교합니다. 만약 이전 명령어가 Load이고, 다음 명령어에서 사용하는 레지스터 번호(IF/ID.RegisterRs1, IF/ID.RegisterRs2)가 이전 명령어에서 값을 로드해오는 레지스터(ID/EX.RegisterRd)와 같다면, Load 명령이 수행될 때까지 대기해야 합니다.

스크린샷 2023-05-14 오후 11 04 18


로드-사용 해저드 감지

  • 사용 명령어가 ID 단계에서 해석될 때 확인합니다.
  • ALU 피연산자 레지스터 번호는 ID 단계에서 다음과 같이 제공됩니다.
    • IF/ID.RegisterRs1, IF/ID.RegisterRs2
  • 다음 조건을 만족할 때 로드-사용 해제드가 발생합니다.
    • ID/EX.MemRead and ((ID/EX.RegisterRd = IF/ID.RegisterRs1) or (ID/EX.RegisterRd = IF/ID.RegisterRs2))
  • 해저드가 감지되면 스톨을 하고 버블을 삽입합니다.

Stall the Pipeline (파이프라인 정체)


로드 명령과 이후 명령어 간의 데이터 위험을 검출했을 때, 파이프라인에서 대기해야 합니다. 이를 위해 다음과 같은 과정을 수행합니다.


  1. ID/EX 레지스터의 제어 값을 0으로 설정하여, EX, MEM 및 WB는 nop(작동 없음)을 수행
  2. PC(Program Counter)와 IF/ID 레지스터를 업데이트하지 않고, 현재 명령어를 다시 해독하도록 합니다.
  3. 다음 명령어를 다시 가져오기 전에, 1 사이클 동안 대기합니다. 이 동안에 Load 명령의 결과 값을 MEM에서 읽어올 수 있습니다.
  4. 그 후, 다시 파이프라인을 수행하며, 이전 명령어에서 읽어온 값을 EX 단계에서 바로 사용할 수 있도록 전달합니다.

스톨과 성능

  • 스톨은 성능을 감소
    • 그러나 올바른 결과를 얻기 위해서는 필수적
  • 컴파일러는 위험과 스톨을 피하기 위해 코드를 조정
    • 파이프라인 구조에 대한 지식이 필요합니다.




Branch Hazards


스크린샷 2023-05-14 오후 11 14 42


만약 분기 결과가 MEM 단계에서 결정된 경우, 해당 명령어들을 플러시합니다(제어 값을 0으로 설정합니다).


분기 명령어는 IF 단계에서 가져온 후 ID 단계에서 분기 대상을 계산하고, EX 단계에서 분기 대상을 비교하여 분기를 수행합니다. 그러나 분기 대상이 메모리에서 로드되어야 하는 경우, MEM 단계에서 분기가 결정됩니다. 이 경우, 이전 단계에서 이미 로드가 시작되었기 때문에 분기 결과가 나올 때까지 파이프라인의 앞 부분에 있는 명령어들은 계속 실행됩니다.


하지만 분기 결과가 나오면, 해당 분기가 수행되지 않는 경우 플러시가 발생합니다. 이때, 파이프라인에 있는 명령어들을 취소하고(ID/EX 레지스터의 제어 값을 0으로 설정), 프로세서는 분기 대상 주소로 다시 돌아가 새로운 명령어를 가져옵니다. 이렇게 함으로써, 분기 명령어 다음에 오는 명령어들이 잘못된 결과를 출력하는 것을 방지할 수 있습니다.


분기 지연 시간을 줄이는 방법

하드웨어를 ID 단계로 이동하여 분기 결과를 결정합니다.
분기 대상 주소 더하기기
레지스터 비교기


예시: 분기가 수행되는 경우


36: sub x10, x4, x8
40: beq x1, x3, 16 // PC 상대적 분기, 40+16*2 = 72
44: and x12, x2, x5
48: orr x13, x2, x6
52: add x14, x4, x2
56: sub x15, x6, x7
...
72: ld x4, 50(x7)


위 코드에서, 분기 대상 주소를 계산하는 주소 더하기와 분기 대상 레지스터를 비교하는 레지스터 비교기를 ID 단계로 이동시키면 분기 결과를 더 빠르게 결정할 수 있습니다. 이렇게 하면, 분기 대상 주소를 계산하는 더하기기와 레지스터 비교기가 ID 단계에서 동작하므로, EX 단계에서 이를 수행하는 것보다 훨씬 빠릅니다. 따라서, 분기 결과를 결정하기 위해 파이프라인에서 불필요한 대기 시간이 줄어들어 전체적인 성능이 향상됩니다.


스크린샷 2023-05-14 오후 11 19 55

스크린샷 2023-05-14 오후 11 20 17


Dynamic Branch Prediction

깊고 슈퍼스칼라 파이프라인에서는 분기 지연 시간이 더 큰 문제가 됩니다. 이를 해결하기 위해 동적 분기 예측이 사용됩니다.


동적 예측 사용 방법

  • 분기 예측 버퍼(분기 이력 테이블)를 사용합니다.
  • 최근 분기 명령의 주소로 인덱싱됩니다.
  • 결과(분기 수행/미수행)를 저장합니다.
  • 분기 실행 시,
    • 테이블을 확인하고 이전 예측 결과가 같으면 그대로 실행합니다.
    • 결과가 다르면, 예측을 뒤집고 다시 실행합니다.
    • 분기 목적지까지 fetch 할 때는 예측 결과에 따라 fall-through나 분기 대상지에서 fetch를 시작합니다.
    • 예측이 틀렸을 경우, 파이프라인을 지우고 다시 예측을 수행합니다.

이렇게 동적 분기 예측을 사용하면, 정적 분기 예측보다 더욱 정확한 예측이 가능하며, 분기 예측 실패에 따른 지연 시간을 줄일 수 있습니다.


1-bit predictor


1-bit predictor는 이러한 상황에서 예측을 잘못하는 경우가 많습니다. 예를 들어, 내부 루프에서 마지막 반복에서 분기를 수행하고 다음 반복에서 첫 번째 분기를 수행하는 경우, 1-bit predictor는 분기를 예측을 두 번 틀리게 됩니다.


내부 루프에서 마지막 분기에서는 분기가 발생하지 않을 것으로 예측하고, 이로 인해 분기를 제대로 수행하지 못합니다. 그러나 다음 반복에서 첫 번째 분기가 발생할 것으로 예측하면, 실제로 분기가 발생하지 않으므로 다시 한 번 예측을 잘못하게 됩니다.


따라서 이러한 경우를 예측하기 위해 1-bit predictor만으로는 부족합니다. 이를 보완하기 위해서는 더 복잡한 예측 방법이 필요합니다. 예를 들어, 2-bit predictor를 사용하면 이러한 상황에서도 예측 정확도를 높일 수 있습니다.


2-bit predictor

2-bit predictor는 1-bit predictor와는 달리 두 번 연속으로 예측을 실패한 경우에만 예측을 변경합니다. 이전 상태와 현재 상태를 기반으로 예측을 수행하며, 예측 상태를 2-bit counter에 저장합니다.


예측 상태에는 다음과 같은 세 가지 상태가 있습니다.


  • Strongly taken (11): 분기가 발생할 것으로 예측되고, 이전에도 분기가 발생했을 경우
  • Weakly taken (10): 분기가 발생할 것으로 예측되고, 이전에는 분기가 발생하지 않았을 경우
  • Weakly not taken (01): 분기가 발생하지 않을 것으로 예측되고, 이전에는 분기가 발생했을 경우
  • Strongly not taken (00): 분기가 발생하지 않을 것으로 예측되고, 이전에도 분기가 발생하지 않았을 경우

예측이 정확한 경우에는 2-bit counter를 그대로 유지하며, 예측이 실패한 경우에는 2-bit counter를 업데이트합니다. 두 번 연속으로 예측을 실패한 경우에만 예측을 변경하기 때문에, 이전 상태에 따라서 예측이 자주 변경되는 문제를 해결할 수 있습니다. 이를 통해 예측 정확도를 향상시킬 수 있습니다.


동적 분기 예측을 사용하더라도, 분기 대상 주소를 계산해야합니다. 분기가 발생하면, 대상 주소를 계산해야하므로 한 사이클의 지연이 발생합니다.

분기 대상 버퍼 (Branch Target Buffer)를 사용하면 대상 주소를 캐시에 저장하여 계산 지연을 최소화할 수 있습니다. 이 캐시는 PC (프로그램 카운터)로 색인화되며 분기 명령이 가져올 때 캐시에 저장됩니다. 만약 분기가 예측된 대로 발생하고, 캐시에서 해당 분기의 대상 주소가 검색된 경우, 대상 주소를 즉시 가져올 수 있습니다. 이를 통해, 분기 대상 주소를 계산하는 시간을 줄이고 성능을 향상시킬 수 있습니다.






Processor

명령어 수준 병렬성(ILP)은 병렬 처리를 위해 여러 명령어를 동시에 실행하는 기술입니다.

파이프라이닝(Pipelining)은 여러 명령어를 병렬로 실행하는 것을 의미합니다. ILP를 증가시키기 위해 다음과 같은 방법을 사용할 수 있습니다.


더 깊은 파이프라인(더 많은 파이프라인 단계)

+ 각 단계의 작업량이 줄어듦 => 클럭 주기가 짧아짐

다중 실행(Multiple issue) - issue : 뭔가를 실행

  • 파이프라인 단계를 복제하여 여러 개의 파이프라인을 생성하고 클럭 주기마다 여러 개의 명령어를 동시에 시작하는 기술
    • 위를 통해 CPI<1 , 소스 명령어당 사이클(IPC), IPC(Instructions Per Cycle)를 증가
      • 예: 4GHz 4-way 다중 실행
        • 한 클럭 주기마다 최대 4개의 명령어를 시작
        • 1초 동안 4억 개의 클럭 주기가 있으므로, 이 시스템은 매 초에 최대 16억 개의 명령어를 실행
        • BIPS(Billions of Instructions Per Second)로 표현하면 16 BIPS
        • 최대 CPI는 0.25이고 최대 IPC는 4
      • 16 BIPS, peak CPI = 0.25, peak IPC = 4
  • 하지만 의존성으로 인해 실제로는 이 값이 감소합니다.
    • 의존성 : 한 명령어의 실행 결과가 다른 명령어에 영향을 미치는 상황을 말하며, 이로 인해 명령어들을 순차적으로 실행해야 하는 경우가 발생하여 병렬성을 제한
  • 따라서, 다중 실행을 통해 ILP를 증가시킬 수 있지만, 의존성으로 인해 실제 성능은 이론적인 최고 성능보다는 낮아질 수 있습니다.



다중 실행(Multiple issue)


정적 다중 실행(Static multiple issue)

  • 컴파일러가 함께 실행되어야 할 명령어를 그룹화하고, 이를 "발행 슬롯(issue slots)"에 패키징하는 방식
  • 컴파일러는 위험(hazard)을 감지하고 피하기 위해 명령어를 조정
  • 이 방식은 컴파일 시점에서 명령어들을 사전에 그룹화하여 다중 실행을 구현
  • 정적 다중 실행은 컴파일러에 의해 사전에 최적화되기 때문에 실행 중에는 큰 비용이 들지 않습니다. 그러나 이 방식은 컴파일러의 지원이 필요하며, 컴파일러가 모든 가능한 위험 상황을 파악하고 처리

동적 다중 실행(Dynamic multiple issue)

  • CPU가 명령어 스트림을 조사하고 각 클럭 주기마다 발행할 명령어를 선택하는 방식
    • 컴파일러는 명령어를 재배치함으로써 다중실행을 구현하였다면 CPU는 실행 시점에서 고급 기법을 사용하여 위험을 해결
  • 실행 중에 명령어를 선택하고 위험을 해결하기 때문에 CPU에서 추가적인 하드웨어와 소프트웨어 지원이 필요
  • CPU는 실행 중에 명령어를 조사하고 위험을 처리하기 위해 고급 기법을 사용합니다. 이 방식은 컴파일러의 도움을 받을 수 있지만, CPU 자체에서 동적으로 명령어를 선택하고 처리

❓정적 다중 실행은 컴파일러와 하드웨어 간의 협력이 필요하며, 동적 다중 실행은 CPU가 동적으로 명령어를 선택하고 처리하는 데에 더 많은 기능이 필요합니다.




Speculation

  • Speculation은 명령어에 대해 "추측"을 하고 이를 실행하는 기술
  • 가능한 빨리 동작을 시작하며, 추측이 맞는지 확인합니다.
  • 추측이 맞으면 동작을 완료하고, 그렇지 않으면 되돌아가서 올바른 작업을 수행합니다.
  • 실행 속도를 높이기 위해 사용되는 기술이지만, 추측이 틀렸을 경우 롤백하는 오버헤드가 발생할 수 있습니다.
  • 추측이 정확성과 성능 간의 균형을 유지하는 것이 중요

예를 들어, 분기(branch) 결과에 대해 추측할 수 있습니다. 분기가 발생할 때 가능한 경로를 추측하고, 이를 기반으로 동작을 시작합니다. 그런 다음 실제로 경로를 따르는지 확인합니다. 만약 추측이 맞다면 동작을 완료하고, 추측이 틀렸다면 롤백(roll-back)하여 올바른 동작을 수행합니다.


또한, 저장소(store) 이후에 로드(load)를 추측할 수도 있습니다. 저장소 이후에 바로 로드를 수행하여 작업을 가속화합니다. 그러나 만약 저장소의 위치가 업데이트되었다면 추측이 틀렸다는 것을 알 수 있습니다. 이 경우 롤백하여 이전에 저장된 값으로 올바르게 동작을 수행합니다.


Compiler/Hardware Speculation

컴파일러는 명령어를 재배치할 수 있습니다. 예를 들어, 분기 명령어 이전에 로드 명령어를 이동시킬 수 있습니다. 또한, 잘못된 예측으로부터 복구하기 위해 "체크" 및 "수정" 명령어를 포함할 수도 있습니다.


하드웨어는 실행할 명령어를 미리 예측하여 앞서 실행할 수 있습니다. 결과를 버퍼에 저장하여 실제로 필요할 때까지 유지한 후 잘못된 예측이 발생한 경우에는 버퍼를 비웁니다.


Speculation and Exceptions

예외가 예측 실행되는 명령어에서 발생하는 경우에는 어떻게 될까요? 예를 들어, 널 포인터 체크 이전에 예측적으로 로드 명령어가 실행되고 예외가 발생한다면 어떻게 될까요?


정적 추론 (Static speculation)의 경우, 예외를 지연시키는 ISA (명령어 집합 구조) 지원을 추가할 수 있습니다. 즉, 예외가 발생하는 명령어를 실제로 실행하기 전까지 예외를 보류시킴으로써 예외를 처리합니다.


동적 추론 (Dynamic speculation)의 경우, 예외를 명령어 완료까지 버퍼링할 수 있습니다. 그러나 명령어 완료가 발생하지 않을 수도 있습니다. 명령어가 실행 중에 예외가 발생한 경우, 이를 버퍼에 저장해두고 나중에 예외 처리를 수행할 수 있습니다. 그러나 이 경우 명령어 완료가 발생하지 않으면 예외 처리도 이루어지지 않을 수 있습니다.




Static Multiple Issue

정적 다중 수행 (Static Multiple Issue)은 컴파일러가 명령어를 "발행 패킷"으로 그룹화하는 것을 말합니다. 발행 패킷은 한 사이클에 발행될 수 있는 명령어들의 그룹입니다. 이 그룹은 파이프라인 리소스에 필요한 것으로 결정됩니다.


  • 발행 패킷은 매우 긴 명령어로 생각할 수 있습니다.
    • 즉, 동시에 실행되는 여러 작업을 지정합니다.
    • 매우 긴 명령어 워드 (Very Long Instruction Word, VLIW)로 알려져 있음
      • VLIW는 하나의 명령어 안에 여러 개의 동시 연산을 포함하는 명령어 형식
      • 컴파일러는 발행 패킷을 구성함으로써 이러한 VLIW 형식을 활용하여 여러 개의 연산을 동시에 실행할 수 있는 기회를 최대화하려고 합니다.

정적 다중 수행을 스케줄링하는 경우 컴파일러는 몇 가지 혹은 전체적인 하자드(hazard)를 제거

  1. 명령어를 발행 패킷으로 재배열
    • 컴파일러는 패킷 내에서 의존성이 없도록 명령어를 재배열
    • 이렇게 함으로써 한 사이클에 여러 개의 명령어를 동시에 실행
  2. 패킷 간에 일부 의존성이 있을 수도 있음
    • 발행 패킷 간에 의존성이 있는 경우, 컴파일러는 이를 처리하기 위해 적절한 방법을 사용
      • 일반적으로 이러한 의존성을 최소화하기 위해 패킷 내부에서 가능한 한 많은 독립적인 작업을 배치하려고 노력
  3. 필요한 경우 nop(No Operation) 명령어로 패킷을 패딩
    • 발행 패킷의 크기를 일정하게 유지하기 위해 필요한 경우 nop 명령어를 삽입할 수도 있습니다. 이는 패킷 내에서 실행 가능한 작업이 부족한 경우에 사용될 수 있습니다.

즉, 컴파일러는 의존성을 최소화하고 가능한 한 많은 작업을 동시에 실행할 수 있도록 명령어를 재배열하고 패킷을 구성합니다. 필요한 경우에는 nop 명령어로 패킷을 패딩하여 일정한 크기를 유지합니다.


RISC-V Static Dual Issue

Static Dual Issue는 RISC-V 아키텍처에서 지원하는 특정한 구현 방식
실제 구현부를 보면 dual port로 구분되어 보임.

스크린샷 2023-05-16 오후 8 56 45


이 구현 방식에서는 명령어들이 두 개씩 그룹화되어 실행됩니다.

  1. 두 개의 명령어 패킷:
    • 명령어들은 두 개씩의 명령어로 구성된 패킷에 포함
    • 이러한 패킷은 한 번에 동시에 실행(첫번째는 ALU/branch를 수행, 두번째는 Load/store 수행)
    1. ALU/분기 명령어
      • 패킷 내에는 ALU(산술 논리 연산)나 분기를 수행하는 명령어가 포함됩니다.
      • ALU 명령어는 덧셈, 뺄셈, 비트 연산 등을 수행하며, 분기 명령어는 조건에 따라 프로그램의 흐름을 제어합니다.
    2. 로드/스토어 명령어
      • 패킷 내의 다른 명령어는 로드나 스토어 명령어
      • 로드 명령어는 메모리에서 데이터를 가져오고, 스토어 명령어는 데이터를 메모리에 기록합니다.
  2. 64비트 정렬
    • 패킷 내의 명령어들은 64비트 경계에 정렬
    • 이러한 정렬은 메모리 접근의 효율성을 높이고 정렬 관련 문제를 방지하기 위해 필요
  3. 실행 순서
    • ALU/분기 명령어는 로드/스토어 명령어보다 먼저 실행
      • 이렇게 함으로써 로드/스토어 명령어들이 앞선 명령어의 연산 결과에 의존할 수 있도록 합니다.
    • 사용되지 않는 명령어는 nop으로 채움

스크린샷 2023-05-16 오후 9 00 44


Dual-Issue

이중 수행을 지원하는 구현 방식
이를 통해 더 많은 명령어를 병렬로 실행할 수 있게 됩니다.


그러나 이로 인해 다음과 같은 하자드(hazard)가 발생할 수 있습니다

  1. EX 데이터 하자드 (EX data hazard)
    • 단일 수행의 경우 포워딩(forwarding)을 사용하여 스톨(stall)을 회피할 수 있습니다.
    • 그러나 이중 수행에서는 동일한 패킷 내에서 ALU 연산 결과를 로드/스토어에 사용할 수 없습니다.
      • add $t0, $s0, $s1
        load $s2, 0($t0)
        • 위 같은 명령어에서는 두 개의 명령어를 두 개의 패킷으로 나눠야 하므로 사실상 스톨이 발생하게 됩니다.
  2. 로드-사용 (Load-use hazard)
    • 로드 명령어의 경우 사용 연산과의 의존성으로 인해 여전히 한 사이클의 지연이 발생합니다. 그러나 이제는 두 개의 명령어가 동시에 실행되기 때문에 로드-사용(hazard)의 영향이 더 커집니다.

이러한 하자드를 해결하기 위해서는 더 공격적인 스케줄링이 필요합니다. 즉, 컴파일러는 명령어의 순서를 조정하여 하자드를 최소화하고 가능한 한 많은 명령어를 병렬로 실행할 수 있도록 해야 합니다.


스크린샷 2023-05-16 오후 9 04 24


  • dual issue
    • 각의 명령어는 Load/Store 단계, ALU/Branch 단계 등에서 처리
    • instruction scheduling
      • "lw $t0, 0($s1)"은 메모리에서 데이터를 읽어와 레지스터($t0)에 저장하는 명령어
        • 파이프라인에서 Load/Store 단계에서 처리되기에 다른 명령어들과 충돌할 가능성이 있음.
        • 이 명령어는 이전에 처리된 명령어와 다음 명령어들과 최대한 충돌하지 않도록 스케줄링
      • lw 전에 alu연산은 불가하다. 따라서 첫 싸이클에서는 lw가 먼저 진행
      • sw를 뒤로 보내는 대신 offset을 4bit 추가하기(addi $s1, $s1,–4)
      • addi 명령을 먼저 실행 가능하고 ALU 연산을 하는동안 lw의 한 사이클 기다리는 부분을 nop이 아닌 명령어를 채우는 것이 가능(addu $t0, $t0, $s2)

마지막으로, 이미지에서는 IPC(Instructions Per Cycle)이 계산되는 과정도 보여줍니다. IPC는 한 사이클에서 처리된 명령어의 개수를 나타내며, 이 예시에서는 5개의 명령어가 4개의 사이클에서 처리되었으므로 IPC는 1.25가 됩니다.




루프 언롤링 (Loop Unrolling 또는 Loop Unwinding)

병렬성을 더욱 노출시키기 위해 루프 본문을 복제하는 기법


원래의 루프 코드
for(int i=N; i>0; i--) { //addi, bne
    a = A[i];            //lw
    a += b;              //addu
    A[i] = a;            //sw
}

언롤링된 루프 코드
for(int i=N; i>0; i-=2) {
    a = A[i];
    a += b;
    A[i] = a;
    a = A[i-1];
    a += b;
    A[i-1] = a;
}

for(int i=N; i>1; i-=2) {
    a = A[i];
    c = a + b;
    A[i] = c;
    a2 = A[i-1];
    c2 = a2 + b;
    A[i-1] = c2;
}
  • 루프 언롤링은 원래 루프에서 한 번의 반복문을 두 번의 반복문으로 분리하여 실행
    • 한 번에 두 개의 원소를 처리
    • 루프 본문의 명령어들이 서로 의존하지 않아 병렬성을 더욱 높임
      • 실행 단계 간의 데이터 의존성을 줄여 성능을 향상
    • 또한 두번째 언롤링된 루프 코드는 아래의 특징이 있음
      • 첫 번째 반복문은 원래의 루프와 동일하게 동작하며, 두 번째 반복문은 첫 번째 반복문과 독립적으로 병렬로 실행(즉, 서로 겹치지 않기에 윗쪽 3문장과 아랫쪽 3문장은 병렬로 실행 가능)



정리

루프 언롤링 (Loop Unrolling 또는 Loop Unwinding)은 루프의 제어 오버헤드를 감소시키는 기법

  • bne 명령어의 실행 횟수를 N에서 N/2로 줄이는 등의 효과
    • branch의 개수가 줄어듦
  • 루프의 복제본마다 다른 레지스터를 사용하여 병렬로 실행
    • register renaming(실행할때 마다 레지스터를 달리 사용해 병렬로 동작할 수 있도록 함)
    • 루프에서 발생하는 반복 종속성을 피함
  • cpu한테 좋음

루프 언롤링 예시

IPC (Instructions Per Cycle) = 14/8 = 1.75 이는 2에 가까워지기는 하지만 레지스터와 코드 크기의 비용이 발생합니다.


- ALU/branch Load/store cycle
Loop: addi $s1, $s1,–16 lw $t0, 0($s1) 1
nop lw $t1, 12($s1) 2
addu $t0, $t0, $s2 lw $t2, 8($s1) 3
addu $t1, $t1, $s2 lw $t3, 4($s1) 4
addu $t2, $t2, $s2 sw $t0, 16($s1) 5
addu $t3, $t4, $s2 sw $t1, 12($s1) 6
nop sw $t2, 8($s1) 7
bne $s1, $zero, Loop sw $t3, 4($s1) 8

RISC-V에서 RAW와 WAR는 명령어 종속성(dependency)을 나타내는 개념

  1. RAW (Read After Write) RAW 종속성은 한 명령어가 다른 명령어로부터 값을 읽는 경우 발생
    • 즉, 이전 명령어가 레지스터에 값을 기록한 후에 해당 값을 읽는 다음 명령어가 있는 경우 RAW 종속성이 형성
add x1, x2, x3 // R1 = R2 + R3 
sub x4, x1, x5 // R4 = R1 - R5

두 번째 명령어에서 R1의 값을 사용하기 전에 첫 번째 명령어가 R1에 값을 쓰기 때문에 RAW 종속성이 발생합니다. 이러한 종속성은 명령어 실행 순서에 따라 올바른 결과를 얻기 위해 조정되어야 합니다.


  1. WAR (Write After Read) WAR 종속성은 한 명령어가 다른 명령어로부터 값을 읽은 후에 그 값을 덮어쓰는 경우 발생
  • 이전 명령어가 값을 읽은 후에 해당 값을 변경하는 다음 명령어가 있는 경우 WAR 종속성이 형성
lw x1, 0(x2) // R1 = Memory[R2 + 0] 
add x2, x1, x3 // R2 = R1 + R3

첫 번째 명령어에서 R1의 값을 읽은 후 두 번째 명령어에서 R1의 값을 변경하므로 WAR 종속성이 발생합니다. 이러한 종속성은 명령어 실행 순서에 따라 정확한 결과를 얻기 위해 조정되어야 합니다.


RAW와 WAR 종속성은 파이프라인 처리에 영향을 미치고, 적절한 종속성 해결 기법(예: 파이프라인 스톨, 데이터 forwarding 등)을 사용하여 이러한 종속성을 처리하고 프로그램의 정확성과 성능을 보장합니다.


⚡️ 파이프라이닝

  • 연산을 겹치는 행위

⚡️multiple issue

  • 파이프라이닝이 된 상태에서 파이프라인의 수를 늘리는것
  • 동시에 파이프라인을 여러개 돌림



동적 다중 실행 (Dynamic Multiple Issue)

"슈퍼스칼라" 프로세서에서 사용되는 기술
CPU가 각 사이클마다 몇 개의 명령어를 실행할지 결정하는 방식으로 동작합니다. 이를 통해 구조적 및 데이터 위험을 피할 수 있습니다.

  • 컴파일러 스케줄링을 필요하지 않음(그렇다고 쓸모없지 않음, 도움은 됨)
  • CPU가 프로그램의 의미론을 보장하기 때문에 도움이 될 수 있음
    • CPU가 구조적 및 데이터 위험을 피하면서 명령어를 동시에 실행함으로써 성능을 향상
    • CPU는 여러 개의 명령어를 한 사이클에 동시에 발행할 수 있도록 동적으로 결정
    • 이를 통해 명령어의 병렬성을 최대한 활용하여 실행 속도를 향상

동적 파이프라인 스케줄링

CPU가 명령어를 순서대로 레지스터에 기록하면서도 명령어를 순서에 상관없이 실행하도록 허용
이를 통해 대기 상태를 피하고 성능을 향상시킬 수 있음

lw $t0, 20($s2) // R1 = Memory[R2 + 20] 
addu $t1, $t0, $t2 // R3 = R1 + R2 
sub $s4, $s4, $t3 // R5 = R4 - R3 
slti $t5, $s4, 20 // R6 = (R4 < 20) ? 1 : 0
  • 동적 파이프라인 스케줄링을 사용하면 lw 명령어가 대기 중인 동안에도 addu 명령어를 실행
  • 명령어의 실행 순서와 상관없이 명령어를 최대한 동시에 실행하여 성능을 향상
  • 이는 명령어의 발행 순서와는 다른 순서로 명령어를 실행할 수 있다는 것을 의미
    • Out Of Order : instructions can be executed in different orders than they are fetched
  • 하지만 결과를 순서대로 레지스터에 기록해야합니다.
    • 즉, 명령어가 순서대로 발행되었다고 가정하고, 결과는 순서대로 레지스터에 기록됩니다.
    • 이를 통해 프로그램의 의미론을 보장하면서 명령어 실행의 유효성을 유지할 수 있습니다.

스크린샷 2023-05-16 오후 9 29 07


먼저, "레지스터 쓰기를 위한 버퍼를 재정렬한다"는 말은 CPU 내부의 레지스터에 대한 쓰기 작업을 조정하고 최적화하는 것을 의미합니다. 일반적으로 CPU는 명령어들을 순차적으로 실행하는 것이 아니라 동시에 여러 개의 명령어를 동시에 처리하려고 합니다. 이때 레지스터에 대한 쓰기 작업을 효율적으로 조정하면 CPU 성능을 향상시킬 수 있습니다.

"종속성을 유지하면서 재정렬한다"는 말은 명령어들 간에 서로 의존 관계가 있는 경우에도 재정렬 작업을 수행하되, 의존성을 유지하여 올바른 실행 순서를 보장한다는 의미입니다. 이를 통해 CPU는 명령어들을 가능한 동시에 실행하면서도 프로그램의 의미를 올바르게 해석할 수 있습니다.

또한, "대기 중인 피연산자를 보유하고, 결과는 대기 중인 예약 스테이션으로도 전송된다"는 말은 아직 필요한 피연산자들이 준비되지 않은 명령어들을 기다리면서 해당 피연산자들을 저장하고, 연산이 완료되면 해당 결과를 기다리고 있는 다른 명령어들이 사용할 수 있도록 전달한다는 의미입니다. 이를 통해 명령어들 간의 의존성을 처리하면서 CPU의 처리량을 향상시킬 수 있습니다.

마지막으로, "발급된 명령에 대한 피연산자를 제공할 수 있다"는 말은 발급된 명령어들이 필요로 하는 피연산자들을 제공할 수 있는 기능을 갖추고 있다는 의미입니다. 이를 통해 CPU는 실행 중인 명령어들이 필요로 하는 데이터에 빠르게 접근하여 지연시간을 최소화하고, 명령어들을 더 효율적으로 실행할 수 있습니다.

요약하자면, 동적 스케줄링 CPU는 명령어들을 재정렬하고 의존성을 유지하면서 효율적으로 처리하기 위한 기술

Register Renaming

  • 예약 스테이션(Reservation Stations)과 재정렬 버퍼(Reorder Buffer)를 통해 효과적으로 수행됩니다.
  • 명령어가 예약 스테이션으로 발급될 때, 해당 명령어에서 필요로 하는 피연산자가 레지스터 파일(Register File)이나 재정렬 버퍼에 이미 사용 가능한 상태인 경우, 해당 피연산자는 예약 스테이션으로 복사됩니다. 이후에는 해당 레지스터에 대한 필요성이 없으므로 레지스터의 값을 덮어쓸 수 있습니다.
  • 그러나 필요로 하는 피연산자가 아직 사용 가능하지 않은 경우, 이를 제공하기 위해 기능 장치(Function Unit)에 의해 예약 스테이션에 제공됩니다. 이 경우에는 레지스터 업데이트가 필요하지 않을 수도 있습니다.
  • 레지스터 리네이밍은 프로그램에서 동일한 레지스터를 여러 번 사용하는 상황을 처리하기 위한 기술
    • 이를 통해 명령어 간의 종속성을 관리하고, 효율적인 명령어 실행과 병렬 처리를 가능하게 합니다. 리네임된 레지스터들은 물리적인 레지스터들과 매핑되어 실제 연산을 수행하고, 리네임된 레지스터들의 값을 이용해 명령어 실행을 진행합니다.

요약하자면, 레지스터 리네이밍은 예약 스테이션과 재정렬 버퍼를 통해 피연산자를 효율적으로 할당하고, 명령어 간의 의존성을 관리하는 기술입니다. 이를 통해 CPU는 더욱 효율적으로 명령어를 실행하고 병렬 처리를 수행할 수 있습니다.


Speculation

CPU의 성능을 향상시키기 위한 기법으로, 예측된 분기나 로드를 실행함으로써 지연을 최소화하고 병렬 처리를 촉진

  • 분기 예측과 지속적인 명령어 발급(Predict branch and continue issuing)은 분기 명령어를 예측하고 해당 분기의 결과가 결정될 때까지 실행을 지속시키는 것을 의미
    • 분기 예측을 통해 CPU는 분기 명령어에 의한 지연을 최소화하고, 분기 예측이 옳았을 경우에만 명령어의 실행 결과를 확정(commit)합니다.
  • 로드 추측(Load speculation)은 로드 명령어에 대한 지연과 캐시 미스(Cache miss)를 피하기 위한 기법
    • 로드 추측은 효과적인 주소와 로드된 값에 대한 예측을 수행합니다.
    • 또한, 완료되지 않은 스토어(Store)가 있는 경우에도 로드를 먼저 수행하며, 스토어된 값은 로드 유닛으로 우회하여 전달합니다.
    • 로드 추측은 추측된 결과가 확인될 때까지 로드 명령어의 결과를 확정하지 않습니다.



동적 스케줄링(Dynamic scheduling)은 컴파일러에 의한 코드 스케줄링 대신 CPU에서 수행되는 이유

  1. 예측할 수 없는 지연: 모든 지연이나 대기 상태는 컴파일러에 의해 예측하거나 사전에 알 수 있는 것은 아닙니다. 예를 들어, 캐시 미스(cache miss)는 실행 중에 발생할 수 있는 지연으로서 상당한 시간을 소요합니다. 동적 스케줄링은 CPU가 실제 실행 시 동적으로 명령어를 스케줄하고 데이터 의존성에 따라 조정할 수 있도록 합니다.

  2. 분기와 제어 흐름: 분기문(if-else 문 또는 반복문 등)은 프로그램 실행 중에 동적으로 제어 흐름을 변경합니다. 컴파일러는 미리 분기 결과를 정확하게 예측할 수 없습니다. 동적 스케줄링은 CPU가 여러 경로를 가정하여 명령어를 예측적으로 실행하고, 실제 분기 결과에 기반하여 올바른 결과를 결정할 수 있도록 합니다.

  3. 하드웨어의 차이점: 동일한 명령어 집합 아키텍처(ISA)의 다른 구현은 대기 시간과 위험 요소에 차이가 있을 수 있습니다. 동적 스케줄링은 CPU가 사용 가능한 하드웨어 리소스를 효율적으로 활용하고 기반 마이크로아키텍처의 특성과 제약 조건에 적응할 수 있도록 합니다.


동적 스케줄링을 사용함으로써 CPU는 예측할 수 없는 지연을 최소화하고, 제어 흐름 변경에 따른 명령어 실행을 최적화하며, 하드웨어 리소스를 효율적으로 활용할 수 있습니다. 이는 컴파일러에 의한 정적 스케줄링만 의존하는 것보다 더 나은 성능과 리소스 활용을 가능하게 합니다.


다중 실행(Multiple Issue)은 작동하지만 우리가 원하는만큼 효과적이지는 않음

프로그램은 실제 종속성(dependency)을 가지고 있어 ILP(Instruction-Level Parallelism)를 제한합니다.
몇 가지 종속성은 제거하기 어렵습니다.
예를 들어, 포인터 별칭(pointer aliasing)과 같은 경우입니다.
또한, 병렬성을 드러내기 어려운 경우도 있습니다.
명령어 발행 중에 제한된 윈도우 크기로 인해 발생합니다.

  • 메모리 지연과 제한된 대역폭은 파이프라인을 가득 채우는 것이 어렵습니다.
    • 이는 파이프라인이 계속해서 실행될 수 있도록 하는 것이 어렵기 때문입니다.
  • 좋은 방식으로 실행한다면 추측(Speculation)은 도움이 될 수 있습니다.
    • 추측은 예측을 통해 실행하는 것으로, 잘 수행된다면 성능 향상에 도움이 될 수 있습니다.



Power Efficiency

전력 효율성은 현대 프로세서 설계에서 중요한 고려 사항입니다. 동적 스케줄링과 추측 기술의 복잡성은 전력 소모 증가로 이어질 수 있습니다. 이는 이러한 기능을 구현하기 위해 필요한 추가 하드웨어 구성 요소와 제어 논리로 인한 것입니다.


일부 경우에는 단일 복잡한 코어 대신 여러 개의 간단한 코어를 사용하는 것이 더 나은 전력 효율성을 제공할 수 있습니다. 작업 부하를 여러 개의 코어에 분산시킴으로써 각 코어는 더 낮은 전력 수준에서 작동할 수 있습니다. 이는 각 코어가 독립적으로 동작하므로 전체 시스템 성능을 향상시키면서 전력 소모를 줄일 수 있는 장점이 있습니다.


여러 개의 간단한 코어를 사용하는 것은 전력 효율성을 향상시키는 하나의 전략일 뿐이며, 실제로는 설계 목표와 제약 사항에 따라 다양한 방식으로 전력을 관리하고 최적화해야 합니다.


Microprocessor Year Clock Rate Pipeline Stages Issue Width Out-of-order/Speculation Cores Power
i486 1989 25MHz 5 1 No 1 5W
Pentium 1993 66MHz 5 2 No 1 10W
Pentium Pro 1997 200MHz 10 3 Yes 1 29W
P4 Willamette 2001 2000MHz 22 3 Yes 1 75W
P4 Prescott 2004 3600MHz 31 3 Yes 1 103W
Core 2006 2930MHz 14 4 Yes 2 75W
UltraSparc III 2003 1950MHz 14 4 No 1 90W
UltraSparc T1 2005 1200MHz 6 1 No 8 70W

위 표에서 "Out-of-order/Speculation"은 각 마이크로프로세서의 실행 방식을 나타내며, 해당 프로세서가 명령어를 순서대로 실행하는지 아니면 순서를 변경하거나 추측하여 실행하는지를 나타냅니다. Out-of-order/Speculation이 "Yes"로 표시된 프로세서는 실행 순서를 동적으로 변경하거나 추측하여 명령어를 병렬로 실행할 수 있습니다.


Out-of-order/Speculation 기술은 프로세서 성능을 향상시키는 데 도움이 될 수 있습니다. 순서를 변경하거나 추측하여 명령어를 병렬로 실행함으로써 유휴 시간을 줄이고 전체적인 작업량을 늘릴 수 있습니다. 이를 통해 프로세서는 더 많은 명령어를 동시에 실행할 수 있고, 전체적인 처리량과 성능이 향상될 수 있습니다.


그러나 Out-of-order/Speculation을 구현하는 데는 더 많은 하드웨어 리소스와 논리가 필요하므로 전력 소비가 증가할 수 있습니다. 이는 복잡성과 전력 효율성 사이의 트레이드오프입니다. 따라서 전력 효율성이 중요한 환경에서는 Out-of-order/Speculation을 사용하는 대신 더 간단한 프로세서 코어를 사용하는 것이 더 효율적일 수 있습니다.


따라서 Out-of-order/Speculation의 발전은 성능 향상에 기여할 수 있지만 전력 효율성 측면에서는 조심스럽게 고려되어야 합니다. 설계자는 성능과 전력 소비 간의 균형을 고려하여 최적의 솔루션을 선택할 수 있습니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'컴퓨터 구조' 카테고리의 다른 글

컴퓨터 구조 6(병렬 프로그래밍, GPU&CPU 비교)  (0) 2023.06.28
컴퓨터 구조 5(캐시)  (0) 2023.06.28
컴퓨터 구조 3(Datapath)  (0) 2023.05.03
컴퓨터 구조 2(RISC-V)  (0) 2023.05.03
컴퓨터 구조 1(구성 요소 및 CPU TIME)  (0) 2023.05.03

+ Recent posts

티스토리툴바