Computation Structures

개요

이 디렉토리는 여러 operator들에 공통적으로 나타나는 상위 수준의 계산 구조를 정리합니다.

초점은 개별 연산자의 고유한 기능이나 구현 방식이 아니라, 서로 다른 연산자들 아래에서 반복적으로 발견되는 계산의 구조적 형태에 있습니다. 예를 들어 reduction, streaming accumulation, mergeable summary, weighted aggregation 같은 구조는 서로 다른 operator들에서도 공통적으로 나타날 수 있습니다.

이 계층의 목적은 특정 hardware, backend, kernel 형태를 직접 설명하는 데 있지 않습니다. 그보다 주어진 operator를 더 추상적인 계산 개념 위에서 해석하고, 서로 다른 연산자들을 공통된 구조 언어로 분류할 수 있도록 만드는 데 있습니다.

즉 computation-structures는 개별 operator를 직접 설명하는 계층이 아니라,
operator들을 더 일반적인 계산 범주로 분해하고 연결하기 위한 상위 분류 체계입니다.

---

왜 필요한가

연산자들은 서로 이름도 다르고 수식도 다르지만, 그 내부 계산을 보면 반복적으로 비슷한 구조를 공유하는 경우가 많습니다.

예를 들어 어떤 연산은 여러 값을 하나로 모으는 구조를 가지며, 어떤 연산은 부분 상태를 점진적으로 갱신하는 구조를 가지며, 또 어떤 연산은 부분 요약값들을 결합해 전체 결과를 형성합니다. 이런 공통성을 드러내지 않으면 operator는 각각 독립적인 개별 항목처럼만 보이게 됩니다.

하지만 compiler나 generator의 관점에서는 개별 연산자 이름보다,
그 연산이 어떤 계산 구조에 속하는가를 먼저 아는 것이 더 중요한 경우가 많습니다.
왜냐하면 실제 분류, 변환, 조합, 실현 가능성 판단은 종종 operator 이름보다 구조적 성격에 더 크게 의존하기 때문입니다.

따라서 이 계층은 연산자 목록을 단순 나열하는 대신,
그 연산자들을 더 상위의 계산 구조들로 다시 묶고 해석할 수 있게 해주는 역할을 가집니다.

---

이 계층이 다루는 것

computation-structures는 다음과 같은 질문을 다룹니다.

• 이 연산은 여러 값을 하나의 결과로 축약하는가?
• 이 연산은 부분 결과를 유지하며 점진적으로 갱신될 수 있는가?
• 이 연산은 중간 요약 상태들의 결합으로 이해될 수 있는가?
• 이 연산은 단순 합이 아니라 가중된 집계 구조를 가지는가?
• 이 연산은 입력들 사이의 대응 관계를 따라 결합되는가?
• 이 연산은 전체를 직접 다루기보다 부분 구조들의 조합으로 이해될 수 있는가?

이 질문들은 특정 operator의 의미를 직접 설명하기 위한 것이 아니라,
주어진 operator를 더 일반적인 계산 구조로 분류하기 위한 기준들입니다.

---

이 계층의 역할

computation-structures의 핵심 역할은 다음과 같습니다.

1. operator를 상위 개념으로 분류한다

개별 operator를 그 자체로만 보지 않고, 어떤 계산 구조들의 조합으로 이해할 수 있는지 드러냅니다.

예를 들어 하나의 operator는 단일 구조만 갖는 것이 아니라,
reduction과 broadcasted application의 조합일 수도 있고,
pairwise combination과 weighted aggregation의 조합일 수도 있습니다.

2. 구조적 공통성을 드러낸다

이름이 다른 연산자들이 실제로는 같은 계산 골격을 공유할 수 있음을 보여줍니다.

이는 operator catalog를 더 추상적인 수준으로 재조직하는 데 도움이 됩니다.

3. 후속 계층의 기반을 제공한다

properties, invariants, realization, lowering 같은 다음 계층은
이 계산 구조 위에서 더 구체적인 조건과 제약을 다루게 됩니다.

즉 computation structure는
“이 연산이 어떤 종류의 계산인가”를 먼저 말하고,
그 이후에 property는 “무엇이 허용되는가”, invariant는 “무엇이 유지되어야 하는가”, realization은 “어떻게 구체화되는가”를 다루게 됩니다.

---

포함 범위

이 계층에는 특정 연산자에 묶이지 않는, 보다 일반적인 계산 구조가 포함됩니다. 예를 들면 다음과 같습니다.

• elementwise transformation
• pairwise combination
• reduction
• mergeable summary
• streaming accumulation
• weighted aggregation
• broadcasted application
• partitioned aggregation
• re-materializable intermediate

이 항목들은 특정 hardware나 kernel 조직을 직접 가리키지 않습니다.
대신 서로 다른 operator들을 공통된 계산 형식 위에서 분류하기 위한 개념적 구조들입니다.

