데이터 의존성

참고 : jinh2352_데이터의존성, 두 변수 값 바꾸기에 대한 고찰: 후속편

데이터 의존성(Data Dependency)

• 명령어들 사이의 데이터 흐름
  • 의존성 있는 명령은 순서대로 실행되어야 함
    -> 최적화 시 고려 필수 고려
• 데이터 헤저드(Hazard) : 컴퓨터 구조에 한정하여, 이러한 의존성을 말함.

RAW (Read after Writer) 의존성

• 흐름 의존성(flow dependency), 진짜 의존성 (true dependency)
• 1번 명령이 계산 결과 생성
• 2번 명령이 사용
• @ : x기준, 2번 명령은 1번 명령이 끝이 나야 사용 가능.
  • x의 값에 대해 Write -> Read 과정

    x = y + 1; // (1) x에 대한 값 쓰기
    z = x * 2; // (2) x에 대한 값 읽기

• XOR-Swap 방식이 최적화가 temp방식 보다 어려운 이유

WAR (Write after Read)

• 반 의존성 (anti dependency), 가짜 의존성 (false dependency), 이름 의존성 (name dependency)
• 1번 명령에서 x 값 읽기
• 2번 명령에서 x 값 쓰기
• @ : x 기준, 2번 명령은 1번 명령과 동시 || 순서 변경에도 문제가 없음

  z = x + 2; // (1)
  x = y + 1; // (2) <- (1) 번 명령은 (2)와 관련이 없음
  a = x / 2;

• 의존성 제거

  • (2) 번 명령의 x의 이름을 x1 등의 다른 이름으로 변경

    z = x + 2; 
    x1 = y + 1; // 이후 `x`들도 전부 `x1`로 이름 변경 필요
    a = x1 / 2;

WAW (Write after Write)

• 출력 의존성 (output dependency), 가짜 의존성 (false dependency), 이름 의존성 (name dependency)
• 같은 대상 사용에 따른 의존성
• @ : WAR과 달리, 순서도 중요

  x = z + 1;  // (1)
  x = y + 3;  // (2)
  a = x / 2;

• 의존성 제거

  • (2) 번 명령의 x의 이름을 x1 등의 다른 이름으로 변경

    x = z + 1;
    x1 = y + 3;
    a = x1 / 2;