🤖 AI

AI-PROPELLER: Warehouse-Scale Interprocedural Code Layout Optimization with AlphaEvolve

AI-PROPELLER은 실제 하드웨어 실행을 활용하여 정밀한 보상 신호를 얻음으로써 대규모 웨어하우스 규모 애플리케이션에 대해 최초로 성공적인 미세 조정된 절차 간 코드 레이아웃 최적화를 달려 0.23%에서 1.6%의 성능 향상을 이끌어내는, Propeller 포스트 링크 옵티마이저를 진화시킨 에이전트 워크플로우인 Magellan을 소개합니다.

원저자: Chaitanya Mamatha Ananda, Rajiv Gupta, Mircea Trofin, Aiden Grossman, Sriraman Tallam, Xinliang David Li, Amir Yazdanbakhsh

게시일 2026-06-02

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Chaitanya Mamatha Ananda, Rajiv Gupta, Mircea Trofin, Aiden Grossman, Sriraman Tallam, Xinliang David Li, Amir Yazdanbakhsh

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 수백만 권의 책(함수)과 수십억 페이지의 코드 명령어가 담긴 거대하고 믿기지 않을 정도로 복잡한 도서관(컴퓨터 프로그램)이 있다고 상상해 보십시오. 수년 동안 사서들(최적화 도구)은 책을 찾기 쉽게 만들기 위해 책장에 책을 배치하는 작업을 해왔습니다.

기존 방식은 한 번에 책 한 권씩 정리하는 방식이었습니다. 만약 어떤 책에 100개의 장(chapter)이 있다면, 사서는 가장 인기 있는 장들이 서로 바로 옆에 오도록 그 장들을 재배치했습니다. 이것을 내부 프로시저(intraprocedural) 최적화라고 부릅니다. 이 방식은 도움이 되었지만, 큰 기회를 놓쳤습니다. 책 A의 가장 인기 있는 장 바로 다음에 책 B의 가장 인기 있는 장이 와야 할 수도 있기 때문입니다. 만약 이 두 책이 도서관 반대편에 있다면, 독자(컴퓨터 프로세서)는 다음 페이지를 넘기기 위해 방을 가로질러 달려가야 했고, 이는 시간과 에너지를 낭비하게 만들었습니다.

AI-PROPELLER는 이 문제를 해결하기 위해 한 번에 한 권의 책이 아니라, 전체 도서관을 한꺼번에 재배치하는 새로운, 매우 똑똑한 사서 시스템입니다.

이 시스템이 어떻게 작동하는지 간단한 개념으로 나누어 설명하겠습니다.

1. 문제점: "조합론적(Combinatorial)" 악몽

책 한 권을 재배치하는 것도 어렵습니다. 하지만 모든 인기 있는 페이지가 (설령 다른 책에 있더라도) 다음에 올 페이지와 바로 옆에 위치하도록 수백만 권의 책을 재배치하는 것은 인간의 두뇌나 전통적인 컴퓨터로는 풀 수 없는 거대한 수학적 문제입니다. 이는 마치 10만 명의 관중이 있는 경기장에서 모든 사람이 각기 다른 구역에 흩어져 있음에도 불구하고, 모두가 자신의 가장 친한 친구 옆에 앉고 싶어 하는 완벽한 좌석 배치를 찾는 것과 같습니다.

게 further, 기존의 사서들은 어디에 무엇을 둘지 결정할 때 "추측(정적 모델)"을 사용했습니다. 그들은 실제로 배치를 테스트하지 않고, 단지 무엇이 효과적일 것이라고 계산했을 뿐입니다.

2. 해결책: "AI 에이전트" (Magellan)

연구진은 Magellan이라 불리는 시스템을 사용했는데, 이는 지치지 않고 실험을 수행하는 로봇 팀처럼 작동합니다. 이 팀에는 두 명의 주요 작업자가 있습니다.

설계자 (AlphaEvolve): 책을 배치하는 규칙을 쓰고 다시 쓰는 AI입니다. "만약 책 A를 세 부분으로 나누고 그 중간 부분을 책 B 옆에 둔다면 어떨까?"와 같은 새로운 아이디어를 시도합니다.
조율사 (Vizier): 이러한 규칙들의 구체적인 숫자들을 미세 조정하는 도구입니다 (예: "책 사이의 거리를 얼마나 멀게 할 수 있는가?").

3. 핵심 비결: 실제 환경 테스트 (추측하지 않음)

