[Quantitative approach] ch3.4 Overcoming Data Hazards With Dynamic Scheduling

* Computer architecture - a quantitative approach chapter3.4와 appendix C.7 을 읽고 정리한 내용입니다.

---

 

 

 

RISC Instruction Sets and Efficiency of Pipelining

 

instruction set이 단순하면 pipeline에서 execution efficiency를 달성하기 수월해진다.

memory에 store된 두 값을 더하고 그 결과를 다시 memory에 저장해야 하는 경우

load instruction 2개, add instruction 1개, store instruction 1개가 필요하다.

대부분 이 작업은 stall을 하지 않는다면 sequential하게 진행되지 않을 것이다.

따라서 static pipeline 방식에서 변화하여 stall을 줄이기 위해 instruction execution을 reorder하는 방식의 dynamic scheduling 방식을 적용했다.

 

 

 

Dynamically Scheduled Pipelines

 

compiler = static scheduling

단순한 pipeline은 이미 pipeline에 있는 instruction과 bypassing 혹은 forwarding으로도 hide될 수 없는 fetch된 instruction 간에 dependency가 없다면 instruction을 fetch하고 issue한다.

하지만 만약 hazard를 피할 수 없다면 나중에 들어오는 instruction은 dependence가 해결된 다음에 fetch되거나 issue될 수 있다. 여기서 performance loss가 발생하게 되고, compiler는 instruction 간 hazard가 발생하는 것을 막기 위해 instruction을 schedule할 수 있다. 만약에 multiple functional unit을 사용한다면 많은 수의 unit들은 idle 상태에 놓일 것이다.

 

 

 

in-order execution

instruction이 pipeline에서 hazard 발생으로 인 stall되면 이후의 어떠한 instruction도 실행될 수 없다.

 

Dynamic Scheduling의 Idea

fdiv.d 	f0,f2,f4
fmul.d 	f6,f0,f8
fadd.d 	f0,f10,f14

 

위 코드는 RISC V의 floating point pipeline operation을 나타낸 것이다.

fmul.d와 fadd.d 사이에는 f0로 인해 anti dependence가 존재한다. 

만약 pipiline이 fmul.d를기다리는 동안 fadd.d를 실행한다면 antidependence를 위반하게 되어 WAR hazard를 일으키게 된다. 마찬가지로 fdiv.d가 완료되기 전에 fadd.d를 실행한다면 WAW hazard가 발생할 것이다. 이러한 hazard는 register renaming을 통해 막을 수 있다.

 

dynamic scheduling은 out-of-order completion를 사용하지만 프로그램에서 발생하는 exception을 그대로 보존해야 한다. 하지만 가끔씩 dynamic scheduling 방식으로 인해 imprecise exception이 발생할 수 있다.

이유는 다음과 같다.

1. pipeline이 이미 exception을 발생시킨 instruction보다 나중에 나오는 instruction을 이미 완료했기 때문

2. pipeline은 아직 exception을 발생시킨 instruction보다 이전에 있는 instruction을 완료하지 못했기 때문

imprecise exception은 exception 이후에 execution이 다시 시작되는 것을 어렵게 만든다.

 

 

 

out-of-order execution = out-of-order completion

data operation이 available해지자 마자 instruction이 execution을 실행하길 원한다.

predecessor instruction이 stall되면 issue process를 두 부분으로 나눈다. 

1. structural hazard 발생했는 지 확인 

2. data hazard가 없어질 때까지 기다림

 

따라서 ID pipe stage는 두 stage로 split된다.

1. Issue - instruction을 decode하고 structural hazard가 발생했는 지 확인 (in-order 방식)

2. Read operands - data hazard가 사라질 때까지 기다리고 operand를 읽는다. 

따라서 IF -> ID (Issue -> Read operands) -> EXE -> MEM -> WB 이며 multiple instruction은 동시에 실행될 수 있다.

 

 

 

dynamic scheduling = dynamically controlled pipelining

