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

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

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

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