기술 요약: MileStone – 다목적 컴파일러 단계 순서 최적화 프레임워크

1. 문제 정의

본 논문은 프로그램의 중간 표현 (IR) 을 효율적인 기계어로 변환하기 위한 최적의 최적화 패스 순서를 결정하는 컴파일러 단계 순서 문제를 다룹니다. 표준 컴파일러 최적화 레벨 (예: LLVM 의 -O1, -O2, -O3) 은 고정된 순서를 제공하지만, 이는 방대한 탐색 공간의 극히 일부에 불과하며 상충되는 성능 목표를 균형 있게 조정하지 못합니다.

핵심 과제는 실행 시간, 코드 크기, 에너지 소비를 동시에 최적화해야 한다는 점입니다. 이러한 목표들은 본질적으로 상충됩니다. 예를 들어, 공격적인 루프 언롤링은 실행 시간을 단축시킬 수 있지만 코드 크기와 에너지 사용량을 증가시킵니다. 전통적인 접근 방식은 고정된 휴리스틱이나 단일 목표 최적화에 의존하는 경우가 많아, 에너지 제약이 있는 임베디드 시스템이나 고성능 컴퓨팅과 같은 다양한 배포 환경에 필요한 트레이드오프 (파레토 최적 해) 를 포착하지 못합니다. 또한, 완전 탐색은 계산적으로 불가능하며, 기존 학습 기반 방법들은 종종 다목적 제약을 지원하지 않거나 동적 프로파일링에 크게 의존합니다.

2. 방법론: MileStone 프레임워크

MileStone 은 컴파일러 단계 순서를 제약 다목적 최적화 (CMOO) 문제로 모델링하는 모듈형 학습 기반 프레임워크입니다. 이는 정적 성능 예측을 위한 그래프 신경망 (GNN) 과 적응형 탐색을 위한 강화 학습 (RL) 을 통합합니다. 프레임워크는 네 가지 긴밀하게 통합된 모듈로 구성됩니다.

2.1 그래프 생성기 (GG)

GG 는 프론트엔드 컴파일 단계 후 LLVM IR 에서 **제어 및 데이터 흐름 그래프 (CDFG)**를 추출합니다. 구문적 표현과 달리 CDFG 는 프로그램의 구조적 및 의미론적 관계를 포착합니다. CDFG 의 각 노드는 기본 블록 대지시어와 메모리 연산, 산술 연산, 제어 흐름과 같은 특정 지시어 오퍼코드를 인코딩하는 10 차원 이진 특성 벡터로 표현됩니다.

2.2 GNN 기반 성능 예측기 (GNNPP)

GNNPP 는 **그래프 합성곱 네트워크 (GCN)**를 활용하여 코드를 실행하지 않고 CDFG 표현으로부터 컴파일 후 지표 (실행 시간, 코드 크기, 에너지 소비) 를 직접 예측합니다.

• 아키텍처: 이 모델은 노드 특성을 집계하고 다중 홉 종속성을 포착하기 위해 2 층 GCN 을 적용한 후, 그래프 수준의 임베딩을 생성하기 위해 평균 풀링을 수행합니다.
• 학습: 에너지 및 코드 크기의 경우 평균 제곱 로그 오차 (Mean Squared Logarithmic Error) 를, 실행 시간의 경우 평균 절대 오차 (Mean Absolute Error) 를 사용하여 회귀 모델로 학습됩니다.
• 역할: GNNPP 는 대리 모델 (surrogate model) 로서 RL 에이전트를 안내하기 위한 신속한 성능 추정을 제공함으로써, 탐색 과정에서 반복적인 물리적 실행의 필요성을 제거합니다.

2.3 RL 기반 다목적 탐색기 (RLMOE)

RLMOE 는 최적화 패스 선택을 **마르코프 결정 과정 (MDP)**으로 모델링된 순차적 의사결정 과정으로 간주합니다.

• 상태: CDFG 그래프 임베딩, 현재 노드 식별자, CDFG 메타데이터, 사용자 정의 에너지 제약을 포함합니다.
• 행동: 현재 노드에 특정 최적화 지시를 적용할지 여부를 결정합니다.
• 보상: 희소 보상 함수가 최종 단계 ($T$) 에서만 적용되며, 예측된 코드 크기, 실행 시간, 목표 에너지 소비량과의 편차를 가중합으로 계산합니다. 중간 보상은 0 입니다.
• 알고리즘: 프레임워크는 **Deep Q-Network (DQN)**와 **Proximal Policy Optimization (PPO)**를 모두 지원합니다. PPO 는 클리핑된 대리 목적 함수와 일반화 이점 추정 (GAE) 을 활용하여 대규모 프로그램에서 특히 뛰어난 안정성과 성능을 일반적으로 보여줍니다.

