명령어 파이프라이닝 / Forwarding과 분기 예측

Pipelining

기존의 파이프라인을 적용하지 않은 멀티사이클 방식은, 한 명령어를 처리하고 그 이후에나 다음 명령어를 처리시켜 ALU를 사용 시에는 메모리가 쉬고, 메모리를 사용 시에는 ALU가 쉬었다. 즉 명령어의 단계 외의 다른 컴포넌트가 IDLE 상태로 처리를 대기하는 식이었다.

 

파이프라이닝은 여러 명령어를 중첩하여 명령어 처리 단계를 병렬 실행시키는 기술이다. 한 사이클안에서 여러 명령어를 동시에 처리하여 쉬는 컴포넌트 없이 작업하여 더 효율적인 처리를 가능도록 한다. 

 

위 그림에서의 예시라면 위의 파이프라인을 적용하지 않은 프로세서는 3개의 LW 명령어를 처리하는데 2400ps의 시간을, 아래 파이프파인을 적용한 프로세서는 약 1400의 시간을 사용한다. 이때 3개의 명령어가 아닌, 명령어를 충분히 많다고 가정하면 파이프라이닝 방식에선 매 200ps 마다 명령어가 처리되기 때문에 성능 향상은 명령어 사이의 간격 비율(약 4배)에 근접한다. 파이프라이닝은 개별 명령어의 실행 시간을 줄이지는 못하지만 (한 명령어 처리에 800사용), 명령어 처리량을 증대시킴으로써 성능을 향상한다.

 

Latch

Latch는 pipelining이 각 단계마다 다른 명령어를 처리하고 그 결과를 다음 사이클의 다음 단계 인풋으로 사용해야 하기 위해 아래 그림과 같이 각 단계 사이에 두고 단계별 인풋과 아웃풋을 저장한다.

 

한 사이클이 실행되면 latch의 입력부에서 각 단계별 처리 인자를 받아 처리하고, 처리 결과를 다음 단계의 latch의 결과부에 저장한다. 이후 한 사이클이 종료되는 시점에서 latch의 단계별 결과부를 입력부로 옮기는 것으로 다음 사이클에서 입력부를 이전 사이클의 결과부로 하는 것이다.

 

 

3 hazards 

이런 파이프라이닝을 설계하기 위해선 아래 세가지 문제를 해결해야한다.

 

1. 구조적 해저드

 

 한 개 이상의 명령어를 중복된 하드웨어에서 처리하고자 하는 상황을 말한다. 예를 들면 fetch 단계와 memoryAccess단계에서 메모리 자원을 동시에 사용하고자 하는 경우를 말한다. 이런 경우 Bubble을 추가하여 중복 사용되는 하드웨어가 생기지 못하도록 하는 방식이 있을 수 있고, 또는 아예 자원을 추가하여 중복을 피할 수도 방법도 있다. 전통적인 5단계의 프로세서라면 명령어를 담는 메모리 자원과 데이터를 담는 메모리 자원을 분리하는 것으로 fetch 단계와 memoryAccess단계의 메모리 자원을 분리할 수 있게 되는 것이다.

 

2. 데이터 해저드

 

명령어가 아직 처리 중인 앞선 명령어에 종속성을 가질 때 발생한다. 예를 들면 일렬의 명령어가 순차적으로 동일한 레지스터 R2를 쓰고, 읽는다고 가정해보자. 각각 execute, decode 단계에 있는 경우 decode 단계의 명령어는 앞선 명령어가 레지스터에 연산의 결과를 저장하지 않은 상태로 decode에서 그 값을 읽어버린다. execute 단계에 있는 '쓰기' 명령어가 writeBack 단계에 가서야 레스터에 값을 저장하기 때문이다.

 

따라서 이는 앞선 명령어가 writeBack를 처리하기까지 다음 명령어를 대기시키는 방식(Stalling 또는 Freezing), writeBack에 저장될 값이 결정되는 시점의 값을 미리 앞 당겨 사용하는 방식(Forwarding), 또는 아예 컴파일 시점에 컴파일러 수준에서 일정 거리 안에서 사용되는 레지스터의 중복 사용을 피하는 방식으로 해결할 수 있다.

 

3. 제어 해저드 

 

