Lecture 15: The Processor - 4

경희대학교 김정욱 교수님의 컴퓨터 구조 수업을 기반으로 정리한 글입니다.

Pipeline Hazards

Pipelining는 속도가 향상된다는, 즉 성능이 향상된다는 장점이 있다.

하지만, 매 cycle마다 instruction을 실행해야 하는데 그렇지 못하는 경우, 3가지 Hazards가 발생한다.

 

Three types of pipeline hazards

1. Structure hazards: 구조적 문제

2. Data hazards: 필요한 데이터를 아직 못 받은 문제

3. Control hazards: 브랜치 문제

1. Structure Hazards

Problem

현재에는 데이터가 저장된 메모리, instruction이 저장된 메모로 나눠져 있다.

하지만 과거엔 영역이 나누어져 있긴 하지만 메모리가 하나로 되어 있었다.

 

때문에 메모리 입장에선 주어진 시간에 하나의 signal만 받을 수 있고,

2개의 signal을 동시에 받을 수 없는 Structure Hazards 문제가 있었다.

 

※ 현재 시점에선 Structure Hazards는 완전히 해결된 문제이다.

▶ resource conflicts

 

Fetch를 하기 위한 PC 값과,  Memory에 접근하기 위한 Address 값을 동시에 받아야 하는 문제가 발생한다.

 

즉, instruciton과 data가 같은 메모리에 저장되어 있는 과거엔 fetch, memory 단계가 같은 clock cycle에 겹치면,

같은 메모리에 동시에 접근하여 자원 충돌 문제가 발생했다.

Solution

Solution 1: Stall

한 사이클을 중지한다.

▶ Stall

 

원시적인 해결 방법으로, Fetch 혹은 MEM 중 하나가 쉬는 방법이다.

하지만 이는 결론적으론 해결되지 않았다.

 

CC4에서는 해결이 되었지만, CC5에서 또다른 Fetch와 clock cyle이 겹치는 문제가 발생한다.

때문에 instruciton이 4개인 위 그림을 예시로 설명하면, clock cycle 기존 8개에서 3번 쉼으로 인해 11개로 늘어나게 된다.

 

Solution 2: Dividing Instruction memory and data memory

instruction memory와 data memory를 나눈다.

 

이는 근본적인 해결 방법으로, 서로 다른 signal을 처리할 수 있게 한다.

2. Data Hazards

Problem

필요한 데이터 값을 아직 받지 못해 발생하는 문제이다.

▶ pipeline data hazard 예시

 

$r2와 $r3를 더한 결과를 $r1에 저장한 후, Write Back이 되어야만 $r1과 $r3를 뺀 값을 $r4에 저장할 수 있다.

이때, sub가 EX 하는 단계에서 $r1이 업데이트가 안 되어 있는데 $r1과 $r3를 빼게 되게 되는 문제가 발생할 수 있다.

 

single cycle의 경우 이러한 문제가 발생하지 않지만, pipeline의 경우에는 $r1이 새롭게 저장되지 않고 저장할 준비를 하고 있는

상태에서 그 다음 명령어인 sub가 $r1이 업데이트 되었다고 생각하고 계산하면 업데이트 되기 전 $r1 값으로 연산이 되어,

원하는대로 처리가 안 될 것이다.

 

즉, 이전 명령어의 WB 단계가 이루어지기 전에, 이 WB의 반영이 필요한 register를 사용하는 다음 명령어의 EX 단계가 수행되는 경우 발생하는 문제이다.

Solution

Solution 1: Stall

사이클을 중지한다.

▶ Example

 

하지만, 이러한 원시적인 솔루션은 2 clock cycle을 멈추는 것은 파이프라인에서 2개의 clock cycle 낭비를 초래한다.

결국, single cycle과 별 차이가 없게 된다.

 

※ R-format으로 이루어질 경우엔 MEM 단계가 불필요하다. 그래서 single cycle의 경우, IF -> ID -> EX -> WB × 2로 solution 1 방법과 동일하 8개의 cycle을 돌게 된다. 때문에 pipeline의 복잡성 및 긴 cycle의 시간으로 맞추는 것을 고려하면 single cycle이 더 효율적일 수 있다.

 

Solution 2: Forwarding or Bypassing (전달, 우회)

EX 단계에서 나온 WB될 값을 미리 다음 instruction으로 넘겨준다.

▶ Example

 

쉬어 갈 필요 없는 가장 좋은 솔루션이다.

