Data dependency

Pipelined Microarchitecture and Dependency Handling

1. Data Dependency in Pipeline

1.1. Data Dependency의 개념

• 두 개의 명령어가 동일한 레지스터 값을 사용하는 경우 발생.
• 결과 값이 올바른 실행 순서를 따르도록 보장해야 함.

1.2. 종류 (Types of Data Dependency)

1. RAW (Read After Write) - 진짜 종속성
   • 이전 명령어가 값을 쓰기(write) 전에 다음 명령어가 읽기(read)하면 오류 발생.
   • 해결 방법: Forwarding or Stalling
2. WAR (Write After Read) - 가짜 종속성
   • 이전 명령어가 값을 읽기(read)하는데, 이후 명령어가 먼저 값을 쓰기(write)하면 오류 발생.
   • 해결 방법: 레지스터 리네이밍(Register Renaming)
3. WAW (Write After Write) - 출력 종속성
   • 두 개의 명령어가 같은 레지스터에 값을 쓰기(write)하는 경우.
   • 해결 방법: Scoreboarding, Reordering

2. Handling Data Dependencies

2.1. 해결 방법 (Five Ways of Handling Flow Dependences)

1. Detect and Wait (검출 후 대기)
   • 명령어 종속성을 감지하면 파이프라인을 Stall(멈춤) 시킴.
   • 간단하지만 성능 저하 발생.
2. Detect and Forward/Bypass (검출 후 전달/우회)
   • 연산이 완료되면 바로 다음 명령어에 값을 전달.
   • RAW 문제 해결에 효과적.
3. Detect and Eliminate (검출 후 제거)
   • WAR/WAW와 같은 불필요한 종속성을 없애도록 코드 변경.
4. Predict (예측 기반 실행)
   • 분기 예측과 유사하게 데이터의 의존성을 예측하여 실행.
5. Do Something Else (다른 작업 수행)
   • 종속성이 해결될 때까지 독립적인 다른 작업을 수행.

3. Stalling and Interlocking

3.1. Stalling (멈춤)

• 새로운 명령어를 실행하지 않고 대기하는 기법.
• 하드웨어 기반 Interlocking: 종속성이 해결될 때까지 CPU가 대기.
• 소프트웨어 기반 Interlocking: 별도의 NOP(아무것도 하지 않는 명령어)를 삽입하여 파이프라인을 유지.

3.2. Scoreboarding

• 각 레지스터에 Valid Bit(유효성 비트) 를 추가하여 사용 가능 여부를 추적.
• 유효하지 않은(Invalid) 레지스터에 접근하려 하면 Stall 발생.
• 장점: 단순한 구현, RAW(진짜 종속성) 문제 해결 가능.
• 단점: 필요 없는 종속성(WAR, WAW)까지 감지하여 불필요한 Stall 발생.

3.3. Sequence Tagging

• 각 명령어에 일련번호를 부여하여 추적.
• 어떤 명령어가 어떤 값을 갱신했는지 확인 가능.
• 불필요한 Stall을 줄이고 성능을 향상.

• inst5의 r2는 inst1에서 나온 값이 아니라 inst2에서 계산된 값을 사용해야 함.
• 하지만 inst5가 inst1의 값을 참조하면 잘못된 결과가 발생.
  • 해결 방법:
    • Scoreboarding → r2가 아직 유효하지 않음을 감지하고 Stall.
    • Forwarding → inst2에서 갱신된 값을 inst5에 전달.

Handling Data Dependency in Pipelined Microarchitecture

1. Understanding Data Dependency

1.1. What is Data Dependency?

Data Dependency란 이전 명령어의 연산 결과를 이후 명령어가 필요로 할 때 발생하는 종속성을 의미합니다.
만약 필요한 연산 결과가 아직 저장되지 않았는데 이후 명령어가 해당 값을 사용하려고 하면 잘못된 데이터가 전달될 가능성이 있습니다.

1.2. Conditions for Dependency

Data Dependency가 발생하려면 아래 두 가지 조건이 만족되어야 합니다.

Condition 1: Dependency Distance ≤ 3

• Dependency가 존재하려면 두 instruction 간 거리가 3 이하여야 함.
• Pipeline에서는 Write Back(WB) 단계가 완료되기 전에 이후 명령어가 해당 값을 참조하면 문제가 발생합니다.
• 만약 거리가 4 이상이면 이전 명령어의 WB가 완료된 후이므로 Dependency가 존재하지 않음.

Condition 2: Register Usage Dependency

• 이전 명령어(IA)가 특정 Register를 업데이트하고, 이후 명령어(IB)가 해당 Register 값을 사용하려고 하면 Dependency 발생.
• 예: IA가 r2를 업데이트하고, IB가 r2를 읽어야 한다면 IA의 결과가 나오기 전까지 IB는 Stalling 필요.

2. Handling Data Dependencies

2.1. Scoreboarding

• 각 레지스터에 Valid Bit(유효성 비트) 를 추가하여 사용 가능 여부를 추적.
• 유효하지 않은(Invalid) 레지스터에 접근하려 하면 Stall 발생.
• 장점: 단순한 구현, RAW(진짜 종속성) 문제 해결 가능.
• 단점: 필요 없는 종속성(WAR, WAW)까지 감지하여 불필요한 Stall 발생.

2.2. Combinational Logic for Dependency Detection

• 명령어 간 Register 사용 여부를 분석하여 데이터 의존성을 판별.
• use_rs(I) 함수와 같은 논리를 사용하여 특정 명령어가 rs 필드를 읽는지 확인.
• Combinational Logic을 활용하면 Stalling 없이 필요한 경우에만 Stall을 적용.
  