2.4 RL 기반 데이터베이스 생성기 (RLDBG)

RLDBG 는 학습 데이터 수집을 자동화하는 자기 진화 지식 베이스입니다. RLDBG 는 RLMOE 를 반복적으로 호출하여 다양한 패스 순서를 탐색하고, 생성된 구성을 컴파일한 후 **평가기 (Evaluator)**를 사용하여 프로파일링하여 실제 지표 (ground-truth metrics) 를 획득합니다. 이러한 CDFG-지표 쌍은 GNNPP 를 학습하고 정제하기 위해 저장되며, 시간이 지남에 따라 예측 정확도와 탐색 효율성을 향상시키는 피드백 루프를 생성합니다.

3. 주요 기여

본 논문은 네 가지 주요 기여를 제시합니다:

1. 통합 프레임워크: 사용자 정의 제약 하에서 실행 시간, 코드 크기, 에너지 소비를 균형 있게 조정하는 다목적 최적화 문제로 컴파일러 단계 순서를 공식화하는 MileStone 프레임워크 도입.
2. 그래프 기반 신경 모델: IR 그래프에서 구조적 및 의미론적 속성을 학습하여 프로그램 성능 지표를 정확하게 예측하는 GNN 모델 개발.
3. RL 기반 탐색: 다중 목표 간의 파레토 최적 트레이드오프를 식별하고 패스 순서를 탐색하기 위한 RL 기반 접근 방식 (DQN/PPO) 구현.
4. 자기 개선 메커니즘: 다양한 최적화 결과를 집계하여 예측 정확도와 탐색 효율성을 모두 향상시키는 자기 진화 데이터 수집 메커니즘 (RLDBG) 통합.

4. 실험 결과

실험은 NVIDIA RTX 3090TI GPU 를 사용하여 표준 벤치마크 (PolyBench: gemm, 3mm, floyd-warshall) 에서 수행되었습니다. 프레임워크는 LLVM 최적화 레벨 (-O1부터 -O3까지), 휴리스틱 탐색 방법 (유전 알고리즘, 입자 군집 최적화), 그리고 독립적인 RL 에이전트와 비교되었습니다.

• 파레토 최적 해: RLMOE(DQN 및 PPO 모두 사용) 는 일관되게 베이스라인을 능가하여 더 낮은 에너지 소비와 더 작은 코드 크기를 가지면서도 경쟁력 있는 실행 시간을 유지하는 솔루션 공간 영역을 찾았습니다.
• 제약 조건 충족: 사용자 지정 에너지 제약 하에서 RLMOE 는 독립적인 RL 에이전트 (83–85%) 와 전통적인 최적화 레벨 (3–9%) 에 비해 훨씬 높은 일치율 (90–93%) 을 달성했습니다.
• 실행 시간 단축: 동일한 에너지 예산 하에서 MileStone 은 LLVM -O3 대비 최대 **45%**까지 실행 시간을 단축했습니다. 구체적으로, RLMOE-PPO 는 다양한 벤치마크에서 15–45% 의 감소를 보였습니다.
• 아키텍처 분석: 연구는 2 층 GCN 아키텍처가 예측 정확도와 과도 평활화 (oversmoothing) 문제 회피 사이의 최적 균형을 제공한다는 것을 확인했습니다.

5. 중요성과 주장

본 논문은 MileStone 이 다목적 컴파일러 단계 순서를 위한 효과적이고 확장 가능한 솔루션을 제공한다고 주장합니다. 그 중요성은 다음과 같습니다:

• 단일 목표 최적화를 넘어선 접근: 실행 시간, 코드 크기, 에너지 간의 트레이드오프 표면을 성공적으로 탐색하여 컴파일러가 특정 하드웨어 및 워크로드 요구 사항 (예: IoT 장치에서 에너지 효율성 우선순위) 에 적응할 수 있게 합니다.
• 효율성: GNN 기반 정적 예측과 RL 을 결합함으로써 완전 탐색과 반복적인 동적 프로파일링의 prohibitive 한 비용을 회피합니다.
• 적응성: 자기 진화 데이터베이스는 시스템이 시간이 지남에 따라 개선되도록 하여, 정적 휴리스틱이 놓치는 다양한 파레토 효율 구성을 포착합니다.

저자들은 정적 그래프 학습과 강화 기반 탐색을 통합하는 것이 복잡한 컴파일러 파이프라인을 최적화하는 강력한 길을 제공하며, 특히 여러 상충되는 성능 지표를 균형 있게 조정해야 하는 시나리오에서 그렇다고 결론지었습니다. 향후 작업은 프레임워크를 더 큰 산업용 워크로드로 확장하고, 상세한 마이크로아키텍처 모델을 통합하며, 동적 최적화 시나리오를 지원하도록 제안됩니다.