Lec 12 · VLIW 컴파일 기법 (loop unrolling, software pipelining, trace scheduling)

1.1Lec 9(VLIW) 후반부: VLIW 복습과 초기 VLIW machine(AP-120B, Multiflow Trace, Cydra-5).

1.2B[i]=A[i]+C loop 로 기본 schedule 0.125 → loop unrolling 0.36 → software pipelining 1 FLOP/cycle 비교.

1.3irregular code 의 짧은 basic block 문제와 trace scheduling. p16 부터는 Zoom 회의 이동으로 이 영상에 설명 없음.

상황·문제Zoom 무료 계정 40분 제한으로 회의가 끊기면 미리 준 다른 Zoom 링크로 재접속하라는 안내(닉네임 변경 요청 포함).

상황·문제VLIW = 한 very long instruction 에 여러 연산(Int·Mem·FP slot 각 2개)을 담는 구조.

원인연산 latency 가 다르고 hardware 가 dependence check·stall 을 하지 않으므로, instruction 내·instruction 간 독립성을 compiler 가 보장해야 한다.

해결복잡도를 hardware→software 로 이동. 성공하면 단순 HW 에 execution unit 을 더 붙일 수 있으나 많은 application 에선 잘 안 된다고 언급.

상황·문제초기 VLIW 는 compiler 가 미성숙해 활용이 어려웠다.

원인AP-120B(1976) 시절 compiler 가 이 구조를 위한 code 를 만들지 못함. 짧은 basic block 이 많으면 한 word 를 채울 연산을 찾기 어려움.

해결AP-120B: software pipelining·loop unrolling 을 쓴 hand-coded vector math library. Multiflow: trace scheduling 으로 basic block 묶음, 28 ops/1024-bit. Cydra-5: 7 ops/256-bit, rotating register file.

상황·문제compiler 가 여러 연산을 한 word 에 schedule 해 병렬 실행을 극대화해야 한다.

원인hardware interlock 이 없어 dependent 연산 사이 간격을 compiler 가 확보해야 한다.

해결사이에 넣을 유용한 일이 없으면 NOP 을 넣어 hazard 회피.

상황·문제vector 에 scalar 를 더하는 loop 를 VLIW 에 올리면 성능이 매우 낮다.

원인fld(3 cycle)→fadd(4 cycle)→fsd 의존 사슬만 있고 loop body 에 독립 연산이 부족.

해결1 FP op / 8 cycles = 0.125 ops/cycle(이상적 1 의 1/8) → loop unrolling 등으로 독립 연산을 늘려야 함.

상황·문제0.125 ops/cycle 은 loop body 내 독립 연산 부족 때문.

원인unroll 없이는 한 iteration 에 fld·fadd·fsd 한 쌍뿐.

해결4-way unroll → 4 fadds / 11 cycles = 0.36(약 3배). 대가: code size 증가, FP register 2→8개. N 이 4의 배수가 아니면 cleanup loop.

상황·문제unroll 후에도 FP unit 이 충분히 쓰이지 않는다.

원인한 iteration 안에서만 schedule 하면 load→add→store latency 동안 slot 이 빈다.

해결독립인 여러 iteration 의 연산을 겹쳐 schedule(다음 iteration fld 를 현재 fadd 와 동시에). prolog·iterate·epilog 구조로 4 fadds / 4 cycles = 1 FLOP/cycle.

상황·문제두 기법의 overhead 차이를 그래프로 비교.

원인unrolling 은 iteration 마다 ramp-up(load)·wind-down(store) 을 반복해 main 부분 동안 HW 를 다 못 씀.

해결software pipelining 은 여러 iteration 을 압축해 main 부분을 계속 실행, 시작·끝 비용은 loop 당 한 번.

상황·문제control flow 가 복잡한 program 은 짧은 basic block 이 많다.

원인다음에 어느 basic block 이 실행될지 모르므로 block 경계를 넘어 연산을 모을 수 없다.

해결block 끝마다 덜 채워진 instruction 이 생겨 성능 저하 → trace scheduling 필요.

상황·문제여러 basic block 에 걸쳐 연산을 schedule 해야 한다.

원인가능한 trace 가 여러 개이고, 실행 중 trace 밖 경로로 나갈 수 있다.

해결profiling 으로 자주 실행되는 경로를 trace 로 골라 한 번에 schedule, trace 밖으로 나가면 fixup code 로 되돌리고 올바른 일을 수행. 흔한 경로가 대부분이면 평균 성능 향상.

상황·문제p16(Problems with classic VLIW) 을 띄운 상태로 약 3.5분 음소거, 이후 40분 제한 때문에 다른 회의로 옮긴다고 안내하고 종료. p16 이후 내용은 이 영상에 없음.

고정 slot 에 여러 독립 연산을 담은 instruction. dependence check·interlock 을 compiler 가 대신.

dependent 연산 사이에 넣을 일이 없을 때 hazard 회피용으로 compiler 가 넣는 빈 연산.

loop body 를 여러 번 복제해 독립 연산을 늘림. code size·register 증가, cleanup loop 필요.

서로 다른 iteration 의 연산을 겹쳐 schedule. prologue·epilogue 필요, overhead 는 loop 당 한 번.

software pipelining 된 loop 앞의 시작 code 와 뒤의 마무리 code.

profiling 으로 고른 빈번 경로의 basic block 열을 한 번에 schedule, 이탈 시 fixup code.

Cydra-5 가 구현. 강의에서 뒤에 다룬다고만 언급(이 영상에선 설명 없음).

4.1B[i]=A[i]+C 기본 schedule 의 FP ops/cycle 과 그 원인은?

4.24-way unroll 후 성능과 대가는?

4.3software pipelining 이 unrolling 보다 나은 이유는?

4.4trace scheduling 에서 trace 밖 경로가 실행되면?