23.09.12 최초 작성

1. Pipeline

여러 작업을 병렬적으로 처리하는 방법이다.

1.1 성능 향상

$(실행 시간_{파이프라인 적용})=\frac{(실행 시간_{파이프라인 미적용})}{(파이프 단계 수)}$

1.2 Pipelining에 적합한 Arm Structure

1. 모든 명령어가 같은 길이를 가진다.
   • 한 사이클에 명령어 인출과 해독이 쉽게 이루어진다.
2. 명령어 형식의 갯수가 적고 Format이 일반화되어있다.
3. 메모리 피연산자가 적재와 저장 명령어에서만 나타난다.
   • 실행단계에서 메모리 주소를 계산하고 다음 단계에서 메모리에 접근할 수 있다.

2. Datapath & Control

• IF(Instruction Fetch from Memory) : 명령어를 메모리에서 인출하는 과정
• ID(Instruction Decode & Register Read) : 명령어를 해독해서 Operand Register를 읽는 작업
• EX(Execute Operation or Calculate address) : Operation을 수행하고 주소를 계산하는 작업
• MEM(Access Memory Operand) : Operand, 목적지에 Address가 있을 때 메모리에 접근하는 과정
• WB(Write Result Back to Register) : 레지스터에 작업 결과를 기록하는 작업

각 Stage마다 소요되는 시간이 다르기 때문에 가장 긴 Stage에 맞춰 작업을 수행한다.

3. Hazard

다음 명령어가 다음 클럭 사이클에 실행될 수 없는 상황.

3.1 Structure Hazard

• 동시에 같은 resource(HW)를 사용하려고 할 때 발생한다.
• 만약에 동시에 같은 공간을 Load/Store, Fetch 하려고 할 때 Fetch 과정이 멈추게 된다(Stall).
• 명령어, 데이터 메모리를 따로 두어 이를 방지할 수 있다.

3.2 Data Hazard

• 어떤 연산의 결과를 통해 연산을 수행해야 하는데 아직 결과가 나오지 않았을 때 발생한다.

• 이전 명령어의 X1 결과를 받아올 수 없으므로 이전 명령어의 연산이 끝난 뒤 다음 명령어의 IF가 시작될 수 있다.

• 어떤 결과값을 바로 사용할 수 있도록 추가적인 Datapath를 두어 아래 그림과 같이 해결할 수 있다. (Forwarding/Bypassing)
  

• 하지만 이전 명령어의 결과값이 계산되지 않았을 때 Forwarding을 활용해 완전히 해결할 수 없는 경우도 있다.

  

3.2.1 Forwarding

SUB X2,X1,X3 // Register X2 written by SUB
AND X12,X2,X5 // 1st operand(X2) depends on SUB
OR X13,X6,X2 // 2nd operand(X2) depends on SUB
ADD X14,X2,X2 // 1st(X2) & 2nd(X2) depend on SUB
STUR X15,[X2,#100] // Base (X2) depends on SUB

AND, OR연산에서 Hazard가 발생한다.

Detecting the Need to Forward

다음과 같은 경우 Data Hazard가 발생한다.
(ID/EX.RegisterRs : ID/EX에 있는 파이프라인 레지스터 Rs)
(Rd = XZR일 경우 Forwarding 하지 않음)

• 1a. EX/MEM.RegisterRd = ID/EX.RegisterRn1
• 1b. EX/MEM.RegisterRd = ID/EX.RegisterRm2
• 2a. MEM/WB.RegisterRd = ID/EX.RegisterRn1
• 2b. MEM/WB.RegisterRd = ID/EX.RegisterRm2

1)의 경우 EX/MEM 레지스터로부터 Forwarding
2)의 경우 MEM/WB 레지스터로부터 Forwarding

만약 레지스터(Rd)에 쓰지 않는 명령어의 경우 forwarding이 불필요하다. (마찬가지로 Rd = XZR(0)일 경우 Forwarding 하지 않음) 이를 Control Signal에 Write 신호가 인가되었는지 여부에 따라 판단한다.

• Forwarding Unit을 추가해 EX/MEM.RegisterRd,MEM/WB.RegisterRd,ID/EX.RegisterRn1,ID/EX.RegisterRm2값을 입력받아 비교한 결과를 Forward A, Forward B Control 신호로 내보낸다.
  • 각 Forward A, Forward B는 2비트 신호이며 각 값의 의미는 다음과 같다

  값	Source	의미
  Forward A = 00	ID/EX	레지스터로 부터 나온 값을 Rn1으로 선택
  10	EX/MEM	ALU로 부터 나온 값을 Rn1으로 선택
  01	MEM/WB	이전 사이클에서 나온 ALU 결과 or 메모리 데이터를 Rn1으로 선택
  Forward B = 00	ID/EX	레지스터로 부터 나온 값을 Rm2으로 선택
  10	EX/MEM	ALU로 부터 나온 값을 Rm2으로 선택
  01	MEM/WB	이전 사이클에서 나온 ALU 결과 or 메모리 데이터를 Rm2으로 선택

• EX Hazard

if (EX/MEM.RegWrite
and (EX/MEM.RegisterRd ≠ 31)
and (EX/MEM.RegisterRd = ID/EX.RegisterRn1)) ForwardA = 10
if (EX/MEM.RegWrite
and (EX/MEM.RegisterRd ≠ 31)
and (EX/MEM.RegisterRd = ID/EX.RegisterRm2)) ForwardB = 10

• MEM Hazard

