들어가며
파이프라이닝과 그 하위 개념들에 대해서 알아보자.
파이프라이닝의 예시
위 그림처럼 세탁을 하는 구조가 있다고 해보자. 세탁물을 돌리고, 건조하고, 개서, 장롱에 넣는 것이다.
위 그림에서 1번째 방법처럼 수행을 하면 하나의 task를 수행하는 동안 다른 stage가 놀게 되는 상황이 발생한다.
2번째 방법으로 수행하면 어떻게 될까? 훨씬 시간이 짧아진다 왜냐하면 특정 한 시점에서 idle한 stage의 수가 줄어들기 때문이다.
이렇게 overlapping execution을 파이프라이닝이라고 한다.
파이프라이닝을 하면 파이프라이닝의 stage 수에 비례해서 속도가 향상된다.
그리고 파이프 라이닝은 특정 시간 내에 처리할 수 있는 양인 처리량(throughput)이 증가한다.
Five stages
파이프라이닝은 5가지 단계로 구성되어 있다.
순서대로
- 명령어를 가져옴
- 명령어를 해석해서 레지스터 파일에서 데이터를 읽음
- 산술, 논리 연산을 수행
- 메모리에서 데이터를 읽거나 씀
- 레지스터에 데이터를 씀
이다.
LEGv8과 파이프라이닝
LEGv8은 다음과 같은 이유로 파이프라이닝에 유리하다.
- 모든 명령어가 32비트로 이루어져있다. 그래서 IF, ID 단계를 one cycle로 처리하는데에 용이하다.
- 메모리에 접근하는 명령어가 Load, Store 2개뿐이기에 EX, MEM단계를 단순화해서 하드웨어를 만들 수 있다.
- 메모리 align이 잘되어있어서 불필요한 메모리 접근이 없다.
위 그림에서 네모박스는 저장소를 의미한다. 오른쪽이 색칠되어있으면 다음 stage에 write동작을 수행한 것이고, 왼쪽이 색칠되어 있으면 이전 stage에서 write를 당한 것으로 본다. 위 그림에서 ADD연산은 메모리를 사용하지 않으므로 MEM스테이지는 색칠되지 않은 것을 볼 수 있다.
Hazard
Hazard란 원하지 않는 또는 예기치 않은 변화가 발생할 수 있는 잠재적인 문제를 의미한다.
structural hazard
명령어를 읽어들이는 메모리와, 데이터를 읽어들이는 명령어가 분리되어있지 않을 경우에 발생할 수 있는 hazard이다.
위 그림에서 Instruction을 가져오려는 부분과 데이터를 읽으려고 하는 부분이 중복될 수 있는 경우이다.
구조적 해저드는 두 메모리를 분리하면서 해결된다.
Data hazard
특정 stage가 다른 stage가 끝나야만 실행될 수 있기에 발생할 수 있는 hazard이다.
위 그림처럼 add연산 이후에 sub연산을 하려고 하는데 add연산의 Rd가 바로 다음 sub연산에서 피연산자로 이용될 경우, sub연산은 add연산이 끝나기를 기다려야한다.
이를 해결하기 위해서 하드웨어를 이용하며, ADD연산의 Ex가 끝나자마자 바로 SUB에게 데이터를 전달해주는 것으로 해결한다. 그리고 이를 전방전달(forwarding)이라고 한다.
Load-use data hazard
Load 명령어를 사용하기 떄문에 발생하는 hazard이다.
이 경우에는 어쩔 수 없이 파이프라이닝을 한 단계 지연하게 되며 이를 Bubble이라고 한다.
이 말고도 명령어의 순서를 바꾸는 소프트웨어적인 방법을 사용하기도 한다.
Control hazard
조건부 분기에 의해서 PC값이 변경될 때 이미 파이프라인에 있는 명령어가 Flush 되는 경우이다. 조건부 분기를 하는 명령어에서 분기는 MEM stage에서 결정된다. 그래서 그 전에 3단계의 flush가 발생한다. 이는 하드웨어를 추가해서 ID stage에서 분기를 결정하게 해서 해결할 수 있다.
위 그림처럼 한 번의 bubble만으로 control hazard를 해결한다.(기존에는 3번이다.)
그런데 한 번의 stall을 해결하기 위해서 에측(prediction)을 한다.
Prediction
Static branch prediction
for문이나 if문에서 backward(이전주소)로 분기할 것이라고 예측하는 것이다.
Dynamic branch prediction
하드웨어가 실제 branch behaivor을 측정해서 현재 trend를 파악해서 앞으로도 trend대로 움직일 것이라고 판단하는 것이다.
- N-bit dynamic branch prediction: 현재 상태가 taken인데 n번의 not-taken이 발생하면 그 다음부터는 not-taken이 발생할 것이라고 예측하는 것이다.
- Hybrid dynamic branch prediction: branch에서 제일 best인 prediction을 골라주는 것. 과거 브랜치의 기록이 있는 BHR(Branch History Register)을 이용한다. 그리고 BTB(Branch Target Buffer)이 타겟 주소를 계산한다.
Pipline DataPath
파이프라인은 앞의 stage 정보를 저장하는 특별한 register가 필요하다. 왜냐하면 파이프라이닝 기법에 의해서 앞서 계산된 결과는 그 다음 사이클에 사라지기 때문이다. 그래서 저장을 해두어야한다.
위 그림에서 색칠된 레지스터는 Pipline register라고 불리며 이전 stage의 모든 데이터를 저장할 수 있을만큼 충분히 크다.
위 그림에서는 마지막에 WB stage에서 데이터를 작성하려고 할 때, regster file에 제공된 Write register가 정확한가에 대한 의문을 제기하고 있다. 왜냐하면 register file에 데이터를 쓸 때 Rd에 관련된 정보는 없기 때문이다.
이 문제를 해결하기 위해서 Rd를 쭉 pipline register에 저장해서 가지고 다닌다. 그러면 어느 레지스터에 write을 해야하는 지에 대한 정보가 유지된다.
WB stage in Store Instruction
store 명령어를 사용하면 WB stage에서 할 일이 없다. 그래도 진행은 한다. 다만 아무것도 하지 않을 뿐이다.
Pipline Diagram
파이프라이닝은 위같은 다이어그램으로 표현할 수 있다.
빨간색 점들로 둘러쌓인 부분은 Steady state라고 불리며 모든 stage가 활성화되어있는 상태를 의미한다. 그 이후에는 점점 idle stage가 증가하며 이를 flushing이라고 한다.
Pipline control
Control 신호들은 어떨까? 최초에 ID stage에서 생성된 컨트롤 신호들은 한 번 생성되면 사라진다. 하지만 각 stage가 진행됨에 따라서 필요한 신호들을 그때그때 주어야하는데 그 때마다 다시 Control 신호를 생성할 수는 없다.
그 때는 Pipline Register를 확장해서 이후 stage에 control 신호들이 전달될 수 있게 한다.
Control Signal이 추가된 Piplined Datapath이다.
Register file 앞에 있는 Reg2Loc 신호는 R-type, D-type instruction이 서로 포멧이 다르기 때문에 어디서 Rd의 관련된 정보를 가져올 것인지를 선택하는 MUX를 제어한다.
Hazard in Piplined Datapath
Data hazard
위 그림에서 2, 3번째 명령어에서는 해저드가 발생한다. 이를 어떻게 탐지할 수 있을까?
위 조건을 만족하면 해저드가 발생했다고 간주한다. EX stage에서 계산되어서 그 값이 저장될 레지스터 주소와 EX stage에서 계산될 레지스터 주소가 같으면 Data hazard가 발생했다고 간주한다. MEM stage에서도 마찬가지이다.
하지만 이후에 들어온 레지스터에서 레지스터에 write을 수행하지 않는다면 아무 의미가 없다.
그래서 Rd레지스터가 0인지를 검사하고(0이면은 write을 하지 않는다는 뜻이다.)
RegWrite 신호가 0인지를 추가적으로 본다.
그리고 ALU앞에 Mux를 추가해서 기존의 흐름대로 온 데이터, forwarding으로 온 데이터 등, 다양한 데이터에서 어떤 데이터로 ALU연산을 할 건지를 선택한다.
위 상황에서는 더블 해저드가 발생했다고 볼 수도 있다. 하지만 1번째 명령어의 연산 결과가 3번째로 가는 것은 아니기 때문에 MEM 해저드라고 판단해서는 안된다. 그래서 MEM 해저드는 MEM 해저드가 발생한 그 상황에 EX 해저드가 발생하지 않아야만 MEM 해저드로 간주한다.
Load-use hazard detection
위 그림 MemRead signal이 1이고 ID/EX(먼저 입력된 명령어)의 Rd와 IF/ID(나중에 입력된 명령어)의 피연산자가 같은 경우에는 Load-use hazard가 발생했다고 간주한다. 그러면 stall하고 bubble을 insert한다.
stall을 발생하면 세가지 동작이 수행된다.
- PC값 update를 막는다.
- IF/ID update를 막는다.
- ID/EX register를 모두 0으로 만든다. 이건 뒤에 있는 모든 elemnet를 멈추게 한다.
Control hazard
분기 명령어가 발생하면 3개의 stage에서 flush가 발생한다. 이를 줄기이기 위해 ID stage에서 분기 판별을 한다. 그러면 flush 횟수를 줄일 수 있다.
위 그림의 맨 오른쪽 네모박스를 보면 ID stage에서 분기를 결정할 수 있게 두 레지스터의 차가 0인지를 확인하는 하드웨어가 추가되었다.
그리고 매 순간마다 PC값을 계산해서 앞단으로 넘겨주며 PC값을 업데이트하기 직전에 mux를 추가해서 만약에 분기가 결정되면 분기 주소로 PC값을 업데이트하도록 MUX에 신호를 보낸다.
