Speculative executions

 

 

Out-of-Order architecture를 사용하는 이유?

instruction level parallelism을 증가시키기 위해서이다.

 

프로세서에서 실행되는 instruction의 갯수를 증가시킴으로써 ILP를 exploting한다

-> parallelism을 사용해서 프로세서의 성능을 늘릴 수 있다.

-> pipeline, OoO architecture를 사용해서 ILP를 늘릴 수 있다.

 

Thread-level-parallelism

프로세서 내부에서 실행되는 스레드 갯수를 증가시킴으로써 프로세서의 성능을 증가시킴

 

tomasulo 알고리즘은 OoO architecture implementation의 baseline이다.

 

tomasulo 알고리즘의 이점

프로세서 내에서 실행될 수 있는 명령어 갯수를 증가시킬 수 있다.

instruction result는 register file에서 immediate하게 업데이트 된다. 

 

 

tomasulo 알고리즘의 단점

processing engine에서 instrucion의 execution이 완료되고 나면 그 result 값은 tag와 함께 CDB를 타고 register file로 전송되고 ISSQ로 포워딩된다. 이 때 result는 integer register나 floating point register로 written back된다.

instruction result가 register file 혹은 memory에 update되면 이 instruction의 result를 cancel하기 어렵다.

따라서 프로세서의 state를 roll back할 수 없다.이는 매우 critical한 문제이다.

 

 

 

tomasulo 알고리즘 : Control Hazards

- branch instruction을 실행하면 true 혹은 false path를 선택해야 하는데, 이 때 dispatcher는 stall한다.

- branch instruction은 integer ISSQ로 dispatch된다. 

- branch instruction은 branch 결과값(taken하는 지 not taken하는 지)을 CDB로 전달한다. 

    - 만약 taken이라면 dispatch는 IFQ를 clear하고 IF stage를 진행한다

    - 만약 not taken이라면 dispatch는 IFQ를 이어서 resume한다.

- 속도를 높이기 위해 front-end는 branch 명렁어가 back-end 단계에 있을 때 target instruction에 있는 instruction들을 prefetch를 해서 precode할 수 있다.

 

normal application에서 conditional branch instruction의 비율은 15~20퍼센트 정도 된다.

그래서 매 4~5 cycle 마다 conditional branch instruction이 나타난다.

평균 single basic block에는 4~5개의 instruction이 들어간다.

토마술로 알고리즘은 OoO프로세스 아키텍쳐이고 이는 basic block을 적용하는데, basic block의 크기는 매우 작기 때문에 OoO 프로세스의 장점을 효율적으로 이용할 수 없다.

프로세스의 성능을 증가시키려면 프로세스에서 실행되는 명령어 갯수를 ILP를 이용해서 증가시켜야 한다. 

그런데 branch instruction으로 인해 ILP를 exploit할 수 없다. -> severe performance bottleneck

 

 

 

tomasulo 알고리즘의 Problem

1. complete된 instruction은 immediate하게 commit된다.

2. precise하게 exception을 support할 수 없다.

- static pipeline에서는 precise exception을 support하기 위해 in-order completion을 사용했다.

- tomasulo 알고리즘은 OoO방식이므로 precise exception을 support할 수 없다.

3. branch instruction으로 인해 뒤따라오는 명령어를 실행할 수 없으므로 ILP를 효율적으로 높일 수 없다. -> branch instruction은 프로세스의 instruction의 barrier로 동작

 

 

 

 

 

 

tomasulo 알고리즘과 Hazard

RAW 해저드의 경우 true data dependency였다. 

이는 former instruction이 producer이고 following instruction이 consumer일 때 발생한다.

 

WAW, WAR 해저드의 경우 static pipeline아키텍쳐에서 컴퓨터 프로세서는 atomic execution을 수행한다.

instruction이 수행되면 result가 immediately하게 업데이트 되기 때문에 WAW, WAR 해저드를 염려하지 않아도 된다.

하지만 OoO 아키텍쳐에서 컴퓨터 프로세서는 이 둘을 고려해 주어야 한다. 그렇기 때문에 instruction의 latency가 다양해진다.

 

 

tomasulo알고리즘이 WAW 해저드와 WAR 해저드를 serve할 수 있는 방법

add r1 r2 r3 
add r1 r4 r5

 

여기서 r1이 같기 때문에 WAW 해저드가 발생한다.

add1과 add2의 r1 값에 write 되는 값은 각각 다르다. 

register renaming을 통해 이 해저드를 해결할 수 있다.

instruction이 dispatch 되면 tomasulo 알고리즘은 destination register numberfmf ISSQ entry  number로 바꾼다

add r1 -> add tag100

