06. Loop-carried Dependences and Parallelism

서울대학교 컴퓨터공학과 이재진 교수님의 "확장형 고성능 컴퓨팅" 강의를 필기한 내용입니다.

• 목차

수업 시작 전 check-in 잡담

• ILP: Dependence 가 없는 Instruction 들을 한번에 처리하는 것
  • 얘네들을 여러 core 에 각각 [[Out-of-Order Execution, OoO (Arch)|OoO execution|dispatch]] 하여 처리하는 것.

True, False dependence §

• Flow dependence 와 같은 경우에는 좀 더 “순서” 와 관련있는 개념이다.
  • 즉, (1) 값이 준비된 다음 (2) 읽어야 하기 때문.
  • 따라서 이런 dependence 를 True dependence 라고 부르는 것.
• 하지만 anti dependence 와 output dependence 는 “순서” 와는 느낌이 좀 다르다.
  • 이놈은 사용한 공간을 “재활용” 하는 것이기 때문.
  • 물론 그렇다고 해서 순서를 바꿔도 된다는 것은 아님; 개념적으로 “순서” 와 좀 거리가 있다라는 의미다.
  • 따라서 이런 놈들을 False dependence 라고 부르고, 다른 공간을 사용하게 하는 것으로 해결 가능하다.
• 가령 다음 예시를 보면

• 왼쪽에는 이런 depenedence 가 있다:
  • Flow dependence: $S_1-{\delta }^t\to S_2$, $S_3-{\delta }^t\to S_4$
  • Anti dependence: $S_2-{\delta }^t\to S_3$
• 이때, 오른쪽 처럼 $S_1$, $S_2$ 에서 사용하는 공간은 $t_1$ 로 바꿔주고 $S_3$, $S_4$ 에서 사용하는 공간은 $t_2$ 로 바꿔주면 anti dependence 는 해결되고 flow dependence 만 남는다.

Loop-related Dependence, 9:1 (8:1) Law §

• 보통 code 전체에서 시간을 많이 잡아먹는 부분은 전체의 10% ~ 20% 밖에 안되는 loop 이다 (9:1 (8:2) 법칙).
• 즉, loop 은 common case 이기 때문에 여기를 paralellism 하는 것 (loop parallelism) 은 성능 향상에 아주 도움이 된다.
  • 잘 발생하지도 않는 corner case 를 optimization 하는 것은 바보짓이다.
• 요즘 compiler 는 대부분 이런 optimization 이 거의 “완벽” 에 가까울 정도로 잘 되어 있다고 한다.
• Loop parallelism 을 위해 분석할 때는 Loop Unroll 하는 것이 도움이 된다고 한다.
• Loop parallelism 에서의 중요한 전제가 되는 이론은: 모든 dependence 가 보존되는 code 순서 변경은 원래의 program 과 “의미” 가 동일하다는 것이다.
  • 여기서 “의미” 가 뭔지는 잘 모르겠는데 대강 “program 의 의도” 라고 생각하자.

Loop-independent, Loop-carried Dependence §

• Loop 의 inner job (매 iteration 에서 수행하는 작업, {} 안의 code) 간에 dependence 가 있으면 Loop-carried dependence, 없으면 Loop-independent dependence 라고 부른다.
• 가령 다음의 코드를 보자.

for (int i = 0; i < N; i++) {
	A[i] = B[i];
	F[i + 1] = A[i];
}

• 얘를 unroll 해보면,

A[0] = B[0];
F[1] = A[0];
 
A[1] = B[1];
F[2] = A[1];
 
A[2] = B[2];
F[3] = A[2];

• Inner job 내부적으로는 flow dependence 가 있지만, job 간에는 dependence 가 없다는 것을 알 수 있다. 이런 경우가 Loop-independence dependence 인 것.
• 반면에 다음의 코드를 보자.

for (int i = 0; i < N; i++) {
	A[i + 1] = F[i];
	F[i + 1] = A[i];
}

• 이건 unroll 하면

A[1] = F[0];
F[1] = A[0];
 
A[2] = F[1];
F[2] = A[1];