hardware가 stall을 줄이기 위해 instruction을 rearrange하는 방식이다.

• issue stage에서 모든 instruction은 in-order 방식으로 진행된다.
• read operand stage에서 모든 instruction은 stall될 수 있기 때문에 out-of-order방식으로 진행된다

 

dynamic scheduling architecture

 

I-cache는 instruction fetch를 한다. PC값을 사용해서 instruction cache에 access하면 instruction이 fetch되게 된다.

다음으로 instruction decode 단계에서는 fetch된 instruction이 instruction decode에 의해 decode되는데, integer register file에서는 integer type instruction을, floating point type instruction에서는 floating point type instruction을 처리한다. 

execution 단계에서는 AGU(Address Generation Unit)을 사용해서 address를 separate하며, integer ALU로 integer type instruction의 연산을 수행하고 FP ALU를 이용해 floating point type instruction의 연산을 수행한다. 

이 때 load/store instruction은 AGU에 포함된다. 만약 execution 이 complicate해지면 reserve된 것은 다시 instruction decode 단계에서 RF로 written back된다.

write back 단계에서 integer type instruction과 floating point type instruction은 D-cache를 거치지 않는다.

D-cache가 load/store instruction으로 인해 access되고 나면 integer type은 integer RF로, floating point type은 floating point RF로 witten back된다. 즉 D-cache에서 instruction decode 단계의 register file로 넘어가는 경로를 wite back path이라 한다.

dynamic controlled pipelining은 integer, floating point memory instruction을 처리하기 위해 multiple processing engine을 갖고 있다. 따라서 이러한 instruction은 다른 processing unit에 대해 parallel하게 실행될 수 있다.

 

여기서 문제점을 찾아보자면, 사실 integer processing engine은 상대적으로 간단하다. 그래서 integer type ALU는 1cycle, 즉 fixed cycle을 소비하며 매우 simple하다.

하지만 floating point type ALU는 5 cycle 정도를 소비하며 d-cache로부터 FP ALU로 되돌아오는 insruction으로 인해 extra cycle이 추가됨으로써 약간 더 complicate하다.

 

뿐만 아니라 memory에서도 문제점이 있다. memory가 fixed latency, fixed cycle을 갖고 있다고 하고 cache hit의 경우를 가정했을 때 data cache에서 hit과 miss에 기반해 memory instruction의 latency는 variable해진다.

memory instruction을 위해 요구되는 cycle은 각각의 situation에 의해 변화된다는 것을 알 수 있다.

즉 memory instruction은 1cycle만 소비할 수도 있지만 그 이상의 cyle time을 소비할 수도 있는 것이다. 따라서 multiple processing engine은 다양한 delay를 가질 수 있게 되는 것이다. 그렇기 때문에 processing engine에 fixed cycle을 사용할 수 없다. 

따라서 dynamic controlled pipelining의 문제점은 모든 processing engine이 모든 stage에서 다양한 cycle을 갖게 되기 때문에 다양한 delay를 갖게 된다는 것이다. 

 

 

 

* 이 문제를 하드웨어적으로 해결하기 위해서는 다음과 같은 idea를 이용한다.

comsumer는 producer가 만든 result를 소비한다. consumer는 그러고 나서 consumer만의 result를 만들어낸다. 

consumer의 latency는 특정 파형처럼 매우 다양해질 수 있다.

 

소비자의 latency의 평균치를 사용할 수도 있겠지만 현실에서 task는 매우 빠르게 processing 되며 추가적인 cycle이 걸리게 된다.

이 과정에서 problem을 해결하기 위해 queue를 사용한다. 따라서 이 프로세서의 output으로부터의 result는 일시적으로 queue에 저장되게 되고 consumer는 producer로부터 합리적인 방식로 이용할 수 있다. 

만약 queue를 사용하지 않는다면 consumer는 매우 빠르게 work하게 되고 producer로부터의 result는 consumer로 매우 빠르게 process된다. 하지만 consumer가 매우 느리다면 producer는 result를 consumer에게 전달할 수 없게 되어 processor의 성능은 저하된다. 

