Kim Seon Deok
[Quantitative approach] ch3.1 Instruction-Level Parallelism: Concepts and Challenges ~ 3.2 Basic Compiler Techniques for Exposing ILP 본문
[Quantitative approach] ch3.1 Instruction-Level Parallelism: Concepts and Challenges ~ 3.2 Basic Compiler Techniques for Exposing ILP
seondeok 2023. 12. 15. 06:08
Pipeline
multiple instruction의 실행을 overlap하여 performance를 향상시키는 기법
Instruction-level parallelism
instruction 간 overlap되는 것을 말한다.
- 하나의 instruction이 다른 instruction에 dependent 하다는 것을 결정하는 건 프로그램에 parallelism이 얼마나 많이 존재하고, 그 parallelism을 어떻게 활용할 수 있는지를 결정한다.
- 만약 두 instruction이 parallel하고 pipeline이 충분한 자원을 갖추고 있어, structure hazard가 발생할 위험이 없다면, 임의의 depth의 pipeline에서 동시에 실행될 수 있다.
ILP에 접근하는 방식
1. 하드웨어를 활용해 dynamic하게 parallelism을 발견하고 활용하는 방식
2. compile time에 parallelism을 static하게 찾기 위해 소프트웨어적인 테크닉을 활용하는 방식
Pipeline CPI
pipeline 프로세서의 CPI값은 기본 CPI와 stall로 인해 발생하는 모든 요소를 더한 값이다.
Ideal pipeline CPI는 하드웨어가 얻을 수 있는 최대 성능이다.
해당 수식을 통해 ideal pipeline CPI를 줄이기 위해서는 hazard 처리가 중요하다는 것을 알 수 있다.
Pipeline Speedup
만약 pipeline의 cycle time overhead를 무시하고 각 stage가 균형잡혀있다 가정하면 speedup은 다음과 같다.
모든 instruction이 동일한 cycle 수를 갖는 경우 pipleline의 깊이와 동일해야 한다. 이 경우 pipeline되지 않은 CPI는 pipeline의 깊이와 같아지게 되어 speedup은 다음과 같다.
Data dependence
- instruction i가 결과값을 생성하며 instruction j에서 해당 결과값이 사용되는 경우
- instruction j는 instruction k에 대해 data dependence를 가지고, instruction k는 instruction i에 대해 data dependence를 갖는 경우
Loop: fld f0,0(x1) // f0=array element
fadd.d f4,f0,f2 // add scalar in f2
fsd f4,0(x1) // store result
addi x1,x1,-8 // decrement pointer 8 bytes
bne x1,x2,Loop // branch x16¼x2
위의 루프에서 fld의 f0은 fadd.d에서 사용된다.
fadd.d의 f4는 fsd에서 사용된다.
addi의 x1은 bne에서 사용된다.
따라서 두 instruction이 data dependent하다면 data hazard chain이 존재하게 되어, 두 instruction은 sequential하게 실행되어야 하며고 동시에 실행되거나 완전히 overlap될 수 없다.
만약 instruction들을 동시에 실행하게 되면 pipeline은 hazard를 감지하여 stall함으로써 overlap을 줄이거나 제거한다.
name dependence
두 instruction이 동일한 register 혹은 memory location(= name)을 사용하지만 해당 name과 관련된 instruction 사이에 data flow가 없는 경우에 발생
- instruction i가 instruction j를 앞서는 경우
1. antidependence : instruction j가 instructon i가 읽는 register나 memory location에 write를 수행할 때 발생
2. output dependence : instruction i와 instructoin j가 동일한 register혹은 memory location에 write를 수행할 때 발생
1 2 모두 원래 명령어 간 순서를 보존해야 한다. instruction i가 올바른 값을 read하고 최종적으로 write된 값이 instruction j로 인한 것이어야 한다.
뿐만 아니라 1 2 모두 data가 instruction 간에 transfer 되는 것이 아니기 때문에 실제 data dependence가 아닌 name dependence이다. 그렇기 때문에 name이 변경된다면 충돌이 일어나지 않게 되어 동시에 실행되거나 reorder될 수 있다.
register renaming : register이름을 재설정하는 것이다. 이는 컴파일러에 의해 static하게 수행되거나 하드웨어에 의해 dynamic하게 수행될 수 있다.
control dependence
instruction이 branch instruction과 관련해 원래 프로그램 순서대로 실행되어야 하는 것을 결정한다.
if p1 {
S1;
};
if p2 {
S2;
}
S1은 P1에 dependent하며 S2는 P2에 dependent하다.
control dependence는 제약조건이 있다.
1. branch에 control-dependent한 instruction은 해당 branch에 의해 더 이상 control 되지 않도록 branch 앞으로 이동할 수 없다. (ex) if-then에서 then을 if 앞으로 가져올 수 없다)
2. branch에 control-dependent가 없는 instruction은 해당 branch에 의해 control되도록 branch 뒤로 이동할 수 없다.
(ex) if-then에서 if문 앞의 문을 가져와 then 부분으로 이동할 수 없다)
단 프로그램의 순서에 영향을 미치는 경우가 있다.
1. exception
2. data flow
Data hazard
instruction 간 dependence가 존재하고 실행 중에 overlap이 있다면 dependence가 있는 operand의 access 순서가 변경될 수 있는 경우를 말한다.
dependence로 인해 프로그램은 소스 프로그램에서 결정된 대로 sequential한 순서를 따라 실행되어야 한다.
단 Pipeline에서 hazard 발생을 막는 것에 한해서는 프로그램의 순서를 바꿀 필요가 있다.
명령어 순서 : i -> j
/* RAW hazards */
add r2, r5, r3
add r3, r2, r3- RAW(read after write) : i가 write하기 전에 j가 read를시도하여 발생하는 hazard -> j는 이전 값 즉, 잘못된 값을 얻게 됨 -> data dependence에 해당. 위 코드에서는 r2 register를 참고
/* WAW hazards */
add r2, r5, r3
add r2, r1, r3- WAW(write after write) : i가 write 하기 전에 j가 write를 시도하여 발생하는 hazard -> i가 작성한 값이 destination에 write된다. -> output dependence에 해당. 위 코드에서는 r2 register를 참고
/* WAR hazards */
add r2, r5, r3
add r3, r2, r3- WAR(write after read) : i가 read하기 전에 j가 write를 시도하여 발생하는 hazard -> i는 새로운 값 즉, 잘못된 값을 얻게 됨 -> data dependence에 해당 -> 위 코드에서는 r3 register를 참고
프로세서가 ILP를 활용하는 방법
Loop Unrolling & scheduling
/*Loop unrolling 적용되기 이전*/
Loop: fld f0,0(x1) // 1cycle
stall // 2cycle
fadd.d f4,f0,f2 // 3cycle
stall // 4cycle
stall // 5cycle
fsd f4,0(x1) // 6cycle
addi x1,x1,-8 // 7cycle
bne x1,x2,Loop // 8cycle위의 경우 8 cycle이 걸린다.
해당 루프를 7 cycle로 줄이기 위해 addi를 reposition하면 다음과 같다.
/*Loop unrolling 적용된 이후*/
Loop: fld f0,0(x1)
addi x1,x1,8
fadd.d f4,f0,f2
stall
stall
fsd f4,8(x1)
bne x1,x2,Loop여기서 load, add, store를 하는 데 각각 1 cycle이 걸려서 총 3cycle이 걸리고
나머지 4 cycle은 addi, bne instruction과 2번의 stall로 인한 loop overhead이다.
이 4 cycle을 줄이기 위해 overhead instruction 갯수보다 더 많은 operation을 수행해야 한다.
- loop unrolling은 instruction 갯수를 늘리는 방법이다. loop body를 여러 번 복사하고 loop 종료 코드를 조정함으로써 구현할 수 있다. loop unrolling은 branch를 제거하기 때문에 서로 다른 iteration에서의 instruction을 스케줄링할 수 있다. (branch hazard의 갯수를 줄임) loop body 안에서 추가적으로 독립적인 instruction을 만들어서 더 많은 computation을 드러내고 data use stall을 제거할 수 있다. 그리고 unroll된 loop에서 동일한 address를 참조하지 않는다면 load 및 store는 독립적이게 되어 서로 교환될 수 있다.
- scheduling은 unroll된 loop의 성능을 최적화하는 중요한 단계이다. scheduling과정이 없으면 unroll된 loop의 FP load 또는 operation에 dependent한 operation이 뒤따라와 stall이 발생하게 된다.
위의 9cycle이 걸렸던 loop를 바탕으로 loop를 최적화하지않고 unroll하게 되면 (8*3 + 2) cycle 동안 실행되게 된다.
(fld에서 1 cycle stall + fadd.d에서 2cycle stall)
scheduling을 적용하게 되면 instruction의 실행 순서가 최적화되어 stall을 최소화하고 independent한 instruction의 실행을 overlap할 수 있다.
optimization 1
/*Loop unrolling(iteration : 4) 및 scheduling이 적용된 이후*/
Loop: fld f0,0(x1)
fadd.d f4,f0,f2
fsd f4,0(x1) // 1 loop
fld f6,-8(x1)
fadd.d f8,f6,f2
fsd f8,-8(x1) // 2 loop
fld f0,-16(x1)
fadd.d f12,f0,f2
fsd f12,-16(x1) // 3 loop
fld f14,-24(x1)
fadd.d f16,f14,f2
fsd f16,-24(x1) // 4 loop
addi x1,x1,-32
bne x1,x2,Loop위 코드는 이전 코드의 loop를 풀어서 loop body가 4번 나오도록 unrolling 한 것이다.
scheduling을 통해 3번의 loop 마다 중복되어 나타나던 addi 와 bne instruction은 제거되어 마지막에 한 번만 수행되도록 최적화 된 것이다. -> overhead instruction을 제거하여 loop의 성능을 향상시킴
하지만 위 코드에는 코드의 길이가 상당히 길어진다는 단점이 있다.
loop의 upper bound를 n이라 가정하고 loop를 k번 복사하도록 unrolling 한 경우,
하나의 큰 Loop가 생성되고 그 Loop 안에 특정 loop의 내용이 k번 반복되게 된다.
- unroll됨으로써 반복되는부분은 (n / k)번 실행된다.
- scheduling됨으로써 중복이 제거되고 나머지에서 실행되는 부분은 (n mod k)번 실행된다.
따라서 전체적으로 loop가 (n mod k) + (n / k) 번 반복되게 된다.
optimization 2
/*Loop unrolling(iteration : 4) 및 scheduling 이후*/
Loop: fld f0,0(x1)
fld f6,-8(x1)
fld f0,-16(x1)
fld f14,-24(x1)
fadd.d f4,f0,f2
fadd.d f8,f6,f2
fadd.d f12,f0,f2
fadd.d f16,f14,f2
fsd f4,0(x1)
fsd f8,-8(x1)
fsd f12,16(x1)
fsd f16,8(x1)
addi x1,x1,-32
bne x1,x2,Loop
이전 최적화 코드는 loop가 한번 반복되는 동안 load instruction - operation instruction - store instruction이 차례대로 나타났다.
하지만 이번 최적화 코드는 load instruction과 operation, store instruction이 모두 그룹화되어 나타나는데, 이를 통해 load instruction의 결과를 기다리는 동안에도 다른 operation instruction들이 더 많이 실행될 수 있어 전체 성능이 더욱 향상될 수 있다.
-> 같은 작업을 수행하지만 instruction의 실행 순서를 최적화해서 성능을 개선한 것이다.
loop unrolling을 적용하기 위해 필요한 단계
- loop의 independence 확인 -> 각 computation이 서로 독립적으로 실행될 수 있는지 확인
- 다른 register 사용 -> 동일한 register를 사용해서 발생하는 dependece를 방지
- 추가적인 branch instruction 제거 -> 불필요한 instruction을 최소화
- load store interchange 확인 -> 다른 iteration에서 load와 store가 서로 독립저깅라면 instruction을 최적으로 조정 가능
- code scheduling -> instruction을 최적으로 정렬
looop unrolling 및 scheduling을 통한 performance gain을 제한하는 요인
1. unroll에 따른 overhead 감소 -> loop를 unroll할 때마다 각각의 unroll에 대해 개선되는 overhead 양이 감소한다.
2. code size 제한 -> loop가 클 경우 code 크기가 증가하게 되어, instruction cache miss rate가 증가할 수 있다.
3. compiler 제한
4. register pressure 발생 -> loop를 unrolling하게 되면 동일한 register를 사용하게 된다. ILP를 증가시키기 위해 코드를 scheduling하면서 live한 value 값의 수가 증가하게 되어 사용 가능한 register 갯수가 부족해지게 된다. 따라서 loop를 효과적으로 스케줄링하는 데 어려움이 생길 수 있기 때문에 각 computation에 대해 다른 register를 사용해야 한다.
따라서 이러한 제약 요인을 고려해서 loop unrolling을 적용해야 한다.