• 이렇게 되는데, 이때 line 1, 4 사이와 2, 3 사이에 flow dependence 가 있다는 것을 알 수 있다.
• 따라서 이런 경우에 Loop-carried 가 되는 것.

Loop fusion §

• Loop fusion 은 말 그대로 loop 을 합치는 것
• 이때의 장점은
  • 합치면 BRNACH instruction 을 아낄 수 있고, 따라서 Branch misprediction 도 줄일 수 있다.
  • 그리고 counter (i) 를 절반 횟수만큼만 increment 하면 된다.
  • Locality 를 더 잘 고려할 수 있어서 cache hit 이 높아진다
  • (참고) 위의 세 장점들을 반대로 생각하면 이것이 loop 을 사용할 때의 overhead (Loop overhead) 이다.
• 이때는 합쳤을 때의 dependence 는 어떻게 되는지 파악해서 fuse 해도 되는지 판단한다.
  • 만약 dependence 의 방향이 합친 후에는 반대로 된다면, 합치지 못한다.
  • 아래의 예시를 보자.

• Unrolling 하면 더 파악하기가 편하다.
  • 위의 경우에는
    • b[1 ~ N-1] 까지의 read 이후에 b[0 ~ N-2] 까지의 write 가 있으니까 $S_1-{\delta }^a\to S_2$ (WAR dependence) 가 있다.
    • 그리고 이때는 합치면 iteration $i-1$ 에서의 S1: a[i-1] = b[i-1] 와 iteration $i$ 에서의 S2: b[i-1] = c[i] + 1 간에 마찬가지의 $S_1-{\delta }^a\to S_2$ (WAR dependence) 가 있는 것을 알 수 있다.
  • 근데 아래의 경우에는
    • a[1 ~ N-1] 까지의 write 이후에 a[2 ~ N] 까지의 read 가 있으니까 $S_1-{\delta }^t\to S_2$ (RAW dependence) 가 있다.
    • 하지만 합치면 iteration $i$ 에서의 S2: d[i] = a[i+1] + 1 와 iteration $i+1$ 에서의 S1: a[i+1] = b[i+1] + 3 간에 WAR dependence 가 있으니까 방향은 $S_2-{\delta }^a\to S_1$ 으로 반대이다.
    • 즉, 이때는 합치면 안된다는 소리.

Loop distribution (Fission) §

• 반대의 개념은 loop distribution 인데, 위에서는 합치는게 좋다 해놓고 왜 분리하는 것을 설명하냐:
• SIMD 같은 vectorization 하기 위해서다.
  • 즉, loop 을 vector 크기 단위로 쪼갠 다음 그 loop 에 대해 그냥 vectorized execution 을 때리겠다는 심보이다.
• 즉, loop 을 쪼갬으로써 loop-carried 를 loop-independent 로 바꾼 다음 vectorization 을 할 수 있다.
• Dependence cycle 이 있을 때 이것을 깨지 않는다면, 이렇게 해도 무방하다.
  • Dependence 방향이 바뀌는 것도 cycle 이 깨지는 것이다.
  • Cycle 이 애초에 없어도 당연히 상관없다.
• 다음의 예시를 보자.

• 왼쪽은
  • Iteration $i-1$ 의 S1: a[i-1] = b[i-1] + 3 과 iteration $i$ 의 S2: b[i-1] = a[i+1] + 1 간의 WAR dependence ($S_1-{\delta }^a\to S_2$) 하나와
  • Iteration $i$ 의 S2: b[i-1] = a[i+1] + 1 와 iteration $i+1$ 의 S1: a[i+1] = b[i+1] + 3 간의 WAR dependence ($S_2-{\delta }^a\to S_2$) 하나가 있어 cycle 을 형성하는데
  • 다만 위 그림에서 ${\delta }^t$ 로 표시된건 오타인거같다; 이건 WAR dependence 가 맞지
• 오른쪽은
  • S1: a[1 ~ N-1] 의 write 이후에 S2: a[2 ~ N] 의 read 가 있으니까 RAW dependence ($S_1-{\delta }^t\to S_2$) 하나와
  • S1: b[1 ~ N-1] 의 read 이후에 S2: b[0 ~ N-2] 의 write 가 있으니까 WAR dependence ($S_1-{\delta }^t\to S_2$) 하나가 있어 cycle 이 깨진다.
  • 그래서 오른쪽으로 distribution 할 수는 없는 것.

