연산 의미 명세와 불변성 기반 실행 구조 분석 방법론

1. 연구 방향의 확장

현재 연구는 CUDA 커널이 어떤 SASS 명령으로 변환되는지를 롹인하는 단계에서 출발,

SASS 는 수학적으로 정의된 연산이 실제 NVIDIA GPU 에서 실행되는 가장 구체적인 표현 중 하나이지만,연산의 전체 의미를 보존하는 표현은 아니다.

고수준 연산이 SASS 까지 lowering 되는 동안 tensor shape, reduction axis, 연산자 이름, 그래프 상의 역할고 ㅏ같은 정보는 상당 부분 사라진다

연구의 근본적인 질문은 다음과 같다

수학적으로 정의된 연산은 여러 표현 계층을 거치며 어떤 실행 구조로 변환되는가?

 

2. 수학적 기초를 다시 정의해야 하는 이유

SASS 에서 관찰되는 구조는 다음과 같은 서로 다른 원인에 의해 만들어질 수 있다.

1. 수학적 정의상 반드시 필요한 구조
2. 선택한 알고리즘에 의해 발생한 구조
3. 특정 CUDA kernel 구현 때문에 발생한 구조
4. 컴파일러가 선택한 lowering 방식
5. GPU architecture 의 제약
6. 제거하거나 변경할 수 있는 구현상의 비효율

SASS 에서 발견되는 max reduction 은 Softmax 의 본래 정의가 직접 강제한 구조가 아니다.

이는 Softamx 의 대수적 불변성을 이용해 선택한 안정적인 알고리즘이 만든 실행 구조

이 차이를 구분해야 한다

• 어떤 명령과 reduction 이 반드시 필요한가
• 어떤 단계는 다른 알고리즘으로 대체할 수 있는가
• 어떤 중간값은 제거할 수 있는가
• 어떤 연산 순서는 변경 가능한가
• 어떤 차이는 단순한 compiler lowering 의 결과인가

SASS 또는 특정 IR 을 분석하기 전에 각 연산의 의미, 불변성, 변환 자유도를 명확하게 정의해야 한다.

 

3. 연구에서 필요한 수학적 기초의 범위

필요한 것은 각 연산을 최적화와 lowering 관점에서 해석하는 데 필요한 최소한의 수학적 의미

각 연산에 대해 세 가지 질문에 답할 수 있어야 한다

• 무엇을 계산하는가
• 무엇이 반드시 보존되어야 하는가
• 무엇은 변경할 수 있는가

 

4. 연산의 의미를 구성하는 기본 요소

4.1 입력과 출력

먼저 연산이 어떤 입력을 받고 어떤 출력을 생성하는지 정의해야 한다.

 

4.2 데이터 의존성

데이터 의존성은 수학적 의미와 실행 구조를 연결하는 가장 중요한 요소

표현 계층이 연산 그래프, loop, MLIR, PTX, SASS 중 무엇이든 이 의존 관계 자체는 유지되어야 한다.

 

4.3 연산 domain

연산이 어느 원소 집합에 적용되는지 정의해야 한다.

특히 reduction 에서는 연산자뿐 아니라 reduction domain 이 의미의 핵심이다.

 

4.4 관측 가능한 값

연산 내부의 모든 중간값이 외부에서 관측되는 것은 아니다.

관측 가능성은 materialization 제거와 fusion 가능성을 판단하는 직접적인 기준이다.

 

5. 불변성의 분류

5.1 의미 불변성

구현과 표현이 달라져도 반드시 유지해야 하는 연산의 본래 의미.

이 조건은 CUDA kernel, MLIR, PTX, SASS 중 어떤 계층에서도 유지되어야 한다.

 

5.2 대수적 불변성

연산의 표현을 변경해도 수학적 결과가 유지되는 성질

이러한 성질은 연산 순서 변경, parallel reduction, 상태 기반 갱신과 algebraic simplification 의 근거가 됨

 

5.3 구조적 불변성

표현 방식이 달라져도 유지되는 계산 구조

이 구조는 SASS 보다 높고 낮은 순서에서도 추적할 수 있다. 

예로 softmax 는 다음 구조는 유지된다

• 여러 입력에 대한 집계
• 공통 정규화 상태
• 여러 출력에서 사용

 

5.4 통계적 불변성

확률과 nomalization 연산에서는 통계적 성질도 보존 조건이 된다. 

이러한 성질은 저정밀도, 근사 exponential, approximate reciprocal 을 사용하는 구현의 정확성을 검증하는 기준이 된다.

 

5.5 순서 불변성과 순열 등가성

일부 연산은 입력 원소의 순서를 바꾸면 출력도 동일한 방식으로 재배치된다. 

각 연산에서 순서가 의미의 일부인지, 단순한 저장 배치인지 구분해야 한다.

 

5.6 수치적 불변성과 허용 오차

각 최적화 실험에서는 어느 수준의 동등성을 목표로 하는지 명시해야 한다.

 

6. 변환 자유도

불변성이 반드시 보존해야 할 조건이라면, 변환 자유도는 의미를 유지하면서 변경할 수 있는 부분이다.

6.1 연산 순서 변경

