The Processor Part.3 - Computer Architecture

• 다음 싸이클에서, 다음 Instruction이 실행되는 것을 막아버리는 상황이 발생할 수 있다.
• 즉, 매 cycle 마다 instruction을 실행해야 할텐데, 그렇지 못하는 상황이 발생할 수 있다.

• Structure Hazard(구조적 위험)
• instruction을 수행하기 위해 필요한 하드웨어 자원이 사용 중(busy)일 수 있다.
• E.g. 두 개의 instruction이 같은 시점에 같은 메모리를 읽으려 할 때

• Data Hazard(데이터 위험)
• instruction을 수행하기 위해 필요한 데이터가 있는데, 다른 instruction이 데이터를 read/write 하고 있다면(그 데이터가 busy 상태라면), 완료하기까지 기다려야 한다.
• instruction이 파이프라인에 아직 존재하는 이전의 instruction의 결과에 의존할 때
add r1, r2, r3
sub r4, r2, r1

• Control Hazard(제어 위험)
• 어떤 instruction을 수행하기 위해 다른 instruction의 결과에 의존하는 경우, 제어 행동을 결정하는 것이 이전의 instruction에 의존하는 경우.
• branch instructions
beq r1, r4, loop
add r1, r2, r3

Structure Hazards

• 하드웨어 자원을 이용하는 것에서의 충돌

• 단일(single)메모리를 사용하는 MIPS pipeline에서
• Load/Store 명령은 data 접근을 위해 memory에 접근한다.
• instruction fetch도 instruction을 가져오기 위해 memory에 접근한다.
• 서로 동시에 진행될 순 없으므로, 한 쪽은 대기를 해야하고, 해당 cycle을 지연(느리게 하다, stall) 시킬 수 있다.
• pipeline에 “bubble”을 야기할 수 있다. (아무 것도 하지 않는)

• 그러므로 pipeline화 된 datapath는 Instruction memory와 data memory가 분리되어야 한다.
• 메모리에서 instruction 영역과 데이터 영역의 분리
• 혹은 instruction과 data cache를 분리

Single Memory causes a Structural Hazard

Data Hazard

• instruction에 어떤 문제가 있는가?
• RAW → Read After Write. 쓰기 후에 읽기

• 이는 forwarding(bypassing)으로 hazard를 해결할 수 있다.
• 그렇다면 forward가 필요한 때는 어떻게 알 수 있을까?

sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)

Dependencies

• 전의 instruction이 끝나기 전에 다른 instruction을 시작하는 문제

• 녹색석을 위에서 아래로 표현했지만, 실제 장치는 하나이기 때문에 오른쪽에서 왼쪽으로 표현해야 한다.
• 다음 cycle 기준으로 EX/MEM 레저스터가 생성된 값을 가지고 있고 (해당 명령어는 MEM 단계로 들어갔으니), 다다음 cycle 기준으로 EX/MEM 레지스터에는 이미 다른 값으로 덮혔지만, MEM/WB 레지스터에 해당 값을 가지고 있다(해당 명령어는 WB 단계로 들어갔으니)
 

Stall: One Way to “Fix” a Data Hazard

• 기다림을 통해 data hazard를 해결할 수 있지만, throughput에 영향을 준다.

How About Register File Access?

Another Way to “fix” a Data Hazard

• 일시적인 result를 이용해서, 기다리지 않게 한다.

Forwarding

Data Forwarding (aka Bypassing)

• 모든 데이터는 시간을 거슬러 올라가는 종속성.
• EX stage는 R-type ALU result / 효과적인 주소 계산 결과를 생성
• MEM stage는 lw results 생성

• 임의의 파이프라인 레지스터에서 ALU로 입력을 가져감으로써 전달
• ALU 입력에 MUX 추가
• 따라소 Rd 데이터를 EX의 stage Rs 및 Rt ALU 중 하나 혹은 둘 다 전달할 수 있다.
• 00: normal input(ID/EX 파이프라인 레지스터)
• 10: 이전 instr (EX/MEM 파이프라인 레지스터)에서 전달
• 01: instr 2 back에서 forwarding (MEM/WB 파이프라인 레지스터)

• 적절한 control hardward 추가
• forwarding을 사용하면 데이터 종속성이 있는 경우에도 최대 속도로 실행할 수 있다.
 

Detecting the Need to Forward

• pipeline을 통해 레지스터 번호를 넘겨준다(pass)
• e.g., ID/EX. RegisterRs = ID/EX pipeline register의 Rs(SourceRegister)를 위한 레지스터 번호

• EX stage에서의 ALU 피연산자 레지스터 번호는 다음과 같다. (R-format의 ALU)
• ID/EX. RegisterRs, ID/EX.RegisterRt

• Data Hazard가 발생하는 경우는 아래의 4가지 경우이다.

• 1a/b는
• (다음 cycle의 instruction) EX의 Rs/Rt(피연산자들)가 (이전 cycle의 instruction)MEM의 Rd가 같을 때.
• 즉 WB를 위한 대상 레지스터에 값이 쓰이고, 다른 명령어가 그걸 읽어야 하는데, 아직 값이 쓰이지 않아서.
• 1cycle 전의 instruction에서, EX직후에서 “계산된 Rd에 쓰일 값”을 끌어와서 사용.