DOALL, DOACROSS parallelism §

• DOALL (DO-ALL) loop 는 그냥 loop-carried 가 없는 상황이다.
  • 따라서 이 경우 inner job 을 parallel 하게 돌리는 것을 DOALL Parallelism 이라고 한다.
• DOACROSS (DO-ACROSS): loop-carried 가 있어도 loop-independent 한 부분만 잘 분리해서 parallel 하게 계산하고, loop-carried 부분만 sequential 하게 계산하는 방법이다.
  • 즉, 부분적으로 parallel processing 하는 것.
• 이놈은 좀 예시로 확인해 보자. 예시는 위키 에서 들고왔다.
• 가령 다음과 같은 코드가 있을 때

for (int i = 1; i < n; ++i) {
	a[i] = a[i-1] + b[i] + 1; // S1
}

• 이놈은 $I(i)-{\delta }^t\to I(i+1)$ 의 dependence 가 있다. 이제 좀 보이시죠?
• 이때 중간의 b[i] + 1 은 dependence 가 없다. 그래서 이놈을 이렇게 쪼개고

for (int i = 1; i < n; ++i) {
	int tmp = b[i] + 1; // S0
	a[i] = a[i-1] + tmp; // S1
}

• 이런식으로 S0 에 대해서만 parallel processing 해주면 된다.

for (int i = 1; i < n; ++i) {
	begin_parallel();
	int tmp = b[i] + 1; // S0
	end_parallel();
	a[i] = a[i-1] + tmp; // S1
}

• 뭐 물론 구체적인 코드는 아니지만 그래도 대강 감은 잡히죠?

Reduction §

• Reduction 은 여러 값들을 연산해 하나의 값이 나오는 aggregation 같은 연산을 말한다.
• 이건 교환법칙 (Commutative Property), 결합법칙 (Associative Property) 를 만족하고 항등원 (Identity) 가 있는 연산에 대해 가능하다.
  • 이런놈은 덧셈 ($+$), 곱셈 ($\times$), 최소값 ($min$), 최대값 ($max$) 등이다.
  • 참고로 최소값의 항등원은 최대값이고 최대값의 항등원은 최소값이다.
• 이놈을 sequential 하게 계산하는 것은 $N$ 개의 원소에 대해 $N-1$ 개의 연산이 필요한데,
• Parallel 하게 계산하면 다음처럼 BST 식으로 계산해서 $log(N)$ 만에 계산하게 할 수 있다 (사진 출처).

Map Reduce

• Map Reduce 에 대해 자세히 설명하지는 않았지만, 이 reduction 을 이용한 것이다.
• 개념 자체는 단순한데 실제로 되게 하는 것이 어려웠댄다.
• 근데 jeff dean (지금은 google 에 있는) 이 30만대의 서버로 이걸 처음으로 구현했고, 이 논문이 엄청난 임팩트가 있었댄다.

Prefix Sum §

• $i$ 번째 값 $A_i$ 를 계산하기 위해 배열의 $a_0$ 부터 $a_i$ 까지의 값을 다 연산해야 하는 경우 ($A_i=operation(a_0,...,a_i)$) 에 이것을 어떻게 parallel 하게 할 수 있을까?
  • DELTA decoding 과 같은 상황을 생각하면 된다.
• 이때는 간격을 1씩 늘려가며 parallel 하게 계산하면 된다.
  • 즉, 처음에는 인접한 값들 (간격 1) 끼리 계산하고, 다음번에는 앞선 결과를 간격 2 를 띄우고 연산하고를 반복하는 것.
  • 이 방식을 Prefix sum 이라고 한다.
• 그림으로 이해하는게 더 편하다: 이렇게 하겠다는 것 (사진 출처).

Parallelism §

