기술 요약: OrderPlace

문제 정의

매크로 배치(Macro placement)는 현대 칩 물리 설계에서 매우 중요한 단계로, 최종 집적 회로의 품질, 성능 및 제조 가능성을 근본적으로 결정합니다. 형식적으로, 이는 고정된 캔버스 내에서 중첩 없이 매크로의 물리적 위치를 결정해야 하는 대규모 조합 최 optimization 문제입니다. 최근의 머신러닝 발전이 좌표 결정 속도를 높였으나, 배치 순서의 시간적 차원(즉, 어떤 순서로 매크로를 배치할 것인가)은 여전히 정적 휴리스틱이나 무작위 순열에 의해 지배되고 있습니다.

본 논문은 배치 순서가 단순한 전처리 단계가 아니라 최적화를 결정짓는 핵심 요소라고 주장합니다. 순차적 배치 프로세스에서 초기 결정은 이후 모든 매크로에 대한 가용 경계 조건을 정의합니다. 시퀀스의 초기에 발생한 단 한 번의 하위 최적(suboptimal) 배치는 돌이킬 수 없는 "도미노 효과"를 유발하여 솔루션 공간을 제약하고 좋지 않은 지역 최적점(local optima)으로 이끌 수 있습니다. 그럼에도 불구하고, 기존 방법들은 주로 "어디에 배치할 것인가?"라는 공간적 질문에 집중하며, "누가 먼저 갈 것인가?"라는 시간적 질문은 고정된 사전 정보(prior)로 취급합니다. 더욱이, 순서 신호는 강력한 정제 방법들에 의해 가려지는 경우가 많고, 단일 시퀀스를 평가하기 위해서는 전체 배치 사이클을 실행해야 하는 막대한 계산 비용이 발생하기 때문에 순서의 영향을 탐구하는 것은 매우 어렵습니다.

방법론: OrderPlace

이러한 과제를 해결하기 위해 저자들은 매크로 배치 순서 전략을 자동으로 발견하도록 설계된 프록시 가이드형 대규모 언어 모델(LLM) 진화 프레임워크인 OrderPlace를 제안합니다. 이 프레임워크는 세 가지 주요 구성 요소로 작동합니다.

1. 초기 배치 순서 전략

프레임워크는 다양한 탐색 공간을 제공하기 위해 전략의 모집단을 초기화합니다. 이들은 다음과 같이 분류됩니다:

• 정적 전략 (Static Strategies): 매크로 수준의 기하학적 및 위상적 특징(예: 면적, 차수, 넷 연결성)만을 기반으로 우선순위를 계산합니다.
• 동적 전략 (Dynamic Strategies): 물리적 역학(예: 스프링 포텐셜, 필드 모델, 엔트로피 감소)에서 영감을 얻어, 변화하는 배치 상태에 따라 우선순위를 조정합니다.

2. LLM 기반 전략 진화

OrderPlace는 LLM(예: GPT-4, DeepSeek-V3, Claude)을 사용하여 코드 수준의 순서 전략을 진화시킵니다. 이 과정은 다음과 같습니다:

• 프롬프트 엔지니어링: LLM에 VLSI 전문가 역할을 정의하는 시스템 프롬프트와 이전 세대의 상위 성능 전략(Top-K)에 대한 평가 결과를 포함하는 사용자 프롬프트를 제공합니다.
• 코드 생성: LLM은 정적 정렬기(static sorters) 또는 동적 우선순위 함수로서의 새로운 Python 클래스를 생성합니다.
• 진화 루프: 프레임워크는 세대에 걸쳐 전략의 모집단을 유지합니다. 적합도 점수(fitness scores)를 기준으로 상위 K개의 전략을 선택하고, 이를 컨텍스트로 사용하여 새로운 후보 전략을 생성함으로써 새로운 조합과 동적 메커니즘의 발견을 촉진합니다.

3. 프록시 가이드 평가

모든 후보에 대해 전체 규모의 최적화를 수행하는 데 드는 과도한 비용을 완화하기 위해, OrderPlace는 경량 프록시 평가 메커니즘을 도입합니다.

• Wire-Mask-Guided Greedy Procedure: 전체 최적화 대신, 미리 계산된 와이어 길이 마스크(wire-length masks)에 의해 가이드되는 결정론적 그리디 배치 알고리즘을 사용하여 전략을 평가합니다.
• 병렬 몬테카를로 (Parallel Monte Carlo): 각 전략을 여러 개의 무작위 초기 시드에서 병렬로 실행하여 반둘레 와이어 길이(HPWL) 결과의 분포를 생성합니다.
• 적합도 점수 산출: 전략의 적합도는 성공적인 실행에 대한 평균 HPWL입니다. 타임아웃 메커니즘과 구문 검증을 통해 효율성과 견고성을 보장합니다.

