GPGPU

일하면서 알게 된 여러가지 병렬프로그래밍 언어들 정리

Highlevel: DPC++(sycl), OpenMP, thrust

써본적없어서 뇌피셜임. Parallelize가능한 몇가지 고차함수구조와 메모리관리를 OpenCL을 사용해 구현한걸 제공하는것으로 알고있다. 태생적으로 빡센 최적화는 불가능해 보임.Host단에서만 코딩하는 느낌을 받을듯.

Middle-level: OpenCL, CUDA, Metal(아마도?), GLSL, HLSL

여기부터는 Host단 코드와 Kernel단 코드를 둘 다 짜는 느낌을 받는다. Host단에서는 Kernel컴파일&실행하고, Kernel단에서는 실제적인 병렬연산을 Global Workgroup id라는거로 자신의 인덱스에 따라 처리한다. 항상 이러한 Massive-Parallel한 계산기는 어떻게 synchronize하는지, lock같은게 있는건가? 싶었는데 lock이 비용이 비싸서 그냥 아예 제공을 안한다고 한다. 인덱스별로 처리하는 각각을 work-item이라 한다. global workgroup은 전체 work-item의 합집합을 의미하고, 그 약수(약벡터?)크기를 가질 수 있는 local workgroup이란게 있어서 그 내부에서는 work-item끼리 제한적으로 synchronize하는 방법으로 barrier를 제공한다.(배리어를 호출하면 local workgroup내부의 모든 work-item이 그 지점까지 실행할때까지 기다리게 된다. 이후 모두 모이면 진행). 이 local workgroup은 하나의 subslice내에서만 할당될 수 있으며, 이는 보통 말하는 core들을 합쳐놓은 단위다. 내가 공부하고있는 Intel GPU는 코어를 Execution Unit이라고해서 1subslice=8EU인 구조이다. 물론 인텔내장그래픽은 1코어당 7스레드 동시실행?(work-item들을 SIMD로 묶어처리한다는듯?)을 할 수 있으므로 Local Workgroup Size(=대략 subslice의 코어개수*코어당 동시실행가능한 스레드)(이하 LWS)가 56사이즈정도까진 지원되는것으로 알고있다. 안타깝게도 local workgroup외부로는 sync가 불가능하다(유일한 예외: 호스트에서 전체계산 wait하는것). 이러한 제약사항을 볼 때, CPU에서는 가능한 복잡한 sync들이 필요한 로직은 GPU로는 불가능한것 같다. GPU에선 Task Parallel은 힘들고 Data Parallel만 가능하다 라고 표현할 수 있을듯.

Low-level( HW assembly(V-Tune으로 볼 수 있다는듯?), Spir-V )

아무튼 OpenCL도 컴파일과정(호스트프로그램에서 런타임에 드라이버로 코드 보내서 컴파일. JIT방식?)이 있기때문에 뭔가 더 로우한 명령어가 있을테고, 정확한 명칭은 모르겠어서 일단 HW assem이라고 적었다. HW assembly의 경우 gpu별로 다르지 않나 추측하고 있다. 일하다보면 가끔 V-Tune으로 열어볼일이 생긴다는듯. Spir-V의 경우 기계어와 1:1되는 어셈블리는 아닌데 HW-independant한 interpret어셈블리같은 느낌인듯. 사이트에서 소개도 성능을 포기하지 않는다?는 설명이 있던거같은데 약간 JAVA의 JVM bytecode를 표방하는 느낌이다.

GPGPU로 효율적인것과 비효율적인것

Middle-level에서 잠깐 나왔지만 GPU가 FLOPS가 높다고 해서 모든계산이 효율적인게 아니다. Data Parallel하다는건 계산에 사용되는 data가 서로 상호작용하지 않는다는의미로, 많은 유용한 연산들이 Data Parallel하지만 어떤 연산들은 그렇지 못하다. 다음 두가지 예시를 보자.