• 2a/b는
• (다음 cycle의 instruction)EX의 Rs/Rt(피연산자들)가 (이전 cycle의 instruction)WB의 Rd가 같을 때.
• 마찬가지로, WB을 위한 대상 레지스터에 값이 쓰이고, 다른 명령어가 그걸 읽어야 하는데, 아직 값이 쓰이지 않아서.
• 2cycle 전의 instruction에서, “Rd에 쓰일 값이 흐르던 것”을 MEM이후에서 끌어와서 사용.

• forwarding은 이전의 instruction에서 늦게 쓰여지는 것들을 해결하는 것이라서 (아직 그 값이 안쓰여져서 문제였던), pipeline register에 함께 전해지는 제어 신호를 살펴보면, RegWrite 신호(마지막 WB에서 register에 쓰이라는 신호)를 찾아볼 수 있을 것이다.
• EX/MEM.RegWrite, MEM/WB.RegWrite

• 그리고 쓰이는 것이니, 쓰일 대상 레지스터 번호를 나타낼 Rd도 $zero가 아닐 것이다.
• EX/MEM.RegisterRd ≠ 0
• MEM/WB.RegisterRd ≠ 0
• 0번 레지스터는 쓰기가 불가능한 $zero 고정이기 때문

Datapath with Forwarding Hardware

• Forwarding 감지를 위해, 현재 cycle의 Rs, Rt를 Forwarding Unit에 보낸다.
• 현재 피연산자 Rs,Rt가 제대로 준비되었는지가 Data hazard와 forwarding으로 해결의 핵심이므로, 현재 cycle은 피연산자가 필요한 실행단계인 EX stage 이다.

• 1cycle 전의 instruction과 2cycle 전의 instruction에서 (둘 다 아직 덜 끝난) 쓰여질 목표 레지스터(Rd)가 현재 Rs나 Rt와 같다면, 레지스터에는 값이 아직 제대로 쓰이지 않았을 것이다.

• 이전 cycle의 Rd를 보존하기 위해, Rd를 pipeline register에 넘겨지도록 한다.
• 1cycle 전의 Rd는 EX/MEM.RegisterRd에
• 2cycle 전의 Rd는 MEM/WB.RegisterRd에.

• Forwarding Unit에서는,
• 현재 cycle의 Rs나 Rt와, EX/MEM.RegisterRd 혹은 MEM/WB.RegisterRd가 같은 번호를 가지는지 비교한다.
• EX/MEM.RegisterRd, MEM/WB.RegisterRd 모두 Rs, Rt와 일치하지 않으면 상관없다.
• EX/MEM.RegisterRd가 Rs나 Rt와 일치한다면, EX직후인 ALU의 결과값을 가져와서 사용한다.
• MEM/WB.RegisterRd가 Rs나 Rt와 일치한다면, WB로 쓰려는 값을 가져와서 사용한다.
• Forwarding Unit은 제어신호를 3x1의 MUX들로 보내, ALU의 피연산자로 ID stage의 레지스터의 값(일반적인 경우)를 사용할지, forwarding으로 가져온 값을 가용할지 제어한다.
 

Data Forwarding Control Conditions

첫번째 구현

1. EX/MEM hazard:

두번째 구현

1. EX/MEM hazard:

1. MEM/WB hazard:

세번째 구현

1. EX/MEM hazard:

1. MEM/WB hazard:

Yet Another Complication!

• 다음의 순서를 생각해보자. (RAW. Read After Write. 쓰기 후에 읽기)

• 병렬식으로 순서가 얽히지 않고(WAW or WAR의 Data hazard가 아니더라도), 반드시 순서대로 진행된다고 하더라도,

• 양쪽 hazard가 모두 일어난다면, (1cycle 전, 2cycle 전)
• 좀 더 최근(현재에 가까운) 것을 사용

• double일 경우에는 EX/MEM hazard의 조건이 변경됨
• EX/MEM hazard가 아닐 경우에만 MEM/WB hazard forwarding
• 즉, double이라면, 항상 EX/MEM hazard로 보고 EX 직후의 값(1cycle 이전의, 최근의)을 가져오면 된다

수정된 Control Condtions

1. MEM/WB hazard

Datapath with Forwarding Hardware

Memory-to-Memory Copies

• 바로 store 뒤에 있는 load의 경우(메모리-투-메모리 복사본), MEM/WB 레지스터의 전달 하드웨어를 데이터 메모리 입력에 추가하여 중단을 방지할 수 있다.
• 메모리 액세스 단계에 전달 장치를 추가해야 한다.
• load를 함으로써 중단을 피해야 한다.

Forwarding(or Bypassing): What about Loads

• forwarding을 사용해서 항상 stall (기다림)을 피할 수는 없다
• 필요한 상황에 값이 아직 계산되지 않았다면
• 제 때에 값을 끌어올 수도 없이 “존재하지도 않는다면” 활용도 불가능하다.