이것이 가장 중요한 부분입니다. AI는 새로운 배치가 좋은지 추측하는 대신, 실제로 도서관을 구축하고 테스트합니다.

AI는 코드의 새로운 배치를 만듭니다.
이 프로그램을 실제 작동하는 바이너리(소프트프트웨어의 새 버전)로 컴파일합니다.
이 새 버전을 실제 하드웨어에서 실행합니다.
실제 성능 카운터(스톱워치와 연료 게이지 같은 것)를 사용하여 정확히 얼마나 빨리 실행되는지 측정합니다.

이를 통해 AI는 "보상 신호"를 얻습니다. 만약 새로운 배치가 더 빠르다면, AI는 금메달을 받고 더 많이 그렇게 하도록 학습합니다. 만약 더 느리다면, 그 실수를 피하도록 배웁니다. 통제된 환경 내의 실제 하드웨어에서 테스트했기 때문에, 결과는 단순히 이론적인 것이 아니라 믿을 수 없을 정도로 정밀합니다.

4. 결과: 작은 이득, 거대한 영향

이 논문은 LLVM Clang 컴파일러(다른 소프트웨어를 빌드하는 데 사용되는 도구)와 거대한 Google 검색 서비스와 같은 대규모의 실제 소프트웨어에서 이 시스템을 테스트했습니다.

Clang 컴파일러: 새로운 시스템은 속도를 1.6% 높였습니다.
Google 검색 서비스: 검색 서비스를 0.23% 더 빠르게 만들었습니다.

여러분은 "0.23%는 아무것도 아니지 않나?"라고 생각할 수도 있습니다. 하지만 거대한 데이터 센터의 세계에서 이것은 숨겨진 금광을 발견한 것과 같습니다. 매일 수십억 건의 검색에서 0.23%의 시간을 절약한다면, 수백만 달러의 전기 및 서버 비용을 아낄 수 있습니다. 이는 러너가 경주를 9.58초에 끝내느냐, 9.56초에 끝내느냐의 차이와 같습니다. 아주 미세한 차이지만 세계 기록과 2위의 차이를 가르는 결정적인 차이입니다.

5. 실제 작동 방식 ("분할" 기술)

논문은 AI가 발견한 특정 기술을 강조합니다.

기존 방식: 만약 함수(코드 조각)에 "핫(hot, 자주 사용되는)" 부분과 "콜드(cold, 드물게 사용되는)" 부분이 있다면, 기존 시스템은 함수를 두 개로 나누었습니다: 핫한 부분은 한 선반에, 콜드한 부분은 다른 선반에 두는 식입니다.
AI-PROPELLER 방식: AI는 때때로 함수를 세 개 이상의 조각으로 나누어야 한다는 것을 깨달았습니다. AI는 함수 A의 특정 "핫"한 덩어리가 원래의 "책"이 무엇인지와 상관없이 함수 B의 "핫"한 덩어리 바로 옆에 배치되어야 한다는 것을 찾아냈습니다. 본질적으로 코드를 작고 정밀한 퍼즐 조각으로 자른 뒤, 가장 많이 사용되는 조각들이 항상 서로 맞닿아 있도록 재조립하는 것입니다.

요약

AI-PROPELLER는 함수 경계를 넘어 대규모 산업용 소프트웨어의 내부 코드를 재배치하는 데 AI를 성공적으로 사용한 첫 번째 시스템입니다. 이 시스템은 단순히 추측하는 것이 아니라, 직접 구축하고, 테스트하며, 실제 하드웨어로부터 배우고 학습합니다. 이를 통해 이미 "완벽하게 최적화되었다"고 여겨지는 소프트웨어에서 추가적인 성능(0.23% ~ 1.6%)을 짜냅니다. 이는 전체를 하나의 조각이 아닌 전체적인 그림으로 바라볼 때, 성숙한 시스템 안에서도 여전히 숨겨진 속도가 기다리고 있음을 증명합니다.

기술 요약: AI-PROPELLER

문제 정의

Propeller 및 BOLT와 같은 포스트 링크 최적화 도구(Post-link optimizers, PLOs)는 정밀한 프로파일 가이드형 내부적(intraprocedural) 코드 레이아웃을 통해 대규모 웨어하우스 애플리케이션의 성능을 성공적으로 개선해 왔습니다. 이 도구들은 함수 내에서 기본 블록(basic blocks)을 재정렬하고 핫/콜드(hot/cold) 코드 영역을 분리하여 명령 인스트럭션 캐시 및 TLB 활용도를 최优化합니다. 그러나 이들은 함수 간(interprocedural) 코드 레이아웃 영역은 여전히 미개척 상태로 남겨두고 있습니다.

