Attribute-State 기반 Online Kernel Selection 설계

1. 배경 및 문제 정의

AST 기반 규칙 매칭이나 단순 op 패턴 탐색은 다음 한계

• op 간 속성 교차 조건이 폭발적 증가
• DAG 구조에서 어디까지 fuse 가능한지에 대한 위치 정보 소실
• 커널 선택 시점이 불분명, 디버깅 / 결정성 저하

속성 기반 추상 상태 AttributeState 를 누적하면서, 구성 중 커널을 확정하는 방식의 사용

 

2. 핵심 개념 개요

2.1 기본 아이디어

• 각 op 는 희소한 속성 행렬 Attribute Matrix 로 추상화된다.
• ops 를 순차적으로 결합하며, 속성 행렬은 row 별 결합 연산을 통해 누적된다.
• 결합이 더 이상 불가능한 시점에서 해당 구간에 대해 커널을 즉시 확정한다.

누적 과정 중 region 이 닫히는 순간마다 순차적으로 선택된다.

 

3. AttributeState 정의 (최소 구조)

AttributeState {
  anchor:   op_id        // fused region 시작점
  last:     op_id        // 현재 region 끝
  attrs:    AttributeMap // 희소 속성 행렬
  candidates: KernelSet  // 가능한 커널 후보 집합
  invalid_reason: string | None
  score_hint: optional cost hint
}

3.1 attrs 속성 행렬

 

• sig: 연산 시그니처 (GEMM, GEMM+BIAS, GEMM+BIAS+RELU 등)
• shape: 텐서 차원 정보
• dtype: input/output/acc dtype
• layout: stride, contiguous, transA/B
• epilogue: bias, scale, activation
• effects: side-effect, alias 가능성
• requirements: alignment, vector width 등

 

모든 op가 모든 row 를 채우지 않으며, 희소 구조로 관리된다.

 

4. Row-wise 결합 의미론

속성 결합은 행별로 서로 다른 연산자를 사용한다.

shape	동일성 검사 / unify
dtype	promotion / compatibility
layout	호환성 검사
sig.linear	지배(dominance)
activation	overwrite 또는 dominance
epilogue flags	OR
effects	sticky propagation

4.1 예시: GEMM + BiasAdd

• linear row: GEMM이 지배 → BiasAdd의 linear 성분 소거
• epilogue.bias: false ⊕ true → true

결과는 GEMM+BIAS 상태로 canonicalize 된다.

4.2 예시: Linear + ReLU

• linearity: linear ⊕ nonlinear → nonlinear
• activation: none ⊕ relu → relu

비선형이 선형을 포함하므로 ReLU가 선택된 상태로 수렴한다.

 

5. 위치 정보: anchor / extent 모델

속성 누적만으로는 “어디까지 fuse 되었는지”를 알 수 없으므로,
행렬의 위치 역할을 다음 두 값으로 명시한다.

• anchor: fused region 시작 op id
• last: 현재까지 포함된 마지막 op id

이 두 값만으로 다음이 가능하다.

• 커널 적용 위치 결정
• region 경계 명확화
• flush 시점 디버깅

 

6. Online Kernel Selection 절차

6.1 기본 루프

1. lowered ops를 순차적으로 순회
2. Compose(state, op) 시도
3. 성공 시:
   • attrs 누적
   • candidates 교집합 갱신
   • last 갱신
4. 실패 시:
   • flush(state) → 커널 1개 확정
   • state = start_new(op)

마지막 op 이후에도 flush(state) 수행

 

6.2 flush 동작

flush는 해당 region에 대해 커널을 1개 확정하는 행위다.

• kid = argmin_cost(state.candidates)
• 실행 계획(plan)에 [anchor..last] → kid 추가
• region 상태 종료

flush 이후 선택된 커널은 되돌리지 않는다 (결정성 확보).

 

7. Kernel 후보 관리 (KernelIndex)

• 모든 커널은 메타데이터로 인덱싱됨
  • 지원 sig
  • dtype/layout 제약
  • epilogue schema
  • alignment 조건
• state.candidates는 누적 과정에서 교집합으로 점점 줄어든다.
• candidates가 empty가 되면 즉시 flush 트리거.

 

8. Flush 트리거 조건

다음 중 하나라도 발생하면 region을 닫는다.

1. 속성 결합 실패
2. candidates empty
3. side-effect barrier 등장
4. region 길이 제한 초과
5. 명시적 sync / join 포인트

 

9. DAG에 대한 처리 전략

• 기본 전제: lowered ops는 이미 선형 스케줄로 정렬됨
• DAG 합류(join) 지점에서는:
  • 기본 구현: best-only state 유지
  • 확장 옵션: k-best (beam) 상태 유지

초기 구현은 k=1을 권장한다.

 

10. 설계의 핵심 성질 요약

• 커널 선택은 online / streaming
• 선택 단위는 region
• 규칙 엔진이 아니라 속성 공간의 자연스러운 수렴
• 위치 정보는 anchor/last로 최소화
• 캡처/리플레이 환경에서 결정성 유지