Branch Log · Open in interactive viewer →

4 Processor (Part III)

4.14 RISC-V pipelined datapath

RISC-V impl pipeline

기존에 살펴본 datapath에서 (single-cycle instruction과 달리) pipelined processor에서 특히 주의해야 하는 흐름이 있다. 보통 한 instruction이 수행되는 과정은 datapath의 왼쪽에서 오른쪽으로 진행되었지만, 단 두 가지 예외가 있었다.

이 두 예외가 pipeline의 다음 instruction에 영향을 주게 되며, 각각 data hazard, control hazard를 일으키게 된다.

4.14.1 Pipeline Register

결국 pipelined processor에서는 "data dependence가 해결될 때까지 값을 저장(forwarding)"하거나, "branch outcome이 결정될 때까지 PC를 저장"하는 등, 각 단계별 state를 저장해 두기 위한 pipeline register를 구축했다.

PC도 IF stage를 위한 pipeline register로 볼 수 있다. 대신 다른 pipeline register와 다르게 visible한 특징을 가진다.

pipeline register

WB 다음으로는 pipeline register가 없다. WB 단계를 거치는 load instruction은 register file에 기록하기 때문에, 필요하면 register file을 다시 읽으면 되기 때문이다.

가령 data hazard 상황에서 pipeline register를 사용하여 해결하는 forwarding 예시를 보자.

하지만 바로 앞 instruction이 load instruction이라면, memory read가 끝나지 않았을 것이기 때문에 forwarding을 해서는 안 된다. 이를 load-use-data hazard라고 한다.

3 cycle이 넘어가면 data hazard는 일어나지 않는다.

4.14.2 pipelined datapath: load instruction

ld instruction을 수행한다고 가정하고 datapath를 따라가 보자.

  1. IF: instruction을 fetch한 뒤, instruction 값을 IF/ID register에 저장한다.

IF for Load

  1. ID: IF/ID register에에서 immediate, 두 register 값을 읽은 뒤, IF/ID register에 해당 값을 저장한다.

ID for Load

  1. EX: IF/ID register를 읽고 ALU로 target address를 계산한 뒤, EX/MEM register에 address를 저장한다.

EX for Load

  1. MEM: EX/MEM register를 읽고 memory address를 파악한 뒤, memory에서 읽은 값을 MEM/WB register에 저장한다.

MEM for Load

  1. WB은 pipeline register에서 값을 읽고 register file에 저장한다.

4.15 forwarding

pipeline에서는 forwarding을 통해 data hazard를 막을 수 있었다. 다음은 forwarding을 구현하지 않은 datapath와 구현한 datapath의 그림이다.

no forwarding

with forwarding

총 네 가지 입력을 받는다. 이 네 가지 입력을 비교해서 (3 cycle 미만에서만 존재할 수 있는) data hazard를 발견하는 것이다.

출력은 ForwardA, ForwardB 두 가지로, 3x1 MUX를 control한다.(각각 첫 번째, 두 번째 operand를 선택)

4.15.1 data hazard example

아래 dependency를 가지는 코드를 보자.

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

위 프로그램이 어떻게 pipeline에서 수행될까? 아래 그림을 보자.

data hazard example

x2 값에 주목하자. 그림에서 'Value of register x2'라고 적힌 부분이다.

여기서 2번 and, 3번 or instruction에서 실제로 x2가 쓰이는 cycle은 각각 4, 5 cycle이라는 점에 주목하자.(EX 단계의 시작 부분)

pipeline register field에 이름을 붙여서 data hazard의 종류를 세부적으로 구분해 보자.

앞서 2번 and instruction은 조건 1a를 만족한다

4.15.2 Double Data Hazard

Doubld data hazard, Load-use data hazard

아래 예시 코드를 보자.

add x1, x1, x2    // x1
add x1, x1, x3    // x1 data hazard 
add x1, x1, x4    // x1 data hazard

이러한 경우 forwarding을 어떻게 해야 할까? 정답은 더 최근의 결과값인 MEM 단계의 값을 forwarding해야 한다.

hazard detection unit(해저드 검출 유닛)이 이러한 hazard를 판단해 준다.

4.16 branch taken example

전체적인 datapath를 나타낸 그림은 다음과 같다.

branch taken

4.17 Instruction-Level Parallelism

