DiffRMST: 전역 배치용 GPU 가속 완전 미분 가능 직교 최소 신장 트리 와이어 길이 모델

요약

본 논문은 반도체 설계 분야의 분석적 전역 배치(global placement)를 위해 완전 미분 가능한 직교 최소 신장 트리 와이어 길이 모델인 DiffRMST를 제안합니다. 기존 방법들이 가진 이산성 및 비미분 가능 문제를 공간 스무딩과 로그-합-지수 기법으로 해결하여, 토폴로지를 인식하는 기울기 기반 최적화를 가능하게 했습니다. GPU 구현을 통해 전역 배치 속도를 크게 향상시켰습니다.

핵심 포인트

• DiffRMST는 분석적 배치를 위한 완전 미분 가능한 RMST 와이어 길이 모델이다.
• 공간 스무딩과 log-sum-exp 기법으로 이산성을 연속 분포로 정의했다.
• 키르히호프 행렬-트리 정리를 활용하여 기울기 기반 최적화를 구현했다.
• GPU 구현을 통해 전역 배치 속도를 8개 스레드 CPU 대비 평균 $14.7 imes$ 향상시켰다.