함수 경계를 넘어 기본 블록을 재정렬하는 함수 간 레이아웃은 역사적으로 다음과 같은 이유로 구현이 어려웠습니다:

조합 폭발(Combinatorial Explosion): 탐색 공간이 내부적 탐색보다 수십 배 더 큽니다 (예: 웨어하우스 규모의 애플리케케이션은 약 140만 개의 함수와 약 4,000만 개의 기본 블록을 가질 수 있음).
복잡한 시맨틱스(Complex Semantics): 폴스루 점프(fall-through jumps)를 제거할 수 있는 내부적 레이아웃과 달리, 함수 간 레이아웃은 호출-반환(call-return) 시맨틱스를 엄격히 준수해야 합니다. 서로 다른 함수의 블록을 인접하게 배치한다고 해서 동적 인스트럭션 수가 줄어드는 방식이 다르기 때문에 비용 모델링이 복사합니다.
검증된 가치의 부재: 이전의 함수 간 레이아웃 시도들은 빌드 시간을 3~10배 증가시키면서도 성능 향상은 미미하거나 입증되지 않았으며, 이로 인해 커뮤니티에서는 이를 "향후 과제"로 취급해 왔습니다.

결과적으로, 산업 현장의 웨어하우스 규모 환경에서 정밀한 함수 간 레이아웃의 성능 잠재력은 아직 입증되지 않은 상태입니다.

방법론

본 논문은 Magellan 에이전트 워크플로우를 활용하여 함수 간 코드 레이아웃을 위한 컴파일러 휴리스틱을 진화시키는 프레임워크인 AI-PROPELLER를 소개합니다.

1. Magellan 프레임워크

AI-PROPELLER은 Propeller 코드 레이아웃 정책을 최적화하기 위해 두 가지 구성 요소를 통합합니다:

AlphaEvolve (LLM 에이전트): 레이아웃 휴리스틱의 소스 코드(code_layout.cc)를 진화시킵 sleep니다. 초기 정책과 프롬프트를 입력받아, 휴리스틱을 개선하기 위한 새로운 코드 편집(추가, 수정, 삭제)을 생성합니다.
Vizier (Black-box 최적화 도구): 진화된 정책에 의해 노출되는 수치적 하이퍼파라미터(컴파일러 플래그)를 미세 조정합니다.

2. 고충실도 보상 신호 (High-Fidelity Reward Signal)

근사적인 정적 비용 모델에서 벗어난 것이 핵심적인 혁신입니다. 진화 루프가 정밀하고 노이즈가 없는 보상 신호를 받을 수 있도록 다음과 같이 설계되었습니다:

하드웨어 실행: 시스템은 여러 레이아웃 변체를 컴파일하고 실제 하드웨어(Intel Skylink 시스템)에서 실행합니다.
노이즈 감소: 환경을 엄격하게 제어합니다 (Turbo Boost, SMT, ASLR 비활성화; CPU 주파수를 피크치의 75%로 고정).
통계적 안정성: 실행 간 편차를 0.05% 미만으로 유지하기 위해 각 바이너리를 10회씩 실행합니다.
보상 계산: 보상은 실제 성능 카운터(사이클 수)로부터 유도되며, $1 - (\text{cycles} / \text{reference})$ 로 계산됩니다.

3. 진화된 정책

프레임워크는 함수 간 재정렬의 세 가지 핵심 요소를 제어하는 정책을 진화시킵니다:

체인 분할 임계값 (Chain Split Threshold): 기본 블록 시퀀스를 분할할 시점을 결정합니다. AI-PROPELLER은 이 임계값을 0에서 213으로 높여, 더 많은 시퀀스가 분할되어 함수 간에 재삽입될 수 있도록 했습니다.
메모리 오프셋 (전방/후방): 엣지가 수익성이 있다고 간주되는 블록 간의 최대 거리를 정의합니다. 진화된 정책은 이러한 제한 범위를 크게 확장하여 (예: 전방 방향 1024바이트에서 3059바이트로), 호출자-피호출자(caller-callee) 간의 장거리 관계를 포착하도록 했습니다.
글로벌 정렬 로직: 함수별 블록 ID 정렬을 글로벌 레이아웃 인덱스로 대체하여, 최종 바이너리가 의도한 함수 간 순서를 보존하도록 보장합니다.

