stringtranslate.com

Размещение (автоматизация электронного проектирования)

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

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

Особенности применения

В случае специализированных интегральных схем или ASIC область компоновки ядра чипа состоит из ряда рядов фиксированной высоты, с небольшим пространством между ними или без него. Каждая строка состоит из ряда мест, которые могут быть заняты компонентами схемы. Бесплатный сайт — это сайт, который не занят ни одним компонентом. Компонентами схемы являются стандартные ячейки, макроблоки или площадки ввода-вывода. [1] Стандартные ячейки имеют фиксированную высоту, равную высоте строки, но имеют переменную ширину. Ширина ячейки представляет собой целое число узлов.

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

Помимо ASIC, размещение сохраняет свою первостепенную важность в структурах вентильных матриц, таких как программируемые пользователем вентильные матрицы (FPGA). Здесь готовые транзисторы обычно располагаются рядами (или «массивами»), которые разделены каналами маршрутизации. [2] Размещение отображает подсхемы схемы в программируемые логические блоки FPGA таким образом, чтобы гарантировать завершение последующего этапа маршрутизации.

Цели и ограничения

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

Другие ключевые ограничения включают в себя

Обычно существует несколько целей оптимизации, в том числе:

Кроме того, желательно быстро завершить процесс размещения.

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

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

Основные техники

Размещение делится на глобальное и детальное. Глобальное размещение вносит существенные изменения, распределяя все экземпляры по соответствующим местам в глобальном масштабе с возможностью незначительного перекрытия. При детальном размещении каждый экземпляр перемещается в ближайшее законное место с очень умеренными изменениями планировки. Размещение и общее качество дизайна больше всего зависят от глобальной производительности размещения.

Ранние методы размещения интегральных схем можно отнести к категории комбинаторной оптимизации . Для конструкций ИС с тысячами или десятками тысяч компонентов наилучшие результаты показывают методы моделирования отжига [3], такие как TimberWolf [4] . Когда проекты ИС выросли до миллионов компонентов, при размещении стало использоваться разделение гиперграфов [5] с использованием фреймворков вложенного разделения, таких как Capo. [6] Комбинаторные методы напрямую предотвращают перекрытие компонентов, но затрудняют оптимизацию межсоединений в больших масштабах. Обычно они являются стохастическими и могут давать совершенно разные результаты для одного и того же ввода при многократном запуске.

Аналитические методы глобальной модели размещения соединяют длину непрерывной функцией и минимизируют эту функцию непосредственно с учетом ограничений плотности компонентов. Эти методы работают быстрее и лучше масштабируются, чем комбинаторные методы, но не предотвращают перекрытие компонентов и должны подвергаться постобработке комбинаторными методами для детального размещения. Квадратичное размещение — это ранний аналитический метод, который моделирует длину межсоединений с помощью квадратичной функции и использует высокопроизводительные методы квадратичной оптимизации. При разработке он продемонстрировал конкурентоспособное качество результатов, а также стабильность, в отличие от комбинаторных методов. ГОРДИАН [7] формулирует стоимость длины провода как квадратичную функцию, сохраняя при этом разделение ячеек посредством рекурсивного разделения. Алгоритм [8] моделирует плотность размещения как линейный член квадратичной функции стоимости и решает проблему размещения с помощью чистого квадратичного программирования. Распространенным усовершенствованием является взвешивание каждой цепи на величину, обратную ее длине на предыдущей итерации. При условии, что процесс сходится, это минимизирует объективную линейную зависимость от длины провода. [9] Большинство современных квадратичных россыпей (KraftWerk, [10] FastPlace, [11] SimPL [12] ) следуют этой схеме, каждая из которых имеет разные эвристические методы определения силы линейной плотности.

Нелинейное размещение моделирует длину провода с помощью экспоненциальных (нелинейных) функций и плотность с помощью локальных кусочно-квадратичных функций, чтобы добиться большей точности и, следовательно, улучшения качества. [13] Последующая научная работа включает APlace [14] и NTUplace. [15]

ePlace [16] — это современный алгоритм глобального размещения. Он разделяет экземпляры путем моделирования электростатического поля, что сводит к минимуму затраты на качество и обеспечивает хорошую производительность.

В 2021 году Google Brain сообщил о хороших результатах использования методов искусственного интеллекта (в частности, обучения с подкреплением) для решения проблемы размещения. [17] Однако этот результат весьма спорен, [18] [19] [20], поскольку статья не содержит прямых сравнений с существующими россыпями, и ее трудно воспроизвести из-за запатентованного содержания. По крайней мере один изначально положительный комментарий был отозван после дальнейшего рассмотрения. [21]

Смотрите также

Рекомендации

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

Дальнейшее чтение/Внешние ссылки