AICF / MCIR 에서 패턴의 새로운 정의

1. 문제 의식

기존 컴파일러에서 패턴은 대체로 표면적으로 반복되는 구조를 뜻한다.

• matmul - add -relu
• conv - batchnorm - activation
• 특정 shape / layout 조합
• 특정 memory access 형태
• 특정 fusion 가능 subgraph

이런 패턴은 강력함

하지만 이는 주어진 표현 위에서 반복되는 모양을 찾음

즉, 패턴의 기준이 형태에 있다.

 

문제는 실제 최적화의 핵심이 항상 형태에 있지 않다는 것

따라서 

무엇을 패턴으로 볼 것인가를 다시 ㅣ정의해야 한다.

 

2. 기존 패턴 정의의 한계

기존 패턴 시스템은 보통 다음 전제를 깔고 있다.

• operator 가 기본 단위
• graph substructure 가 패턴의 주 대상
• memory 는 lowering 이후에 다룬다
• legality 는 shape / type / dependency 중심으로 판단
• 최적화는 주어진 표현 위에서의 rewrite 문제

이 정의는 실용적이지만 한계가 존재

2.1 표면이 다르면 같은 구조를 놓친다

두 계산이 전혀 다른 op chain 처럼 보여도 실제로는 둘 다

• online reducible
• partial summary mergeable
• tile-local completion 가능
• rematerializable

할 수 있다면, 이 둘은 같은 종류의 realization logic 으로 다뤄야 한다.

기존 패턴 시스템은 이를 포착하지 못한다.

 

2.2 표면이 비슷해도 legality 가 다를 수 있다.

겉으로 비슷한 reduction chain 이라도

• 하나는 associative summary 를 가진다
• 다른 하나는 global normalization state 가 필요

면 둘은 같은 패턴이 아니다.

즉 structural similarity 가 semantic equivalence 를 보장하지 않음

 

2.3 memory 와 execution realizability 를 부차화한다

기존 시스템은 memory 를 보통 결과적으로 발생하는 배치 문제로 다룬다.

하지만 실제로는

• 어떤 계산이 streaming 으로 실현 가능한가
• 어떤 intermediate 가 metarialization 없이 가능한가
• 어떤 partition 이 legality 를 보존하는가

가 계산 구조 자체를 결정한다.

즉 realzability 는 후처리 문제가 아니라 계산의 구성 조건

 

3. 2층에서의 패턴 : 새로운 정의

패턴은 더 이상 단순ㄴ한 구조 반복이 아니다.

기존 정의

Pattern = 반복되는 구조적 형태

새로운 정의

Pattern = 반복해서 등장하는 semantic contract 와 realizability property 의 조합

즉 

무엇이 어떻게 생겼는가가 아니라

무엇이 어떤 의미 조건 아래, 어떤 방식으로 실현 가능한가를 묻는다.

여기서 패턴은 다음을 포함한다

• 무엇이 보존되어야 하는가
• 어떤 재배열이 합법적인가
• 어떤 부분 계산이 충분 요약이 되는가
• 어느 수준까지 local completion 이 가능한가
• materialization 없이 다음 단계로 넘어갈 수 있는가
• exact equality 대신 어떤 bouned equivalence 가 허용되는가

따라서 2층의 패턴은

syntax pattern 이 아니라 legality-bearing semantic pattern 이다.

 

4. 패턴화 대상의 전이

2층에서는 패턴화 대상 자체가 바뀐다.

4.1 기존 패턴화 대상

• op 종류
• graph topology
• tensor shape
• layout tag
• access order

 

4.2 새로운 패턴화 대상

• preserve 해야 하는 invariant
• partial summary 의 merge law
• online progrssion 가능성
• tile-local completion 가능성
• reconstructability / rematerializability
• bounded numeric equivalence
• redorderable - under - condition 구조

형태적 반복에서

의미 실현 가능성 구조의 반복으로 이동한다.

 

5.  2층에서 패턴의 최소 원자

2층의 핵심은 단지 새로운 패턴 몇 개를 추가하는 것이 아니다.

더 중요한 것은 패턴을 구성하는 최소 원자가 바뀐다는 점

기존 원자는 보통 다음과 같다

• OpKind
• edge relation
• shape match
• layout property

하지만 2층에서는 다음과 같은 원자가 더 본질적

• preserve
• mergeable
• streamable
• reconstructable
• bounded_equiv
• tile_localiable
• reorderable

중요한 것은 단순 태그가 아닌

변환 legality 와 realizability 를 생성하는 단위라는 점

 

6, 패턴은 변환 후보가 아니라 존재론적 분류

이 계산은 본질적으로 어떤 종류의 계산인가?

변환 이전에

계산 분류 체계를 구성한다.

attentino 을 단순히

• QK^T
• scale
• mask
• softmax
• matmul

의 op chain 으로 볼 수도 있지만,

2층에서는 이를 다음처럼 다시 볼 수 있어야 한다.

• online normalized weighted reduction
• mergeable summary computation
• blockwise stream-realizable process
• bounded-state transition structure

계산 단위의 분류 기준 자체의 변환

 

7. 목록이 아닌 생성 문법이어야 한다

패턴 사전만 늘리는 것이 아님

중요한 것은 개별 사례보다 그 사례들을 낳는 상위 구조이기 때문

필요한 것은 다음 둘 중 하나

• semantic pattern grammer
• property composition algebra

패턴이 열거되는 것이 아닌 생성

예를 들어

• marge law + bounded summary + progressive update
  • online reducible class
• reconstructable + bounded sorking set
  • rematerialization - admissible class
• order-insensitive law + bounded drift contract
  • reorderable numeric class
• local completion + merge-safe boundary
  • tile-local realizable class

flash attention 패턴 같은 이름이 아닌

그 패턴을 가능하게 하는 구조 조합을 이해하게 되낟.

 

8. 패턴의 판정 방식

8.1 Core semantic law

계산 정의 자체에 붙는 법칙

• associative merge
• summary sufficiency
• reconstructable state relation 

 

8.2 Derived property

분석을 통해 추론되는 성질

• stream realizable
• tile-localizable
• rematerializable

 

8.3 Equivalence constract

동치 판단을 위한 기준

• exact equivalence
• bounded-drift equivalence
• order-insensitive equivalence

 

8.4 Policy / cost constraint

현재 환경에서 어떤 realization 이 바람직한지 정하는 조건

• memory budget
• latency preference
• recompute vs store preference
• numeric drift budget