AI Compiler의 의미론적 최적화 구조 분석 - Rule_based Graph Rewrite vs RFM Algebraic Approach

1. AI Compiler 의 실제 계층 구조

TensorRT, TVM, OpenXLA / XLA, PyTorch Inductor 는 보통 다음 4 계층으로 구성된다.

 

Layer 0 - Frontend IR 생성

• 모델 - Graph IR
• 노드 = 연산
• 엣지 = 텐서 흐름

여기까지는 의미 해석 없음, 그냥 구조화

 

Layer 1 - Canonicalization (정규화 패스)

그래프를 일관된 형태로 바꾸기

• Add(x, 0) -> x
• Mul(x, 1) -> x
• Conv _ Bias -> BiasFoldConv

이 단계는 이미 의미론적 판단, 수학적으로 동치인지 확인 후 구조를 바꿈

 

Layer2 - Pattern-based Rewrite / Fusion

기존 방식의 특징

• 패턴은 규칙 목록으로 정의됨
• Subgraph matcher 가 그래프를 순회
• 매칭되면 rewrite 수행
• legality 는 조건문으로 검사

구조는 규칙 기반 + 명시적 조건 검사

 

2. 기존 의미론적 접근의 본질

의미를 명시적 규칙으로 표현한다.

의미는 존재하지만, 수학적 공간으로 승격되진 않음

 

3. Rich Feature Matrix 접근의 구조

핵심 구성

• Binary Adjacency Matrix - 연결 구조
• Rich Feature Matrix - 노드의 의미 벡터
• Bitmask / Metadata Enxoding - 제약 조건
• Algevraic 탐색 - 패턴 감지

 

4. 핵심 차이점

1) 의미 표현 방식

기존

• Op 이름 중심
• enum 기반
• 속성은 attribute dict

RFM

• 의미른 feature vector 정규화
• dtype, layout, side-effect, memory pattern 등을 벡터화
• lagality 판단을 bit 연산으로 환원

의미가 데이터 구조가 아니라 선형 공간의 좌표가 된다.

 

2) 패턴 탐색 방식

기존

• DFS / BFS 기반 subgraph matcher
• rule 하나씩 검사

RFM

• 행렬 곱으로 k-hop 경로 탐지
• 특정 의미 필터를 projection 연산으로 계산

그래프 탐색을 선형대수 연산으로 환원

그래프 탐색기가 아닌 대수 계산기로 바꾸기

 

3) Lagality 검사 방식

기존

if dtype == ...
if layout == ...
if no alias ...

RFM

legal_mask = feature_i & feature_j & compatibility_mask

Bitwise 연산 한 번으로 legality 판정

명시적 조건 분기 대신 연산적 판정

 

4) Rewrite 결정 방식

기존

• rule triggered -> rewrite

RFM

• 후보 집합 생성
• profit score 계산
• score 기반 정렬 후 rewrite

즉 rewrite 가 탐색 결과의 함수가 된다.

 

5. 이론적 관점 차이

의미	규칙 기반	벡터 공간
탐색	그래프 순회	행렬 연산
합성 가능성	명시적 정의	연산으로 판정
확장성	rule 추가	feature 확장
일반화	낮음	높음

 

6. 기존 접근의 한계

• Rule explosion
  • 패턴 수 증가 - rule 수 증가
• 일반화 부족
  • 새로운 연산 추가 시 rewrite rule 재작성 필요
• 의미 조합의 폐쇄성 부족
  • 조합 가능성이 명시적으로 정의되어야 함