Dependences (의존성)

프로그램을 짤 때 명령어들 사이에 어쩔 수 없이 생기는 끈끈한 관계입니다. 이 관계 때문에 함부로 순서를 바꾸거나 동시에 실행할 수 없습니다.

A. Data dependence (True data dependence)

• 의미: 앞 명령어가 만든 진짜 데이터(Real data)가 뒷 명령어에게 필수적인 상황.
• 유발 해저드: RAW (Read After Write)
• 직관적 이해: "네가 계산을 끝내야 내가 그걸 받아서 쓴다고!"
• RAW 가 나올 가능성이 있다는 뜻이지 무조건 Data Dependence = RAW 이거는 아니다.

B. Name dependence (False dependence)

• 의미: 데이터가 이어지는 건 아닌데, 우연히 같은 레지스터 이름(Same register name)을 써서 엮여버린 상황.
• 유발 해저드: WAW (Write After Write), WAR (Write After Read)
• 직관적 이해: "우린 볼일도 없는데 왜 하필 같은 F2 방을 쓰겠다고 겹쳐서 난리야?"
• Occurs when two instructions both access the same data storage location due to reuse the storage (Also called storage dependence, at least one of the accesses must be a write.)

두 가지 대환장 파티 (Sub-types)

이 '가짜 의존성' 때문에 스케줄이 꼬여서(Out-of-order) 발생하는 두 가지 해저드입니다.

A. Antidependence (반의존성)

-> 잠재적 WAR 해저드
공식: "앞 놈이 방에서 값을 읽기도(Read) 전에, 뒷 놈이 쳐들어와서 새 값을 써버린다(Write)!"

• 상황: A가 202호에 있는 짐을 읽고(Read) 체크아웃해야, B가 들어와서 자기 짐을 풀어놓을(Write) 수 있습니다.

• 대참사 (WAR: Write After Read): B가 너무 성질이 급해서 A가 짐을 싸서 나가기도 전에 방에 들어와서 자기 짐을 다 풀어버렸습니다(Write). A는 어리둥절하며 자기 짐이 아닌 B의 짐을 들고나가버립니다(Read). 프로그램 로직이 완전히 파괴됩니다.

B. Output dependence (출력 의존성)

-> 잠재적 WAW 해저드
공식: "앞 놈이 쓴(Write) 방에, 뒷 놈이 또 쓴다(Write)!"

• 상황: A가 먼저 202호 테이블에 문서를 올려두고(Write), 나중에 B가 들어와서 그 위에 자기의 최신 문서를 덮어써야(Write) 합니다. (결국 방에는 최신인 B의 문서가 남아야 정상이죠.)

• 대참사 (WAW: Write After Write): B가 손이 엄청 빨라서 문서를 벌써 올려두고 나갔는데, 굼벵이 같은 A가 뒤늦게 들어와서 자기 옛날 문서를 테이블에 턱 덮어씌워 버립니다. 최종 결과물이 과거의 쓰레기 데이터로 오염됩니다.

C. 만병통치약: "방을 바꿔라!" (Register Renaming)

Name dependencies can be avoided by changing instructions to use different locations

• "A랑 B가 서로 데이터 주고받을 일도 없는데 굳이 같은 방을 쓰게 해서 이 사달을 내? 야, B! 너 그냥 비어있는 저기 물리적 빈방(P10) 하나 새로 파서 이름만 F2라고 달아놓고 써!"

• 이렇게 하드웨어 내부적으로 몰래 방을 두 개로 쪼개주면, A와 B는 서로 평생 마주칠 일 없이 동시에 쌩쌩 달릴 수 있습니다. WAR와 WAW 스톨이 그 즉시 0이 되어 소멸해 버리는 것입니다.

C. Control dependence

• 의미: Branch, Jump 명령어 때문에 다음 명령어가 실행될지 말지 운명이 결정되는 상황.
• 유발 해저드: Control stalls (Branch penalty)