consumer의 delay가 vary하다면 queue를 사용할 수 있다는 점이 hardware design적으로 중요하다. 

producer 부분과 consumer 부분을 구별할 수 있으며 consumer 부분의 delay는 달라지기 때문에 queue를 사용할 수 있다.

 

 

 

queue가 추가되어 advanced된 dynamic scheduling architecture

 

processing unit(integer ALU, AGU, floating point ALU)는 다양한delay를 갖고 있을 것이다.

그렇기 때문에 다음과 같이 3개의 processing engine 앞에 queue를 추가해 주면 된다.

D-cache 역시 다양한 latency를 갖게 되므로 LD, ST로 인한 cache access에 대비한 execute stage와 그 다음 단계를 연결하는 2개의 queue가 필요하다.(LQ,SQ)

AGU 앞에 있는 process engine 은 LQ와 SQ를 call한다.

 

 

 

Dynamic Scheduling With a Scoreboard

 

Scoreboarding

resource가 충분히 존재하고 data dependence가 없을 때 out of order방식으로 instruction을 실행하도록 허용하는 technique

 

fdiv.d 	f0,f2,f4
fadd.d 	f10,f0,f8
fsub.d 	f8,f8,f14

 

위 코드는 RISC V의 floating point pipeline operation을 나타낸 것이다.

여기서 fadd.d 와 fsub.d 간에 WAR hazard가 존재한다. fsub.d가 fadd.d 실행 전에 먼저 실행된다면 f8에 incorrect한 값이 write되므로 문제가 발생한다. 

기존 RISC V의 simple pipeline technique에서 ID stage에서는 structural hazard와 data hazard가 발생하는 지 확인하는데, 아무런 hazard도 발생하지 않았다면 instruction은 ID stage로부터 issue되어 다음 stage로 넘어간다.

따라서 위 예시를 통해 hazard가 발생함에도 불구하고 fsub.d를 실행시키기 위해서 out-of-order execution = out-of-order completion방식을 사용한다. 

 

 

 

 

scoreboard는 WAW, WAR hazard는 나중에 따라오는 instruction이 stall되도록 만들기 때문에, 이러한 hazard가 발생하는 것을 막아야 한다. 

 

 

 

 

scoreboard가 포함된 RISCV의 모습

 

 

2개의 multiplexer, 1개의 adder, 1개의 divide unit, 1개의 integer unit이 있다 가정

모든 instruction은 data dependence가 기록되는 scoreboard를 통과하고 이 단계는 RISCV파이프라인의 ID stage를 대체한다. scoreboard는 그다음 instruction이 언제 operand를 read할 수 있고 execution을 시작할 수 있는 지를 결정한다.

scoreboard가 instruction이 즉시 실행될 수 없다고 판단하게 되면, instruction이 실행될 수 있는 시점을 찾게 된다. 따라서 모든 hazard detection과 resolution은 scoreboard로 집중되게 된다.

scoreboard는 또한 instruction이 destination register로 결과를 write할 수 있을 때를 제어한다.

 

instruction은 실행과정에서 4개의 단계를 거친다.

 

1.Issue : instruction의 functional unit이 free상태이고 active instruction이 destination register를 갖고 있지 않다면, scoreboard는 functional unit으로 instruction을 보내고 내부 data structure를 업데이트한다. issue 단계는 ID 단계를 대신한다. 다른 functional unit이 destination register로 결과값을 write하려 하지 않는다면 WAW hazard는 발생할 수 없다.

structural 혹은 WAW hazard가 존재해서 stall이 발생하게 되면 뒤따르는 instruction은 hazard가 해결될 때까지 대기해야 한다. instruction issue와 fetch 사이에 entry가 1개인 buffer를 넣게 되면 buffer 가 가득 차게 되자마자 즉시 stall이 발생할 것이고 queue형태의 buffer를 넣게 되면 multiple instruction을 수용할 수 있으므로 queue가 가득 찰 경우에 stall할 것이다.