데이터 의존성이 없는 연산은 순서를 변경하거나 병렬로 실행할 수 있다.

 

6.2 Reduction tree 변경

Reduction 연산자가 결합 가능하다면 순차적인 reduction 을 tree 형태로 변경 가능

이 변환은 warp reduction 과 block reduction 의 수학적 근거가 된다.

 

6.3 Materialization 제거

중간값이 외부에서 관측되지 않고 producer 와 consumer 가 같은 실행 범위에서 처리될 수 있다면 global memory 저장을 제거 가능

 

6.4 재계산과 저장의 교환

중간값을 저장하는 대신 필요할 때 다시 계산할 수 있다.

다양한 판단 기준의 존재

• 계산 비용
• memory traffic
• register 사용량
• 중간값 lifetime
• consumer 수
• cache locality

 

6.5 Online 또는 streaming 변환

연산을 부분 상태로 표현할 수 있다면 전체 입력을 materialize 한 후 처리하지 않고, 입력을 순차적, tile 단위로 소비 가능하다

 

6.6 Memory hierarchy 변경

값의 수학적 의미는 유지한 채 저장 위치를 변경할 수 있다.

실행 스케줄과 하드웨어 자원에 관한 자유도

 

6.7 정밀도 변경

FP32, FP16, BF16, ...

허용 오차 전제 하 

 

7. 의미적 primitive

반복적 등장 기본 의미 단위 정의

7.1 Elementwise map

• 출력 원소 사이 의존성 없음
• 다른 elementwise 연산과 fusion 하기 쉬움
• tread-level parallelism 이 자연스러움

 

7.2 Affine transform

• multiplication 과 addition 의 결합
• FMA 가능성
• epilogue fusion 가능성
• scale 과 bias 의 재사용

 

7.3 Reduction

• reduction domain
• 연산자
• 항등원
• 결합성
• 교환성
• 순서 민감도
• partial result merge 가능성

 

7.4 Broadcast

• 공통값 재사용
• thread 간 전달
• register, shuffle, shared memory 선택
• reduction 결과와 자주 결합됨

 

7.5 Scan 과 recurrence

• 상태 의존성
• 순차적 구조
• associative scan 으로 변환 가능 여부
• online algorithm 과 연결

 

7.6 Matrix contraction

• multiplication 과 reduction 의 결합
• tile reuse
• register blocking
• shared memory staging
• accumulator lifetime

 

7.7 Normalization

• reduction
• broadcast
• elementwise transform
• 공통 통계값 재사용
• 수치 안정성

 

7.8 Selection

• comparison
• predicate
• branch 또는 bracnhless lowering
• divergence 가능성

 

7.9 Layout transformation

..

8. 연산 의미 명세의 표준 형식

각 연산은 다음 공통 목차로 작성한다.

1. 연산 개요

연산이 해결하는 문제와 모델에서 맡는 역할을 설명한다.

2. 수학적 정의

입력, 출력, 수식, axis와 parameter를 정의한다.

3. 입력·출력 domain

• shape
• dtype
• reduction axis
• parameter
• masking
• boundary condition

4. 데이터 의존성

• 출력이 의존하는 입력
• 원소 간 의존 관계
• row, warp, block 또는 전체 tensor 범위의 의존성
• producer-consumer 관계

5. 의미 불변성

구현이 달라져도 반드시 유지해야 할 조건을 정의한다.

6. 대수적 성질

• 결합성
• 교환성
• 선형성
• 단조성
• 멱등성
• shift invariance
• scale invariance
• 순열 등가성

7. 통계적·기하학적 의미

필요한 경우 확률, norm, 거리, 분포와 관련된 의미를 설명한다.

8. 관측 가능한 값

최종 출력과 내부 중간값을 구분한다.

9. 가능한 알고리즘

동일한 수학적 연산을 계산하는 여러 알고리즘을 비교한다.

10. 허용되는 변환

• 연산 순서 변경
• reduction tree 변경
• fusion
• materialization 제거
• recomputation
• online 변환
• tiling
• precision 변경

11. 제한되는 변환

• 의미를 훼손하는 axis 변경
• masking 조건 위반
• dependency 제거
• normalization domain 변경
• 허용 오차를 넘는 근사

12. 추상 실행 모티프

특정 ISA와 무관한 형태로 실행 구조를 표현한다.

load
→ local transform
→ reduction
→ broadcast
→ output transform
→ store

13. 표현 계층별 lowering

다음 계층에서 연산이 어떻게 나타나는지 비교한다.

• 연산 그래프
• loop 또는 알고리즘
• compiler IR
• CUDA kernel
• PTX
• SASS
• runtime execution trace

14. 예상 최적화 지점

• memory traffic
• reuse
• kernel boundary
• synchronization
• register pressure
• occupancy
• instruction dependency

15. 정확성 검증 기준

• reference 식
• bitwise equality 여부
• max absolute error
• max relative error
• 통계적 조건
• NaN/Inf 처리
• 극단 입력

16. 실험 설계

• baseline 구현
• 변형 구현
• 입력 크기
• compiler 옵션
• 측정 항목
• SASS 비교 기준
• profiler 지표

이 형식을 모든 연산에 동일하게 적용하면 연산 간 비교가 가능해진다.