1. Control Dependence (운명 공동체)
   BEQZ R12, skipnext: "만약 R12가 0이면, 밑에 두 줄 무시하고 skipnext로 건너뛰어!"

   여기서 DSUBU와 DADDU는 BEQZ의 눈치만 봐야 하는 상황입니다. BEQZ가 점프해 버리면 얘네는 실행조차 안 되니까요.

   이것을 서로 Control dependence 관계에 있다고 부릅니다.
   

2. 룰 브레이킹: "일단 땡겨 써!" (Software Speculation)
   파이프라인 성능을 높이려면 빈 공간에 명령어를 꽉꽉 채워 넣어야 합니다. 그래서 똑똑한 컴파일러가 미친 짓을 하나 계획합니다.

   컴파일러: "야, DSUBU R4, R5, R6! 너 저기 BEQZ 브랜치 위로 자리 옮겨서 먼저 실행해버려!" (Violate the control dependence)

   이게 왜 위험한 도박일까요?
   만약 BEQZ가 0이어서 skipnext로 점프(Taken)해버리는 상황을 가정해 봅시다. 원래대로라면 DSUBU는 실행되지 말았어야 하는데, 우리가 순서를 위로 끌어올리는 바람에 억지로 실행되어 버렸습니다! 그 결과 R4 레지스터에는 쓰레기 값이 덮어씌워졌습니다.

3. 면죄부 조건 (Without affecting correctness)
   방금 R4가 오염됐죠? 그런데 만약 점프해서 도착한 skipnext 위치(OR 명령어)부터 프로그램이 끝날 때까지, 그 어떤 명령어도 R4 값을 읽지 않는다면 어떨까요? * 쓰레기 값이 들어있든 말든, 아무도 안 쓰니까 프로그램의 최종 결과(Correctness)에는 아무런 악영향을 주지 않습니다!

   컴파일러 용어로 이런 상태의 레지스터를 "죽었다(Dead)"고 표현합니다.

   슬라이드에 적힌 "if R4 is not used after skipnext"가 바로 이 면죄부의 조건입니다.

이렇게 컴파일러가 코드를 분석해서 "어차피 결과에 영향 없으니 브랜치 위로 끌어올려 버리자!"라고 판단하고 스케줄링을 꼬아버리는 기술을 Software speculation (소프트웨어적 추측 실행)이라고 부릅니다.

---

2. 한계 돌파를 위한 무기: Advanced Techniques

A. Loop unrolling

-> Reduces Control stalls

• 루프(for문 등)를 쫙 펼쳐서 코드를 길게 씁니다. 그러면 루프를 돌기 위한 Branch 명령어 자체가 사라지므로 컨트롤 스톨이 줄어듭니다.

//100 branch
for(i=0; i<100; i++) {
	sum[i] = sum[i]+d;
    }
   
//50 branch, 코드 한줄 더써서 100->50으로 줄임
for(i=0; i<100; i++) {
	sum[i] = sum[i]+d;
    sum[i] = sum[i+1]+d;
    }

B. Basic pipeline scheduling / forwarding

-> Reduces RAW stalls

• 컴파일러가 순서를 예쁘게 정리하거나(Scheduling), 하드웨어가 계산된 값을 바로 던져주면(Forwarding) 데이터를 하염없이 기다리는 RAW 스톨이 해결됩니다.
• 우리가 원래 하던 방식

C. Dynamic scheduling w. scoreboarding

-> Reduces RAW stalls

• 하드웨어가 실시간으로 멈추지 않고 실행 가능한 다른 명령어부터 먼저 처리해 버려서 데이터 대기 시간(RAW)을 숨깁니다.
• out of order execution in HW

D. Dynamic scheduling with register renaming

-> Reduces WAR & WAW stalls