RISC V의 ID 단계를 시작하는 과정이라고 보면 된다.

2.Read operands : scoreboard는 source operand가 사용가능한지를 monitoring한다. 이전에 issue된 active instruction이 write하려 하지 않는다면 source operand는 사용가능하다. source operand가 사용가능하다면 scoreboard는 functional unit에게 register로부터 operand를 read하여 execution을 실행하도록 한다. 이 단계에서 scoreboard는 RAW hazard를 dynamic하게 해결하고 instruction은 아마 out of order 방식의 execution 단계로 보내질 것이다. RISC V의 ID 단계를 완료하는 과정이라고 보면 된다.

3.Execution : functional unit은 operand를 받자 마자 execution을 시작한다. execution을 하고 나서 result값을 얻게 되면 scoreboard에 execution이 끝났음을 알린다. 이 단계는 RISC V의 EXE 단계를 거치는 과정이라고 보면 된다. 특히나 RICV FP pipeline에서 execution stage는 multiple cycle이 걸린다.

4.Write result : scoreboard가 functional unit이 execution을 완료했음을 감지하게 되면 scoreboard는 WAR hazard의 유무를 확인하고 만약에 WAR hazard가 있다면 instruction을 완료하기 위해 stall한다. WAR hazard가 없다면 scoreboard는 functional unit에게 결과를 destination register에 write하도록 시그널을 보낸다. RISC V의 WB단계를 완료하는 과정이라고 보면 된다.

 

 

instruction의 operand가 register file에 모두 available한 경우에만 read하기 때문에 scoreboard는 forwarding을 활용하지 않는다. 기존 RISC V의 단순한 형태의 pipeline 모델과는 다르게, instruction은 execution단계가 끝나자 마자 결과값을 register file에 write한다. 따라서 pipeline latency가 감소하며 forwarding unit을 통해 얻었던 이득이 줄어들게 된다. 그리 execution 결과값을 write하는 단계와 operand를 read하는 단계가 overlap되지 않기 때문에 추가적인 latency가 1cycle로 추가된다. 만약 이 overhead를 제거하려면 추가적인 buffering이 필요하다.

 

 

 

Dynamic scheduling의 이점

1. 다른 microarchitecture에서 여러 binary 파일을 필요로 하거나 recompile되어야 하는 필요성을 없애면서 하나의 pipeline에서만 compile되었던 코드를 다른 pipeline에서도 효율적으로 돌아갈 수 있게 한다.

2. compile 시 dependency가 unknown일 때 대처할 수 있게 한다. memory reference, data dependent branch와 같은 경우 dynamic linkn이나 dispatching을 사용하여 대처할 수 있다.

3. cache miss와 같은 예측할 수 없는 latency를 허용함으로써 miss가 해결될 때까지 기다리는 동안 다른 코드를 실행할 수 있다.

따라서 dynamic scheduling의 이점은 하드웨어가 복잡해짐으로써 얻는 대가이다. data flow를 변경할 수는 없지만 dependency가 존재할 때 stall을 피하려 한다. 

static scheduling은 compiler에 의해 수행되며 dependency가 있는 명령어를 분리해서 stall을 최소화하 하는 방식이었는데 이는 dynamic scheduling pipeline 방식을 적용하는 프로세서에도 역시 일부 적용될 수 있.

 

 

 

 

 

Dynamic Scheduling Using Tomasulo’s Approach

Tomasulo's algorithm

토마술로 알고리즘은 IBM 360/91의 long memory access와 long floating-point delay를 해결하기 위해 만들어졌다.

토마술로 알고리즘은 antidependence와 output dependence를 register renaming을 통해 dynamic한 방식으로 처리한다.

instruction의 operand가 사용가능한 시점을 track하여 RAW hazard를 최소화 하고 register의 이름을 변경해 WAW 및 WAR hazard를 최소화한다. 뿐만 아니라 loop의 multiple iteration의 execution을 overlap한다.

 

 