• Parallelism 은 Dependence 를 따져서 없는것들을 한번에 실행하는 것이 핵심 기법이다.
• 세 개로 구분지을 수 있다: ILP, Task parallelism, Data parallelism
• 뭐 ILP 는 앞 에서 봤으니까 나머지 두개만 더 보자.

Task parallelism §

• Worker 여러개에 각각의 무관한 job 을 할당하는 것이다.
  • 비유하면 위 그림처럼 뷔페에서 각 요리사가 요리를 하나씩 도맡아서 하는 형태

• 보통은 각 task 들의 실행 시간이 균일하지 않기 때문에, 가장 오래걸리는 task 를 기준으로 해서 위 그림처럼 나눠서 task 들을 scheduling 한다.
• 근데 worker 가 더 늘어나도 항상 빨라지지는 않는다.
  • 가령 data dependency 를 고려하면 해당 data 를 사용할 수가 없어서 worker 를 늘려도 어차피 놀게 되는 경우가 생기는 등
  • 요리사 비유로 생각해 보면, $N$ 인분을 $P$ 명이 만든다 할 때 누구는 샐러드 만들고 있어서 빨리 끝나서 놀고 있고 누구는 스테끼 굽느라 한참걸리면 어차피 완료되는 시점은 제일 오래걸리는놈이다.
  • 위 그림에서도 보인다: 어차피 core 0 끝나는 동안 core 1 이 나머지 일을 다 할 수 있기 때문에, core 를 더 늘려봤자 별 도움이 안된다.
  • 그래서 code 에는 적용하기 힘든 경우가 있다.

Data parallelism §

• Data parallelism 은 각 worker 가 전체 data 의 일부분을 처리하게 하는 방법이다.
  • 즉, 위의 비유처럼 요리사 $P$ 명이 전체 $N$ 인분을 만들기 위해 각자 $N/P$ 인분을 만드는 방식이다.
• 이건 Loop parallelism 으로 불리기도 하고, worker 를 늘렸을 때 성능이 더 좋아질 수 있다.
  • 가령 위의 비유에서 $P$ 를 증가시키면 각자가 준비해야 하는 양이 줄어들어 더 빨리 끝나게 되는 것과 비슷하다.
• 이걸 instruction level 로 제공하는 것이 SIMD 이고
• 만약에 여러 process 나 Thread 가 동시에 처리하는 등 단위가 instruction 이 아니라 program 이 되면 이것을 Single Program, Multiple Data (SPMD) 라고 부른다.

Multithreaded processors §

Application-derived architecture

• 이재진교수님이 거의 매 수업시간마다 하는 얘기긴 한데
• 어떤 architecture 의 필요성은 application 에 의해 결정된다는 소리이다.
• 즉, 어떤 application 이 필요한 architecture 를 넣어야지 그냥 더 효율적인 것 같다는 생각으로만 architecture 를 구상하면 안된다는 것.
• 이 Multithreaded processor 도 같은 맥락이다: 대부분의 application 들이 thread 를 생성해 병렬적으로 작업을 하기 때문에, 이 기조에 맞는 architecture 를 구상해서 나온게 이놈임.

• Thread-level parallelism (TLP) 은 별다른게 아니고 그냥 Thread 를 여러개 돌려 parallel processing 하는 것을 일컫는 용어이다.
  • SPMD 랑 구분을 짓는다면 TLP 는 thread 를 활용해 parallel processing 을 하는 좀 더 general 한 용어라는 것?
• 그리고 이 TLP 를 효율적으로 지원하기 위한 processor 가 Multithreaded Processor 이다.
  • 보통 CPU spec 에 보면 몇 core 몇 thread 할 때 그놈임
• 일단 Superscalar processor 에서는 여러개의 instruction 을 issue 할 수 있는데,
  • Issue-width 라는 것은 한번에 issue 할 수 있는 instruction 의 최대 개수
  • 이것이 N 이라는 것 (N-issue processor) 은 N 개의 issue slot 과, N 개의 ID unit 이 있다는 소리이다.
• 이때 Multithreaded processor 는 여러개의 thread 로 부터 instruction 을 받아와 그놈들을 issue 하는 방식으로 처리된다.
  • 이때는 아무 thread 에서 긁어오는게 아니라 Data dependence 가 없는 애들만 가져온다 (thread of control).