---

포함하지 않는 것

이 계층은 다음 내용을 직접 설명하지 않습니다.

• 개별 operator의 고유한 의미
• 특정 수식의 정확한 형태
• 수치 안정성 규칙 자체
• 변환 허용 여부나 재배열 가능성 같은 성질
• backend별 realization
• hardware-specific execution detail

예를 들어 associativity, commutativity, reorderability 같은 것은 structure 자체가 아니라 property에 가깝고, numerical stability requirement는 invariant에 가깝고, shared memory, tensor core, cp.async, warp/block organization 같은 것은 realization에 가깝습니다.

computation-structures는 그보다 앞선 수준에서, 연산자를 분류할 수 있는 계산적 범주를 정리하는 역할을 가집니다.

---

문서화 원칙

이 디렉토리의 각 항목은 가능한 한 다음 원칙을 따라야 합니다.

1. operator-independent 해야 한다

각 구조는 특정 operator 하나의 설명으로 닫히지 않아야 합니다.
핵심은 “이 구조가 어떤 operator에서 보이는가” 이전에,
“이 구조 자체가 어떤 계산 형식인가”를 먼저 설명하는 데 있습니다.

2. hardware-free한 언어를 유지해야 한다

가능한 한 tile, warp, block, tensor core 같은 구현 단위를 직접 전제하지 않습니다.
그런 표현은 realization 단계에서 다루고, 여기서는 계산의 구조적 성격만 다룹니다.

3. 분류 가능성을 제공해야 한다

각 structure는 나중에 실제 operator를 입력받았을 때,
그 operator를 이 구조의 관점에서 categorize할 수 있도록 충분히 일반적이어야 합니다.

4. 단일 구조보다 조합 가능성을 허용해야 한다

하나의 operator는 하나의 structure만 갖지 않을 수 있습니다.
따라서 각 structure는 배타적 label이라기보다,
operator를 해석하는 데 쓰이는 구성 요소로 이해하는 것이 적절합니다.

---

다른 계층과의 관계

Computation Structures ↔ Operators

operator는 최종 분류 대상이고, computation structure는 그 operator를 더 상위 수준에서 해석하기 위한 범주입니다.

즉 operator는 structure의 사례이고, structure는 operator를 재분류하기 위한 언어입니다.

Computation Structures ↔ Properties

structure는 계산의 형태를 말하고, property는 그 구조 위에서 어떤 변환이나 재배열이 허용되는지를 말합니다.

예를 들어 reduction이라는 구조가 있다고 해서 항상 자유로운 재배열이 허용되는 것은 아닙니다.
그 여부는 structure가 아니라 property에 의해 결정됩니다.

Computation Structures ↔ Invariants

structure는 계산이 어떤 형식으로 조직되는가를 말하고, invariant는 그 계산이 변형되더라도 무엇이 유지되어야 하는가를 말합니다.

즉 structure는 분류의 언어이고, invariant는 보존의 언어입니다.

Computation Structures ↔ Realization

structure는 hardware-free한 상위 개념이고, realization은 그것이 특정 backend나 hardware 위에서 어떤 형태로 구현되는지를 다룹니다.

예를 들어 하나의 partitioned aggregation structure는 어떤 환경에서는 sequential form으로, 다른 환경에서는 tiled form으로, 또 다른 환경에서는 fused form으로 realization될 수 있습니다.

---

예시적 해석

이 계층의 목적은 operator를 구조적 언어로 다시 읽을 수 있게 만드는 데 있습니다.

예를 들면 다음과 같은 식의 해석이 가능합니다.

• GEMM
  → pairwise combination + reduction
• LayerNorm
  → reduction + mergeable summary + broadcasted application
• Softmax
  → reduction + weighted aggregation + streaming accumulation
• Attention
  → pairwise combination + weighted aggregation + streaming accumulation
• ReLU
  → elementwise transformation

중요한 점은, 이런 분류가 곧 구현 방식을 뜻하는 것은 아니라는 것입니다.
이는 어디까지나 operator를 더 일반적인 계산 구조들 위에서 이해하기 위한 상위 개념적 해석입니다.

---

최종 정리

computation-structures는 개별 operator의 고유한 기능을 설명하는 곳이 아니라,
주어진 operator들을 더 상위의 계산 구조들로 분류하고 해석하기 위한 계층입니다.

이 계층은 hardware-free한 언어를 유지하면서, 서로 다른 연산자들 아래에서 반복되는 계산의 공통 형식을 정리합니다. 이를 통해 operator catalog는 단순한 나열이 아니라, 더 일반적인 계산 범주들 위에서 재구성될 수 있습니다.

결과적으로 computation-structures는
AI compiler / generator가 주어진 연산자 집합을 더 추상적인 구조 단위로 파악하고, 이후의 property, invariant, realization 단계로 연결해 나가기 위한 출발점이 됩니다.