Геометрия кристалла: строгий математический порядок расставил миллиарды транзисторов и сократил провода
Глобальное размещение смешанного размера одновременно оптимизирует расположение крупных макросов и миллионов стандартных ячеек в современной физической конструкции сверхкрупномасштабной интеграции (СБИС). Современные аналитические россыпи обеспечивают высокую масштабируемость, но их нелинейные цели и управление плотностью делают их чувствительными к первоначальному размещению. В этой статье представлена геометрическая структура, которая формулирует инициализацию размещения как квадратичную программу с квадратичными ограничениями (QCQP) с центроидом первого порядка и ограничениями расширения второго порядка. Явные цели распределения смешанного размера определяются на основе геометрии матрицы и размеров объекта, что позволяет получить стабильные значения ограничений даже при экстремальных изменениях размеров. Изменение масштаба матрицы ограничений с учетом использования предотвращает патологическое распространение, когда фиксированные объекты занимают значительную площадь кристалла. Затем QCQP преобразуется в оптимизацию многообразия Стифеля посредством метрического выравнивания и центрирующей проекции, что делает основную геометрическую структуру явной. Полученная в результате квадратичная цель с ограничениями Штифеля допускает эффективную крупномасштабную оптимизацию с помощью метода римановых последовательных подпространств (SSM). Разрежение циклов с сортировкой по углам для многоконтактных цепей периодически сохраняет лапласову аппроксимацию разреженной, но геометрически согласованной. В качестве встроенного инициализатора для существующих аналитических россыпей наш метод обеспечивает улучшение взвешенной длины провода по половине периметра (wHPWL): среднее значение 13.8% при RePlAce в четырех тестах TILOS, поддерживаемых его потоком, 3.5% при DREAMPlace во всех 20 тестах и 4.8% при AutoDMP в 19 тестах со сходящимися базовыми линиями. Оценка после трассировки показывает, что эти улучшения перед трассировкой распространяются на проекты трассировки: длина трассируемого провода уменьшается на 1,1 до 2.3% по всем трем тестам. Площадь и мощность стандартной ячейки также уменьшаются во всех трех случаях. Нарушения правил проектирования (DRC) уменьшаются в двух из трех случаев.
## В чем суть открытия На протяжении полувека закон Мура держался на способности инженеров уплотнять транзисторы. Однако сегодня на площади кристалла соседствует разношерстный мегаполис: колоссальные блоки встроенной памяти возвышаются над морем крошечных логических ячеек, превосходя их по площади в тысячи раз. Когда алгоритмы пытаются найти положение для каждого компонента, они сталкиваются с чудовищной многомерной оптимизацией. Парадокс кремниевой индустрии заключался в том, что лучшие оптимизаторы всегда стартовали почти вслепую — со случайной или грубой расстановки. Попав в неудачную конфигурацию, вычислительный конвейер запутывался в локальных минимумах: гигантские блоки перекрывали друг друга или вылетали за границы кристалла. Исследователи доказали, что эту хаотичную фазу можно обойти, подчинив начальное распределение строгой геометрии искривленных пространств. ## Как это устроено: принцип работы Создатели метода взглянули на расстановку элементов не как на раскладку коробок, а как на движение в искривленном многообразии Штифеля — пространстве ортогональных матриц. Физическая задача требует компромисса: логика тянет элементы друг к другу, но компоненты обязаны равномерно заполнять чип без наложений. Авторы математически упаковали индивидуальные размеры каждого макроблока и свободную площадь чипа в квадратичные ограничения разброса. Метрическое выравнивание превратило физические запреты в естественное геометрическое свойство — ортонормированность на многообразии Штифеля. Чтобы быстро найти решение среди миллионов переменных, авторы применили метод последовательных подпространств. Вместо перебора всех координат строится маломерное касательное подпространство размерности не более восьми. На каждом шаге совершается криволинейный шаг по геодезической линии многообразия, сохраняя допустимость решения. Для многоконтактных сетей применяется циклическая аппроксимация: контакты сортируются по углу вокруг центра тяжести сети, что гарантирует разреженность уравнений без потери топологии. ## Результаты и доказательства Подход проверили на двадцати признанных бенчмарках (наборы MMS и TILOS) объемом до двух с половиной миллионов ячеек. Метод интегрировали в три открытые системы проектирования: RePlAce, DREAMPlace и AutoDMP. Во всех тестах геометрический старт превзошел стандартные эвристики. В RePlAce длина соединений сократилась в среднем на 13,8%, а на процессоре NVDLA — на рекордные 36,2%. В DREAMPlace среднее улучшение составило 3,5%, а в AutoDMP — 4,