공사 중이지만 공사 중이지 않아서 공사해야겠다고 다짐했습니다.

static branch prediction

• branch 결과를 보기 위해 기다리지 않고 branch hazards를 해결한다.

• predict not taken: 늘 branch가 not taken한다고 예측하고 sequential instruction을 fetch한다. branch가 taken이 될 때만 멈추고 target으로 간다.

• pipeline에서 쫓아냄

• branch가 메모리에 있으면 세 개

• branch가 taken되면 instruction을 flush한다.

• branch가 MEM에 있으면 three stalls가 필요하다. (IF, ID, EX stages)

• branch가 EX에 있으면 two stalls

• branch가 ID에 있으면 one stall

• flush: machine의 state를 바꾸지 않게 모든 instruction이 no-op이 되도록 하거나 control code를 0으로 만든다. mem과 reg에 write되도록 하게 만들면 안된다. (기존에 beq 다음에 가져온 명령어를 버림고 다시 시작)

• 파이프라인을 branch destination부터 다시 시작한다.

Flushing with Misprediction(Not taken)

• taken?
  예측이 가능하기는 하지만 target 주소를 알아야한다. IF에서 계산할 때까지 시간이 걸리므로 penalty가 있다. 굳이 taken을 예측할 필요가 없다.

Branching Structures

• loop은 여러 차례 반복되므로 not taken으 방식으로 실행을 하다가 taken 하는게 효율적
• j 명령어에 대하여 항상 no-op penalty가 발생한다.
• loop 검사문이 아래에 있으면 다음 명령어는 루프를 탈출한 뒤의 명령어이다. 따라서 not taken prediction이 작동하지 않는다.

predict taken

• 항상 one stall cycle이 발생

• 처음 브랜치를 만나면 penalty를 지불해야 한다.

• 브랜치에 대한 branch target instrcution의 주소를 cache하는 소프트웨어적 방법 사용

• 어쨋든 penalty가 존재.

• 런타임에서 프로그램의 상태에 따라 결정 -> dynamic branch prediction

Dynamic Branch Prediction

• instruction stream이

• deeper pipeline: stage를 여러개로 쪼개는 방법

• superscalar: 여러개의 파이프라인 구성하여 여러개의 명령어가 동시에 실행

• 이런 환경에서는 예측이 실패할 경우 branch penalty가 굉장히 커짐

• branch prediction buffer(branch history table)

• 최근 branch instrcution address를 기록

• outcome: taken/not taken 여부 기록

• branch를 과거에 taken 했는지 안했는지 나타내는 비트가 있음(IF/ID register에 존재) (BHT)

• prediction이 맞으면 마찬가지로 옳바른 instructiond으로 가서 다시 restart

• 1% 에서 20% 사이로 실패할 확률이 감소함

• Branch Target Buffer(BTB)

• IF/ID stage에 잇음

• branch taken을 할 때 target 주소와 다음 sequential instruction을 저장하는 일종의 cache

• taken을 위해 target buffer에 taken 했을 때 instruction을 기록해두고, 다음 방문했을 때 history table이 taken이면 바로 target buffer의 명령어를 가져와서 실행, 실패하면 not taken

1-bit Prediction Accuracy

• 1-bit predictors

• 0 => not taken

• 1 => taken

• 2-bit predictor

• 10번 루프일 때 80%의 예측률(처음, 마지막 fail)

• 2-bit predictors

• 두 번 연속으로 틀리면 반대로 바꾼다.

• 이중 loop에서

• 10번 돌고 나서 탈출할 때 틀리고 다시 재방문 시 taken하여 또 맞음. 10번 중 1번만 예측이 틀리므로 10번 실행시 정확도 90%로 올릴 수 있다.

Unexpected Events in Pipeline

• control signal에 의하여 event sequnce가 바뀌는 경우를 제외하고 순차적으로 명령어를 처리한다.
• 예상치 못한 이벤트로 control flow가 변화한다.
• unexpected events
  • exception: cpu 내부에서 발생
  • interrupt: 외부의 I/0 controller에 의하여 발생

Two types of Exceptions

• interrupts: asynchronous(어디서 어떻게 생길지 모른다)
  • external events에 의하여 발생
  • 파이프라인에서 현재 진행하고 있는 instrcutions는 다 끝낸 다음에 OS interrupt handler는 뒤에 붙는다.
• traps(exception): synchronous(CPU 내부의 task로 인해 발생)
  • internal events에 의하여 발생
  • 문제를 일으키는 instruction 앞의 것은 정상적으로 실행, 중간에 문제 발생하는 instruction OS trap handler가 처리하고 서비스가 끝난 뒤에 문제를 일으키는 명령어 실행

Dealing with Exceptions

• 또다른 형태의 control hazard
  • 이전 instruction을 마침
  • 뒤에 따라오는 instruction은 flush
  • register에 exception의 cause를 적는다.
  • offending instruction의 주소를 저장
  • 서비스 루틴으로 점프해서 서비스를 받는다.
  • offending instruction부터 시작

