Motivations
지난 10년간 DNNs(Deep Neural Networks)은 ML model들 중 가장 중요한 model class로 부상하게 되었다. 그러나 DNNs은 매우 큰 연산량을 지니고 있고 highly parallelizable work들을 요구해 multi and many core processors에 적합하다.
그러한 역할을 GPUs(Graphics Procssing Units)가 현재까지 해오고 있다. 이에따라 GPUs를 이용하여 high-performance programs 작성을 쉽게 도와주는 frameworks도 함께 발전하게 되었다.(e.x CUDA, OpenCL) 하지만 여전히 GPUs의 locality와 parallelism에 대한 최적화는 challenge로 남아있고, 기존 존재하는 optimization primitives들을 결합하여 최적화하기 어렵다. 게다가 GPUs의 architecture는 빠르게 진화하고 있어 최적화된 programs이 더 어렵다.
GPU programming의 어려움을 극복하고자, 여러 systems(e.x Tiramisu, Tensor Comprehensions, Halide, TVM)이 등장했지만 여전히 낮은 유연성을 가지고 있고 cuBlas, cuDNN, TensorRT library 들을 이용한 handwritten compute kernel에 비해 현저히 느리다.
좀 더 실용적인 GPU programming을 위해 Triton은 blocked algorithms에 기반을둔 programming paradigms를 채택했다. 구체적으로 "Single Program, Multiple Data"(SPMD) excution model을 다시 분석하였고, threads가 아닌 bolcked된 programs을 제안한다. 다음은 matirx multiplication에 대한 CUDA programming과 Triton Programming의 차이를 보여준다.
Blocked programming의 key benfit은 block-structured iteration을 한다는 점이다. 이는 sparse operations에 대해 구현할 때 기존 DSLs(Domain-Specific Languages)들 보다 훨씬 유연한 programming을 가능하게 해준다.
Challenges
위에서 제시된 blocked programs 방식의 가장 큰 challenge는 작업 scheduling이다. 즉, 현대 GPUs 에서 효율적으로 실행되기 위해 작업들이 어떻게 partition 되어야 하는지에 대한 문제가 main challenge 이다. 이 문제를 해결하기 위해 Triton compiler는 block-level-data-flow analysis를 많이 이용한다.
- data-flow analysis
data-flow analysis란 program 내에서 data가 어떻게 흘러가는지 분석하는 기법이다. data-flow analysis는 program 내 변수들의 값 또는 그 변수들이 연산되는 방식에 대한 표현 방법들을 tracking 하는 기법 등을 포함한다. compiler는 data-flow analysis의 결과를 가지고 program 최적화를 진행 할 수 있다.
Triton compile는 block-level-data-flow analysis 결과를 이용하여 다양한 optimization 기법을 적용한다.(e.g., automatic coalescing, thread swizzling, pre-fetching, automatic vectorization, tensor core-aware instruction selection, shared memory allocation/synchronization, asynchronous copy scheduling) 물론 이러한 기법을 모두 이용한다고 해서 trivial 한 optimization solution을 얻는 것은 아니다.
Reference
1. Introduction-Triton documentation.
2. Data flow analysis in Compiler.