pipelining은 기본적으로 ILP(Instruction-Level Parallelism)을 사용한다. ILP를 증가시키는 방법은 크게 두 가지가 있다.

  1. pipeline depth를 늘린다.

    pipeline depth를 늘리면, cycle이 오래 걸리는 단계를 쪼갤 수 있다. 따라서 단계별 cycle이 줄어서 성능이 향상될 가능성이 크다.

  2. multiple issue 방식을 사용한다.

    instruction을 여러 개 동시에 수행하도록 한다.

    이 경우 CPI가 1보다 작아질 수 있다.

   📝 예제 1: multiple issue pipeline performance   

4GHz 4-way multiple-issue microprocessor에서 IPS, peak CPI, peak IPC를 구하라

   🔍 풀이   

$1G = 10^9$ = 10억 = 1 Billion

4.17.1 Multiple Issue Processor Implement

우선 두 가지 문제를 해결해야 multiple issue를 구현할 수 있다.

이러한 문제를 multiple issue processor은 크게 두 가지 방법으로 해결하여 구현한다.

compiler가 수행한다. 즉, 'instruction stream 나누기/hazard 해결'을 compile 시 수행한다. 동시에 hazard를 찾아서 해결한다.

hardware(CPU)가 수행한다. 즉, 'instruction stream 나누기/hazard 해결'을 runtime에 수행한다.

여전히 compiler도 instruction reordering 등으로 도움을 준다.

4.17.2 Speculation

ILP를 잘 활용하기 위한 기법으로 speculation(추정)이 있다. 몇 가지 예시를 보자.

speculation은 compiler가 할 수도, hardware가 할 수도 있다. 하지만 speculation이 틀렸을 때 rollback하는 과정은 서로 다르다.

추정 정확도를 check하기 위한 instructions을 추가한다. 또한 fix-up instructions 루틴도 추가한다.

추정 결과가 틀린 것을 알 때까지 buffer에 저장해 둔다. 그리고 틀린 것을 알게 되면, buffer에 담긴 추정 결과를 flush하고 올바른 순서를 다시 실행한다.

하지만 speculation이 잘못되면, performance 저하뿐만 아니라 exception까지 일어날 수 있다.

4.18 Static Multiple Issue Processor

compiler는 같은 cycle에 처리할 instructions을 issue packets라는 묶음으로 나눈다. packets로 만들 수 있는 instruction 조합은 제한이 있기 때문에, 이를 VLIW(Very Long Instruction Word)라는 하나의 단위로 보기도 한다.

이때 compiler는 대부분의 data hazard, control hazard를 해결하고, reorder한 instruction을 issue packets에 담는다.

조합이 성립하지 않는 상황(nop)은 Pad를 넣어서 대신한다.

다음은 (64bit aligned) two-issue packets 예시다.

two-issue packets

이 경우 datapath는 다음과 같다.

two-issue datapath

4.18.1 hazards in the dual-issue RISC-V

   📝 예제 2: scheduling for dual-issue RISC-V   

다음과 같은 assembly code가 있을 때, 이를 dual-issue RISC-V로 scheduling하라. 그리고 IPC를 구하여라.

Loop: ld   x31, 0(x20)       // x31 = array element
      add  x31, x31, x21     // x21의 scalar 값을 더한다.
      sd   x31, 0(x20)
      addi x20, x20, -8      // decrease pointer(ex: &A[i])
      blt  x22, x20, Loop

   🔍 풀이   

예제에서 dependency를 찾아보자.

따라서 ALU/branch instruction과 load/store instruction으로 scheduling하면 다음과 같은 결과가 된다.

ALU/branch load/store cycle
Loop nop ld x31, 0(x20) 1
addi x20, x20, -8 nop 2
add x31, x31, x21 nop 3
blt x22, x20, Loop sd x31, 8(x20) 4

IPC는 5/4 = 1.25이다.(CPI = 4/5 = 0.8)

4.18.2 Loop Unrolling

추가로 loop문의 성능을 높일 수 있는, 다시 말해 ILP를 높일 수 있는 compiler 기법으로 loop unrolling(=loop unwinding)이 있다.

예를 들어 다음과 같은 C code가 있다고 하자.

for(int i=N; i>0; i--) {    
    a = A[i];              
    a += b;                 
    A[i] = a;               
}

위 code에 loop unrolling을 적용하면 다음과 같이 바뀐다.

