[컴파일러] 16. 명령어 수준 병렬성과 스케줄링

// ILP가 높은 코드
a = x + y     // 이 세 명령어는 서로 독립적
b = p + q     // 동시 실행 가능
c = r - s

// ILP가 낮은 코드
a = x + y     // 순차적 의존성
b = a + z     // a에 의존
c = b * 2     // b에 의존

a = b + c     // a를 쓰기
d = a + e     // a를 읽기 (대기 필요)

a = b + c     // b를 읽기
b = d + e     // b를 쓰기 (이름 변경으로 해결 가능)

a = b + c     // a를 쓰기
a = d + e     // a를 다시 쓰기 (순서 유지 필요)

// 5단계 파이프라인: IF(Fetch), ID(Decode), EX(Execute), MEM, WB(Writeback)

시간:    1    2    3    4    5    6    7
명령1:  IF   ID   EX   MEM  WB
명령2:       IF   ID   EX   MEM  WB
명령3:            IF   ID   EX   MEM  WB

// 이상적으로 매 클록마다 하나의 명령어 완료

// 데이터 해저드 (RAW)
ADD R1, R2, R3    // R1에 결과 쓰기 (WB 단계)
SUB R4, R1, R5    // R1을 읽기 (ID 단계) - 아직 값이 준비 안됨!

// 해결: 포워딩(forwarding) 또는 지연(stall)
ADD R1, R2, R3
NOP               // 버블 삽입 (stall)
SUB R4, R1, R5

// 컴파일러가 독립적인 명령어를 사이에 삽입하면 stall 방지
ADD R1, R2, R3
MUL R6, R7, R8    // 독립적인 명령어로 빈 슬롯 채움
SUB R4, R1, R5

// 2-issue 슈퍼스칼라 프로세서
시간:    1         2         3
슬롯1:  ADD       MUL       LD
슬롯2:  SUB       AND       ST

// 이상적으로 매 클록마다 2개 명령어 완료
// (IPC = Instructions Per Cycle = 2)

// VLIW 명령어 (4개 연산 슬롯)
// | ALU1     | ALU2     | MEM      | BRANCH   |
// | ADD R1.. | MUL R3.. | LD R5..  | NOP      |

// 각 슬롯은 독립적인 기능 유닛에서 실행
// 병렬 실행의 책임이 컴파일러에 있음

// 원본 코드:
// 1: LD  R1, a       // 로드 지연시간 = 2
// 2: ADD R2, R1, R3  // R1에 의존 (RAW)
// 3: LD  R4, b       // 독립적
// 4: MUL R5, R4, R6  // R4에 의존 (RAW)
// 5: ADD R7, R2, R5  // R2, R5에 의존

// 의존성 DAG:
//   1 --2--> 2 --1--> 5
//   3 --2--> 4 --1--> 5
// (간선의 가중치 = 지연 시간)

알고리즘: 리스트 스케줄링

1. 의존성 DAG 구성
2. 각 노드의 우선순위 계산 (보통 임계 경로 길이)
3. 준비 리스트(ready list)에 의존성이 없는 명령어 추가
4. while 준비 리스트가 비어있지 않음:
     a. 우선순위가 가장 높은 명령어를 선택
     b. 현재 사이클에 발행
     c. 후속 명령어의 의존성이 해소되면 준비 리스트에 추가

// 의존성 DAG (지연시간):
//   LD a(2) -> ADD(1) -> ST(1)
//   LD b(2) -> MUL(3) -> ST(1)

// 우선순위 (루트까지 임계 경로 길이):
//   LD a: 2+1+1 = 4
//   LD b: 2+3+1 = 6  (더 높은 우선순위)
//   ADD: 1+1 = 2
//   MUL: 3+1 = 4
//   ST(ADD 결과): 1
//   ST(MUL 결과): 1

// 스케줄링:
// 사이클 1: LD b (우선순위 6, 가장 높음)
// 사이클 2: LD a (LD b 결과 대기 중, 다른 것 발행)
// 사이클 3: MUL (LD b 결과 준비됨, 사이클 1+2=3)
// 사이클 4: ADD (LD a 결과 준비됨, 사이클 2+2=4)
// 사이클 5: ST (ADD 결과, 사이클 4+1=5)
// 사이클 6: ST (MUL 결과, 사이클 3+3=6)

