안녕하세요, ENERZAi에서 Nadya를 개발하고 있는 김재우입니다. 이전 블로그 게시물에서 Nadya의 타입 추론에 대해 소개드린 바 있는데요.

Optimium 탐구(6) — 정적 타입 언어와 타입 추론안녕하세요? ENERZAi에서 Nadya를 개발하고 있는 은승욱이라고 합니다. 지난 주 글에서 고성능 컴퓨팅을 위한 프로그래밍 언어 Nadya에 대해서 설명드렸는데요. 이번 주에는 Nadya를 설계할 때 고심을…medium.com

오늘은 Nadya 내부의 컴파일러 기술에 대해 소개드리려고 합니다. 오늘 소개드릴 컴파일러 기술은 사용자의 코드를 분석하고 최적화하여 타겟 하드웨어에서 빠르고 효율적으로 실행되는 최적의 결과물을 도출하기 위해 필요한 기술입니다.

Nadya Optimizing Compiler(ndc)

ndc는 에너자이가 자체 개발한 컴파일러로, Nadya 코드를 Binary로 변환하는 역할을 수행합니다. 이 Binary는 단순한 Binary가 아니라, ndc만이 제공할 수 있는 고도로 최적화된 Binary인데요. ndc는 Optimium에서 사용되는 계산 커널을 빠르게 구축하기 위해 필요한 에너자이의 핵심 기술입니다. 뿐만 아니라, ndc 를 활용하면 하드웨어에 대한 깊은 지식이 없는 프로그래머도 빠르고 효율적인 프로그램을 작성할 수 있습니다. 지금부터 ndc가 어떻게 작동하는지 간략히 소개하겠습니다.

Parsing & Lexing

아시다시피, 컴퓨터는 영어 또는 한국어와 같은 인간의 언어를 이해하지 못하며, 0과 1로 구성된 기계어만을 이해할 수 있습니다. 독자분들 중 기계어 코딩을 즐기는 분이 계실지도 모르지만, 대부분의 경우 머리 아픈 기계어 코딩을 선호하지 않을 것입니다.

컴파일러는 사람이 읽을 수 있는 언어로 작성된 코드를 기계어로 번역하여 이러한 문제를 해결하는데요. 첫 번째 단계는 구문 분석 및 Lexing입니다.

Lexer

Lexer는 코드를 ‘토큰’으로 분해합니다. 토큰은 코드 내에서 의미를 가지는 최소 단위의 구성 요소입니다.

예를 들어, 다음과 같은 코드를 작성한다고 가정해 보겠습니다.

let myVar = a + 1

Lexer는 위의 코드를 다음과 같은 토큰으로 분해합니다.

let, myVar, =, a, +, 1

이는 매우 간단한 작업으로 보이지만, 실제로는 동일한 문자가 다른 의미를 가질 수 있기 때문에 문맥에 대한 인식이 필요한 작업입니다. (예를 들어, <는 보통 '작다'를 의미하지만, 구문 cast<i32>(...)에서는 타입 표현의 시작을 의미합니다). 따라서 Parser와 Lexer는 문맥을 인식해야 하며, Nadya에서는 이를 해결하기 위해 두 번의 구문 분석을 수행합니다.

Parser

Parser는 Lexer로부터 토큰을 받아 Abstract syntax tree(AST)로 반환합니다. AST는 프로그램을 정의하는 트리 구조로 코드를 변환합니다. AST의 각 노드는 해당 언어의 의미를 나타내며, 특정 조건에서 프로그램이 어떻게 동작해야 하는지를 정의합니다.

위의 코드를 Nadya에서 정의된 AST로 변환해 보겠습니다.

위 그림에서 확인할 수 있듯이, AST는 프로그램을 실행하는 데 필요한 몇 가지 중요한 정보를 포함하고 있습니다.

1. 프로그램의 구성 요소(Literal, id, 숫자 등)

2. 프로그램 구조

프로그램을 실행하기 위해서는 적절한 순서로 트리를 순회해야 하며, 위 그림에서는 ‘let’ 노드를 실행하기 위해서는 ‘myVar’와 ‘Add’ 노드를 실행한 결과물이 필요합니다.

Operations on AST