토마술로 알고리즘의 key principle

• instruction이 execute할 준비가 되었을 때 dynamic하게 determine
• 불필요한 hazard를 줄이기 위해 register를 renaming

toumasulo's algorithm

 

dynamically controlled pipelining은 horizontal direction으로 진행된다.

토마술로 알고리즘은 vertical direction으로 진행된다.

instruction cache에서 instruction은 instruction fetch engine을 통해 fetch되어 instruction fetch queue(IFQ=instruction queue)에 저장된다. IFQ는 FIFO 형식을 사용한다. instruction은 in-order형식으로 fetch되고 instruction decoder에 의해 in-order형식으로 decode된다. decode 된 instruction은 다른 issue 방식으로 issue queue와 backend part로 전달된다.

이 과정을 dispatch라 한다.  IFQ에 있는 마지막 instruction은 decode되고 instruction class를 기반으로 다른 issue queue로 dispatch된다. ISSQ 는 issue engine과 함께 붙어있다. ISSQ의 instruction 중 하나가 ready 상태라면 이 instruction은 processing engine으로 issue된다. issue engine을 dispatch함으로써 instruction은 ISSQ의 entry 중 하나로 issue된다.

issue된 instruction은 processing engine(integer/branch, AGU, FP)로 전달될 수 있다.

instruction이 processing engine으로 전달되는 과정을 issue(issuance)라 한다. 

processing engine에서 instruction의 execution이 완료되고 나면 그 result value는 tag와 함께 CDA(Common Data Bus)를  타고 register flie로 전송된다. result는 integer register나 floating point register로 written back된다. D-cache가 업데이트 되면 CDB로 연결된다. LQ와 SQ는 memory에서 data hazard를 support한다. 또한 register file과 각 ISSQ queue는 instruction tag로 분리된다. 

 

example.

add 	r1 r2 r3 
sub 	r4 r1 r5

add instruction은 IFQ에서 issue queue로 dispatch된다. 그리고 destination register인 r1에 있는 data를 업데이트 한다.

add instruction이 ISSQ로 dispatch되고 나서 integer unit에서 실행되기 까지는 일부 시간이 걸리는데, 그렇기 때문에 execution이 되기 전까지 r1에 있는 value는 unknown value이다. 

add 명령어가 ISSQ로 dispatch되고 이 ISSQ가 각 entry마다 tag를 갖고 있다면 이 tag는 r1으로 written된다. 즉 tag는 instruction이 dispatch되었다는 것을 뜻한다. 하지만 이 add instruction이 완료되고 나서 result값과 tag값은 CDB로 올라가게 된다. tag 값은 ISSQ와 register file에서 check되는데, 이 과정을 snoop이라 한다.

이후 다음 instruction인 sub r4 r1 r5 sub는 fetch되고 register file을 확인한다. 하지만 register file에는 이미 add 명령어로 인해 valid한 tag(r1)이 존재한다. 이 r1은 sub 명령어를 위해 사용되어야 하는데 아직 ready상태가 아니다. 따라서 tag는 sub 명령어를 따라 전달되어 sub r4 r1 r5 -> sub r4 tag r5 로 변환된다. 즉 out-of-order 프로세스가 tag number로 register의 name 을 rename하는 것이다. tag number를 통해 data dependency를 handle할 수 있게 된다.

 

 

instruction이 fetch될 때 tag가 할다오디는데, 할당된 tag가 instruction마다 다르다면 다른 hazard를 handle할 수 있다.

 

 

 

tomasulo's algorithm 정리

• Front-end = instruction fetch + instruction decode + dispatch
  • instruction이 fetch됨
  • instruction fetch queue에 FIFO형식으로 instruction이 저장됨
  • input operand가 동일한 다른 instruction이 먼저 back-end stage에서 실행되고 있다 하더라도instructiondl IFQ의 가장 마지막 entry에 도달하면 decode되고 ISSQ로 dispatch된다.