where in the pipeline exception occur

• arithmetic overflow => EX (synchronous)
• undefined instruction => ID (synchronous)
• TLB or page fault => IF, MEM (synchronous)
• I/O service request => any (asynchronous)
• Hardware malfuncition => any (asynchronous)

Handling Exceptions

• System control coprocessor에서 managed
• 예외를 만들어내는 instruction의 PC를 저장: MIPS에서 Exception Program Counter(EPC)에 저장
• 어떤 문제가 생겼는지 기록
  • 원인 기록
  • opcode 0 -> undefined , 1 -> overflow
• handler의 주소 8000 00180로 jump

Handler Actions

• read cause and transfer to relevant handler
• determine action required
  • if restartable
    • corrective action을 행함
    • use EPC to return to program
• 아니면
  • 프로그램을 종료시킴
  • 에러 리포트, 중지

명령어를 쫓아내는 방식: mispredicted branch와 유사

• exception이 발생하면 flush out 시켜주는 control 시그널을 넣어줌, cause와register epc를 적음

PC saved in EPC register

• pc의 명령어는 handler가 해결해주기 때문에 pc + 4가 저장되어서 다음 명령어를 실행한다.

Exception Properties

1. exception 발생
2. flush out 후 epc에 write
3. epc의 번지와 cause를 기록 => 다시 epc 번지부터 시작

Handle Exceptions

• cause register: expception의 cause 기록
• epc register: offending instruction과 그것에 쓰는 control signal 기록
• exception handler에 가서 서비스를 받음 (8000 0180)
• trap인 경우에 발생하는 일

interrupt인 경우

• 외부의 처리를 요청하는 것
• 내부의 실행중인 명령어 실행하고 function 호출하듯이 interrupt service routine으로 가서 처리를 해주고 다음 명령어로 돌아온다.

multiple exceptions

• 한번에 exception 발생 가능.
• 뒤의 instructions를 cancel하고 가장 앞에 있는 exception부터 처리한다.
• precise excpetions라 부른다.

Summary

• 모던 프로세서서는 성능 때문에 파이프라이닝 채택, 이상적 CPI = 1, clock cycle이짧음
• 가장 느린 pipeline stage가 clock rate을 결정하므로 stage latency를 balanced하게 맞춰야 한다.
• hazards
  • structural => 메모리를 여러개 사용
  • data => forward 또는 stall
  • control => stall, delay decision, static and dynamic prediction
• pipeline needs exception handling

Instruction-Level Parallelism(ILP)

• to increase ILP
  • deeper pipeline
    • stage의 작업량을 줄여서 => 더 짧은 clock cycle
  • multiple issue
    • pipeline을 복사 => 여러개의 파이프라인
    • 클락 당 여러개의 명령어 동시에 start
    • CPI < 1이므로 IPC(instructions per cycle)
      • e.g. 4ghz 4-way multiple-issue
        • 16 bips(billion instruction per sec), peak cpi = 0.25, peak IPC = 4
        • ips 구하는 법 : clock rate / cpi , clock rate = 4 * 10^9, cpi = 0.25
      • dependency로 인하여 실제로는 감소한다.

Multiple Issue

• static multiple issue
  • 컴파일러가 여러개의 명령어를 내보낼 수 있도록 묶는다.
  • issue slot으로 묶는다.
  • 컴파일러가 hazard를 감지하고 회피한다.
• dynamic multiple issue
  • CPU가 instruction pool에서 동시에 실행 가능한 것들을 선발해서 내보내는 구조
  • 컴파일러는 instruction을 reordering을 하여 돕는다.
  • CPU hazards 해결

Speculation(예측해보고 맞으면 진행, 틀리면 백)

• instruction의 예측 실행(guess)를 한다.
  • 가능한 빨리 연산을 시작
• load 앞의 store: 두개가 다른 주소라 가정하고 실행
• memory access의 dependency는 실제 실행중에만 확인 가능

Compiler/hardware speculation

• compiler can reorder instructions

  • branch decision이 결정된 다음에 실행되는 것을 선실행
  • load across store: lw/sw 명령을 주소가 다르다고 가정하고 실행

• 틀리면 회복해주기 위해 fix-up instructions

• 예측 결과가 결정이 되고 필요한 시점까지 기다렸다가 버퍼에 있는 것을 써준다.

• flush buffers on incorrect speculation

Exception

• 예측 실행하고 있는 명령에서 exception이 발생한다면?
• static: 예측의 결과를 deferring을 했다가 결과가 나올 때까지 밀어둔다.
• dynamic: 하드웨어로 buffer에 넣은 뒤에 진짜로 실행이 되는건지 확인하고 exception 출력 여부 결정

static multiple issue

• instruction을 issu packet이라는 그룹으로 만들어서 pipeline에 내보낸다.
  • 필요한 pipeline resource에 의해 결정
