PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimization

기술 요약: PrefixAgent

문제 정의
프리픽스 가산기(Prefix adders)는 디지털 시스템의 핵심적인 산술 회로이지만, 비트 폭이 커짐에 따라 설계 공간이 기하급수적으로 증가하여 전수 조사가 불가능합니다. 전통적인 설계 방법론은 정형화된 구조(예: Kogge–Stone, Brent–Kung)나 수동 최적화에 의존하며, 이는 다양한 타이밍 제약 조건과 비균일한 입력 도착 시간 하에서 면적, 지연 시간, 전력을 균형 있게 조절하는 데 실패하는 경우가 많습니다. 이를 자동화하기 위해 머신러닝 접근 방식(RL, VAE, MCTS)이 제안되기도 했으나, 새로운 시나리오에 대한 재학습 요구로 인해 일반화 성능이 떨어지고 확장성 문제가 있으며, 거대한 액션 공간을 탐색하는 데 비효효율적입니다. 또한, 회로 설계 분야에서의 기존 대규모 언어 모델(LLM) 활용은 두 가지 결정적인 한계에 직면해 있습니다: (1) 20개 이상의 노드를 가진 복잡한 그래프를 효율적으로 추론하지 못한다는 점, (2) 특정 최적화 작업을 위해 모델을 미세 조정(fine-tuning)할 수 있는 고품질의 해석 가능한 학습 데이터가 부족하다는 점입니다.

방법론
본 논문은 두 단계의 분해(two-phase decomposition)와 도구 통합 추론(tool-integrated reasoning, TIR) 패러다임을 통해 이러한 과제를 해결하는 LLM 기반 설계 프레임워크인 PrefixAgent를 제안합니다.

1. 두 단계 분해 (Two-Phase Decomposition):

   • 1단계 (백본 최적화 - Backbone Optimization): 전체 프리픽스 그래프를 직접 생성하는 대신, 본 프레임워크는 문제를 "백본 합성(backbone synthesis)"과 "국소 구조 정제(local structure refinement)"로 분해합니다. 백본은 최상위 비트(MSB)의 캐리를 계산하는 서브그래프로 정의됩니다. 이는 설계 공간을 카탈랑 수(Catalan numbers)의 곱 형태에서 단일 카탈랑 수의 관계로 축소시켜 복잡성을 크게 단순화합니다. LLM은 초기 직렬 백본 구조를 바탕으로 "재그룹화(regroup)" 연산(서브트리 재구성)을 수행하여 그룹화 패턴을 최적화함으로써 백본을 반복적으로 정제합니다.
   • 2단계 (국소 구조 정제 - Local Structure Refinement): 최적화된 백본이 구축되면, 보조 노드들을 추가하여 전체 프리픽스 가산기를 구성합니다. 이후 LLM은 물리적 구현 도구로부터 얻은 피드백을 바탕으로 타이밍 위반을 해결하기 위해 국소적 구조 정제(예: 레벨 최적화, 팬아웃 감소, 노드 클로닝)를 수행합니다.

2. 도구 통합 추론 (Tool-Integrated Reasoning, TIR):
   PrefixAgent는 대규모 추론 모델(LRM)이 외부 도구에 정밀한 구조적 수정을 위임할 수 있도록 함수 호출(function calling) 기능을 채택합니다. LLM은 고수준의 의사결정(무엇을, 어디를 최적화할 것인가)에 집중하고, 외부 도구는 수정 사항을 실행하고 피드백(예: 타이밍 정보가 포함된 S-expression, 물리적 지표)을 제공합니다. 이는 고수준 추론과 알고리즘적 정밀도 사이의 간극을 메워줍니다.