• 왜냐면 하나의 thread 에 대해서는 ILP 가 부족하기 때문이다.

• 위 그림이 바로 그런 상황이다.
  • Thread 하나에 대해서 issue 를 했을 때는 data dependence 때문에 모든 slot 을 다 채우지 못하거나 (Horizontal waste),
  • Bubble 등에 의해 아무것도 issue 되지 않을 수 있다 (Vertical waste).
• 때문에 여러 thread 로부터 instruction 을 받아오는 방식으로 ILP 수준을 최대로 끌어올리는 것이 핵심 아이디이다.
  • 위에서 본 것 처럼 하나의 thread 에서는 dependence 때문에 parallel 하게 실행할 수 있는 instruction 이 한정될테니까,
  • 여러개의 thread 의 instruction 들을 다 던져서 ILP 를 최대로 뽑아먹겠다는 입장인 것.
• 그리고 현대의 CPU 들에서 이것은 Simultaneous Multithreading (SMT) 으로 구현되어 있다.

Vertical Multithreading §

• 우선 첫번째의 시도는, 중간중간의 vertical waste 에다가 다른 thread 의 instruction 을 끼워 넣는 것이다.
  • 즉, 한 cycle 내에서는 하나의 thread 의 instruction 들만 issue 된다.
  • 이 방식을 Vertical Multithreading 이라고 한다.
• 이렇게 하면 instruction issue latency 를 hiding 하게 된다.
• 이때 thread scheduling 은 두가지의 방식이 있다.
  • Fine-grained multithreading: 매 cycle 마다 thread 간의 context switching 을 해주던가.
  • Coarse-graned multithreading: Data hazard 나 cache miss 등의 long-latency 상황에서만 context switching 을 하던가.
    • 따라서 이때는 당연히 매 cycle 이 아닌 수 cycle 단위로 context switching 이 된다.
• 여기서 context switching 이라는 용어를 사용했는데, 이건 Process context switch 와 유사하지만 “단위” 가 다른 것이다.
  • 저기서는 process (혹은 thread) 전체를 갈아끼우는 것을 말하는 것이고,
  • 여기서는 다른 thread 의 instruction 으로 갈아끼우는 것을 말하는 것이다.
• 따라서 이런 빈번한 context switching 을 빠르게 하기 위해, register file 을 지원하는 thread 의 개수 만큼 pair 를 구비한다.
  • 이놈은 context switch 가 될때 여기에 thread context 를 잠깐 담아두는 용도
    • 매번 memory 에 왔다갔다 하는건 너무 비효율적이자나?
  • “지원하는 thread 개수” 가 CPU spec 에서 “몇 thread” 할 때의 그놈이 이 개수인 것이고, logical core 개수라고도 말한다.

Simultaneous Multithreading, SMT, Hyperthreading §

• 여기서는 이제 1 cycle 에서 issue 할 때 여러개의 thread 에서 instruction 을 긁어오게 된다.
  • 따라서 vertical multithreading 과 다르게 여기서는 여러 thread 의 instruction 이 1 cycle 안에 섞인다.
  • 이 방식을 Simultaneous Multithreading (SMT) 라고 한다.
• 이 기술의 intel 식 이름이 많이 들어본 Hyperthreading 이다
• 참고로 DOALL loop 의 경우에는 thread 들이 같은 resource 에 접근하니까 data dependency 로 인한 ILP 수준 저하가 thread 개수를 늘려도 많이 완화되지 않는다.
  • 그래서 SMT 와는 잘 안맞는다고 하네

Homogeneous Multicores §

• 그래서 CPU 의 종류는 위처럼 나눠볼 수 있다고 한다.
  • 저 Functional units + Cache 쌍을 보통 physical core 라고 하고
  • Processor state 는 위에서 말한 context register - logical core
  • 그리고 여기에 shared cache 가 어떻게 되어 있냐에 따라 위처럼 나뉘는 거다.
• 보통 N-core N-thread CPU 는 중간 아래, N-core 2C-thread CPU 가 오른쪽 아래의 형태를 가진다.