GOMA: Geometrically Optimal Mapping via Analytical Modeling for Spatial Accelerators

이 논문은 공간 가속기에서의 행렬 곱셈 (GEMM) 매핑 공간의 조합적 폭발 문제를 해결하고, 기하학적 추상화와 분석적 모델링을 기반으로 전역 최적 해를 보장하면서도 기존 최첨단 기법 대비 에너지 - 지연 곱 (EDP) 을 2.24~4.24 배 개선하고 해답 도출 시간을 3.83~73.6 배 단축하는 'GOMA' 프레임워크를 제안합니다.

핵심

이 논문은 **"GOMA"**라는 새로운 도구를 소개합니다. 이 도구의 역할은 인공지능 (AI) 칩이 방대한 양의 데이터를 계산할 때, **"어떻게 하면 가장 빠르고 전기도 아끼면서 작업을 끝낼 수 있을까?"**라는 질문에 대한 완벽한 정답을 찾아주는 것입니다.

기존의 방법들은 "시행착오"를 반복하거나 "대략적인 추측"을 했지만, GOMA 는 수학적으로 100% 최적의 방법을 아주 빠르게 찾아냅니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문제 상황: 거대한 도서관과 복잡한 책 정리법

상상해 보세요. 여러분은 거대한 도서관 (인공지능 칩) 을 운영 중입니다. 도서관에는 수백만 권의 책 (데이터) 이 있고, 독자들은 이 책들을 조합해서 새로운 이야기를 만들어야 합니다 (행렬 곱셈/GEMM 작업).

• 작업: 책 A, B, C 를 가져와서 조합하고, 그 결과를 다시 정리해야 합니다.
• 문제: 이 책을 어떻게 정리하느냐에 따라 작업 시간이 1 초가 걸릴 수도, 100 시간이 걸릴 수도 있습니다.
  • 책장을 너무 자주 왔다 갔다 하면 (데이터 이동) 시간이 걸리고, 전기도 많이 씁니다.
  • 책장 (메모리) 의 크기는 정해져 있어서, 한 번에 너무 많은 책을 쌓아둘 수 없습니다.
• 기존의 어려움: 가능한 정리 방법의 조합은 우주의 별 개수보다 많습니다. 그래서 기존 연구자들은 "우연히 좋은 방법을 찾거나", "가장 좋아 보이는 방법을 대충 추측"했습니다. 하지만 항상 최선의 답을 찾지는 못했고, 그 답을 찾으려다 보니 시간이 너무 오래 걸렸습니다.

2. GOMA 의 해결책: "지도와 나침반"을 가진 천재 설계사

GOMA 는 이 문제를 해결하기 위해 세 가지 혁신적인 아이디어를 도입했습니다.

① 3D 큐브로 세상을 보는 눈 (기하학적 추상화)

기존에는 복잡한 계산 과정을 "코드"나 "루프"로만 보았습니다. 하지만 GOMA 는 이를 **3 차원 큐브 (입체 도형)**로 봅니다.

• 비유: 책 정리 작업을 3D 큐브로 생각하면, "어떤 책이 어디에 있는지"가 한눈에 보입니다.
• 효과: 이렇게 보면, "책을 어디로 옮기면 가장 적게 움직일지"가 수학 공식으로 딱 떨어집니다. 더 이상 추측이 필요 없습니다.

② "한 번에 끝내는" 계산법 (분석적 모델링)

기존 도구들은 "이렇게 해보고, 저렇게 해보고"를 반복하며 에너지를 계산했습니다. 하지만 GOMA 는 수학 공식 하나로 모든 상황을 계산해냅니다.

• 비유: 요리사가 재료를 하나하나 저어보며 맛을 보는 게 아니라, 레시피 (공식) 를 보면 바로 "이 요리는 100 점이다"라고 정확히 아는 것과 같습니다.
• 효과: 어떤 방법을 선택하든, 그 방법이 얼마나 에너지를 쓸지 **순간 (O(1))**에 계산할 수 있습니다.

③ "완벽한 정답"을 보장하는 나침반 (전역 최적화)

기존 방법들은 "지금까지 본 것 중 가장 좋은 것"을 찾으면 멈췄습니다 (국소 최적). 하지만 GOMA 는 수학적 증명을 통해 "이것보다 더 좋은 방법은 절대 존재하지 않는다"라고 보장합니다.

• 비유: 미로에서 길을 찾을 때, 기존 방법은 "지금 가는 길이 좋아 보이니 계속 가자"라고 했지만, GOMA 는 미로 전체를 위에서 내려다보며 "여기가 유일한 출구다"라고 정확히 지적해 줍니다.

3. 실제 성과: 얼마나 빠른가요?

실험 결과, GOMA 는 기존 최고의 방법들보다 다음과 같은 압도적인 성과를 냈습니다.

