[Internal/Design] Matrix-based IR Abstraction & Optimization - 최적화 엔진 구현을 위한 행렬 추상화 기반 그래프 리라이팅 ( 복잡한 if-else 분기문을 선형 대수의 연산으로 치환 )

1. 개요 (Philosophy)

그래프를 단순한 리스트가 아닌 위상 정보와 속성 정보가 결합된 행렬 집합으로 취급

이를 통해 패턴 매칭 문제를 행렬의 필터링 및 논리 연산 문제로 치환하여 수학적 엄밀성과 처리 효율을 확보

 

2. 핵심 행렬 정의

2.1 연결 행렬 (Adjacency Matrix, A)

N 개의 op 이 존재할 때, 

• 특성 : DAG 이므로 A 는 적절한 인덱스 정렬 시 하삼각 행렬 형태

 

2.2 속성 / 타입 행렬 (Attribute Matrix, T)

각 Op 의 kind 정보를 나타내는 Sparse 행렬의 정의

• 특정 타입 k 인 Op 들만 선택하는 선택 행렬을 활용

 

3. 수학적 패턴 매칭 (Algebraic Matching)

3.1 Linear Chain 패턴 ( A -> B )

Op i 와 Op j 가 직접 연결된 모든 쌍을 찾는 행렬 M

• M_ij 가 1이면 Op_i, Op_j 는 Fusion 후보가 된다

 

3.2 Multi-step 패턴 (A -> B -> C )

연쇄적인 3개 이상의 Op 를 매칭할 때는 행렬 곱의 결합 법칙을 이용

M_ik = 1 인 지점은 해당 경로가 존재함을 의미

 

4. 알고리즘 워크플로우

• Matrix Construction
• Pattern Filtering
• Conflict Resolution
• Graph Rewrite