이후에 sub r5  r1이 들어온다면 이는 sub r5 tag100으로 바뀐다.

이후에 add r1이 들어온다면 destination이 같으므로 r1은 tag number tag101로 바뀐다.

 

 

 

 

 

tomasulo with speculative execution

 

 

 

 

위는 speculative execution이 적용된 토마술로 알고리즘이다.

speculative execution의 main configuration

• ROB = Reorder buffer
  • 레지스터 파일에 액세스 하기 전에 일시적인 storage
  • FIFO구조
  • speculative value를 hold
  •  
• BPB = Branch Prediction Buffer
• BTB = Branch Target Buffer
  • BPB, BTB는 instruction fetch engine에 연결된다.
  • BPB를 통해 branch instruction의 결과는 taken, not taken으로 predicated된다.
  • BTB는 branch instruction의 target을 estimate한다.
    • branch가 taken된다 predicate되면 branch instruction의 target이 estimate되고 이 taget을 사용해서 instruction은 fetch된다.
    • fetch된 instruction은 instruction fetch queue로 enqueue된다.
    • IFQ에 있는 instruction은 decode 되고 backend에 있는 ISSQ로 dispatch된다.
• RAT = Register Alias Table
  • 레지스터의 3가지 상태를 manage

 

speculative execution을 support하기 위해서는 instruction의 completion과 commit을 구분해야 한다.

- completion : instruction이 execution engine을 통해 수행되고, 생성된 결과값은 특정 스토리지에 저장됨

이 때 결과값은 레지스터에 곧바로 업데이트 되지 않는다.

- commit : data가 레지스터에 업데이트 되었을 때

 

 

또한 레지스터 파일은 3개의 state를 갖는다.

1.pending : execution not yet completed

2.completed : completed but not yet commited - known value는 있는 상태지만 레지스터에 업데이트는 안도니 상태. 일시적으로 스토리지에 저장되어 있는 상태

3.commited : reigster file has requested data - instruction result가 레지스터 혹은 메모리에 업데이트 된 상태

 

 

 

OoO architecture with speculative execution의 특징

dispatch : in-order

completion : out-of-order completion

commit : in-order

 

 

 

 

tomasulo with speculative execution

 

기존 tomasulo알고리즘에서는 WAW, WAR 해저드를 serve하기 위해 tag를 사용해서 register renaming을 했었다.

sepculative execution에서는 ROB entry number를 tag로 하여 register renamingㅇ르 한다.

instruction이 decode 되고 ISSQ로 dispatch되면 instruction은 ROB로 enqueue된다.

ROB : dipatch된 instructio의 order를 track하기 위해 enqueue한다. FIFO 구조이다.

FIFO queue에는 head pointer 와 tail pointer가 있다.

dispatch pointer = head pointer - instruction이 dispatch되고 나서 포인터에 의해 ROB에 저장됨

commit pointer = tail pointer - 매 cycle 마다 instruction이 commit 됨

instruction이 완전히 commit 되고 나면 state가 commit으로 바뀜 + FIFO에서 instruction은 pop out 됨

 

 

step 1) instruction fetch

instruction을 instruction cache로부터 fetch해옴

i-fetch engine은 BPB,BTB에 연결되어 있기 때문에 branch target buffer에 branch target이 저장된다.

fetch된 instruction은 instruction fetch queue로 enqueue된다.

여기서 토마술로 알고리즘과의 차이 : BTB & BPB가 있기 때문에 branch instruction이 있더라도 더 많은 instruction을 fetch해올 수 있다.

step 2) instruction decode / dispatch → 기존 토마술로 알고리즘보다 과정이 더 복잡**

instruction이 IFQ의 가장 마지막에 저장되어 있을 때 decode되고 fetch된다.

이 instruction은 RAT를 확인함. source register의 상태를 확인하기 위해

RAT는 pending, completion, commit의 3가지 상태를 가짐

예를 들어 IFQ 가장 마지막 instruction이 add r1 r2 r3인 경우에서

• r2의 상태가 pending이면, RAT에는 valid ROB entry number가 있다.
• r2의 상태가 completion이라면, RAT에는 valid ROB entry number가 있다. 그리고 이때에는 result가 ROB에 저장되어 있는 상태이다. 따라서 ROB로부터 data를 read할 수 있다.
• 그리고 rd인 r1는 pending 상태로 업데이트 된다.
• r2의 상태가 commit이라면, ROB entry number는 invalid해진다. → r2로 가짐

i-decoder/dispatch에서 instruction이 dispatch되면 dispatch pointer에 의해 instruction은 enqueue된다. → r1은 rob number를 할당받게 됨

instruction이 load 혹은 store일 경우, load/store queue에도 동시에 할당해 주어야 한다.

