[Computer Architecture] Chapter 4: The Processor Part 3

Can pipelining get us into trouble?

 

2025.06.03 - [[학교 수업]/[학교 수업] Computer Architecture] - [Computer Architecture] Chapter 4: The Processor Part 2

[Computer Architecture] Chapter 4: The Processor Part 2

 

이전 part에서는 pipeline에 대해 살펴봤습니다. 그런데 pipeline이 만들어내는 문제점은 없을까요? 있습니다. 이를 hazard라고 부르며 다음 명령어가 다음 clock cycle에 시작되는 것을 막는 상황을 말합니다. 즉, pipeline의 원활한 흐름을 방해하여 명령어 실행을 지연시키는 요인입니다. harzard에는 다음 3가지 종류가 존재합니다:

• Structural Hazards: 두 개 이상의 명령어가 같은 hardware resource를 동시에 사용하려고 할 때 발생합니다. 예를 들어, MIPS pipeline에서는 명령어 인출(IF) 단계와 데이터 메모리 접근(MEM) 단계에서 메모리를 사용하는데, 같은 메모리를 사용한다면 structural hazards가 발생할 수 있습니다.
• Data Hazards: 이전 명령어가 아직 완료하지 않은 결과를 사용하려고 할 때 발생합니다. 이는 pipeline 내에서 명령어 간의 데이터 의존성 때문에 발생합니다.
• Control Hazards: 분기(branch)나 점프(jump)와 같이 프로그램의 실행 흐름을 변경하는 명령어 때문에 발생합니다. 다음 명령어가 무엇이 될지(즉, PC+4로 갈지, 아니면 branch target address로 갈지) 분기 결과가 확정되기 전에 결정해야 하므로 문제가 됩니다.

 

이 세 문제를 해결하는 가장 간단한 방법은 waiting입니다. 즉, hazard가 탐지되면 다음 명령들을 hazard가 발생하지 않을때까지 wait하는 방법입니다. 하지만 이 방법은 performance측면에서 좋은 해결책은 아닙니다.

 

Structure Hazards

 

만약 MIPS pipeline이 오직 하나의 memory만을 사용한다면, load/store 연산을 수행할 때 문제가 발생할 수 있습니다(Structure Hazards). 우선 모든 명령들은 IF를 해야하고, load/store가 0.3의 빈도로 나타난다면, memory access에 필요한 cycle은 1.3이 됩니다(CPI = 1.3). 하지만 load명령이 들어온 경우 하나의 cycle에 한 번의 메모리 접근만을 허용한다면 모든 요청을 제때 처리할 수 없음을 의미합니다. 

 

따라서 이를 해결하기 위해 load명령이 나오면 bubble을 유발하여 clock cycle을 지연시키고, 이는 이상적인 CPI = 1을 달성하지 못하게 됩니다. 이런 문제를 해결하기 위해서는

 

(1) 아까 말했듯 bubble을 유발하는 방법과,

(2) instruction fetch용 memory와 data access용 memory로 분리하는 방법,

(3) register file과 같이 한 번에 한 word 이상을 읽을 수 있는 memory를 사용하는 방법이 있습니다.

 

이 structure hazard문제를 그림으로 나타내면 다음과 같습니다:

structure hazard

 

Data Hazard

 

data hazard는 서로 의존관계를 갖는 데이터를 이용할 때 발생할 수 있으며, 이는 single cycle에서는 발생하지 않는 문제입니다. 예를 들어 아래와 같은 명령어들이 있다면:

data hazards

 

각 명령들은 서로 $2에 대해 의존관계를 갖고 있습니다. 즉 sub $2, $1, $3가 끝나야 and $12, $2, $5를 수행할 수 있지만 pipeline의 구조 때문에 sub의 결과가 나와서 $2에 WB되기 전에 and연산이 이뤄져야하고, 그렇게 되면 and연산은 올바른 $2로 연산하지 않게 됩니다. 이를 data hazard문제라고 합니다.

dependencies

 