Nadya는 몇 가지 특정 변환과 분석 수행에 AST를 활용하는데요. 그중 하나는 타입 추론입니다. 타입 추론은 연산의 결과 타입에 대해 추론하는 작업입니다. 예를 들어, 위의 AST에서 a와 1이 32비트 정수라면, 그 합산 결과도 32비트 정수여야 한다는 것을 추정할 수 있습니다. Nadya는 이 작업을 수행하기 위해 HM (Hindley Milner) 알고리즘에서 영감을 받은 Advanced 알고리즘을 사용합니다. 이 과정에서 Nadya는 템플릿 타입까지 고려하여 모든 표현식의 타입을 추론하고, 타입 Mismatch가 있는지 사용자에게 알려줍니다.

Nadya가 AST에서 수행하는 또 다른 작업은 상수 폴딩(Constant folding)입니다. 상수 폴딩은 런타임 이전 컴파일 타임에 결정되는 값을 미리 계산하여 실행 비용을 줄이는 메커니즘입니다. 예를 들어, 위의 AST에서 컴파일러가 a의 값을 정적으로 결정할 수 있다면, 이 값에 1을 더한 값으로 Add 노드를 대체할 수 있습니다. Nadya는 AST 레벨과 이후 IR(Intermediate Representation)에서 이 작업을 수행합니다. 간단한 작업은 AST를 사용하여 처리하고, 복잡한 작업(분기 및 불필요한 코드 제거)은 IR에서 처리합니다. AST에서 상수 폴딩을 미리 계산하면 AST의 크기가 줄어들고, AST에서 수행되는 다른 분석이나 작업을 더 빠르고 효율적으로 수행할 수 있습니다.

Operations on Intermediate representation

AST가 구성되면, 이를 중간 표현(IR) 형태로 변환할 수 있습니다. IR은 프로그램을 표현하는 기계어와 AST 중간에 위치하는 Layer로, IR generator는 AST를 순회하며 AST의 모든 작업을 보존하는 IR을 생성합니다.

Nadya에서는 프로그램의 전체 구조를 나타내기 위해 다양한 종류의 IR이 활용됩니다.

각 IR은 표현식의 Semantics를 나타냅니다. 예를 들어, Tensor를 더하는 작업은 tensor.add %a, %b : (tensor<i32, 4>, tensor<i32, 4>) -> tensor<i32, 4>와 같은 IR로 표현될 수 있습니다. 이 IR을 받아 컴파일러가 두 Tensor를 어떻게 최적으로 더할 것인 지와 최종적으로 어떻게 어셈블리로 변환할 지를 결정해야 합니다.

이러한 목적을 달성하기 위해 Nadya는 IR을 사용하여 복잡한 최적화 과정을 수행하는데요. 이러한 최적화 과정은 여러 단계를 거쳐 진행됩니다. 예를 들어, Loop가 병렬화될 수 있는지 여부를 High-level context를 이용하여 결정할 수 있는 반면, 특정 코드를 실행할 올바른 하드웨어 내장 함수를 선택하는 것은 Low-level context를 활용합니다.

따라서 Nadya는 다양한 최적화를 처리하기 위해 MLIR 기반의 다양한 IR을 사용하는데요. 저희는 Nadya에 사용되는 이러한 IR들을 Dialect라고 부릅니다. 아래에 저희가 사용하는 대표적인 Dialect와 해당 Dialect에서 수행되는 최적화 작업들을 정리하였으니 참고 부탁 드립니다.

High-level dialects

1. NadyaCore dialect

• Nadya 프로그래밍 모델의 Ownership semantics에 대한 모델링

• Pattern matching 및 Union 타입에 대한 모델링

• 사용자 정의 타입 연산에 대한 모델링

• L-value to R-value 포워딩

• Mem2Reg(메모리 Load/Store 작업을 SSA value로 포워딩)

2. NadyaFunc dialect

• Function call, symbol 및 closure에 대한 모델링

• Inlining 최적화

3. NadyaSCF dialect

• 프로그램 제어 흐름에 대한 모델링

• Paralleism 및 Unroll에 대한 분석

• if/else 연산 단순화에 대한 분석

• Loop Invariant Code Motion(LICM)

4. NadyaAST dialect

• Nadya의 AST 구성 요소에 대한 모델링

Mid-level dialects

1. NadyaArith dialects

• Nadya에서 수행되는 산술 연산에 대한 모델링

• Optimization on arithmetic

• Vectorization

2. NadyaTensor dialects

• Tensor 연산에 대한 모델링

• Tensor 메모리 연산 최적화

Low-level dialects