3. E-Graph 기반 데이터 생성:
   고품질 학습 데이터의 부족 문제를 해결하기 위해, 저자들은 e-graph와 등가 포화(equality saturation) 기술을 활용합니다. 이들은 백본 구조를 S-expression으로 표현하는 도메인 특화 중간 언어(BackboneLang)를 정의합니다. e-graph 내에서 결합 법칙 재작성 규칙(associativity rewrite rules)을 적용함으로써 솔루션 공간을 체계적으로 탐색합니다. 프레임워크는 타이밍 인식 비용 함수를 사용하여 최적화된 백본 후보를 추출하고, e-graph 설명자(explabler)를 사용하여 해석 가능한 재작성 궤적(rewrite trajectories)을 생성합니다. 이 궤적들은 LRM을 미세 조정하기 위한 사고 사슬(Chain-of-Thought, CoT) 추론 데이터를 합성하는 그라운드 트루스(ground truth)로 사용됩니다.

주요 기여

• PrefixAgent 프레임워크: 프리픽스 가산기 최적화를 64비트 설계까지 확장 가능하게 하며, 상용 도구를 능가하는 최초의 LLM 기반 접근 방식입니다.
• 새로운 설계 관점: 백본 생성과 국소 정제를 분리하는 분해 전략을 통해 효율적인 추론과 결함 없는(zero-deficiency) 가산기 합성을 가능하게 합니다.
• 데이터 생성 패러다임: e-graph를 사용하여 LRM 미세 조정을 위한 대규모의 고품질 및 해석 가능한 최적화 궤적을 생성하는 체계적인 방법을 제시하여, 회로 설계의 데이터 부족 문제를 극복했습니다.
• 도구 통합 추론: LLM이 실행을 위해 외부 도구를 호출하는 컨트롤러 역할을 수행하는 아키텍처를 통해 구조적 유효성과 물리적 실현 가능성을 보장합니다.

실험 결과
NanGate45 라이브러리와 OpenROAD 플로우를 사용하여, 생성된 데이터셋으로 미세 조정된 QwQ-32B 모델을 대상으로 균일 및 비균일 입력 도착 시간 프로파일 하에서 실험을 진행했습니다.

• 성능: PrefixAgent는 거의 모든 구성에서 베이스라인 방법들(DP, MCTS, RL, VAE, PrefixGPT 포함)보다 작은 면적의 프리픽스 가산기를 합성합니다. 면적 이점은 비트 폭이 커질수록 현저히 커집니다 (예: 64비트에서 최적의 베이스라인 대비 최대 11.3% 감소).
• 일반화: 본 프레임워크는 강력한 일반화 성능을 입증하였으며, 훈련 세트에 존재하지 않았던 미학습 비트 폭(예: 54비트) 및 비균일 도착 프로파일에서도 우수한 결과를 달رشف었습니다.
• 효율성: PrefixAgent는 새로운 시나리오마다 재학습을 수행할 필요 없이 LRM의 유도에 따라 타겟 최적화를 수행하므로, 탐색 기반 베이스라인(MCTS, RL, VAE) 대비 10배 이상의 속도 향상을 달성했습니다.
• 상용 플로우: 32nm 공정 기술의 상용 물리 설계 플로에서 평가했을 때, PrefixAgent가 생성한 가산기는 상용 합성 도구보다 더 작은 면적을 유지했습니다.
• 절제 연구 (Ablation Studies): 실험 결과는 2단계 정제의 필요성, LLM 추론을 위한 그리드/인접 리스트 인코딩 대비 향상된 프리픽스 표현(EPR)의 우수성, 그리고 고품질 결과를 얻기 위한 CoT 추론의 결정적인 역할을 확인시켜 줍니다.

의의
본 논문은 PrefixAgent가 산술 회로 설계 자동화의 중요한 진전임을 주장합니다. 복잡한 설계 작업을 관리 가능한 하위 문제로 분해하고, 고품질 데이터 생성을 위해 e-graph를 활용함으로써 기존 ML 기반 방식의 확장성 및 일반화 한계를 극복했습니다. 이 프레임워크는 LLM이 도구 통합을 통해 적절히 유도되고 해석 가능한 추론 궤적으로 미세 조정될 때, 복잡한 설계 공간을 효과적으로 탐색하여 전통적인 휴리스틱과 상용 EDA 도구를 모두 능가할 수 있음을 보여줍니다. 저자들은 이 데이터 생성 패러다임과 분해 전략이 곱셈기 최적화와 같은 다른 데이터패스 최적화 작업으로도 확장될 수 있다고 제안합니다.