// 원본 순서대로 실행하면 7사이클 필요
// 스케줄링 후 6사이클로 단축

// 원본 루프 (각 반복에 3개 명령어, 각각 1사이클)
// 반복 i:  A(i), B(i), C(i)
// 반복 i+1: A(i+1), B(i+1), C(i+1)

// 시간:  1     2     3     4     5     6     7
// 원본:  A(0)  B(0)  C(0)  A(1)  B(1)  C(1)  A(2)...

// 소프트웨어 파이프라이닝 후:
// 시간:  1     2     3     4     5
// 원본:  A(0)  B(0)  C(0)
//              A(1)  B(1)  C(1)
//                    A(2)  B(2)  C(2)
//
// 정상 상태(steady state) 커널:
// 시간:  ...   k     k+1   k+2   ...
//              C(i)  C(i+1) ...
//              B(i+1) B(i+2) ...
//              A(i+2) A(i+3) ...

// 1. 프롤로그 (prologue): 파이프라인 채우기
A(0)
A(1), B(0)

// 2. 커널 (kernel): 정상 상태 반복
loop:
    A(i+2), B(i+1), C(i)   // 세 반복이 겹침
    i = i + 1
    if i < n-2 goto loop

// 3. 에필로그 (epilogue): 파이프라인 비우기
B(n-1), C(n-2)
C(n-1)

// 스케줄링에 유리한 코드 (레지스터 많이 사용)
LD R1, a
LD R2, b        // R1 대기 중 다른 로드 수행
LD R3, c
ADD R4, R1, R2  // R1 준비됨
MUL R5, R3, R4

// 레지스터 할당에 유리한 코드 (레지스터 적게 사용)
LD R1, a
ADD R1, R1, b   // R1 즉시 사용 (stall 가능!)
LD R1, c
MUL R1, R1, R1

1. 가상 레지스터(무한 레지스터)로 스케줄링 수행
2. 스케줄링된 코드에 대해 레지스터 할당
3. 스필이 발생하면 스필 코드 삽입 후 재스케줄링

1. 먼저 레지스터 할당 수행
2. 할당된 코드에 대해 스케줄링
3. 스케줄링 자유도가 제한됨 (같은 레지스터 사용으로 인한 거짓 의존성)

1. 레지스터 할당과 스케줄링을 동시에 고려
2. 더 좋은 결과를 얻을 수 있으나 복잡도가 높음

// 흐름 그래프:
//   B1 (실행 확률 100%)
//    |
//   B2 (if cond) -- 90% --> B3
//        |
//        10% --> B4

// 트레이스: B1 -> B2 -> B3 (가장 빈번한 경로)
// 이 경로를 하나의 긴 블록처럼 스케줄링

// B2에서 B3로 명령어를 이동하거나
// B1에서 B2로 명령어를 이동할 수 있음
// (덜 빈번한 경로 B4에 대한 보상 코드 필요)

// 슈퍼블록: 하나의 진입점, 여러 출구점
//   entry -> A -> B -> C -> exit1
//                 |
//                 v
//               exit2
//
// 중간에서 들어오는 간선이 없으므로 코드 이동이 더 자유로움

// VLIW 명령어 패킷 (3 슬롯: ALU, MEM, BR)
// 각 슬롯에 독립적인 연산을 배치

// 사이클 1: | ADD R1,R2,R3 | LD R4, mem1 | NOP        |
// 사이클 2: | MUL R5,R4,R6 | LD R7, mem2 | NOP        |
// 사이클 3: | SUB R8,R5,R7 | ST mem3, R1 | BEQ R8, L1 |

// ILP가 낮은 코드:
// | ADD R1,R2,R3 | NOP         | NOP |
// | MUL R4,R1,R5 | NOP         | NOP |  // 모든 연산이 의존적
// | SUB R6,R4,R7 | NOP         | NOP |

// 해결: 루프 펼침 + 소프트웨어 파이프라이닝으로 ILP 증가