Kim Seon Deok
[General Purpose GPU] ch3.1 ONE - LOOP APPROXIMATION 본문
*General - Purpose Graphics Processor Architecture의 chapter 3.1 ONE - LOOP APPROXIMATION 를 읽고 정리한 내용입니다.
위 figure는 GPU pipeline이다. pipeline은 SIMT front-end와 SIMT back-end로 나뉜다.
single pipeline에는 3개의 scheduling loop가 포함되어 있고 register는 scheduling loop에 access한다.
GPU의 organizing principle은 multiple threading이고 이는 세 가지 scheduling loop 위주로 구성된다.
따라서 approximation loop를 파악함으로써 scheduler loop의 세부 사항을 고려할 수 있다.
- instruction fetch loop = Fetch + I-Cache + Decode + I-Buffer
- instruction issue loop = I-Buffer + Scoreboard + Issue + SIMT Stack
- register access scheduling loop = Operand Collector + ALU + Memory
One loop approximation
One loop approximation은 GPU가 단일 scheduler를 갖고 있다 가정한다. (GPU의 scheduling 단위는 warp)
one loop approximation에서 warp의 program counter는 warp가 다음에 실행할 instruction을 찾기 위해 사용된다.
instruction이 fetch되고 decdode 된 다음 source operand register가 register file로부터 fetch된다.
parallel한 방식으로 register file에서 source operand를 fetching하면서 SIMT execution mask 값은 결정된다.
execution mask와 source register가 available해지면, execution은 SIMD 방식으로 진행된다.
각 thread는 SIMT execution mask가 설정한 lane과 관련된 function unit에서 실행된다.
CPU 구조와 마찬가지로 GPU functional unit은 heterogeneous하기 때문에 일부 instruction만 지원한다.
NVIDIA GPU의 function unit
- SFU (Special Functional Unit)
- LD/ST unit (Load/Store unit)
- Floating-Point fucntion unit
- Inteager function unit
- Tensor Core ( Volta architecture 부터 사용)
function unit은 하나의 warp에 있는 thread 갯수만큼의 lane 수를 포함하고 있다. 하지만 single warp는 1 cycle 보다 긴 cycle 동안 실행되기도 한다. 이러한 이유로 function unit은 더 높은 clock frequency를 갖게 되었다.
function unit이 더 높은 clock frequency에서 수행되게 만들기 위해서는 execution을 pipeline으로 만들고 pipeline depth를 더욱 깊게 하는 방법이 있다.
3.1.1 SIMT EXECUTION MASKING
modern GPU의 가장 큰 특징은 SIMT execution model이라는 것이다. functionality 관점에서 각 thread는 completely independet한 방식으로 실행된다. 이러한 프로그래밍 모델은 predication만으로도 이루어질 수 있지만 현재 GPU는 기존의 predication과 SIMT stack이라 불리는 predicate mask stack을 사용해서 실행된다.
SIMT stack은 모든 thread가 독립적으로 실행될 때 나타나는 2가지 issue를 hadle한다.
1. nested control flow : 하나의 branch는 다른 branch에 대해 control dependent하다.
2. skipping computation : warp 내 모든 thread가 control flow path를 피할 때 computation을 건너뛰는 것 -> control flow가 복잡하다면 computation을 상당히 줄일 수 있다.
do {
t1 = tid*N; // A
t2 = t1 + i;
t3 = data1[t2];
t4 = 0;
if( t3 != t4 ) {
t5 = data2[t2]; // B
if( t5 != t4 ) {
x += 1; // C
}
else {
y += 2; // D
}
}
else {
z += 3; // F
}
i++; // G
} while( i < N );
위 코드는 2개의 branch가 nested 형태로 되어 있는 loop이다.
(하나의 warp 당 4개의 thread가 들어있다 가정)
위 코드는 A/1111에서 시작해 실행되다가 branch instruction( if( t3 != t4 ) ) 이후로는 B/1110와 F/0001로 diverge된다.
B/1110는 branch instruction (if( t5 != t4 ))이후로 C/1000와 D/0110로 diverge되었다가 E/1110에서 converge된다.
G/1111에서 E/1110와 F/0001는 converge된다.
따라서 GPU hardware는 하나의 warp 내 스레드들이 cycle 당 하나의 instruction만 수행하도록 하는 SIMD path방식을 사용하고 있지만, 하나의 warp 내 스레드들이 코드가 branch 되었을 경우 다른 code path 를 따르게 되고 각 code path는 serial하게 실행된다.
- reconvergence point : diverge된 thread를 강제로 다시 lock-step방식으로 실행할 수 있게 하는 프로그램 위치
- Next PC : 다음에 실행할 instruction의 address를 담고있는 register
- Active Mask : 워프 내 thread들이 각각 branch instruction 조건에 따라 실행될 지 여부를 나타냄
divergent code path를 serialization하기 위한 방법으로 stack을 사용한다.
각 stack의 entry는 RPC(reconvergence program counter), next PC, active mask를 포함한다.
warp가 A이후 branch instruction을 거치고 나서 TOS entry에는 B, F가 추가된다.
warp가 실행하는 next instruction은 TOS의 next PC 값을 사용해 결정된다.
SIMT stack의 TOS는 B를 next PC로 가리키고 있기 때문에 active mask로 1110이 F보다 먼저 실행된다.
B이후 branch instruction을 거치고 나서 3.4(d)의 (i)entry의 next PC은 branch가 reconverge 되는지점인 E로 수정된다.
그리고 (ii), (iii) 로 표시된 entry가 추가된다.
divergent branch 이후 stack에 entry를 추가하게 될 때, entry가 추가되는 순서는 reconvergence stack의 최대 깊이를 최소화 하는 데 영향을 미친다. 따라서 active thread를 많이 갖고 있는 entry를 stack에 먼저 추가하고 active thread를 적게 갖고 있는 entry를 그 다음에 추가하는 것이 좋다.
3.1.2 SIMT DEADLOCK AND STACKLESS SIMT ARCHITECTURES
SIMT deadlock
NVIDIA Volta 아키텍쳐가 release되면서 변경된 사항은 divergence 시 masking 동작과 synchronization이었다.
SIMT stack 방식은 SIMT deadlock을 일으킬 수 있다.
SIMT execution을 위한 하드웨어에 대한 연구가 진행된 바가 있는데( [ElTantaway et al., 2014] ), 이 하드웨어에서는 Independent thread scheduling을 통해 SIMT deadlock을 피할 수 있다고 설명한다.
Line A : shared variable인 mutex를 0으로 initialize -> 워프 내 모든 thread는 코드 시작 시 lock 변수 free 상태로 설정
Line B : warp 내 각 thread들은 atomicCAS operation을 수행
Line C : atomicCAS operation을 만족하는 하나의 thread는 critical section에 진입, 나머지 thread들은 loop에서 대기
-> critical section이 끝나면 atomicExch operation을 수행
- atomicCAS(mutex, 0, 1)
- 맨 처음에 mutex의 값을 read한 다음 second input 값인 0과 비교
- 만약 현재 mutex의 값이 0으로 2번째 인자와 같으면 mutex 값을 1로 업데이트 (compare-and-swap operation)
- 만약 현재 mutex의 값이 0이 아닌 다른 값으로 2번째 인자와 다르면 mutex 값은 변경되지 않음
- atomicCAS operation에 의해 return된 값은 mutex의 original value인 0, 즉 mutex 값이 0이 될 때 까지 loop를 반복
- loop에 남아있는 thread들은 SIMT-stack의 꼭대기에서 active한 상태가 되며 계속 spin하며 대기 -> SIMT-deadlock 발생
- atomicExch(mutex,0)
- 특정 thread가 갖고 있던 lock을 해제해서 다른 thread가 lock을 얻을 수 있게 함
- 한 thread가 critical section을 빠져나온 후에 mutex 값을 다시 0으로 설정
- 다른 thread들이 critical section에 들어갈 수 있게 mutex를 다시 열어 둠
- loop를 빠져 나와 reconvergence point에 도달하면 SIMT stack에서 제거되어 더 이상 active한 상태가 아님
warp 내 모든 thread들은 같은 memory location에 access한다.
각 thread에 대해 logical operation 순서를 atomic한 방식으로 수행된다.
오직 1개의 thread만 mutex 값을 0으로 보게 되고 critical section에 진입할 수 있으며 나머지 thread들은 mutex 값을 1로 보게 되어 critical section에 진입 하지 못하고 spin하며 대기하게 되므로, 하나의 warp 안에서 서로 다른 thread에 의해 수행되는 access는 serialize된다.
즉 mutual exclusion 방식을 통해 critical section을 보호하고, SIMT 실행방식에서 여러 thread 간 synchronize가 가능해진다.
STACKLESS SIMT ARCHITECTURES
stack을 warp 당 convergence barrier로 교체하는 방식
convergence barrier mechanism은 warp barrier와 유사하다.
앞의 stack 기반 SIMT 아키텍쳐와 프로그래밍 모델을 동일하게 놓고 보았을 때 branch instruction에 대해 reconverge를 다루는 방식에서 차이가 있다.
warp split
branch instruction 실행 후 일부 thread가 diverge 되어 next PC가 달라짐
이 때 공통되는 PC값을 가지는 일부 thread에 해당하는 thread active field를 업데이트해서 해당 thread의 실행을 enable함
stack 기반 SIMT implementation기법과 다르게, stackless SIMT architecture에서 converge barrier의 scheduler는 diverge된 thread group 간 전환이 자유롭다. 따라서 일부 thread가 lock을 획득하게 되면 그동안 다른 thread는 대기하지 않고 forwarding이 가능하다.
/* nested control flow */
// id = warp ID
// BBA Basic Block ”A”
if ( i d %2==0) {
// BBB
} else {
// BBC
if ( i d = = 1 ) {
// BBD
} else {
// BBE
}
// BBF
}
// BBG
Barrier Participation Mask
- warp 내 어떤 thread가 convergence barrier에 속하는 지를 trace
- warp scheduler가 특정 converge barrier에서 thread를 중지시키는 데 사용됨
- control flow가 nested된다면 barrier participation mask 1개 이상
일반적으로 특정 barrier participation mask에 의해 trace된 thread는 다르게 분기된 branch 이후에 common point에 도달할 때까지 기다린 다음 reconverge한다.
Barrier state
- warp의 각 thread의 상태를 trace
- thread가 ready 상태인지
- converge barrier에서 block되었는지,
- yield 상태(SIMT deadlock이 일어날 수 있는 상황에서 warp 내 다른 thread들이 converge barrier 를 pass하도록 함)인지
Thread rPC : active 상태가 아닌 각 thread에 대해 실행할 다음 instruction의 address를 trace
Thread active : warp내 어떤 thread가 active 상태인지를 나타내는 bit
- ADD instruction
converge barrier participation mask를 초기화
branch instruction이 있는 경우, thread의 각 경로에 대해 새로운 converge barrier participation mask를 설정
- WAIT instruction
warp split이 converge barrier에 도달했을 때 멈추도록 함 & 그 전까지는 대기
thread의 state를 block 상태로 변경
- YIELD instruction
warp split 간 switching을 가능하게 함
위 figure는 SIMT stack architecture와 stackless SIMT architecture의 동작과정 을 보여준다.
- SIMT stack architecture -> stack 기반 reconverge 매커니즘을 사용하기 때문에 reconvege 지점에서 일부 thread가 대기하는 동안 다른 thread 역시 대기를 해야 한다.
- stackless SIMT architecture -> independent하게 thread scheduling을 하기 때문에 x, y는 interleave되어 실행된다.
즉 일부 thread가 대기하는 동안 다른 thread는 independent하게 forwarding가능하다.
위 figure는 stackless architecture가 SIMT deadlock을 피하기 위해 spin lock 코드를 실행하는 방법이다.
3.1.3 WARP SCHEDULING
GPU 각 core에서 GPU host는 많은 갯수의 warp를 포함한다.
warp는 schedule되면 single instruction을 issue하고 schedule 된 warp는 해당 instruction이 실행을 완료하기 전까지 다른 instruction을 issue하지 않는다.
memory system이 일정한 latency 내에 memory request를 처리할 수 있다면, fine-grained multithreading을 사용해서 충분한 갯수의 thread로 latency를 hiding할 수 있도록 core를 설계할 수 있다.
이 경우 round-robin 스케줄링 방식으로 warp를 스케줄링 하도록 해 특정 throughput에 대한 chip의 area를 줄일 수 있다.
round-robin에서 warp는 일정한 순서대로 scheduler에 의해 순서대로 선택되어 실행된다. 따라서 각 instruction은 동일한 time slice를 통해 실행이 완료된다.
core 당 warp 갯수를 증가시켜서 (warp내 thread 갯수) * (issue하는 데 걸리는 시간) > memory latency가 되는 경우, core 내 execution unit은 항상 busy한 상태일 것이다(모든 core에 warp를 채워넣을 수 있기 때문).
따라서 이 지점까지 core 당 warp 갯수를 늘린다면 원칙적으로는 core 당 throughput을 높일 수 있다.
하지만 trade-off가 존재한다. core 당 warp 갯수가 늘어나면 execution unit에 할당되는 부분보다 register file storage에 할당된 부분이 더욱 증가한다.(register 필요↑). 따라서 일정한 chip area에서 chip 당 전체 core 갯수가 감소한다.
그렇기 때문에 memory responce latency는 application의 locality 및 off-chip memory access에 대해 발생한 contention의 양에 따라 달라진다.
round-robin 스케줄링 방식을 사용했을 때 locality property는 자주 사용될 수도 그렇지 않을 수도 있다
- 서로 다른 thread가 실행 중 data를 공유하는 경우 on-chip cache에서 hit하는 memory request thread가 증가할 수 있기 때문에 각 스레드의 progress를 동등하게 진행하는 것이 효율적이다.
- address psace에서 인접한 위치에 access 할 때 round-robin scheduling 방식으로 DRAM에 access하는 것이 더 효율적이다.
- thread가 대부분 인접하지 않은 data에 액세스하는 경우, 특정 thread를 반복적으로 schedule하면 locality를 증가시킬 수 있다.
'General Purpose GPU' 카테고리의 다른 글
| [General Purpose GPU] ch3.4 Research directions on branch divergence(1) (0) | 2024.01.15 |
|---|---|
| [General Purpose GPU] ch3.2 TWO - LOOP APPROXIMATION ~ ch3.3 THREE-LOOP APPROXIM (0) | 2024.01.07 |
| [General Purpose GPU] ch2. Programming model (0) | 2023.12.28 |
| [General Purpose GPU] ch1. Introduction (1) | 2023.12.27 |
