Global placement в VLSI: аналитические методы и квадратичный оптимальный транспорт

Доклад посвящён задаче global placement в VLSI (very large scale integration) — одному из ключевых этапов физического проектирования интегральных схем. Цель этого этапа состоит в определении положения элементов схемы в заданной области размещения так, чтобы минимизировать суммарную длину соединений и одновременно обеспечить допустимую плотность размещения. 

Рассматривается математическая постановка задачи и классические аналитические подходы на примере ePlace и NTUplace3. Обсуждаются характерные для аналитического размещения техники: сглаживание недифференцируемой метрики HPWL, квадратичная модель Bound2Bound, а также ускоренные градиентные методы оптимизации. 

Далее рассматривается альтернативный подход без сглаживающих аппроксимаций, основанный на квадратичном оптимальном транспорте. Выравнивание плотности в нём формулируется как перераспределение площади элементов между областями размещения с минимальной квадратичной транспортной энергией. Также обсуждается интерпретация транспортного поля как электрического потока между областями с различной плотностью.