if (MEM/WB.RegWrite
and (MEM/WB.RegisterRd ≠ 31)
and (MEM/WB.RegisterRd = ID/EX.RegisterRn1)) ForwardA = 01
if (MEM/WB.RegWrite
and (MEM/WB.RegisterRd ≠ 31)
and (MEM/WB.RegisterRd = ID/EX.RegisterRm2)) ForwardB = 01

Double Data Hazard

ADD X1,X1,X2
ADD X1,X1,X3
ADD X1,X1,X4

이 경우 1번째 ADD의 결과 없음으로 2번째 ADD에, 2번째 ADD의 결과 없음으로 3번째 ADD에 Data Hazard가 발생한다. 이로 인해 EX Hazard와 MEM Hazard가 발생하게 된다.
이 때 MEM Hazard에서 오는 Forwarding을 우선한다.

• 개선된 MEM Hazard

if (MEM/WB.RegWrite
and (MEM/WB.RegisterRd ≠ 31)
and not(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 31)
and (EX/MEM.RegisterRd ≠ ID/EX.RegisterRn1))
and (MEM/WB.RegisterRd = ID/EX.RegisterRn1)) ForwardA = 01
if (MEM/WB.RegWrite
and (MEM/WB.RegisterRd ≠ 31)
and not(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 31)
and (EX/MEM.RegisterRd ≠ ID/EX.RegisterRm2))
and (MEM/WB.RegisterRd = ID/EX.RegisterRm2)) ForwardB = 01

• Datapath with Forwarding
  

Load Use Data Hazard

• 파이프라인 사용 시 LOAD 연산이 인출한 데이터를 사용하는 명령어의 경우 LOAD연산이 진행되는 도중 EX단계에 들어가고 사용하는 값이 LOAD연산이 끝날 때 레지스터에 저장되므로 Forwarding을 통해 해결할 수 없다. 따라서 한 단계 지연시켜야 해결할 수 있다.
• 이것을 위해 Hazard Detection Unit이 이 경우를 발견해 해결해야 한다. 만약 Hazard를 검출하면 ID단계의 명령어에 1clock만큼 지연이 발생한다.

if (ID/EX.MemRead and
((ID/EX.RegisterRd = IF/ID.RegisterRn1) or
(ID/EX.RegisterRd = IF/ID.RegisterRm2)))
stall the pipeline

• 지연이 발생한 경우 Control Signal을 0으로 만들어 아무것도 하지 않는 상태(nop 명령어)로 만들어야 하며 PC값이 갱신되는 것을 막아야 한다.

• 이후 DI단계를 다시 한번 실행하며 이어지는 명령어는 IF단계를 다시 실행한다.

-Datapath with Hazard Detection Unit

3.3 Control Hazard(Branch Hazard)

• 분기 시 목적지 주소를 PC에 저장하는데 이전 명령어에 의해 이 값이 변경되는 경우 발생한다.

• 아래 그림과 같이 조건부 분기 명령어마다 지연시켜 해결할 수 있다.

  

• 아래 그림과 같이 분기 명령어가 수행되지 않는다고 예측하고 만약 분기명령어가 수행 될 경우 지연시켜 해결할 수 있다. (Predict)
  

• 만약 분기가 발생한다면 그 판단 시점은 EX단계가 완료될 때이며 이 때 3cycle만큼 진행된 작업들을 모두 쓸어내야(flush)한다.

3.3.1 Dynamic Prediction

• flush는 비용이 많이 드며 이를 방지하기 위해 branch 명령어를 인지하면 분기 여부와 주소 계산을 빠르게 해줘야 한다. 이를 위해 Comparator을 추가해 이 계산을 IF단계에서 수행하도록 했다.

  

• IF단계의 명령어를 버리기 위해 IF.Flush라는 제어선을 추가해 IF/ID파이프라인 레지스터의 명령어 필드를 0(nop)으로 만든다.

4. Exception

• 명령어 실행의 흐름을 바꾸는 사건(분기나 점프와 다름).
• CPU내에서 발생한다

4.1 Exception Handling

1. ELR(Exception Link Register)에 문제를 일으킨 명령어의 주소 저장

2. 특정 주소에 있는 운영체제로 제어를 옮김

3. 운영체제가 적절한 조취를 취함 (미리 정의된 행동, 프로그램 중지 & 오류 보고 ...)

4. ELR을 참고해 재개할 작업을 판단

   예외 판단 방법

• ESR(Exception Syndrome Register)라 불리는 상태 레지스터 확인
• Vector Interrupt를 확인해 상황 확인

4.2 Pipeline에서 예외

• Pipeline에서는 여러개의 Exception이 발생할 수 있다.
• Exception발생 시 가장 많이 진행된 명령어를 우선해 처리한다.
• Pipeline은 Exception을 Hazard의 다른 형태로 취급한다.
• Exception 처리 단계

  1. Exception이 발생한 다음 명령어들을 모두 flush 한다.

     • 이 역할을 하는 제어신호를 각각 ID.Flush, EX.Flush, EX.Flush라고 한다.
     • ID를 flush 하기 위해 제어신호를 0으로 둬 지연시킨다.
     • Hazard Detection Unit은 1이 되며 ID.Flush와 OR 연산을 해 명령어를 버린다.

  2. PC에 Exception을 처리할 명령어의 주소를 저장한다.

  3. 문제를 일으킨 명령어의 주소를 ELR에 저장한다.

• 예외 처리를 위한 Datapath