for (int i=N; i>0; i-=2) {
    a = A[i];
    a += b;
    A[i] = a;      // 
    a = A[i-1];    // dependence
    a += b;
    A[i-1] = a;
}

위와 같은 WAR dependence를 register renaming 기법을 통해 없애면 다음과 같이 바뀐다.

이렇게 바꿀 수 있는 dependence(WAR, WAW)를 antidependence 혹은 name dependence라고 지칭한다.

for (int i=N; i>0; i-=2) {
    a = A[i];
    c = a + b;
    A[i] = c;     
    a2 = A[i-1]; 
    c2 = a2 + b;
    A[i-1] = c2;
}

   📝 예제 3: loop unrolling   

예제 2 코드를 loop unrolling한 dual-issue RISC-V code를 작성하라. 그리고 IPC를 구하여라.

Loop: ld   x31, 0(x20)       // x31 = array element
      add  x31, x31, x21     // x21의 scalar 값을 더한다.
      sd   x31, 0(x20)
      addi x20, x20, -8      // decrease pointer(ex: &A[i])
      blt  x22, x20, Loop

   🔍 풀이   

ALU/branch load/store cycle
Loop addi x20, x20, -32 ld x28, 0(x20) 1
nop ld x29, 24(x20) 2
add x28, x28, x21 ld x30, 16(x20) 3
add x29, x29, x21 ld x31, 8(x20) 4
add x30, x30, x21 sd x28, 32(x20) 5
add x31, x31, x21 sd x29, 24(x20) 6
nop sd x30, 16(x20) 7
blt x22, x20, Loop sd x31, 8(x20) 8

IPC는 14/8 = 1.75이다.(CPI = 8/14 = 0.57)

예제 2의 IPC가 0.8이었으므로 약 2배 가량의 성능 향상을 보인다.

하지만 그 대가로 temporary register를 네 개(x28, x29, x30, x31)나 사용하였으며 코드 크기도 증가했다.

4.19 Dynamic Multiple Issue Processor

dynamic multiple issue processor는 다른 말로 superscalar processor(수퍼스칼라 프로세서)라고도 불린다.

structural, data hazard를 피해서 결정한다.

4.19.1 Dynamic Pipeline Scheduling

CPU가 stall을 막기 위해 OOO(out of order)로 instruction을 실행하도록 한다.

예를 들어 다음과 같은 코드가 있다고 하자.

ld   x31, 0(x21)     // x31
add  x1, x31, x2     // x31 data hazard
sub  x23, x23, x3
andi x5, x23, 20

sub instruction은 실행할 준비가 되어도 ld와 add가 끝나기를 기다려야 한다. 따라서 dynamic pipeline scheduling을 통해 sub instruction을 먼저 실행하도록 하여 hazard를 최대한 피한다.

아래는 dynamic scheduled pipeline의 세 가지 유닛을 나타낸 그림이다.

dynamic scheduled CPU

instruction을 fetch/decode한 뒤, 각각의 instruction을 해당 functional units로 보낸다.

reservation station(대기 영역)이라는 buffer에 opcode, operand를 담고 있다가, functional unit이 준비되면 계산하여 결과를 도출한다.

reorder buffer(재정렬 버퍼)에 결과를 저장해 두었다가, register file이나 (load instruction의 경우) memory에 작성한다.(commit)

이러한 reservation station과 reorder buffer를 이용해서도 register renaming이 가능하다.

copy가 완료된 후부터는 기존 register가 overwrite되어도 상관이 없어진다.

cache miss와 같이 예측할 수 없는 stall, branch instruction과 같이 결과가 dynamically하게 결정되는 경우가 있기 때문에 dynamic pipeline scheduling이 필요하다.

4.19.2 speculative execution

superscalar processor는 speculative execution을 통해 성능을 향상시킨다.

이때 branch outcome이 나올 때까지 commit하지 않는다.

load, cache miss delay를 피한다. 이때 speculation이 성공했는지 알기 전까지 commit하지 않는다.

4.19.3 Power Efficiency

하지만 이러한 dynamic scheduling과 speculation은 power efficiency를 떨어뜨린다.

Power efficiency

예를 들어 P4 Prescott은 compiler가 31 * 3 = 93 instructions을 한 cycle에 issue한다.

server와 같이 power efficiency가 중요한 환경에서는, 보다 power efficiency가 높은 multiple simpler core를 사용한다.