• instruction
  • VLIW(very long instruction word): 일반적인 명령어를 묶어서 긴 명령어를 만드는 architecture

Scheduling Static Multiple Issue

• 모든(아니면 최대한 많이) hazard를 remove
  • packet 안에는 dependency가 없음
  • packet과 packet 사이에는 dependency가 존재 가능하다.
  • 전부 채우지 못하는 경우에는 no-op를 채움

MIPS with Static Dual Issue

• two-issue packets
  • alu/branch
  • load/store
  • 64bit aligned

Hazards in the Dual-Issue MIPS

• 병렬적으로 실행하므로 더 많은 hazard 발생 가능
• EX data hazard
  • add $t0, $s0, $s1
  • load $s2, 0($t0)
  • 2개의 패킷으로 쪼개서 stall이 만들어질 수 있음
• load-use hazard
  • load의 결과를 사용하는 r-type => 무조건 1 cycle stall
  • 2개의 명령어 이상의 distance를 유지해야함
• 더 aggressive scheduling이 필요하다.
• IPC 향상이 적음

loop unrolling

• loop body + loop control
• loop를 재구성
• 병렬성을 향상시키기 위해 컴파일러는 loop body를 복사한다.
  • 한 번 들어갈 때 iteration을 여러번 함.
• 각각 다른 레지스터를 사용
  • 'register renaming'
  • loop carried 'anti dependencies'라고 한다.
• IPC 향상
• 레지스터 코스트랑 코드 사이즈 증가

dynamic multiple issue

• superscaler processors: intruction-level parallelism을 구현하는 cpu
• CPU가 현재 상태에서 issue 가능한 instruction을 가지고 실행하게 만들어준다.
• structural, data hazards 같은 dependency problem 없어야 한다.
• 컴파일러 스케줄링을 도움을 받으면서 해결할수도 있음
• CPU 런타임에서 결정이 되는 것들을 해결

Dynamic pipeline scheduling

• stall을 피하기 위해 instruction을 out of order(컴파일러에서 적힌 명령어 실행 순서를 바꿔서)로 실행 가능
• 실행을 먼저 하고 맨 마지막에는 순서대로 결과를 써줌(commit)

Dynamically Scheduled CPU

• inorder issue
• out-of-order execute
• in-order commit
• ???

Register Renaming

• write after read 같은 경우 서로 이름을 바꿔서 주면 dependency를 해결??
• 같은 이름만 가지고 있는 경우에 해결
• ???????????????????
  -???????????????????????/

dependency의 세가지 종류

1. RAW(read after write) - true dependency

add $s1 $s2 $s3
sub $s4 $s1 $s3

다음

두가지 경우

• superscalar나 pipeline depth가 다른 경우 dependency 발생
• 레지스터 이름만 바꿔서 해결 가능(register renaming)
• false-dependency

2. WAR(write after read)

1. add $s3 $s7 $s8   p3 p7 p8
2. add $s1 $s2 $s3   p1 p2 p3
3. sub $s2 $s4 $s5   p9 p4 p5
4. sub $s6 $s2 $s11  p6 p9 p11

1과 2 사이에 RAW-true dependency 존재
2와 3 사이에 WAR-false dependency 존재

1과 3은 clock cycle에서 EX stage에 있으나 2는 그 병렬적으로 처리가 불가능하다. 1과 2는 RAW 관계라 1에서의 s3의 실행결과를 얻어야 실행 가능하기 때문이다.

그런데 1과 3을 같이 ex단계에 두고 그 다음에 2를 ex stage에 둬도 문제가 발생한다. 3에서 계산된 s2를 2에서도 사용하고 있기 때문이다. 따라서 rat를 이용하여 physical register를 따로 두는 register renaming이 필요하다.

r4 = r1 + r5
r5 = r1 + r2 

r5' = r5
r4 = r1 + r5'
r5 = r1 + r2

3. WAW(write after write)

add $s1 $s2 $s3
sub $s1 $s4 $s5

Speculation

• branch outcome이 결정될 때까지 commit하지 않는다.

• load speculation

  • loaded value 예측
  • outstanding stores

• load는 speculation이 cleared 될 때까지 commit하지 않는다.

dynamic scheduling을 하는 이유

• 똑같은 isa를 쓰는데 코드를 매번 바꿀 수 없다
• ???

multiple issue가 효과를 볼까

• 예상했던 만큼은 아님
• dependency가 ILP를 제한시킨다.
• dependency 중 제거하기 힘든 것들도 있음
• 잘 보이지 않는 것도 있음
• 메모리 delays와 limited bandwidth 내에서 결정
• speculation이 잘 수행되면 도울 수 있다. (speculation은 meltdown 보안 문제를 유발함)
• 예측하지 않은 결과들은 메모리에 버퍼링 되어 있다.

Power efficiency

• dynamic scheduling과 speculations는 power 요구
• core 개수를 늘리고 대신에 clock speed를 줄여 power issue를 해결했다.