여기서 queue는 제한된 자료구조인데, 만약 fully occupied된다면 명령어를 ISSQ, ROB, LD/ST queue에 할당할 수 없게 된다. 따라서 instruction은 dispatch될 수 없고 structure hazard가 발생하게 된다.

instruction이 ISSQ로 issue됨과 동시에 ROB로도 전달된다.

step3) instruction execute

hardware component가 ready상태라면(r2, r3가 execute할 준비가 된 상태라면) cdb와 hardware execution engine의 availability를 확인해야 한다. 그리고 나면 instructino을 execution engine으로 issue할 수 있다. → result는 cdb로 전달됨

원래 토마술로 알고리즘에서 cdb는 ISSQ와 레지스터 파일에 연결된다.

speculation에선 cdb는 rob에도 연결된다. → instruction execution이 complete되고 나면

result는 first ISSQ로 전달된다. (ISSQ에는 pending register가 있기 때문), 그리고 cdb를 따라 completed result는 rob로 전달된다.(rob number가 cdb에 전달됨) 그러고 나서 rat의 status는 completion으로 바뀜

register가 pending state라면 CDB를 타고 ISSQ로 감 + result는 ROB로도 전달됨

ROB의 commited pointer에 의해 instruction이 매 사이클마다 commit됨

instruction이 commit되고 나면 register file이 업데이트 된다.

결론적으로 프로세스의 status는 업데이트 된다.

 

 

 

 

 

 

 

branch instruction을 통해 branch가 miss된 경우 dispatch pointer를 아래로 move할 수 있다. → commmit pointer + 1까지→ instruction의 dispatch를 roll back할 수 있다.

→ branch instruction의 결과가 correct 할 경우 새로운 instruction이 dispatch될 수 있다.

flush of rob = rob entry is initialized and dispatch point is move to the top of ROB, so instructions are canceled.

percise exception을 support하려면

exception이 handle되지 않으면 silent한 상태를 유지한다.

instruction이 commit될 준비가 될 때까지 flag에 의해 handle된다.

스태틱 파이프라인에서 exception이 일어나면 일단 이전의 명령어들은 write back을 완료하고 뒤따라오는 명령어들은 파이프라인에서 flush된다.

토마술로 알고리즘에서 예외를 핸들링 할 경우 ROB에서 exception이 commit된 이후에는 모든 파이프라인이 flush된다. = 뒤따르는 명령어가 프로세서에서 flush된다.

따라서 ROB를 통해 precise exception 구현이 가능해진 것이다.

 

memory hazard를 다룰 때 기존 토마술로 알고리즘 방식과 동일하게 store queue는 두 파트로 쪼개진다.

 

 

 

speculative execution의 특징

store instruction은 ROB의 top에 있는 instruction이 commited되면 실행된다.

store instruction은 memory에 있는 data를 바꾸기 때문이다.

memory disambiguation

ex) store instruction이 어디에 액세스 하려는 지 모르는 상황에서 load instruction이 a에 액세스 하는 상태

st ? // 어떤 address에 액세스하려는 지 모르는 상태

ld a // address a 에 있는 data 에 액세스하려 함

두 가지 경우를 가정할 수 있다.

case1) ? = a

매우 안좋은 상황, 낮은 확률이지만 가능성이 있는 상황

만약 load 명령어가 store 명령어 이전에 실행된다면 load 명령어는 메모리로부터 잘못된 data를 가져올 수 있기 때문이다

store명령어의 주소를 알고 있는 상황에서 load 명령어를 실행할 수 없다. → 문제 발생→이를 conservative approach라 한다.

case2) ? ≠ a

아주 다행인 상황

case1의 경우에 대처하는 방법 - dynamic memory disambiguation이라 부름

 

 

 

 

이 경우 load speculative를 execute함

branch prediction을 사용하는 이유?

prediction hit rate는 매우 높기 때문이다.

(prediction hit rate가 낮다면 branch prediction을 avoid해야 한다. 이는 프로세스의 성능에 매우 안 좋은 영향을 준다. )

따라서 이 방식을 memory disambiguation에도 적용한다.

높은 확률로 st의 address와 ld의 address는 다를 것이다.

일단 st의 address를 모르니까

따라서 load instruction speculative하게 실행된다.

speculation이 hit이라면 execution을 roll back할 필요가 없다. (매우 높은 확률로 speculation은 hit이다 )

speculation이 miss라면 execution을 roll back한다.

main idea는 branch prediction의 approach가 dynamic memory disambigution에 적용된다는 것이다.

사실 메모리 레이턴시는 프로세스의 성능에 크리티컬한 영향을 주는데,

load instruction을 가능한 빨리 실행한다면 프로세스 성능을 향상시킬 수 있다.