분할정복) Matrix Multiplication(Strassen), Convolution(FFT) 이 두가지 연산은 머신러닝을 공부해봤다면 모를수가 없는 연산이다. 그리고 그 두 핵심적인 연산을 분할정복으로 효과적으로 구하는 알고리즘이 존재하며, 분할정복은 data parallel하기 때문에(재귀적으로 쪼개졌을때 이후의 계산은 상호배제적이다) 머신러닝에서 GPU를 통한 연산속도향상이 가능한 것이다. 퀵소트, 머지소트, map&reduce같은것들도 좋은 예시이다. 의존성그래프를 그려보면 Tree형태가 나오며, 이때문에 한 step에서 데이터를 계산한 이후에는 다시 데이터를 가지고 있을 필요없이 discard할 수 있다는게 중요하다. 이러한 Data Parallelism은 OpenCL의 LWS+barrier구조로 계산할 수 있는것 같은데, 그 이유는 엄청 큰 데이터를 한번에 재귀적으로 분할정복하는건 메모리문제가 있지만, 이걸 트리로 보면 아래리프들에서부터 한스텝씩 위로 스위핑하듯이 단계별로 블록을 나누어 처리해줄 수 있는것이다. 그래서 전체문제가 크지 않아 LWS내에 들어간다면 barrier로 스텝별로 sync해주면 되고, LWS를 넘어도 그냥 호스트에서 한스텝씩 실행해서(이때의 커널내부는 barrier 필요없이 한스텝만 작업하면 되겠다) sync해주고를 끝날때까지 반복하면 되는것이다.

아래에는 Data Parallel이 아닌 바로 떠오르는 예시가 없어서 일단 DP로 적어봤는데 별로 좋은예시는 아닌듯. 아래 설명할거는 Multicore Computing이자 GPU의 한계이지 Distributive Computing은 DP도 충분히 유연하게 병렬화할 수 있을것 같고, DP도 toposort순서대로 몇번 host-gpu 왔다갔다하는 계산루프 돌려주면 분할정복처럼 배리어없이 호스트의 sync만으로 계산할 수 있긴 하니까(효율적인지는 글쎄? 분할정복의 경우 데이터크기에 log스텝임이 보장되지만 dp의경우 step이 데이터크기에 linear한 케이스가 있으므로 총 N^2이 되서 차라리 sequential계산이 빠른 경우가 있을수도?). 아무튼 Task Parallel한 작업에 대해서는 GPU도 1subslice밖에 사용할 수 없기 때문에 뭐 요즘 1만쿠다코어 뭐 이런거 나오던데 그런걸 다 활용 못하기 때문에, 복잡한 sync로직이 필요한 작업은 CPU가 더 잘한다는게 요지이다. GPU는 기본클럭도 CPU에 비교할게 못되고, 동기화방법도 제한적이기 때문. 다만, Data Parallel이란 제약을 박고 시작하기 때문에, 스레드를 자체적으로 효율적으로 풀링하고 SIMD화하고 하는거로 알고있다. 실제 실험해본결과도 스레드 많으나 적으나 오버헤드가 그냥 없는수준이었다.

동적계획법) 부분문제에서 다른 부분문제의 결과값을 참조한다. 이때 재귀적으로 쪼개진 서로다른 두 부분이 같은 subproblem의 결과값을 참조할 수 있고, 이때문에 의존성그래프가 Directed Acyclic Graph의 형태를 띄게 된다. 이는 트리보다 general한 형태이며, 트리가 아니기 때문에 data가 어느step까지 사용될지 미리 알 수 없다. topological sorting을 하면 직선형태로 순서를 줄 수 있긴 한데, 어떤 데이터는 계산이후 바로 discard 가능하고 어떤건 좀 오래 들고있어야하고, 이런 조건이 붙게 되서 병렬화한다면 DAG의 mincut이나 뭐 이런 비슷한 개념의 width제한이 있을거같고 무엇보다 이는 OpenCL의 계산모델과 맞지 않다. 의존성이 LWS보다 작다면 위상정렬해서 번호매겨 풀 수도 있을것 같은데, 그보다 의존성이 큰게 존재하는 DP라면 LWS를 넘어가기 때문에 sync를 할 수 없어서 의존성을 표현못하므로 망한다.

잡담) 위에서 위상정렬시 의존성의 최대거리를 최소화하는 문제는 효율적으로 풀 수 있을까? 뭔가 알고리즘문제로 접해본적은 없는게 not P느낌이 나긴하는데 궁금하긴 하다. https://cstheory.stackexchange.com/questions/36230/ordering-of-a-dag-minimizing-some-definition-of-cost https://arxiv.org/pdf/1109.4910.pdf#page=1 NP-complete라는 내용을 찾을 수 있었다. Width Parameters of Graphs, Treewidth라고 표현하는듯?