• 아까 Name dependence는 '방 이름'이 같아서 생기는 가짜 문제라고 했죠? 하드웨어가 겉으로는 F2라고 써놓고, 실제로는 몰래 남는 물리적 방(예: P10)으로 이름을 바꿔치기(Renaming)해버립니다. 겹치는 방이 사라지니 WAR, WAW가 완벽하게 소멸합니다!
• Tomasulo's Algorithm: scoreboarding(RAW) + Register renaming(WAW,WAR)

E. Dynamic branch prediction

-> Reduces Control stalls

• 브랜치 결과를 기다리지 않고 똑똑하게 찍어서(Predict) 먼저 달려가니까 컨트롤 스톨이 줄어듭니다.

F. Issuing multiple instructions per cycle

-> Reduces Ideal pipeline CPI

• 1클럭에 여러 명령어를 쑤셔 넣으니까(Superscalar), 태생적인 한계였던 Ideal CPI = 1을 1 미만(예: 0.5, 0.33)으로 부숴버립니다.

G. Speculation (추측 실행)

-> Reduces All data & control stalls

• "값이 뭐가 될지, 어디로 튈지 일단 찍고 돌격해!" 무지성으로 미리 다 계산해 버리기 때문에 데이터와 컨트롤 스톨을 한꺼번에 무시해 버립니다.
• Tomasulo's algorithm + dynamic branch prediction + Multi instructre

---

Example

Find all dependencies in the following code segment

output dependence: 첫번째 레지스터끼리 같은거
Anti dependence: 두번째, 세번째 레지스터가 첫번째랑 같은거

Output Dependence (출력 의존성) -> WAW Hazard 유발

공식: "앞 놈이 쓴(Write) 방에, 뒷 놈이 또 쓴다(Write)!"

표에서 교수님이 "8 on 1 for R1" 이라고 적어두셨죠? 코드에서 1번과 8번 명령어의 R1 위치를 자세히 보세요.

Inst 1: LD R1, 50(R2) 👉 메모리에서 값을 가져와서 R1에 쓴다 (Write).
Inst 8: SUB R1, R1, #10 👉 계산 결과를 R1에 또 쓴다 (Write).

왜 문제일까요? (What if)
만약 순서가 꼬여서(Out-of-order) 8번이 먼저 R1에 값을 쓱 써버렸는데, 굼벵이 같은 1번이 뒤늦게 와서 옛날 값으로 R1을 덮어씌워 버린다면? 최종적으로 R1에는 쓰레기 값이 남게 됩니다. 그래서 8번은 무조건 1번이 쓰기를 끝낼 때까지 기다려야 하는 의존성(Output dependence)이 생깁니다.

Anti-dependence (반의존성) -> WAR Hazard 유발

공식: "앞 놈이 방에서 값을 읽기도(Read) 전에, 뒷 놈이 쳐들어와서 새 값을 써버린다(Write)!"

예시 A: "5 on 2 for R4"

• Inst 2: ADD R3, R4, R1 👉 덧셈을 하기 위해 R4의 값을 읽는다 (Read).
• Inst 5: ADD R4, R4, #10 👉 계산 결과를 R4에 쓴다 (Write).

디버깅: 2번이 원래 있던 순정 R4 값을 읽고 가야 하는데, 만약 5번이 미쳐 날뛰어서 먼저 R4에 10을 더해버리면(Write)? 2번은 미래의 오염된 값을 읽게 되는 대참사가 벌어집니다.

Control Hazard

BNEZ R2, Loop (조건부 분기 명령어)
이 명령어는 R2가 0이 아니면(Not Equal to Zero) Loop라는 라벨(일반적으로 1번 명령어 LD 위치)로 돌아가고, 0이면 루프를 끝내고 아래(8번)로 내려가라는 뜻입니다.

• 즉, 다음 사이클에서 1~6번이 파이프라인에 다시 들어올지 말지는 7번이 결정하므로, 1~6번은 7번에 대해 Control Dependent 합니다.
• 따라서 8번 명령어가 실행될지 말지도 오직 7번의 결과에 달려있으므로, 8번 역시 7번에 대해 Control Dependent 합니다.