Kernel Selection Algorithm, AI Compiler - Low-Level execution Planning

1. 목적 ( Why Kernel Selection Exists)

AI Compiler 에서 커널 선택의 목적은 가장 빠른 커널을 찾는 것이 아니다.

주어진 실행 조건에서 안전하고, 예측 가능하며, 충분히 빠른 커널을 선택하는 것

 

2. 커널 선택의 위치 (Compiler Pipeline)

High-level IR
   ↓
Low-level IR (execution decisions fixed)
   ↓
Kernel Selection   ← 여기
   ↓
Execution Plan
   ↓
Replay / Launch

• 새로운 커널을 설계하는 것이 아닌
• 이미 존재하는 커널 중에서 하나를 결정

 

3. 전체 알고리즘 개요 (High-level Flow)

Input:
  - Op kind
  - Shape / dtype / layout
  - Target device (arch)
  - Execution constraints

Algorithm:
  1. Hard constraint filtering
  2. Priority-based ranking
  3. Optional cost comparison
  4. Final kernel selection
  5. Cache result

 

4. Step 1 - Hard Constraint Filtering (필수)

선택이 아닌 제거

목적

• 실행 불가능한 커널을 완전히 제거

대표적인 제약 조건

• dtype mismatch
• shape range unsupported
• layout incompatibility
• alignment requirement
• architecture mismatch
• workspace / shared memory limit 초과

이 단계 이후 남은 커널이 후보

 

5. Step 2 - Priority-Based Ranking (핵심)

목적

• 경험적으로 더 나은 커널 선택

우선순위는 휴리스틱의 코드화

일반적인 우선순위 기준

• Fused : 여러 op 를 하나로 처리
• Specialized : 특정 shape / arch 전용
• Vectorized : SIMD / TC 활용
• Arch-tuned : 특정 GPU 최적화
• Static-shape : 동적 처리 없음

점수 예시

int score = 0;

if (kernel.is_fused)        score += 100;
if (kernel.is_arch_tuned)  score += 50;
if (kernel.uses_tensorcore)score += 30;
if (kernel.is_generic)     score -= 20;

 

6. Step 3 - Optional Cost Model

언제 필요한지

• 상위 후보 2~3개
• shape 에 따라 성능 역전 가능성

Cost model 의 현실적 기준

• 비교 가능하면 충분

cost = estimated_bytes / bandwidth
     + estimated_flops / compute_throughput;

또는

• occupancy 추정
• shared memory 사용량
• register pressure

정밀 모델은 대부분 필요 없다

 

7. Step 4 - Final Selection

• 가장 높은 score
• 가장 낮은 cost
• 동일하면 deterministic tie-break

 

8. Step 5 - Result Caching

• 커널 선택은 비싸다
• 동일 조건에서 결과는 같음

Cache Key 예시

(op_kind,
 shape_signature,
 dtype,
 layout,
 device_arch)

 

Kernel selection is not an optimization problem, but a constrained decision problem that chooses a safe and efficient execution strategy under fixed conditions