다시 말해, 이전 명령이 끝나기 전에 의존관계에 있는 데이터를 이용해서 다음 명령이 수행되는 것입니다. 이는 software를 이용해서 해결할 수도 있습니다. 이는 stall(nops)을 하는 것입니다. 즉 위 그림에서 sub $2, ... 에서 WB되는 순간 이후로 모든 명령어들을 delay시키면 됩니다:

Stall: One way to fix a data hazard

 

하지만 이렇게 되면 throughput에 악영향을 줄 수 있기 때문에 최대한 stall을 줄여야합니다. 따라서 WB이후로 미루는 것이 아닌 WB순간까지만 미루는 것입니다. 그리고 이는 internal bypassing을 통해 구현합니다:

internal bypassing

 

원래는 WB와 ID단계가 겹쳤을때는 register write보다는 register read가 먼저 수행됩니다. 따라서 WB와 ID가 겹쳐지면 WB의 결과가 ID에 영향을 줄 수 없습니다. *register write은 register 내부에서 clock이 뛰어야 write이 되지만, read는 IF에서 넘어오면서 바로 read가 이뤄지기 때문에 write이 한 박자 느립니다. 그래서 register내부에 internal bypassing path를 추가하여 이를 수정합니다.

 

그리고 이를 통해 stall을 3개에서 2개로 줄일 수 있게 되었습니다:

Stall: one way to fix a data hazard

 

하지만 여전히 부족합니다. 따라서 state register를 사용합니다. 실제 register나 mem에 쓰여지길 기다리고 있는 임시적인 state register의 값을 다음 pipeline stage로 주는 것입니다. 그리고 이를 forwarding이라고 합니다.

another way to fix a data hazard

Forwarding

 

이를 통해서 stall없이 data hazard를 해결할 수 있습니다.

 

Data Forwarding (aka Bypassing)

 

data forwarding은 ALU의 input을 그냥 ID/EX의 값이 아닌, 다른 임의의 pipeline register의 값으로 대체하는 것을 말합니다. 이를 위해 ALU input에 MUX를 달아줍니다. 해당 MUX의 입력값은 다음과 같습니다:

• 00: normal input (ID/EX pipeline register)
• 10: forward from previous instr (EX/MEM pipeline register)
• 01: forward from instr 2 back (MEM/WB pipeline register)

 

이는 최대한 stall없이 최대의 throughput을 보장하는 data hazard 해결 방법입니다.

 

Detecting the Need to Forward

 

그렇다면 언제 forward를 해야한다고 hardware는 알까요? 우선 ALU의 operand가 되는 ID/EX.RegisterRS(Rs field)와 ID/EX.RegisterRt(Rt field)를 기준으로 해당 값이 이전 instr들과 의존관계에 있는 지를 살펴봐야합니다.

 

만약

 

(1) EX/MEM.RegisterRd = ID/EX.RegisterRs or EX/MEM.RegisterRd = ID/EX.RegisterRt 라면 바로 이전 instr의 목적지 register address(Rd field)가 해당 instr의 operand라는 의미로 의존관계에 있음을 알 수 있습니다. 따라서 이 hazard를 해결하기 위해서는 EX/MEM으로부터 forwarding을 수행해야합니다.

 

(2) MEM/WB.RegisterRd = ID/EX.RegisterRs or MEM/WB.RegisterRd = ID/EX.RegisterRt 라면 2 instr전의 목적지 register address(Rd field)가 해당 instr의 operand라는 의미로 의존관계에 있음을 알 수 있습니다. 따라서 이 hazard를 해결하기 위해서는 MEM/WB으로부터 forwarding을 수행해야합니다.

 

또한

 

(3) EX/MEM.RegWrite 이나 MEM/WB.RegWrite 이 1 이어야합니다. 즉 해당 instr의 Rd field로 값이 써질 예정이었는지가 중요합니다. 만약 RegWrite = 0 이면 어짜피 Rd field가 같아도 안 써질 것이기 때문에 forwarding할 의미가 없습니다.

 