• loads instruction에 따라서 stall을 무조건 해야한다.
• lw $2, 20($t1) 명령어에는 20($t1)의 주소를 ALU에서 계산,(이건 수행했음)
• 그 주소를 토대로 MEM에 접근,(이제 접근 중이라 값을 다 못 가져옴)
• 그 곳의 값을 $s2에 load.
• 어쨌든 최대한 줄이려고 해도(레지스터에 write back 전에 빼오려고 해도),MEM에 접근 이후에나 원하는 값을 알 수 있음. 최대한 줄여도 1cycle의 stall이 발생.

Can’t always forward

• Load word는 여전히 hazard를 유발한다: 어떤 instruction이 load instruction에 따라 register에서 값을 읽어오고, 그 값을 이용하여 작업을 해야하는 순간

Stalling

• instruction을 같은 stage에서 keeping 해놓음으로써 stall 가능

Load-use Hazard Detection Unit

• ID stage에 hazard detection unit이 필요하다.
• load하고 그것을 바로 쓰게 된다면 그 사이에 stall을 넣어 줄 unit

1. ID Hazard Detection

• 이전 cycle의 명령어가 MemRead 종류라서, MemRead 신호가 있었고,

• 현재 cycle의 명령어의 피연산자(Rs나 Rt)의 번호가 이전 cycle의 Rt의 번호(메모리에서 읽은 값을 넣을 레지스터 번호)와 같을 경우.
• 왜 Rt냐? Load를 했으면 I-format이기 때문에

Stall Hardware

• 강제로 ID/EX 레지스터의 제어 신호 값들을 모두 0으로 한다(ID 이후 아무것도 동작하지 않도록 한다).
• EX, MEM, WB는 NOP(no-operation)
• EX/MEM 포함, 그 이후의 신호들은 그대로이기 때문에, 이전 cycle의 명령어는 계속 진행됨.
• 한 단계의 bubble이 필요할 뿐.

• 쉰 다음에(제대로 다 준비되면) 명령어를 수행해야 하므로,
• PC와 IF/ID 레지스터의 갱신을 방지한다.
• 현재 명령어가 ID stage에서 다시 decode되도록 한다.
• 직후 명령어(PC+4+4가 아닌 PC+4)가 IF stage에서 다시 fetch되도록 한다.
• 1-cycle의 stall은 이전의 명령어(lw)가 충분히 MEM에서 데이터를 읽어올 수 있도록 해주었다.　　
• 이제 현재 명령어가 EX stage로 진행해도 된다.
 

Adding the Hazard Detection Unit Hardware

• ID stage에서 Hazard Detection Unit이 추가된 것이 보임
• 여기에 ID/EX.MemRead 제어 신호가 전달됨. (1-cycle 전)
• 그리고 ID/EX 레지스터에의 Rt가, (1-cycle 전)
• IF/ID 레지스터의 Rs, Rt가 전달됨. (현재)

• 이것을 토대로 Load-Use Data hazard를 감지하면,
• ID/EX 레지스터에 제어신호를 모두 0으로 하여, 1번 bubble이 생기도록 (한 층만 건드리니까) 해줌.
• PC에는 PCWrite 제어신호를 0으로 하여, PC가 업데이트 되는 것을 방지(직후 명령어는 그대로 다시 fetch)
• IF/IDWrite 제어신호를 보내 현재 명령어가 다시 decode될 수 있도록.
 

Code Scheduling to Avoid Stalls

• 코드의 순서를 바꿈으로써, 다음 instruction에 필요한 결과 값 load 과정에서 발생할 stall을 회피한다.

• C code A = B + E; C = B + F;

• Data Dependency로 stall이 발생하는 순서에서, Independent한 명령어끼리 연속되도록 해서 stall을 없앰.
• 원래의 코드에서, add...,$t2에서, $t2의 값을 알려면, 4($t0) 때문에(MEM 직후까지) forwarding을 해도, 1개의 stall.
• 원래의 코드에서, add...,$t4에서, $t4의 값을 알려면, 8($t0) 때문에(MEM 직후까지) forwarding을 해도, 1개의 stall.
• 원래의 코드는, RAW(Read After Write, write 후에 read)로 Data Dependency가 발생.
• 첫 stall 부분에 차라리lw $t4, 8($t0)를 당겨와서(그동안 이 명령어에 이용되는 값은 변하지 않았으니)　　미리 해 둠(할 수 있는 다른 작업을 해 둠. 바로 위의 명령어와는 independent하니 바로 가능.).
• $t4를 미리 준비해놔서, 두번째 stall도 같이 사라짐.
• 코드의 양이 줄어드는 것이 아님. pipeline에서 발생하는 지연현상을 줄이는 것.
 

Stalls and Performance

• stall은 성능을 저하시킨다.
• 하지만, 정확한 결과를 얻기 위해서는 꼭 필요하다.
• (당연히 정확성이 더 중요. 꼬이면 그 후 다 위험해짐)

• 컴파일러는 코드를 재배치해서 hazard를 피하고 stall을 방지할 수 있다.
• 이를 위해서 컴파일러는 해당 프로세서의 pipeline 구조를 정확히 파악해야 한다.