Computation Structure

프로젝트 소개

개요

이 프로젝트는 GPU 커널 최적화를 단순한 구현 기법의 집합으로 보지 않고,
연산이 본질적으로 어떤 구조를 가지는지, 그리고 그 구조가 어떤 변환까지 의미를 보존한 채 허용하는지를 먼저 정의한 뒤,
그 위에서 실제 커널 구현, 조합, 런타임 선택, 그리고 LLM 기반 코드 생성을 연결하는 시스템이다.

기존의 많은 최적화 시스템은 특정 패턴을 더 빠른 코드로 치환하는 방식에 집중한다.
하지만 이 프로젝트는 그보다 한 단계 앞에서 출발한다.

핵심 질문은 다음과 같다.

• 이 연산은 어떤 계산 구조를 가지는가
• 어떤 변환은 의미를 유지하고, 어떤 변환은 의미를 깨뜨리는가
• 하드웨어의 실제 제약 아래에서 어떤 실현 방식이 가능한가
• 허용된 최적화 공간 안에서 지금 어떤 실행 경로를 선택해야 하는가
• 이러한 제약과 가능성을 이해한 상태에서 커널 코드를 어떻게 생성할 것인가

즉, 이 프로젝트는 **“어떻게 코드를 빠르게 짤 것인가”**만을 다루지 않는다.
그보다 먼저 “어디까지 안전하게 바꿀 수 있는가”, “어떤 구조가 어떤 실현으로 이어지는가”를 체계화한다.

---

문제의식

동일한 연산이라도 구현 방식은 매우 다양하다.
예를 들어 reduction, normalization, attention, fused epilogue 같은 연산들은 표면적으로는 서로 달라 보이지만,
조금 더 깊게 들어가면 다음과 같은 공통 구조를 공유한다.

• 부분 결과를 병합할 수 있는가
• 전체를 저장하지 않고 요약 상태만 유지할 수 있는가
• 중간값을 다시 계산해도 되는가
• 분할 실행과 재조합이 가능한가
• 수치적 재스케일링을 통해 안정성을 유지할 수 있는가

이 공통 구조를 먼저 정의하지 않으면, 최적화는 개별 연산별 기법 모음으로 남게 된다.
반대로 계산 구조와 의미 보존 경계를 먼저 정의하면, 서로 다른 연산들을 더 일반적인 primitive와 motif 수준에서 다룰 수 있게 된다.

이 프로젝트는 바로 이 지점을 목표로 한다.
연산자별 최적화 모음이 아니라, 구조 기반 실행 실현 체계를 만드는 것이다.

---

핵심 관점

이 프로젝트의 중심 관점은 다음 한 문장으로 요약할 수 있다.

연산의 computation structure를 분석하고, 그 구조가 허용하는 preservation semantics를 통해 의미 보존 가능한 최적화 공간을 정의한 뒤, 그 공간 안에서 GPU primitive realization, structural composition, runtime optimization, 그리고 LLM kernel synthesis를 연결한다.

여기서 중요한 것은 Preservation Semantics다.

Preservation은 단순한 부가 정보가 아니다.
이 프로젝트에서는 그것이 전체 시스템을 관통하는 제약축이다.
어떤 구조를 어떤 방식으로 변형할 수 있는지, 어떤 primitive를 선택할 수 있는지, 어떤 조합이 합법적인지, 어떤 런타임 경로가 허용되는지 모두 이 축을 통해 판정된다.

따라서 이 프로젝트는 고정된 최적화 규칙을 적용하는 시스템이 아니라,
의미 보존 경계를 기준으로 허용된 최적화 공간을 구성하는 시스템이라고 보는 편이 더 정확하다.

---

시스템이 다루는 핵심 축

1. Computation Structure

가장 먼저 다루는 것은 연산의 표면적 이름이 아니라 계산 구조 자체다.
이 단계에서는 연산이 어떤 상태를 유지하는지, 어떤 결합 규칙을 가지는지, 스트리밍이 가능한지, 요약 상태로 대체 가능한지 같은 본질적 구조를 정의한다.

