Pipeline CPU(3)- Data Hazard

Pipeline-CPU 목차

• Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU
• Pipeline CPU(2) : Pipeline-CPU의 간략한 이해
• Pipeline CPU(3) : Data Hazard(RAW)
• Pipeline CPU(4) : Data Forwarding
• Pipeline CPU(5) : Control Hazard

세가지 주요 사항

1. Data Hazard
2. Control Hazard
3. Branch Prediction

이번 Post에서는 Pipeline-CPU를 구현하기 위해 꼭 알아야할 위의 세가지 주요 사항들 중에서도 1. Data Hazard 를 해결하는 방법에 대해 구체적으로 알아봅시다.

Data Dependence

Data Dependence는 크게 RAW, WAR, WAW 이 세가지로 종류를 나눌 수가 있습니다. 각각의 특징들에 대해서 자세히 살펴봅시다.

• RAW(Read-After-Write, True-Dependence)

add x2, x1, x5 // $x2(Write)
add x4, x2, x7 // $x2(Read)

Pipeline-CPU는 Multi-Cycle-CPU와 마찬가지로 IF, ID, EX, MEM, WB의 단계들을 거칩니다. 그러나 연속적으로 매 싸이클마다 새로운 Instruction이 들어오는 Pipeline-CPU의 특성상 RAW와 같은 경우가 발생하였을 때, Write($x2)를 먼저 수행하여야 함에도 불구하고, Write가 되어지지 않은 $x2 레지스터 값을 먼저 읽어오는 매우 심각한 Hazard가 발생합니다.

따라서 연속적인 Instruction들이 쏟아지는 Pipeline-CPU를 완벽하게 작동시키기 위해서는 RAW Hazard를 어떻게 처리하여야 할지 고민해야 합니다.

• WAR(Write-After-Read, Anti-Dependence)
• WAW(Write-After-Write, Output-Dependence)

/* WAR */
add x1, x2, x5 // $x2(Read)
add x2, x4, x7 // $x2(Write)
/* WAW */
add x2, x1, x5 // $x2(Write)
add x2, x4, x7 // $x2(Write)

WAR와 WAW는 함께 묶어서 False dependency라고 합니다. Pipeline CPU에서 instruction의 실행 순서상 read 가 IF/ID에서 항상 먼저 실행된 다음에 WB단계에서 Write가 됩니다. 이러한 Pipeline-CPU의 특성상 False dependency의 경우는 RAW에 해당하는 True data hazard에 해당되지 않습니다.

따라서 False dependency(WAW, WAR)은 레지스터에 저장된 data로 인해 발생되는 문제가 아닌 레지스터의 name과 관계된 문제라고 이해를 하면 됩니다. False dependence(WAR, WAW)의 경우, 만약 무한히 많은 레지스터가 있다면 레지스터를 다음과 같이 Renaming함으로 써 문제를 concurrent-processing에서 발생할 수 있는 문제들을 해결할 수 있게 됩니다.

/* Renaming 전 */
add x1, x2, x5 // $x2(Read)
add x2, x4, x7 // $x2(Write)
/* Renaming 후 */
add x1, x2, x5 // $x2(Read)
add x8, x4, x7 // $x2-->$x8(Write)

RAW Hazard

앞서 살펴본 세가지 Data dependence의 경우 중 하나인 RAW Hazard에 대해 자세히 살펴봅시다. RAW의 경우는 Write를 먼저하고 Read를 꼭 해야하기 때문에, write 가 되기도 전에 다음 Instruction이 IF/ID에서 read를 할 경우 Data Hazard가 발생하므로 이러한 Hazard가 생기는 것을 미리 방지해 주어야 합니다.

그렇다면 우선, CPU는 RAW Hazard가 발생하였다는 사실을 어떻게 알 수 있을까요?

/*RAW Hazard 발생 조건 */
dis(I_OLD, I_YOUNG) <= 3

// I(young) ex) R/I, LD, SD, Bxx, JALR // Read Instruction Operator
// I(old)  ex) R/I, LD, JAL, JALR // Write Instruction Operator
/* write(old instructiion) 보다 read(young instruction)가 먼저 수행될경우 hazard가 발생한다.
dist 가 3 보다 큰 경우는 hazard가 발생하지 않으므로 3 이하인 경우만 고려 */

Feature2. RAW detection Logic

RAW(Read after Write) dependency인 경우에, Data Hazard가 발생하지 않기 위해서는 Write를 먼저 한 이후에 Read Instruction이 수행되어야 합니다. 하지만 Pipeline-CPU는 RAW가 발생한 두 instruction 간의 거리가 3이하일 경우에는 항상 I_YOUNG의 Read가 Write 되기도 전에 먼저 실행이 되는 Hazard가 발생하게 됩니다.

따라서 Feature2에서 확인할 수 있듯이, Write Operator에 해당하는 Instruction과 Read Operator에 해당하는 Instruction 간의 거리를 확인 함으로써 RAW Hazard가 발생할거라는 사실을 확인할 수가 있습니다.

CPU가 RAW Hazard가 발생하였다는 사실을 알아챘다면, 어떻게 Data Hazard 문제를 해결할 수가 있을까요?

Post의 참고자료와 이미지의 출처는 아래와 같습니다.

Computer Organization and Design RISC-V edition
Computer Architecrue Lecture Note @ Carnegie Mellon University, University of, Michigan, Purdue University, University of Pennsylvania, University of Wisconsin and POSTECH.