1. NadyaBase dialects

• Pointers, indirect calls, struct access에 대한 모델링

2. NadyaNeon dialects

• ARM Neon 내장 함수 포워딩에 대한 모델링

각 Dialect는 특정 계층에 위치하며, 각기 다른 목적을 수행합니다. 각 Dialect는 특정 분석 및 변환 작업을 수행하기 위해 서로 상호작용할 수 있지만, 기본적인 역할은 서로 구분됩니다.

기본적으로, ndc는 High-level dialect로 작성된 연산들을 Low-level dialect로 변환합니다. 또한, 자체적으로 다른 종류의 Dialect로 변환하지 않고 업데이트할 수도 있습니다. 그러나 Low-level dialect에서 High-level dialect로의 변환은 수행할 수 없습니다(이러한 이유로 각 Dialect가 특정 ‘계층’에 위치한다고 표현하였습니다).

아래 코드는 AST에서 직접 변환된 IR로, 프로그램의 Semantics는 그대로 유지되는 것을 확인하실 수 있습니다.

%24 = nadyaTensor.constructRange %arg5, %23, %c1_i32_26 : (i32, i32, i32) -> !nadyaTensor.range<i32> loc(#loc37)
%25 = nadyaTensor.load %0[%arg2, %24] : (!nadyaTensor.tensor<f32,(-1, -1)>, <i32, !nadyaTensor.range<i32>>) -> !nadyaTensor.tensor<f32,(-1)> loc(#loc38)
%26 = nadyaArith.addTensor %19, %25 : (!nadyaTensor.tensor<f32,(-1)>, !nadyaTensor.tensor<f32,(-1)>) -> !nadyaTensor.tensor<f32,(-1)> loc(#loc33)
nadyaTensor.store %26, %arg6[%arg2, %12] : (!nadyaTensor.tensor<f32,(-1)>, !nadyaTensor.tensor<f32,(-1, -1)>, <i32, !nadyaTensor.range<i32>>) loc(#loc29)

벡터화 및 Shape inference 수행 후, 위의 IR은 아래와 같이 해석할 수 있습니다.

%19 = nadyaTensor.constructRange %arg5, %18, %c1_i32 : (i32, i32, i32) -> !nadyaTensor.range<i32>
%20 = nadyaTensor.load %0[%arg2, %19] : (!nadyaTensor.tensor<f32,(4096, 64)>, <i32, !nadyaTensor.range<i32>>) -> !nadyaTensor.tensor<f32,(1),vector>
%21 = nadyaArith.addTensor %15, %20 : (!nadyaTensor.tensor<f32,(-1)>, !nadyaTensor.tensor<f32,(1),vector>) -> !nadyaTensor.tensor<f32,(-1)>
nadyaTensor.store %21, %arg6[%arg2, %10] : (!nadyaTensor.tensor<f32,(-1)>, !nadyaTensor.tensor<f32,(4096, 64)>, <i32, !nadyaTensor.range<i32>>)

위의 코드에서 몇몇 -1이 실제 숫자로 변환된 것을 볼 수 있는데요. 이는 컴파일러에서 수행한 상수 전파(Constant propagation) 및 자동 Shape inference의 결과물이라고 볼 수 있습니다. 즉, 컴파일러는 프로그램의 deterministic한 값을 미리 계산하고, 프로그램에서 사용되고 있는 Tensor의 shape를 추론합니다.

뿐만 아니라, ndc는 프로그램에 숨겨져 있는 벡터화 기회를 발굴할 수 있습니다. 위의 코드에서 끝에 벡터가 붙은 Tensor를 확인할 수 있는데, 이는 해당 Tensor에 대한 연산이 부작용 없이 SIMD 내장 함수로 수행될 수 있음을 의미합니다.

한 단계 더 나아가면, IR은 아래와 같이 변환됩니다.

nadyaSCF.for %arg4 from %c0_5 to %40 step %c1_6 {
  %52 = arith.andi %arg4, %42 : index
  %53 = arith.andi %arg4, %44 : index
  %54 = arith.addi %arg4, %c1_6 : index
  %55 = arith.addi %52, %c1_6 : index
  %56 = arith.addi %53, %c1_6 : index
  %57 = nadyaTensor.constructRange %52, %55, %c1_6 : (index, index, index) -> !nadyaTensor.range<index>
  %58 = nadyaTensor.constructRange %53, %56, %c1_6 : (index, index, index) -> !nadyaTensor.range<index>
  %59 = nadyaTensor.constructRange %arg4, %54, %c1_6 : (index, index, index) -> !nadyaTensor.range<index>
  %60 = nadyaTensor.load %24[%57] : (!nadyaTensor.tensor<f32,(-1)>, <!nadyaTensor.range<index>>) -> !nadyaTensor.tensor<f32,(1),vector>
  %61 = nadyaArith.addTensor %60, %31 : (!nadyaTensor.tensor<f32,(1),vector>, !nadyaTensor.tensor<f32,(1),vector>) -> !nadyaTensor.tensor<f32,(1),vector>
  nadyaTensor.store %61, %36[%59] : (!nadyaTensor.tensor<f32,(1),vector>, !nadyaTensor.tensor<f32,(-1)>, <!nadyaTensor.range<index>>)
} {parallel = false}

이제 컴파일러가 Loop를 생성한 것을 확인하실 수 있습니다. 이 Loop에서는 컴파일러가 메모리에서 Index 기반으로 Element들에 접근하여 연산을 수행합니다. 타입에 벡터가 붙은 Tensor의 경우, 해당 연산은 SIMD로 처리할 수 있습니다. 다만 Tensor의 크기가 1일 경우, 일반 덧셈 연산으로 처리되며, 크기가 1보다 크면 AVX나 Neon과 같은 SIMD 연산으로 처리됩니다.

이제 몇 가지 추가 최적화를 거치면 이 IR은 LLVM으로 변환될 수 있습니다.

구체적으로는 MLIR을 사용한 Progressive lowering 작업을 수행한 후, 최종적으로 LLVM IR로 변환되는데요. 이는 LLVM 프로젝트에서 결정된 또 다른 중간 표현입니다.

아래 코드는 위 Loop의 Body 부분을 LLVM으로 표현한 것입니다.

^bb9:  // pred: ^bb8
  %84 = llvm.and %82, %81  : i64
  %85 = llvm.getelementptr %45[%84] : (!llvm.ptr, i64) -> !llvm.ptr, f32
  %86 = llvm.load %85 : !llvm.ptr -> f32
  %87 = llvm.mlir.undef : vector<1xf32>
  %88 = llvm.mlir.constant(0 : i32) : i32
  %89 = llvm.insertelement %86, %87[%88 : i32] : vector<1xf32>
  %90 = llvm.shufflevector %89, %87 [0] : vector<1xf32> 
  %91 = llvm.fadd %90, %69  {fastmathFlags = #llvm.fastmath<contract>} : vector<1xf32>
  %92 = llvm.mlir.constant(0 : i64) : i64
  %93 = llvm.extractelement %91[%92 : i64] : vector<1xf32>
  %94 = llvm.getelementptr %73[%82] : (!llvm.ptr, i64) -> !llvm.ptr, f32
  llvm.store %93, %94 : f32, !llvm.ptr
  %95 = llvm.add %82, %4  : i64
  llvm.br ^bb8(%95 : i64)

LLVM 또한 앞서 소개 드린 방법들 기반으로 올바른 Output을 도출하는 것을 확인할 수 있습니다.

이 LLVM IR은 LLVM의 내부 최적화 프로세스(Clang -O3에서 지원하는 최적화)를 거친 뒤 Binary로 변환될 수 있으며, 이는 ndc의 최종 Output이 됩니다!

Nadya 언어는 컴파일러 분석을 용이하게 하는 고유한 Semantics를 보유하고 있으며, 이러한 강점은 Nadya 맞춤형으로 제작된 IR을 통해 극대화되는데요. Nadya가 목표로 하는 빠르고 효율적인 코드의 생성은 Nadya의 고유한 Semantics, IR, 최적화 기법들의 시너지를 통해 실현된다고 말씀드릴 수 있습니다.

오늘은 Nadya가 어떻게 최적의 결과물을 도출할 수 있는 지 개괄적인 구조를 설명드렸습니다. 앞으로도 블로그를 통해 다양한 최적화 기법이나 MLIR 등의 관련 개념들을 소개드리려고 하니 많은 관심 부탁 드립니다. Stay tuned!

그리고 현재 Nadya를 같이 만들어 나갈 분을 모집 중이니 많은 관심 부탁 드립니다!

AI 컴파일러 엔지니어에너자이의 채용공고를 확인해 보세요.enerzai.career.greetinghr.com