분기 명령어의 결과를 알기 전까지 fetch된 명령어의 유효성 여부를 알 수 없는 문제가 발생한다. 명령어가 분기 명령인지 아닌지 또는 분기 명령어가 실행될지, 아닐지 모른다. 분기 명령이 실행되지 않음을 생각하여 우선 다음 pc의 명령어를 fetch 하나, 만일 분기가 맞다면 이를 알게되는 execute 단계 이전의 fetch, decode는 모두 무의미한 명령어가 수행된 것이다. 반대로 분기 명령어를 실행한다고 생각하였다가 execute 단계에서 분기가 아니라면, 마찬가지로 앞선 단계의 명령어는 무의미해진다. 

 

 

40번의 분기 결과에 따라 44, 48, 52 명령어가 의미를 잃는다.

 

이런 무의미한 명령어를 어떻게 줄이는가가 제어 해저드를 생각하는 주요 관점이 된다. 앞선 예시의 경우처럼 무의미한 명령어가 발생하면 이를 유효하지 않은 명령어로 처리하는 방법(Branch delay), 이전 분기 결과를 기억하는 등 분기 결과를 예측하는 방법(Branch prediction), 더 나아가 아예 PC와 분기 결과를 기록한 버퍼를 이용하여 decode 단계 이전에 분기 결과를 예측하는 방법 등을 사용한다.

 

Data dependency / Scoreboarding

명령어간 데이터 종속성을 어떻게 확인할 수 있을까. 결국 데이터 종속은 쓰기가 완료되기 전에 읽기가 진행되는 경우를 말한다. Scoreboarding은 레지스터에 valid bit를 추가하는 것으로 읽고자 하는 레지스터가 이후에 쓰기가 진행되지는 않는지 확인하는 방식이다. 

 

레지스터에 valid bit를 추가하고, decode 단계에서 '쓰기' 명령어임이 확인된다면, 해당 값을 0으로 하여 유효하지 않음을 표시(book)한다. 이후 writeBack 과정에서 '쓰기'가 완료된다면 그때 해당 값을 1로 하여 다시 사용에 안전함을 표시(release)한다. 이 과정 사이의 '읽기' 명령어는 decode 단계에서 레지스터의 valid bit를 확인하여 읽기에 안전한지, 즉 데이터 종속성이 있는지를 확인하는 것이다.

 

문제는 이렇게만 하면 다른 쓰기 명령어가 진행 중인 경우에도 '쓰기'를 완료한 명령어가 valid bit를 1로 release 하는 문제가 발생할 수 있다. 더 구체적으로 'WWR'가 순차적으로 실행된다고 생각해보자. 먼저 쓰기가 끝나는 명령어는 다음에 순차적으로 쓰기가 발생하는지 알 수 없고, writeBack이 끝나는 동시에 해당 Reg를 release한다. 아직 쓰기가 끝나지 않은 명령어가 이전 단계에서 처리되고 있음에도 decode 단계의 읽기 명령어는 해당 Reg의 valid만을 보고 읽기가 가능하다고 오해하게 된다.

 

 

여러 방법이 있겠지만, Scoreboard에 valid bit와 함께 어떤 명령어에 의해 가장 최근 Book 되었는지 확인하거나, valid bit를 단일 비트가 아닌 현재 쓰기가 진행 중인 처리 명령어의 개수를 기억하고 release할 때마다 이 값을 하나씩 줄일 수 도 있을 것 같다. 전자의 경우 writeBack 단계에서 release시 Reg의 tag가 명령어의 tag와 일치하는지 확인하는 것으로 아직 쓰기가 끝나지 않은 다른 명령어가 있다는 것을 확인하는 것이고, 후자의 경우 처리 명령어의 개수가 0이 아닌지를 확인하는 것으로 아직 쓰기가 끝나지 않은 다른 명령어가 있음을 확인한다.

 

Stall

데이터 의존이 있는 경우(data hazard) 또는 분기가 존재하는 경우, 의존이 없어지거나 분기 여부가 결정될 때까지(control hazard) delay 시키는 것이 가장 편한 솔루션일 것이다. 처리되어야 하는 명령어의 처리 사이클은 동일하고, 그 앞 단계의 유효하지 않은 명령어의 controlSignal에 valid 비트를 추가하여 invalid의 경우 MemoryAccess와 WriteBack 단계를 무시하면 된다. 가장 간단한 Hazard 해결 방안이면서도 사이클이 매번 늘리기 때문에 비효율적이다. 

 