이때, WB될 값을 미리 다음 instruction으로 넘겨줄 뿐, 실제로 WB되는 것은 아니다.

 

예시로 설명하자면, $1에 WB될 값을 pipeline register로 (위 그림에서 긴 네모 블럭) 미리 넘겨는 주지만, CC5에서 WB이 적용되기 전까지 $1 값은 바뀌지 않는다.

즉, 1번 레지스터에서 꺼내는 게 아니라, 더한 결과 자체를 미리 받아 연산하는 것이다.

 

이때, 넘겨 주고 넘겨 받는 것은 모두 pipeline register끼리 이루어진다.

load-use data hazard (Problem)

lw와 R-format 관계에서 lw로부터 꺼내는 값이 다음 R-format의 입력으로 쓰일 때 발생하는 문제점이다.

 

※ lw 다음 R-format이 나왔다고 문제가 발생하는 게 아니라 lw로 꺼낸 값이 R-format의 입력으로 쓰일 때 문제가 발생하는 것이니 주의해야 한다. 또한, R-format의 입력이 아니라 출력으로 쓰일 경우 역시 '입력'으로 쓰이는 것이 아니기에 문제가 발생하지 않는다.

▶ load and use data hazard

 

lw의 경우, EX의 output은 data가 아니라 address이다.

이때 Forwarding 방법을 사용하면, 값을 넘겨야 하는데 address를 넘겨 EX에서 계산하면,

주소 값과 데이터 값을 연산하게 되는 것이기에 당연히 안 된다.

 

Solution 1: Stall (Bubble)

때문에 load-use data hazard의 경우, Forwarding 자체가 바로 될 수 없기에 한 cycle을 쉬어야 한다.

즉, MEM에서 output(data)이 나올 때까지 기다렸다가 EX 단계에 전달을 해주어야 한다.

 

※ 실제로 회로는 하나고 신호가 여러번 왔다 갔다 하는 것이다.

 

※ EX 회로의 윗 부분 input은 rs, 밑 부분 input은 rt이다. 이때 위 그림에선 두 번째 instruction에서 $s0가 rs에 위치하기 때문에 윗 부분 input으로 들어 간다.

 

Solution 2: Reordering to avoid pipeline stalls

▶ Solution of load-use data hazard

 

왼쪽은 순서대로 처리하는 정직한 컴파일러로, lw 다음 R-format이 나오는 경우가 총 2번,

즉 2번의 stall이 발생한다는 문제점이 있다.

 

이러한 문제점을 datapath 차원이 아닌, compiler 차원에,

즉 instruction 순서를 적절히 재배치함으로써 지연을 최소화할 수 있다.

 

lw 다음 R-format이 나올 때 문제점은, Forwarding을 하더라도 필요한 값을 받아올 때까지 기다려야 한다는 것이 있다.

이러한 stall 문제점은 lw와 R-format이 붙어있지 않도록 하기만 하면 해결된다. 때문에 붙어있지 않도록 만들기 위해 lw, R-format 사이에 순서를 바꿔도 영향을 미치지 않는 instruction을 삽입함으로써 해결하는 것이다.

 

※ 왼쪽에서 두 번째 instruction이 $t2가 아니라 $t5면 문제가 발생하지 않는다. 그 이유는 load-use data hazard는 load된 data가 즉시 사용되었을 때 발생하는 문제점인데, 이렇게 변경할 경우 load된 data가 즉시 사용되지 않으므로 load-use data hazard가 발생하지 않는다.

▶ Data Hazard

• data hazard는 다음 (1형 data hazard), 그리고 다다음 (2형 data hazard) instruction까지만 영향을 미친다. (by WB 유무)

Notation of data hazard conditions

▶ 표기법

• EX/MEM 단계의 rd가 ID/EX (다음 명령어) 단계의 rs와 같으면 1a hazard
• EX/MEM 단계의 rd가 ID/EX (다음 명령어) 단계의 rt와 같으면 1b hazard
• MEM/WB 단계의 rd가 ID/EX (다다음 명령어) 단계의 rs와 같으면 2a hazard
• MEM/WB 단계의 rd가 ID/EX (다다음 명령어) 단계의 rt와 같으면 2b hazard

현재 instruction이 읽는 (rs or rt) register 번호와 이전 instruction이 write하는 register 번호 (rd)와 같은지 체크하는 것이다.

이때, data hazard 조건이 만족하면 바로 forwarding을 수행하는 것이다.

 

Notation Format

