Размещение (автоматизация электронного проектирования)
Размещение является важным шагом в автоматизации электронного проектирования — частью физического проектирования. поток, который назначает точное расположение различных компонентов схемы в основной области чипа. Неправильное размещение не только повлияет на производительность чипа , но также может сделать его непригодным для производства из-за чрезмерной длины проводов, превышающей доступные ресурсы маршрутизации . Следовательно, специалист по россыпи должен выполнить задание, одновременно оптимизируя ряд задач, чтобы гарантировать, что схема соответствует требованиям к производительности. Вместе этапы размещения и маршрутизации при проектировании ИС называются местом и маршрутом .
Разместитель берет заданный список соединений синтезированных схем вместе с технологической библиотекой и создает действительный макет размещения. Компоновка оптимизирована в соответствии с вышеупомянутыми целями и готова к изменению размера и буферизации ячеек — шагу, необходимому для обеспечения синхронизации и целостности сигнала . Далее следует синтез дерева часов и маршрутизация , завершающие процесс физического проектирования. Во многих случаях части или весь процесс физического проектирования повторяется несколько раз, пока не завершение проекта будет достигнуто .
Особенности применения [ править ]
В случае интегральных схем специального назначения или ASIC область компоновки ядра чипа состоит из ряда рядов фиксированной высоты, с небольшим пространством между ними или без него. Каждая строка состоит из ряда мест, которые могут быть заняты компонентами схемы. Бесплатный сайт — это сайт, который не занят ни одним компонентом. Компонентами схемы являются стандартные ячейки, макроблоки или площадки ввода-вывода. [1] Стандартные ячейки имеют фиксированную высоту, равную высоте строки, но имеют переменную ширину. Ширина ячейки представляет собой целое число узлов.
С другой стороны, блоки обычно больше ячеек и имеют переменную высоту, что позволяет растягивать несколько строк. [1] Некоторые блоки могут иметь заранее назначенные местоположения (скажем, из предыдущего процесса планирования этажа), что ограничивает задачу укладчика назначением мест только для ячеек. В этом случае блоки обычно называются фиксированными блоками. Альтернативно, некоторые или все блоки могут не иметь заранее назначенных местоположений. В этом случае их необходимо разместить вместе с ячейками в так называемом смешанном режиме размещения.
Помимо ASIC, размещение сохраняет свою первостепенную важность в структурах вентильных матриц, таких как программируемые пользователем вентильные матрицы (FPGA). Здесь готовые транзисторы обычно располагаются рядами.(или «массивы»), разделенные каналами маршрутизации. [2] Размещение отображает подсхемы схемы в программируемые логические блоки FPGA таким образом, чтобы гарантировать завершение последующего этапа маршрутизации.
Цели и ограничения [ править ]
Размещение формулируется как ограниченная оптимизация . В частности, тактовый цикл чипа определяется задержкой его самого длинного пути, обычно называемого критическим путем. Учитывая характеристики производительности, установщик должен гарантировать, что не существует пути с задержкой, превышающей максимальную заданную задержку.
Другие ключевые ограничения включают в себя
- избежание дублирования компонентов схемы (экземпляров в списке соединений)
- размещение компонентов схемы в заранее определенных «местах»
Обычно существует несколько целей оптимизации, в том числе:
- Общая длина провода : сумма длин всех проводов в конструкции.
- Перегрузка маршрутизации : локальная перегрузка — это разница между длинами проводов в регионе и длиной трасс маршрутизации, доступных в этом регионе; локальные значения можно агрегировать несколькими способами, например путем сложения 10 % наибольших значений.
- Мощность : мощность динамического переключения зависит от длины проводов, которая, в свою очередь, зависит от расположения компонентов.
Кроме того, желательно быстро завершить процесс размещения.
Общая длина проводов обычно является основной целью большинства существующих россыпей и служит предшественником других оптимизаций, поскольку, например, мощность и задержка имеют тенденцию расти с увеличением длины проводов. Общая длина провода определяет потребность в маршрутизации и то, может ли она быть удовлетворена за счет обеспечения маршрутизации, определяемого доступными маршрутами маршрутизации. Однако очень короткие провода иногда приводят к тому, что потребность в местной маршрутизации превышает предложение местной маршрутизации. Такие ситуации часто требуют обходных маршрутов, что увеличивает длину проводов и задержки сигнала. Поэтому после предварительной оптимизации общей длины проводов также важно справиться с перегрузками маршрутизации.
При минимизации мощности обычно отмечаются провода с более высокими коэффициентами коммутационной активности и присваивается больший приоритет их укорочению. Если рядом расположено много «горячих» компонентов, может возникнуть горячая точка, что приведет к опасным температурным градиентам. В таких случаях компоненты можно разложить.
Основные техники [ править ]
Размещение делится на глобальное и детальное. Глобальное размещение вносит существенные изменения, распределяя все экземпляры по соответствующим местам в глобальном масштабе с возможностью незначительного перекрытия. При детальном размещении каждый экземпляр перемещается в ближайшее законное место с очень умеренными изменениями планировки. Размещение и общее качество дизайна больше всего зависят от глобальной производительности размещения.
Ранние методы размещения интегральных схем можно отнести к категории комбинаторной оптимизации . Для конструкций ИС с тысячами или десятками тысяч компонентов используется имитация отжига. [3] такие методологии, как TimberWolf [4] показывает лучшие результаты. Когда проекты микросхем выросли до миллионов компонентов, при их размещении использовалось разделение гиперграфов. [5] использование фреймворков вложенного секционирования, таких как Capo. [6] Комбинаторные методы напрямую предотвращают перекрытие компонентов, но затрудняют оптимизацию межсоединений в больших масштабах. Обычно они являются стохастическими и могут давать совершенно разные результаты для одного и того же ввода при многократном запуске.
Аналитические методы глобальной модели размещения соединяют длину непрерывной функцией и минимизируют эту функцию непосредственно с учетом ограничений плотности компонентов. Эти методы работают быстрее и лучше масштабируются, чем комбинаторные методы, но не предотвращают перекрытие компонентов и должны подвергаться постобработке комбинаторными методами для детального размещения. Квадратичное размещение — это ранний аналитический метод, который моделирует длину межсоединений с помощью квадратичной функции и использует высокопроизводительные методы квадратичной оптимизации. При разработке он продемонстрировал конкурентоспособное качество результатов, а также стабильность, в отличие от комбинаторных методов. ГОРДИЕВ [7] формулирует стоимость длины провода как квадратичную функцию, сохраняя при этом разделение ячеек посредством рекурсивного разделения. Алгоритм [8] моделирует плотность размещения как линейный член квадратичной функции стоимости и решает проблему размещения с помощью чистого квадратичного программирования. Распространенным усовершенствованием является взвешивание каждой цепи на величину, обратную ее длине на предыдущей итерации. При условии, что процесс сходится, это минимизирует объективную линейную зависимость от длины провода. [9] Большинство современных россыпей квадратной формы (KraftWerk, [10] ФастПлейс, [11] простота [12] ) следуют этой схеме, каждая из которых имеет разные эвристики определения силы линейной плотности.
Нелинейное размещение моделирует длину провода с помощью экспоненциальных (нелинейных) функций и плотность с помощью локальных кусочно-квадратичных функций, чтобы добиться большей точности и, следовательно, улучшения качества. [13] Последующая академическая работа включает APlace. [14] и НТУплейс. [15]
ePlace [16] это современный глобальный алгоритм размещения. Он разделяет экземпляры путем моделирования электростатического поля, что минимизирует затраты на качество и обеспечивает хорошую производительность.
В 2021 году Google Brain сообщил о хороших результатах использования методов искусственного интеллекта (в частности, обучения с подкреплением) для решения проблемы размещения. [17] Однако этот результат весьма спорен, [18] [19] [20] поскольку статья не содержит прямых сравнений с существующими россыпями, и ее трудно воспроизвести из-за запатентованного содержания. По крайней мере один изначально положительный комментарий был отозван после дальнейшего рассмотрения. [21]
См. также [ править ]
- Автоматизация электронного проектирования
- Процесс проектирования (EDA)
- Разработка интегральных схем
- План этажа (микроэлектроника)
- Место и маршрут
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б А. Кан, Дж. Лиениг, И. Марков, Дж. Ху: «Физическое проектирование СБИС: от разделения графов к временному замыканию», Springer (2022), дои : 10.1007/978-90-481-9591-6 , ISBN 978-3-030-96414-6 , стр. 10-13.
- ^ А. Кан, Дж. Лиениг, И. Марков, Дж. Ху: «Физическое проектирование СБИС: от разделения графов к временному замыканию», Springer (2022), дои : 10.1007/978-90-481-9591-6 , ISBN 978-3-030-96414-6 , стр. 14-15.
- ^ С. Киркпатрик, CDG-младший и член парламента Векки (1983). «Оптимизация путем моделирования отжига». Наука . 220 (4598): 671–680. Бибкод : 1983Sci...220..671K . дои : 10.1126/science.220.4598.671 . ПМИД 17813860 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ К. Сечен и А. Санджованни-Винсентелли (1986). «TimberWolf3.2: новый стандартный пакет размещения ячеек и глобальной маршрутизации». Материалы конференции по автоматизации проектирования . АКМ. стр. 432–439.
- ^ Джордж Карипис, Раджат Аггарвал, Випин Кумар и Шаши Шекхар (1997). «Многоуровневое секционирование гиперграфа: приложения в домене СБИС». Материалы конференции по автоматизации проектирования . АКМ. стр. 526–529.
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Колдуэлл, AE; Кан, AB; Марков, Иллинойс (июнь 2000 г.). «Может ли рекурсивное деление пополам создавать маршрутизируемые размещения?». Материалы 37-й конференции по автоматизации проектирования . стр. 477–482. дои : 10.1109/DAC.2000.855358 .
- ^ Кляйнханс, Дж. М.; Зигль, Г.; Йоханнес, FM; Антрейх, К.Дж. (март 1991 г.). «ГОРДИАН: размещение СБИС с помощью квадратичного программирования и оптимизации нарезки». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 10 (3): 356–365. дои : 10.1109/43.67789 . S2CID 15274014 .
- ^ Х. Эйзенманн и Ф.М. Йоханнес (1998). «Общее глобальное размещение и планировка». Материалы конференции по автоматизации проектирования . АКМ. стр. 269–274.
- ^ Зигль, Георг, Конрад Долл и Фрэнк М. Йоханнес (1991). «Аналитическое размещение: линейная или квадратичная целевая функция?». Материалы 28-й конференции по автоматизации проектирования ACM/IEEE . АКМ. стр. 427–432.
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ П. Шпиндлер, У. Шлихтманн и Ф.М. Йоханнес (2008). «Kraftwerk2 - быстрый подход к квадратичному размещению, управляемый силой, с использованием точной сетевой модели». Транзакции IEEE в области автоматизированного проектирования . 27 (8): 1398–1411. дои : 10.1109/TCAD.2008.925783 . S2CID 16054185 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Н. Вишванатан, М. Пан и К. Чу (2007). «FastPlace3.0: быстрый многоуровневый алгоритм квадратичного размещения с контролем перегрузки размещения». Материалы конференции по автоматизации проектирования в Азиатско-Южно-Тихоокеанском регионе . стр. 135–140.
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Ким, М.-К.; Ли Д.-Дж.; Марков И.Л. (январь 2011). «SimPL: эффективный алгоритм размещения». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 31 (1): 50–60. CiteSeerX 10.1.1.187.1292 . дои : 10.1109/TCAD.2011.2170567 . S2CID 47293399 .
- ^ США 6301693 , У. К. Нейлор, Р. Донелли и Л. Ша, «Система и метод нелинейной оптимизации для оптимизации длины провода и задержки для автоматического устройства для установки электрических цепей».
- ^ AB Канг, С. Реда и К. Ван (2005). «Архитектура и детали высококачественной крупномасштабной аналитической россыпи». Материалы международной конференции по компьютерному проектированию . стр. 891–898.
- ^ Т.-Ц. Чен, З.-В. Цзян, Т.-Ц. Сюй, Х.-К. Чен и Ю.-В. Чанг (2008). «NTUPlace3: аналитическое средство для крупномасштабных проектов смешанного размера с предварительно размещенными блоками и ограничением плотности» (PDF) . Транзакции IEEE в области автоматизированного проектирования . 27 (7): 1228–1240. дои : 10.1109/TCAD.2008.923063 . S2CID 11912537 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Дж. Лу, П. Чен, К.-К. Чанг, Л. Ша, DJ-S. Хуанг, К.-К. Тенг и К.-К. Ченг (2014). «ePlace: размещение на основе электростатики с использованием метода Нестерова». Материалы конференции по автоматизации проектирования . АКМ. стр. 1–6.
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Азалия Мирхосейни, Анна Голди, Мустафа Язган (2021). «Методология размещения графов для быстрого проектирования чипов». Природа . 594 (7862): 207–212. arXiv : 2004.10746 . Бибкод : 2021Natur.594..207M . doi : 10.1038/s41586-021-03544-w . ПМИД 34108699 . S2CID 235395490 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Ченг, Чунг-Куан, Эндрю Б. Кан, Саяк Кунду, Ючэн Ван и Чжан Ван (март 2023 г.). «Оценка обучения с подкреплением для размещения макросов». Материалы Международного симпозиума по физическому дизайну 2023 года . стр. 158–166. arXiv : 2302.11014 . дои : 10.1145/3569052.3578926 . ISBN 978-1-4503-9978-4 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Игорь Львович Марков. «Ложный рассвет: переоценка обучения Google с подкреплением для размещения макросов чипов». arXiv : 2306.09633 .
- ^ Агам Шах (3 октября 2023 г.). «Спорная бумага Google для чипов искусственного интеллекта снова под пристальным вниманием» .
- ^ Кан, Эндрю Б. (2021). «ОТКАЗАННАЯ СТАТЬЯ: Система искусственного интеллекта превосходит людей в разработке планов этажей для микрочипов» . Природа . 594 (7862): 183–185. Бибкод : 2021Natur.594..183K . дои : 10.1038/d41586-021-01515-9 . ПМИД 34108693 . S2CID 235394411 .