Forwarding

writeBack에 저장될 값이 결정되는 시점의 값을 미리 앞 당겨, ALU에서 처리를 마친 결과값 또는 MemoryAccess 단계에서 메모리를 읽은 값을 직접 ALU에 들어갈 input으로 대입하는 방식이다. 단, LW 이후에 바로 레지스터가 겹칠 경우 4단계에서 결정되는 레지스터 값을 같은 사이클에서, 즉 바로 다음 이어지는 명령어의 ALU의 인풋으로 할 수 없기 때문에 아래와 같이 하나의 stall은 피할 수 없다.  

 

 

Branch prediction

분기 결과를 execution stage의 실제 계산을 통한 값이 아닌, 예측 전략에 의한 결과로 생각하고 다음 pc 값을 결정하는 것을 말한다. execution 단계에서 계산한 분기 결과가 예상한 결과와 일치하면, 적어도 한개에서 두개의 무의미한 명령어를 실행하지 않아도 되고, 이는 곧 한개에서 두개의 사이클 이득을 볼 수 있다는 말이 된다.

 

반대로 분기 결과가 예상한 결과와 일치하지 않는다면 예측에 의해 미리 fetch된 한,두개의 명령어가 무의미해지는 것은 같으나, 예측의 실패를 분기 예측 전략에 반영하여 다음번 분기 예측의 가능성을 높인다. 

 

분기 예측에 의해 이득을 볼 수 있는 사이클의 개수는 Branch prediction 방식에 따라 달라진다. decode 단계에서 해당 명령어가 분기 명령어임을 확인한 후 분기 예측이 진행되는 경우에는 fetch 단계에 관련없는 명령어가 이미 실행되고 있는 경우이므로, execution 단계에서 분기 결과를 확인한 후 분기가 처리되는 경우보다 한 개의 사이클 이득을 얻을 수 있다. 또는 이전 분기 결과를 담은 버퍼를 사용하여, fetch 단계에서 pc 값을 통해 분기 명령을 확인하고 분기 예측이 진행되는 경우, 분기 예측을 진행하지 않는 경우보다 두 개의 사이클 이득을 얻을 수 있는 것이다.

 

Static Branch Prediction

분기를 예측하는 전략이 정적인 방식을 말한다. 이 전략으로 해당 분기 명령어가 분기 될지, 안될지를 예측하게 된다. 예를 들면 항상 분기가 일어난다고 예측하는 전략인 Always taken, 반대로 항상 분기가 일어나지 않는다고 예측하는 전략인 Always not taken, 분기의 방향이 후방인 경우에는 분기가 일어남을, 전방인 경우에는 분기가 일어나지 않는다고 예측하는 전략인 BTFNT(Backward taken, Forward not taken) 등이 있다.

 

Dynamic Branch Prediction

분기를 예측하는 전략이 예측과 검증이 진행되면서 이전 예측 성공 여부가 다음 예측에 반영되는 방식을 말한다. 대표적으로 bit counter를 이용하여 이전 결과가 다음번 예측에 반영될 수 있도록 할 수 있다. 대표적인 1bit counter 방식, 2bit counter 방식을 소개한다. 

 

1. single bit counter prediction

 

 

 

 

2. Saturation two bit counter prediction 

3. Hysteresis two bit counter prediction 

Branch target buffer

명령어가 분기 예측되려면 명령어가 우선 해석되어야 한다. 해당 명령어가 분기 명령어인지 확인해야하고, 분기하고자 하는 다음 pc 값을 decode 단계에서 해석해야한다. 만일 명령어가 분기 명령어가 맞으면 분기 예측을 실행하고 taken으로 예측된다면 해석한 nextPc를 다음 fetch의 pc로 사용한다. 이때 이득을 볼 수 있는 사이클은 1개이다.

 