(4) 그리고 Rd field 는 $zero가 아니라는 조건이 필요합니다. $zero는 wired down된 reigster value이기 때문입니다.

 

이들을 datapath로 표현하면 다음과 같습니다:

Datapath with Forwarding Hardware

 

이들을 종합하면 다음과 같은 조건이 생깁니다:

data forwarding control conditions

 

*이때 RegisterRd는 R-format일 경우 Rd field를 말하는 것이지만, I-format에서 load의 경우는 write register address가 Rt filed이기 때문에 RegisterRd = Rt가 됩니다.

 

Yet Another Complication!

 

하지만 forwarding 할 수 있는 register가 두 개 이상이라면 어떤 register의 값을 넣어줘야할까요? 이는 가장 최근의 값을 넣어줘야합니다:

Yet Another Complication!

 

즉, EX/MEM reigster forward와 MEM/WB register forward가 동시에 발생하는 경우는 EX/MEM register forward를 먼저 사용하는 것입니다. 이를 고려하여 condition을 수정하면 다음과 같습니다:

MEM/WB hazard

 

MEM/WB hazard조건에 EX/MEM hazard가 일어날 조건에 not을 붙여줘서 EX/MEM hazard가 일어나지 않을 때만 MEM/WB forwarding이 일어나도록 조절합니다.

 

Memory-to-memory copies

 

lw와 sw가 바로 다음에 나타나면 MEM/WB register에서 바로 값을 받아서 stall 없이 다음 명령을 수행할 수 있습니다. 이를 mem-to-mem copy라고 합니다:

mem-to-mem copy

 

Forwarding: What about Loads

 

forwarding을 통해서 stall을 아에 막을 수는 없습니다. 예를 들어 load-use hazard의 경우는 forwarding으로만은 해결할 수 없어 반드시 stall이 필요합니다.

Forwarding: What about Loads

 

이는 software적으로 nops을 중간에 넣어서 해결할 수도 있고 hardware적으로 stall, bubble연산을 넣는 방법도 있습니다.

stall and bubble

note

 

Load-use Hazard Detection Unit

 

load-use hazard detection condition을 만들때는 다음과 같은 조건들이 들어갑니다:

 

(1) load명령이 왔을 때:

ID/EX.MemRead = 1

 

(2) load명령의 write register address와 다음 명령의 source 이어야한다:

ID/EX.RegisterRt = IF/ID.RegisterRs or ID/EX.RegisterRt = IF/ID.RegisterRt 

Load-use hazard detection condition

 

 

Stall Hardware

 

위 detection unit을 통해 stall이 필요하다고 판단이 되면, 다음 clock cycle에서 pipeline의 진행을 지연시키거나 막기 위해 hardware control signal을 조작해야합니다:

• PC 및 IF/ID pipeline register의 내용이 업데이트되지 않도록 합니다. 이는 PC register와 IF/ID register의 write control을 0으로 설정함으로써 가능합니다. 즉, 다음 instr이 PC에 저장되지 않고 같은 명령을 한 번더 fetch할 수 있으며, IF/ID의 값을 덮어쓰기 당하지 않고 현 상태로 유지할 수 있습니다.
• ID/EX pipeline register로 전달되는 모든 control signal을 0으로 만듭니다. 이를 통해 EX, MEM, WB 단계를 거치는 명령어는 기능적으로 NOP(No Operation)처럼 동작하게 됩니다. 실제로는 RegWrite과 MemWrite만 0으로 만들고 나머지는 dont care가 돼도 됩니다.

Adding the Hazard Detection Unit Hardware

 

Code Scheduling to Avoid Stalls

 

이런 hardware적인 방법이 아닌, scheduling으로 stall을 막을 수도 있습니다. 즉, load-use case를 만들지 않으면 됩니다. 그렇다면 한 번의 stall도 만들지 않고 진행할 수도 있습니다.

Code Scheduling to Avoid Stalls