• Back-end = issue queue + processing engine(=execution engine=execution unit=EUs) + memory part + common data bus
  • ISSQ에 있는 instruction은 input register operand를 위해 대기한다.
  • 일단 register operand가 ready상태가 되면, instruction은 execution을 위해 스케줄링될 수 있고, 다른 instruction과 CDB 혹은 functional unit때문에 충돌하지 않을 것이다.
  • instruction이 execute되면 result값은 CDB로 전송된다.
  • queue와 register에 있는 모든 instruction은 CDB를 monitoring하다가 기다리던 value가 나타나면 grab한다.

 

 

dynamic register renaming

register value는 ISSQ의 entry number로 rename된다. 그리고 동일한 register의 multiple value는 항상 대기한다.

• Dispatch 단계에서 각 input register operand는 reister로부터 fetch된다.
  • 만약 tag가 invalid한 값이라면
    • value는 back-end에서 대기중인 상태가 아니다.
    • register value는 valid하고 ISSQ로 보내진 상태이다.
  • 만약 tag가 valid한 값이라면
    • value는 back-end에서 대기중인 상태이다.
    • register value는 stale하고 tag가 ISSQ로 전송된다

 

Tomasulo : Data hazard on memory

• 토마술로 알고리즘에서 RAW, WAW, WAR 유형의 hazard가 모두 발생할 수 있다.
• Load/Store queue : memory hazard를 해결하기 위해 staging buffer를 사용
• data dependency는 same address로 인해 발생한다. 사실 register를 통해 hazard를 체크하는 건 매우 busy한 작업임에도 불구하고 address는 register value로 결정된다. register number는 deteministic value로, instruction에 포함될 수 있기 때문에 reigser를 instructino에서 사용하여 hazard를 쉽게 식별할 수 있는 것이다.

또한 load instruction은 사실 memory data를 변경시키진 않는다 하지만 store instruction은 critical하게 memory의 data를 변경시킨다.

따라서 store instruction은 매우 중요하고 2가지의 다른 sub instructinon part로 split된다.

1. address part : for generating address -> store address

2. data part : for fetching data on register -> store data

 

example.

st 	?
ld 	a
ld 	b
ld 	c

 

위의 코드의 경우 store instruction의 register 정보가 unknown상태이다.

따라서 높은 확률로 st instruction의 address는 뒤따라 오는 3개의 ld inst의 address와 다를 것이다.

낮을 확률로 st instruction의 address는 뒤따라 오는 3개의 ld inst 중 1개의 ld inst의 address와 같을 것이다.

따라서 store instruction의 뒤따라 오는 3개의 ld inst는 실행될 수 없다. 그렇기 때문 conservative approach라고 볼 수 있다. 하지만 우리는 이러한  낮은 확률의 경우 때문에 approach를 follow해야 한다. 그러기 위해선 ld instruction은 st instruction보다 더 먼저 d-cache에 액세스한다. 그렇게 되면 ld instruction은 올바르지 않은 value를 갖게 된다.

• memory issue queue로부터 cache로의 issue
  • load instruction은 address가 ready상태라면 AGU와 load/store queu로 issue될 수 있다.
  • store sub instruction은 모두 AGU 및 load/store queue로 issue된다.
    • address part는 address register가 준비되면 AGU에서 address를 계산
    • data part는 data가 준비되면 AGU를 통과
  • load/store queue는 load/store queue에서 해결된다.
    • load/store queue는 load/store instruction의 issue order를 track함
    • load/store queue entry는 dispatch 시 reserve된다.
    • load inst는 address가 그 앞에 동일한 주소를 가진 store inst가 없다면 cache로 issue할 수 있다.
    • store inst는 address가 그 앞에 동일한 주소를 가진 store/load inst가 없다면 cache로 issue할 수 있다.
    • address가 unkown하다면 동일하다 간주
    • correctness를 위해 worst case를 다루는 conservative approach이다.