만약 decode 단계가 아닌 fetch 단계에서 분기 예측이 될 수 있다면 어떨까. fetch 단계에서 바로 분기 예측을 실행하고 바로 다음 사이클의 fetch에 그 결과를 사용할 수 있어진다. taken으로 예측된다고 하고, 그 예측이 맞다면 execution 단계에서 결과를 예측하는 것보다 두개 사이클의 이득을 볼 수 있어진다.

 

Branch target buffer는 pc만을 이용하여 분기 예측을 하기 위해 사용하는 버퍼이다. 분기 명령어의 pc값과 target pc값을 저장하고 다음번에 같은 pc가 수행될 때 그 값을 참고하여 분기 예측할 수 있어진다. 

 

 

이때 모든 pc 값을 다 담을 수 없기 때문에, 또 그렇다고 index가 존재하지 않아 모든 buffer line을 매번 탐색할 수 없기 때문에 index와 tag를 이용한다. pc 주소의 일정 부분을 index로, 나머지 부분을 tag로 한다. 이후 다른 pc가 들어왔을 때 index에 해당하는 tag 데이터를 비교하여 해당 인덱스에 같은 명령어 정보가 존재하는지 확인하는 식으로 hit/miss를 결정할 수 있다.

 

Two-level global history branch predictor

프로그램에서 조건문이 연속되고 이들이 서로 의존적인 경우처럼, 특정 명령어의 기록이 아닌 최근에 실행된 분기 명령어의 전역적인 행동의 기록을 Global branch history라고 한다.

 

예를 들어 어떤 프로그램의 가장 최근 분기가 Taken -> Not Taken -> Taken -> Taken 이라고 하자. 이 패턴이었을 때 분기 여부를 기록하고 다음번에 같은 패턴의 분기가 발생할 경우 이전 기록과 같은 분기 결과로 예측할 수 있는 것이다. 이를 테면 single bit counter prediction 전략을 사용하는 상황에서, 기존에 TNTT의 분기 결과가 T이면 다음번 TNTT 분기 결과를 T으로 예상하고, 틀릴 경우에는 다음번 TNTT에서 F를 예상하는 것이다. 

 

 

어떤 분기 패턴에서 기존에 어떤 분기 예측 결과가 있었는지 저장하기 위해 pattern history register가 필요하다. global history register의 n개 비트를 인덱스로 하는, 즉 2^n개의 라인 수를 갖고 있는 분기 예측 결과 표가 필요한 것이다. 위의 예시라면 Pattern history register는 총 16개의 라인이 있을 것이고, single bit counter prediction을 사용하기 때문에 매 라인마다 1bit 씩 이전 분기 예측 결과를 저장하게 되는 것이다. 물론 two bit counter prediction도 문제 없다. pattern history register의 각 라인이 2bit씩 할당되어, strongly taken/weakly taken/weakly not taken / strongly not taken을 저장하면 되는 것이다.

 

Global history register와 branch target buffer를 결합하여 최근 4개 분기 결과에 따른 분기 예측 / Next pc를 얻는 구조는 위와 같다. 이를 Two-level Global history branch predictor라고 한다.

 

Two-level local history branch predictor

Global history와 반대로 특정 명령어에 따른 행동을 기록하고 이 패턴을 통해 분기 예측한다. 예를 들어 이전에 TNTTNT 패턴의 경우 항상 다음은 T으로 이어졌다고 가정해보자. 특정한 pc의 이전 분기 기록이 TNTTNT이라면 다음은 역시 T일 가능성이 크다. 전체 프로그램의 분기 패턴만을 기록하는 Global history branch predictor에선 이 예측을 놓치기 쉽다. Global history branch predictor는 프로그램 전체의 분기 패턴을 기록한다면, Local history branch predictor는 반대로 명령어마다의 이전 분기 패턴을 기록하여 예측에 활용하는 방식이다.

그렇다고 Local history 기반의 예측이 Global history 기반의 예측보다 더 우세한 것은 아니다. 상황에 따라 우세한 global/local history 예측기가 다르고, 우세한 saturation/hysteresis bit counter 전략이 다르다. 따라서 최근에는 여러 예측기를 바꿔가며 서서히 성능을 올려보거나, 분기마다 다른 예측기를 사용하고 결과를 확인하는 등의 방식으로 예측기를 선택한다.