진화적 탐색이 완료되면, 상위 K개 전략은 최종 배치 결과를 생성하기 위해 와이어 마스크 가이드 그리디 절차를 통해 미세 조정(fine-tuning)됩니다.

주요 기여

1. 관점의 전환: 본 논문은 배치 순서가 최적화의 핵심적이면서도 역사적으로 간과되어 온 차원이라는 이론적 및 경험적 증거를 제공합니다. 이는 하위 최적의 순서가 솔루션 품질의 점진적 저하(예: 체인 토폴로지의 경우 $\Omega(l)$, 스타 토폴로지의 경우 $\Theta(g)$ 저하)를 초래함을 입증합니다.
2. 방법론적 혁신: OrderPlace는 매크로 배치 순서링을 위해 특별히 설계된 최초의 LLM 기반 진화 프레임워크입니다. 이 프레임워크는 플로어플래닝 최적화의 값비싼 피드백 루프 문제를 해결하기 위해 프록시 평가를 성공적으로 통합했습니다.
3. 새로운 전략의 발견: 프레임워크는 수동으로 제작된 휴리스틱을 능가하는, 정적 휴리스틱부터 복잡한 물리 기반 동적 규칙(예: 중력 모델, 엔트로피 감소, 넷 폐쇄 우선순위 등)에 이르는 일반화 가능한 정렬 알고리즘을 발견합니다.

실험 결과

저자들은 표준 ISPD 2005 벤치마크 세트(8개의 칩 설계)를 통해 OrderPlace를 평가했습니다.

• 성능: OrderPlace는 8개 회로 중 7개에서 가장 낮은(최상의) HPWL 값을 달 {%} 달성했습니다.
• 비교:
  • WireMask-EA와 비교했을 때, OrderPlace는 와이어 길이를 34.04% 감소시켰습니다.
  • 최첨단 방법인 EGPlace와 비교했을 때, OrderPlace는 와이어 길이를 14.08% 감소시켰습니다.
  • Wilcoxon rank-sum test를 사용한 직접 비교에서, OrderPlace는 EGPlace에 비해 7개의 회로에서 유의미하게 더 우수한 성능을 보였습니다.
• 수렴성: OrderPlace는 현저한 계산 효율성을 보여주었으며, EGPlace보다 훨씬 빠르게 수렴했습니다. 발견된 최적의 전략은 최적화 궤적의 초기 단계에서 일관되게 더 낮은 수렴점에 도달했습니다.
• 혼잡도 및 혼합 크기: OrderPlace는 우수한 라우터빌리티(혼잡도)를 보여주었으며, 글로벌 플레이서(DreamPlace)와 결합했을 때 혼합 크기 배치 작업에서 선도적인 성능을 달성했습니다.
• LLM의 영향: 절제 연구(Ablation studies)를 통해 LLM이 생성한 전략이 모든 수동 제작 초기 전략보다 일관되게 우수함을 확인하였으며, 이는 성능 향상이 기존 휴리스틱을 넘어서는 비자명한(non-trivial) 순서 정책의 발견에서 비롯됨을 나타냅니다.

의의 및 주장

본 논문은 배치 순서가 전통적으로 정적인 전처리 단계로 간주되어 왔으나, 배치 최적화의 결정적인 결정 요인 역할을 한다는 것을 보여주는 최초의 체계적인 증거라고 주장합니다. LLM과 프록시 평가를 통해 순서 발견을 자동화함으로써, 이 방법은 순서 결정 기반 배치에서의 하위 최적 문제를 효과적으로 완화합니다.

저자들은 이 접근 방식이 순서를 고정된 사전 정보로 취对待하거나 RL 에이전트에 의존하여 암묵적으로 순서를 학습하는 이전 연구들과 구별된다는 점을 강조합니다. 대신, OrderPlace는 입력 순서를 하이퍼파라미터로서 명시적으로 최적화합니다. 이 연구는 배치 순서의 최적화 잠재력이 "잠들어 있던" 차원이며, 이를 해제하면 그리디 솔버를 근본적으로 가속화하고 더 나은 글로벌 솔루션을 열 수 있음을 시사합니다.

한계점: 본 연구는 현재 마스크 가이드 그리디 방법에서 배치 순서의 영향을 평가하는 데 국한되어 있습니다. 확률적이고 학습 기반인 방법들과의 상호작용은 아직 탐구되지 않았으며, 향후 연구에서는 배치 순서 지정이 딥러닝 기반 배치 방법을 어떻게 향상시킬 수 있는지 조사할 것을 제안합니다.