주요 기여

함수 간 이득의 첫 번째 입증: 실제 세계의 대규모 웨어하우스 규모 바이너리에서 미세한 함수 간 코드 레이아웃을 사용하여 명확한 성능 향상을 입증한 첫 번째 연구입니다.
확장 가능한 최적화: 이 프레임워크는 빌드 시간이나 메모리 사용량의 눈에 띄는 저하 없이 산업 규모의 애플리케이션(예: LLVM Clang, Search)을 최적화하여, 함수 간 최적화의 엔지니어링 장벽을 극복했습니다.
새로운 휴리스틱 발견: 시스템은 기존의 정적 휴리스틱(Ext-TSP) 및 함수 수준 재정렬(CDSort)보다 뛰어난 비직관적인 레이아웃 정책을 자율적으로 발견했습니다.

실험 결과

프레임워크는 프런트엔드 바운드(front-end bound) 워크로드(LLVM Clang, LevelDB, Redis, 그리고 독점적인 웨어하우스 규모 Search 애플리케이션)에 대해 평가되었습니다.

성능 향상:
- LLVM Clang: 베이스라인(FDO + ThinLTO + Ext-TSP) 대비 실행 시간을 1.6% 단축했습니다. 이는 이미 고도로 최적화된 바이너리에서 추가로 약 20%의 성능을 짜낸 것을 의미합니다.
- 웨어하우스 규모 Search: 배포된 Ext-TSP 베이스라인 대비 **0.23%**의 향상을 달면했습니다. 수치는 작아 보이지만, 저자들은 이 규모의 운영 비용 측면에서 이것이 매우 유의미하다고 언급합니다.
- 기타 벤치마크: LevelDB와 Redis 또한 통계적으로 유의미한 향상(p-value ~0)을 보였습니다.
마이크로아키텍처 영향:
- 프런트엔드 스톨 (Frontend Stalls): AI-PROPELLER은 프런트엔드 바운드 스톨(명령 인스트럭션 페치/디코드 스톨)을 크게 감소시켰습니다. 예를 들어, Clang의 경우 스톨이 45%에서 39%로 감소했고, Redis의 경우 49%에서 34.2%로 감소했습니다.
- 인스트럭션 리타이어먼트 (Instruction Retirement): CPU 파이프라인 슬롯이 인스트럭션을 리타이어하는 데 사용하는 비율(유효 작업)을 개선했습니다 (예: Clang은 27%에서 30%로 개선).
절제 연구 (내부적 vs 함수 간):
- 함수 간 변환을 비활성화했을 때(블록이 함수 내에 연속적으로 머물도록 강제), 성능 이득은 1.6%에서 약 0.3%로 떨어졌습니다.
- 이는 성능 향상의 약 **80%**가 함수 경계를 가로질러 블록을 인터리빙(interleaving)하는 능력에서 비롯되었음을 나타내며, 글로벌 함수 간 재정렬이 성공의 주요 동인임을 확인시켜 줍니다.

의의 및 주장

본 논문은 AI-PROPELLER이 산업 현장의 대규모 바이너리에 미세한 함수 간 코드 레이아웃을 성공적으로 적용한 첫 번째 프레임워크라고 주장합니다. 그 의의는 다음과 같습니다:

잠재력 검증: 이미 하이퍼 최적화된 환경에서도 함수 간 레이아웃의 "미개척된" 잠재력이 실질적이고 측정 가능하다는 것을 증명했습니다.
탐색 공간 극복: AI 기반 에이전트 워크플로우가 수동 튜닝이나 정적 휴리스틱이 실패하는 지점인, 지수적으로 큰 함수 간 레이아웃 탐색 공간을 탐색할 수 있음을 보여주었습니다.
실용성: 이러한 최적화가 분산 빌드 시스템의 확장성을 해치지 않고 달성될 수 있음을 보여줌으로써, 실제 프로덕션 사용이 가능함을 입증했습니다.

저자들은 0.23%~1.6%의 이득이 수치상으로는 작아 보일 수 있지만, 기존의 최첨단 최적화 기술을 적용한 상태에서도 달성하기 매우 어렵다는 점과 웨어하우스 규모 애플리케이션에서 이러한 미미한 개선이 막대한 비즈니스 가치로 직결된다는 점에서 운영상 매우 중요하다는 점을 강조합니다.