예를 들어 서로 다른 operator라도 다음과 같은 구조적 성격을 공유할 수 있다.

• mergeable statistics
• weighted reduction
• rescaled accumulation
• bounded summary state
• streaming normalization
• coupled numerator-denominator

이 단계의 목적은 “이 연산은 softmax인가 layernorm인가”를 묻는 것이 아니라,
“이 연산은 어떤 계산 구조로 환원될 수 있는가”를 묻는 데 있다.

---

2. Primitive Realization

계산 구조가 정의되면, 그 구조를 GPU 위에서 실제로 실현할 수 있는 최소 실행 단위를 정의한다.

여기에는 다음과 같은 것들이 포함될 수 있다.

• reduction tree
• tile staging
• shared memory residency
• streaming accumulation
• online state update
• rematerialized intermediate reconstruction
• warp/block cooperative summary update

이 단계는 추상 구조를 실제 GPU 실행의 단위로 내리는 과정이다.
즉, 구조를 코드로 바꾸기 전의 실행 primitive 층이다.

---

3. Structural Composition

Primitive 하나만으로는 대부분의 실제 연산을 완성할 수 없다.
그래서 다음 단계에서는 primitive들을 어떤 방식으로 결합해 하나의 operator realization이나 fused execution structure를 만들 수 있는지 정의한다.

이 단계는 “무엇을 조합할 수 있는가”를 다룬다.

예를 들어,

• streaming reduction + rescaled accumulation
• mergeable statistics + bounded summary state
• decomposition + weighted aggregation
• tile staging + local accumulation + deferred writeback

같은 조합이 특정 종류의 실행 구조를 만들어낼 수 있다.

이 단계는 정적 조합 원리를 다룬다.
즉, 가능한 실행 구조의 생성 규칙을 정의하는 계층이다.

---

4. Hardware Evidence

구조적으로 가능하다고 해서 실제 하드웨어에서 항상 효율적인 것은 아니다.
그래서 이 프로젝트는 하드웨어의 물리적 제약과 실제 거동을 독립적으로 관측하고 정리하는 축을 가진다.

여기서는 다음과 같은 요소를 다룬다.

• memory bandwidth pressure
• cache behavior
• shared memory bank conflict
• occupancy와 register pressure
• tile residency 한계
• scheduling 및 latency hiding 특성
• global/shared/local traffic 패턴

이 단계의 목적은 단순 벤치마크 수집이 아니다.
어떤 구조가 어떤 비용 구조를 가지는지를 실험적으로 확인하고,
이 결과를 이후 runtime 선택과 synthesis 제약에 반영하는 것이다.

즉, 가능한 구조와 실제로 유리한 구조를 구분하는 근거를 제공한다.

---

5. Runtime Optimization

Structural Composition이 가능한 구조들을 만드는 규칙이라면, Runtime Optimization은 그 구조들 중 현재 조건에서 어떤 경로를 택할지 결정하는 계층이다.

여기서는 다음과 같은 동적 조건이 고려된다.

• input shape
• dtype
• available workspace
• memory pressure
• occupancy 손실 가능성
• latency/bandwidth trade-off
• approximation 허용 여부
• rematerialization 허용 여부

예를 들어 같은 구조라도 실행 시점에 따라 다음과 같은 선택이 달라질 수 있다.

• 더 큰 tile 대신 더 작은 tile 선택
• multi-stage pipeline 대신 shorter pipeline 선택
• materialization 경로 대신 recomputation 경로 선택
• exact path 대신 approximation-enabled path 선택

즉 이 단계는 허용된 최적화 공간 안에서의 동적 경로 선택기다.

---

6. LLM Kernel Synthesis

이 프로젝트에서 LLM은 출발점이 아니다.
LLM은 구조, 제약, 하드웨어 특성, 실행 선택 원리가 먼저 정의된 뒤에 등장하는 최종 합성 계층이다.

LLM이 받는 것은 단순한 “빠른 커널을 만들어라”가 아니다.
그 대신 다음과 같은 구조화된 조건들이다.