• 에너지 효율 (전기 절약): 같은 작업을 할 때, 2.2 배에서 4.2 배까지 전기를 아껴줍니다. (마치 같은 거리를 가는데, 기존 차는 100km 를 달리는데 GOMA 는 25km 만 달려서 도착하는 것과 같습니다.)
• 속도 (답을 찾는 시간): 최적의 방법을 찾아내는 데 걸리는 시간이 3.8 배에서 73 배까지 빨라졌습니다.
  • 기존 방법들이 며칠을 고민해야 할 문제를, GOMA 는 몇 초 만에 "최고의 정답"을 찾아냅니다.

4. 요약: 왜 이것이 중요한가요?

지금 우리는 거대한 AI 모델 (LLM) 시대를 살고 있습니다. 이 모델들은 엄청난 전력을 먹습니다. GOMA 는 **"어떻게 하면 이 거대한 AI 칩을 가장 효율적으로 움직일지"**에 대한 수학적으로 증명된 완벽한 설계도를 제공합니다.

• 기존: "어쩌다 보니 좋은 방법이 나왔어요." (불안정하고 느림)
• GOMA: "이것이 수학적으로 가장 좋은 방법입니다. 그리고 증명할 수 있어요." (완벽하고 빠름)

결론적으로 GOMA 는 AI 칩이 더 작고, 더 빠르고, 더 친환경적으로 작동할 수 있게 해주는 핵심 열쇠가 될 것입니다.

기술 요약

논문 요약: GOMA (Geometrically Optimal Mapping via Analytical Modeling)

1. 문제 정의 (Problem Statement)

• 배경: 공간 가속기 (Spatial Accelerators, 예: TPU, Eyeriss 등) 에서 행렬 곱셈 (GEMM) 은 Transformer 기반의 대규모 언어 모델 (LLM) 등 핵심 워크로드의 주된 연산입니다.
• 핵심 과제: 가속기의 성능과 에너지 효율은 '매핑 (Mapping)' 전략 (데이터 타일링, 루프 순서 변경, 레벨 바이패스 등) 에 따라 결정됩니다.
• 도전 과제:
  • 조합적 폭발 (Combinatorial Explosion): 매핑 공간은 매우 거대하여 (GEMM 의 경우 $10^{10}$ 이상), 최적의 매핑을 찾기 위한 완전 탐색은 계산적으로 불가능합니다.
  • 기존 방법의 한계:
    • 휴리스틱/랜덤 탐색: 전역 최적성 (Global Optimality) 을 보장하지 못하며, 대규모 공간에서 수렴이 어렵습니다.
    • 미분 가능 모델 (Differentiable Approximation): 정수 제약 조건을 완화하여 근사해를 구하므로 오차가 발생하고 최적성 보장이 약합니다.
    • 수학적 프로그래밍 (Mathematical Programming): 정확한 하드웨어 비용 (에너지) 을 모델링하기 어렵고, 기존 방법들은 해결 시간이 너무 오래 걸립니다.
• 목표: 허용 가능한 시간 내에 전역 최적 (Global Optimal) 매핑을 보장하면서도, 에너지 평가가 빠르고 정확한 프레임워크 개발.

2. 방법론 (Methodology)

GOMA 는 기하학적 추상화 (Geometric Abstraction) 와 분석적 모델링 (Analytical Modeling) 을 기반으로 합니다.

• 3 차원 계산 그리드 (3D Compute Grid) 추상화:
  • GEMM 연산을 $P(x, y) = \sum A(x, z)B(y, z)$로 정의하고, 이를 3 차원 계산 점의 집합으로 모델링합니다.
  • 입력 행렬 $A, B$와 출력 $P$는 각각 3 차원 그리드의 3 가지 직교 투영면 ($x-z, y-z, x-y$) 에 대응됩니다.
• 계층적 타일링 및 이동 축 (Walking Axis):
  • 메모리 계층 (DRAM, SRAM, PE Array, Regfile, MACC) 을 3 차원 그리드를 계층적으로 덮는 타일링으로 간주합니다.
  • 이동 축 (Walking Axis): 특정 레벨에서 타일이 이동하는 축을 결정합니다. 이동 축에 수직인 투영면의 데이터는 재사용 (Temporal Reuse) 이 가능하고, 이동 축에 평행한 투영면의 데이터는 자주 업데이트됩니다. 이를 통해 데이터 이동량 (Traffic) 을 정량화합니다.
• 레벨 바이패스 (Level Bypass) 모델링:
  • 특정 데이터가 특정 메모리 레벨에 저장되지 않고 바로 아래 레벨로 전달되는 '바이패스' 전략을 이진 변수로 모델링합니다.
  • 이를 통해 데이터의 실제 이동 경로 (Source-Receiver) 를 동적으로 결정하고, 불필요한 읽기/쓰기 에너지를 제거합니다.
