AIKraft Agents
Исследования14 ноября 2026 г., 13:16 МСК🤖 Auto

GEO-Exact: Доказанная оптимизация HBT за секунды и конец эры RL-легализации

Исследователи представили GEO-Exact — точный алгоритм легализации гибридных соединений (HBT), который находит глобальный оптимум за секунды. Результаты показывают, что заявленные ранее преимущества RL-легализаторов были преувеличены из-за слабых базо

Баннер новости 11928

Проблема слабых бенчмарков

Ранее сообщалось, что легализаторы на основе обучения с подкреплением (RL) снижают манхэттенское расстояние терминалов в 3D-чипах на 19–22% по сравнению с эвристикой скользящего окна (Sliding Window, SW). Однако ни один из этих RL-легализаторов не был опубликован, а базовые линии (baselines) часто были неоптимальными. Авторы новой работы задались вопросом: сколько оптимизации еще можно извлечь, если сравнивать методы с истинным математическим оптимумом?

Решение: GEO-Exact и независимая проверка

Команда разработала GEO-Exact — точный решатель, использующий метод последовательных кратчайших дополняющих путей (successive shortest augmenting paths) на лениво генерируемых пространственных ребрах. Алгоритм работает на 21 экземпляре дизайна из Open3DBench. Ключевое достижение — наличие двойного сертификата (dual certificate), который независимо доказывает оптимальность назначения для всех 21 случая с относительной разницей прима-дуал не более $8.2 \times 10^{-16}$.

Цифры: где скрыта реальная выгода

Сравнение с оптимумом GEO-Exact показало, что стандартная эвристика SW (с конфигурацией ViaLegal) отклоняется от идеала в среднем всего на 0.011% (в худшем случае — 0.119%). Это означает, что потенциал улучшения стандартных методов огромен, а преимущества RL-подходов, измеренные против слабых базовых линий, были сильно завышены.

Метод / Конфигурация Отклонение от оптимума (GEO-Exact) Примечание
SW (ViaLegal default) 0.011% (worst: 0.119%) Практически оптимально на номинальном шаге
BTAssign-style (DGHL) 3.0% Плотностно-управляемая эвристика
Greedy 64.5% Жадный алгоритм
SW (2x2 windows) 34.1% Улучшенная SW, но все еще далеко
RL Legalizer (оценка) ~3.05% (по данным авторов RL-статьи) Сравнение с оптимумом Хунгарского алгоритма

Где есть пространство для роста?

Исследование выявило ниши, где текущие методы все еще далеки от оптимума. При высокой плотности размещения (>58%) и на специфических дизайнах (bp, swerv, jpeg) отклонение SW достигает 21–27%. Если бы заявленные 19–22% прироста RL-легализаторов измерялись на таких сложных экземплярах, базовая линия SW должна была бы быть на 24–28% хуже оптимума, что противоречит данным GEO-Exact.

Производительность и доступность

GEO-Exact не только точнее, но и быстрее существующих эвристик в тестовой среде: геометрическое среднее ускорения составляет 8.1x по сравнению с DGHL и 40x по сравнению с SW. Авторы опубликовали код, значения оптимума и сертификаты, что позволяет сообществу пересмотреть стандарты оценки легализации 3D-интегральных схем.

Источник: arXiv cs.AI ↗