• computation structure
• preservation boundary
• available primitive set
• composition legality
• hardware evidence
• runtime-selected path
• target constraints

즉, 이 프로젝트에서의 LLM kernel synthesis는 자유 생성이 아니라
잘 정의된 실현 공간 안에서의 constrained synthesis다.

이 점이 중요하다.
이 프로젝트는 “LLM으로 CUDA 코드를 만든다”는 데모형 접근이 아니라,
구조적·의미적 제약에 의해 닫힌 공간 안에서 커널을 합성하는 시스템을 지향한다.

---

Preservation Semantics의 역할

Preservation Semantics는 위 단계들 중 하나가 아니라,
전체를 관통하는 전역 제약 계층이다.

이 축은 어떤 변환이 의미를 보존하는지를 규정한다.
예를 들어 다음과 같은 질문들이 모두 이 계층에 속한다.

• 연산 순서를 바꿔도 되는가
• 데이터 표현만 바뀌고 의미는 유지되는가
• 전체 상태 대신 요약 상태만 유지해도 되는가
• 수치적 재스케일링이 허용되는가
• 저장 대신 재계산을 택해도 되는가
• 분해 후 재조합이 의미를 유지하는가
• 오차가 제한된 근사를 허용하는가

이 제약 계층이 없으면 최적화는 경험적 기법의 나열이 된다.
하지만 이 계층이 존재하면 각 최적화는 단순한 트릭이 아니라,
어떤 의미 보존 클래스 안에서 정당화되는 변환이 된다.

즉 Preservation은 legality의 근거이자 capability의 경계다.

---

프로젝트의 차별점

이 프로젝트의 차별점은 다음과 같다.

첫째, 연산자를 이름 중심이 아니라 구조 중심으로 본다.
softmax, layernorm, attention 같은 연산을 별개의 대상으로만 보지 않고,
그 아래에 있는 공통 계산 구조를 먼저 추출한다.

둘째, 최적화를 구현 테크닉이 아니라 의미 보존 가능한 공간의 탐색으로 본다.
이 때문에 프로젝트의 중심은 단순 lowering이 아니라 optimization space construction에 있다.

셋째, runtime을 후처리 계층이 아니라 구조 선택 계층으로 본다.
즉, 미리 하나의 최적 코드로 결정하는 것이 아니라, 허용된 공간 안에서 실행 시점의 조건에 맞는 경로를 선택하도록 설계한다.

넷째, LLM을 코드 자동완성 도구가 아니라 제약 기반 합성기로 위치시킨다.
LLM은 구조와 제약을 모르는 상태에서 자유롭게 생성하는 것이 아니라, 시스템이 정리한 의미·구현·하드웨어 경계 안에서만 동작한다.

---

프로젝트가 목표로 하는 것

이 프로젝트의 최종 목표는 단순히 빠른 커널 몇 개를 만드는 것이 아니다.
더 근본적으로는 다음을 목표로 한다.

• 연산의 공통 계산 구조를 정의하는 것
• 의미 보존 가능한 변환의 범위를 형식화하는 것
• GPU 상에서의 primitive realization을 체계화하는 것
• 구조적 조합 원리를 통해 operator realization을 일반화하는 것
• 하드웨어의 실제 한계를 실험적으로 반영하는 것
• 런타임에서 허용된 최적화 공간을 동적으로 선택하는 것
• 이러한 모든 제약과 구조를 바탕으로 커널 합성을 자동화하는 것

즉, 이 프로젝트는 하나의 커널 라이브러리도 아니고, 단순한 코드 생성기만도 아니다.
이것은 의미 보존 경계 위에서 GPU 실행 구조를 설계하고 실현하는 통합 시스템이다.

---

한 줄 요약

이 프로젝트는
연산의 구조를 해석하고, 의미 보존 가능한 변환 경계를 정의하며, 그 위에서 GPU primitive realization, 구조적 조합, 런타임 최적화, LLM 기반 커널 합성을 연결하는 구조 중심 실행 설계 시스템이다.