• 분석적 에너지 목적 함수 (Closed-form Energy Objective):
  • 위 기하학적 모델을 기반으로 데이터 이동 횟수와 단위 에너지 비용을 곱하여 상수 시간 $O(1)$으로 에너지를 계산하는 정확한 수식 (Closed-form) 을 유도했습니다.
  • 이 모델은 Timeloop 시뮬레이터와 99.9% 이상의 일치도를 보입니다.
• 정수 최적화 문제 (Integer Optimization Problem):
  • 하드웨어 제약 (용량, PE 수, 나누기 가능성) 하에서 위 분석적 에너지 함수를 최소화하는 정수 계획법 (Integer Programming) 문제로 매핑 탐색을 공식화합니다.
  • 분기 한정법 (Branch-and-Bound) 을 사용하여 전역 최적해를 찾으며, 최적성 증명 (Optimality Certificate) 을 제공합니다.

3. 주요 기여 (Key Contributions)

1. 기하학적 추상화 및 분석적 모델: GEMM 매핑을 3 차원 그리드와 투영면 업데이트로 추상화하여, $O(1)$ 복잡도로 에너지를 정확히 계산하는 수식을 처음 제안했습니다.
2. 전역 최적 매핑 프레임워크 (GOMA): 하드웨어 제약 하에서 타일링, 루프 순서, 바이패스 전략을 통합하여 정수 최적화 문제로 풀고, 전역 최적해를 보장하는 자동화된 탐색 시스템을 구축했습니다.
3. 검증 가능한 최적성: 기존 휴리스틱 방법들과 달리, GOMA 는 해결된 문제에 대해 최적성 증명 (Gap=0%) 을 제공하며, 어떤 (워크로드, 하드웨어) 조합에서도 짧은 시간 내에 최적 매핑을 산출합니다.
4. 오픈 소스: GitHub 를 통해 코드를 공개하여 재현성을 확보했습니다.

4. 실험 결과 (Results)

• 실험 환경:
  • 워크로드: Llama-3.2-1B, Qwen3-0.6B (Edge), Llama-3.3-70B, Qwen3-32B (Center) 등의 LLM 프리필 (Prefill) 워크로드.
  • 하드웨어: Eyeriss-like, Gemmini-like (Edge), A100-like, TPU v1-like (Center) 등 4 가지 대표적인 가속기 템플릿.
  • 비교 대상: Timeloop-mapper, LOMA, SALSA, CoSA, FactorFlow 등 SOTA 매핑 도구.
• 성능 지표 (EDP - Energy-Delay Product):
  • GOMA 는 모든 24 가지 테스트 케이스에서 가장 낮은 EDP를 기록했습니다.
  • 기존 최상위 방법 (CoSA) 대비 2.24 배 ~ 4.24 배의 EDP 개선 효과를 보였습니다.
  • 특히 대규모 행렬 곱셈 (Matrix-Matrix GEMM) 에서 휴리스틱 방법들의 성능 저하가 두드러진 반면, GOMA 는 일관된 우위를 보였습니다.
• 해결 시간 (Time-to-Solution):
  • GOMA 는 평균 0.65 초 (최대 3.6 초) 만에 최적 매핑을 찾았습니다.
  • 기존 방법들 대비 3.83 배 ~ 73.6 배 빠른 탐색 속도를 달성했습니다. CoSA 와 같은 모델 기반 방법조차 대규모 워크로드에서 수백 초가 소요되는 반면, GOMA 는 분석적 모델 덕분에 일정한 시간을 유지했습니다.

5. 의의 및 결론 (Significance)

• 이론적/실용적 가치: GOMA 는 공간 가속기 설계 및 최적화 분야에서 '전역 최적성 보장'과 '실시간 탐색'이라는 상충되는 목표를 동시에 달성한 최초의 프레임워크입니다.
• 확장성: 현재는 GEMM 에 집중되어 있으나, 기하학적 추상화 방식은 합성곱 (Convolution) 등 다른 연산자로도 확장 가능하여, 복잡한 소프트웨어 - 하드웨어 공동 최적화 (Co-design) 의 기반이 될 수 있습니다.
• 미래 영향: 대규모 LLM 배포 시 에너지 효율성을 극대화하고, 가속기 설계 공간을 효율적으로 탐색할 수 있는 강력한 도구를 제공합니다.

---

핵심 메시지: GOMA 는 복잡한 매핑 공간을 기하학적으로 단순화하여 정확한 수학적 모델로 변환함으로써, 기존 휴리스틱 방법들의 불확실성을 제거하고 빠르고 검증 가능한 전역 최적 매핑을 실현했습니다.