3. Stalling and CPI Calculation

3.1. Stalling (Pipeline Stall)

• Stalling은 명령어 실행을 잠시 멈추고 WB 단계가 완료될 때까지 대기하는 방법.
• 하드웨어적으로 Interlocking을 수행하여 Stalling 발생.
• CPI 성능을 저하시킴.

3.2. CPI Calculation with Stalls

• CPI는 총 실행 사이클 수를 총 명령어 수로 나눈 값으로 정의됩니다.
• N: 총 실행된 명령어 수
• S: 발생한 Stall Cycle 수
• S (Stall Cycle) 값은 아래 조건에 따라 결정됨.
  • RAW Dependency 발생 빈도
  • Dependent Instructions 간 거리 (Dependency Distance)
  • Dependency가 연속적으로 발생하는 거리

Advanced Dependency Handling in Pipelined Microarchitecture

1. Data Forwarding (Bypassing) 개념

1.1 기존 Stalling의 문제점

이전에는 Stalling을 사용하여 Data Dependency를 해결하는 방법을 배웠습니다.
하지만 Stalling은 실행을 멈추는 것이므로 성능 저하를 유발합니다.

예를 들어, 다음과 같은 명령어가 있다고 가정합니다.

inst1: add r1, r2, r3  // r1 = r2 + r3
inst2: sub r4, r1, r5  // r4 = r1 - r5  (r1의 최신 값이 필요)

• inst1이 r1을 업데이트해야 하는데, inst2는 r1을 사용해야 합니다.
• 하지만 inst1의 결과는 WB (Write Back) 단계에서야 저장됩니다.
• 따라서 inst2는 inst1의 WB가 완료될 때까지 3 사이클을 기다려야(Stalling) 합니다.

1.2 Data Forwarding (Bypassing)의 원리

• Forwarding은 결과값을 메모리(WB)까지 기다리지 않고 즉시 전달하는 기법입니다.
• EX 단계에서 계산된 결과를 곧바로 이후 명령어에 전달하면, Stalling 없이 명령어 실행 가능.
• 즉, inst2가 r1 값을 필요로 할 때, inst1의 EX에서 계산된 값을 곧바로 가져와 사용하면 됩니다.

Forwarding의 핵심 개념

• ALU가 계산한 결과를 바로 다음 cycle에 사용하는 방식.
• Memory(WB) Stage까지 기다리지 않고, Pipeline 내부에서 값을 전달.
• Control Signal을 통해 Forwarding Unit이 값을 전달할지 결정.

2. How Data Forwarding Works (구체적인 동작 방식)

2.1 Forwarding이 적용되는 과정

1. inst1이 r1을 생성하고, inst2가 r1을 사용해야 한다고 가정.
2. inst1의 EX 단계에서 결과가 계산됨.
3. Pipeline 내부에서 이 값을 inst2의 EX 입력으로 직접 전달 (Bypassing).
4. inst2는 WB를 기다릴 필요 없이 즉시 연산 수행 가능.

• 예제 코드

inst1: add r1, r2, r3  // EX에서 r1 값 생성됨
inst2: sub r4, r1, r5  // r1 값이 필요하므로 Forwarding 수행

• inst2가 r1을 사용해야 하는데, inst1이 WB까지 가지 않아도 EX 단계에서 값을 전달 가능.
• 따라서 Stall 없이 Forwarding Unit을 통해 ALU 결과를 즉시 전달.

2.2 Forwarding을 위한 Control Signal

• Forwarding을 수행할지 여부는 Control Signal을 통해 결정.
• Forwarding Unit이 명령어 간의 Register Dependency를 감지하여 ALU에 값을 전달.

Control Signal의 역할

• 이전 명령어에서 rs 또는 rt 레지스터 값을 수정하는지 확인.
• WB까지 가지 않고도 EX 또는 MEM 단계에서 바로 사용할 수 있도록 결정.

3. Forwarding의 Distance에 따른 처리 방법

Pipeline에서 Dependency Distance에 따라 Forwarding을 다르게 처리해야 합니다.

3.1 Distance = 1 (EX → EX)

• 이전 명령어가 EX 단계에서 연산을 수행했고, 바로 다음 명령어가 그 결과를 필요로 하는 경우.
• EX 단계에서 곧바로 다음 EX 단계로 결과를 전달.

3.2 Distance = 2 (MEM → EX)

• Load Word 명령어(lw r1, 0(r2))처럼 메모리에서 값을 읽는 경우 발생.
• 값이 MEM 단계에서 나와야 하므로 EX 단계에서 사용할 수 없음.
• Stall이 필요할 수도 있음.

3.3 Distance = 3 (WB → EX)

• WB가 완료된 후 Register File에서 값을 읽으면 되므로, 추가적인 Forwarding이 필요 없음.
• WB가 끝나면 Register File에 값이 반영되므로, 이후 명령어는 정상적으로 값을 사용할 수 있음.

4. Special Cases: Load Word Instruction & Stalling

4.1 Load Word (lw)의 문제점

inst1: lw r1, 0(r2)   // r1에 메모리 값 저장 (MEM 단계에서 결과 생성)
inst2: sub r3, r1, r4 // r1을 바로 사용해야 함

• lw 명령어는 MEM 단계에서 값을 가져오므로, EX 단계에서 값을 사용할 수 없음.
• 따라서 Forwarding이 불가능하고, 1 사이클 Stall이 필요.

4.2 해결 방법: Compiler-Level Optimization

• MIPS Microprocessor에서는 Load Word 뒤에 항상 NOP(No Operation) Instruction을 삽입.
• 하드웨어적으로 Stalling을 방지하고, 대신 NOP을 삽입하여 성능을 유지.