• AA/BB.RegisterRd = CC/DD.RegisterRs or CC/DD.RegisterRt
• Example) ID/EX.RegisterRs: ID/EX에서 발견되는 레지스터 Rs 번호

※ AA/BB: AA와 BB 단계 사이에 있는 pipeline register

▶ data hazard conditions 예시

▶ Forwarding or Bypassing

▶ Forwarding

• ForwardA: 1형 data hazard
• ForwardB: 2형 data hazard

Detecting data hazards

▶ data hazard - MUX control

 

1. EX hazard (1형 hazard)

① R-format과 R-format 사이에서, ② 이전에 수행된 EX/MEM의 register rd 번호가 현재 수행 중인 ID/EX의 register rs or rt 번호와 같을  발생한다.

 

▶ EX hazard

 

1. EX/MEM pipeline register에 있는 RegWrite 신호 켜져 있고, (R-format 필터링 1)

• RegWrite는 R-format, lw일 때 rd에 write하기 위해 신호가 켜진다. -> R-format or lw

2. EX/MEM pipeline register에 있는 rd 값이 유효하고, (R-format 필터링 2)

• R-format은 rd가 있기에 유효하여 1,  lw는 rd가 없기에 유효하지 않아 0이다. 즉, 유효하다는 것은 결국 R-format이라는 의미이다. -> R-format

3. 이전에 수행된 EX/MEM의 register rd 번호가 현재 수행 중인 ID/EX의 register rs or rt 번호와 같으면 EX hazard 발생한다.

 

2. MEM hazard (2형 hazard)

① lw 다음 R-format일 때, ② 두 개 이전에 수행된 EX/MEM의 register rd 번호가 현재 수행 중인 ID/EX의 register rs or rt 번호와 같을  발생한다.

▶ MEM hazard

 

1. MEM/WB pipeline register에 있는 RegWrite 신호 켜져 있고, (R-format 필터링 1)

• RegWrite는 R-format, lw일 때 rd에 write하기 위해 신호가 켜진다. -> R-format or lw

2. MEM/WB pipeline register에 있는 rd 값이 유효하고, (R-format 필터링 2)

• R-format은 rd가 있기에 유효하여 1,  lw는 rd가 없기에 유효하지 않아 0이다. 즉, 유효하다는 것은 결국 R-format이라는 의미이다. -> R-format

3. 이전에 수행된 MEM/WB의 register rd 번호가 현재 수행 중인 ID/EX의 register rs or rt 번호와 같으면 EX hazard 발생한다.

▶ MEM hazard - Considering additional case

 

MEM hazard의 경우, 첫 번째와 셋 번째만 고려할 게 아니라, 추가적으로 가운데도 위 그림과 같은 예시를 위해 고려해야 한다.

▶ 첫 번째와 세 번째의 data hazard -> 정확한 MEM hazard (final code)

이것도 MEM hazard일까?

 

MEM hazar는 아니고, EX hard가 2개 있는 것이다. (1번째-2번째 EX hazard, 2번째-3번째 EX hazard)

 

값으로 생각해 보면, register 번호만 같지 실제론 값이 다르다. (1번째-2번째 register 값과 2번째-3번째 register 값이 다르다.)

▶ Datapath considering hazards via forwarding

 

※ Control: opcode에 따라 control signal 조정

 

※ Forwarding unit: 조건 체크 ex) RegWrite (WB에 대응하는 control signal)가 켜져 있는지

Load-use data hazards (Problem)

▶ Load-use data hazards

 

Solution: Checking for load instructions

▶ MemRead -> lw일 때만 1, 나머진 0

▶ Load-use data hazard

 

1. ID/EX pipeline register에 있는 MemRead 신호 켜져 있고, (lw 필터링)

• MemRead는 lw일 때 address에 해당하는 Memory를 read하기 위해 신호가 켜진다. -> lw

2. 이전에 수행된 ID/EX의 register rt 번호가 현재 수행 중인 IF/ID의 register rs or rt 번호와 같으면 Load-use data hazard 발생한다.

 

※ Load-use data hazard는 미리 파악하여 앞에 쉬어줘야 한다. 때문에 ID/EX, IF/ID 대신, EX/IM, ID/EX로 설정하면 problem을 인식하고 stall 하기엔 늦어 버린다. 그래서 한 단계 전에서 수행하는 것이다. 

How to Stalling?

 

Insert nop (no operation)

nop: 상태를 바꾸는 연산을 하지 않는 instruction (redordering)

▶ reordering

▶ 회로