Размещение в проектировании электронных схем

Введение

Стадия проектирования электронных схем

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

Специфика применения

В случае прикладных интегральных схем, или ASIC, область расположения ядра чипа состоит из ряда рядов фиксированной высоты, между которыми может быть некоторое или никакое пространство. Каждый ряд состоит из множества площадок, которые могут быть заняты элементами схемы. Свободная площадка – это площадка, не занятая каким-либо элементом. Элементы схемы могут быть стандартными ячейками, макроблоками или ввода-вывода (I/O) площадками. Стандартные ячейки имеют фиксированную высоту, равную высоте ряда, но переменную ширину. Ширина ячейки является целым числом площадок. Макроблоки, напротив, обычно больше ячеек и имеют переменную высоту, которая может занимать несколько рядов. Размещение отображает подсхемы в программируемые логические блоки FPGA таким образом, чтобы гарантировать завершение последующего этапа трассировки.

Основные методы

Размещение делится на глобальное и детальное размещение. Глобальное размещение вносит существенные изменения, распределяя все экземпляры по соответствующим позициям в глобальном масштабе с допустимыми незначительными перекрытиями. Детальное размещение перемещает каждый экземпляр в ближайшее допустимое место с минимальными изменениями макета. Эффективность глобального размещения оказывает наибольшее влияние на качество размещения и общий дизайн. Ранние методы размещения интегральных схем можно отнести к комбинаторной оптимизации. Для ИС-дизайнов, содержащих тысячи или десятки тысяч компонентов, методы имитации отжига, такие как TimberWolf, демонстрируют наилучшие результаты. С ростом ИС-дизайнов до миллионов компонентов, размещение стало использовать разделение гиперграфов с применением вложенных фреймворков разделения, таких как Capo. Комбинаторные методы напрямую предотвращают перекрытия компонентов, но испытывают трудности с оптимизацией соединений в больших масштабах. Они, как правило, стохастичны и могут выдавать существенно различающиеся результаты для одного и того же входного набора данных при повторных запусках. Аналитические методы глобального размещения моделируют длину соединений непрерывной функцией и непосредственно минимизируют эту функцию с учетом ограничений на плотность компонентов. Эти методы работают быстрее и лучше масштабируются, чем комбинаторные, но не предотвращают перекрытия компонентов и требуют постобработки комбинаторными методами для детального размещения. Квадратичное размещение – это ранний аналитический метод, который моделирует длину соединений квадратичной функцией и использует высокопроизводительные методы квадратичной оптимизации. При разработке он продемонстрировал конкурентоспособное качество результатов и стабильность, в отличие от комбинаторных методов. GORDIAN формулирует стоимость трассировки как квадратичную функцию, одновременно распределяя элементы посредством рекурсивного разделения. Алгоритм моделирует плотность размещения как линейный член в квадратичной функции стоимости и решает задачу размещения с помощью чистого квадратичного программирования. Распространенным улучшением является взвешивание каждой сети обратной величиной ее длины на предыдущей итерации. При условии сходимости процесса это минимизирует целевую функцию, линейную по длине трассировки. Большинство современных квадратичных разместителей (KraftWerk, FastPlace, SimPL) следуют этой схеме, каждый со своими эвристиками для определения силы линейной плотности. Нелинейные методы размещения моделируют длину трассировки экспоненциальными (нелинейными) функциями, а плотность – локальными кусочно-квадратичными функциями, для достижения большей точности и, следовательно, повышения качества. Дальнейшие академические работы включают APlace и NTUplace. ePlace – это современный алгоритм глобального размещения. Он распределяет экземпляры, имитируя электростатическое поле, что минимизирует потери качества и обеспечивает высокую производительность. В 2021 году Google Brain сообщил о хороших результатах использования методов искусственного интеллекта (в частности, обучения с подкреплением) для задачи размещения. Однако этот результат вызывает споры, поскольку в статье отсутствуют прямые сравнения с существующими разместителями, и его трудно воспроизвести из-за конфиденциальности контента. По крайней мере один первоначально положительный отзыв был отозван после дальнейшего рассмотрения.

Placement is divided into global placement and detailed placement. Global placement introduces dramatic changes by distributing all the instances to appropriate locations in the global scale with minor overlaps allowed. Detailed placement shifts each instance to nearby legal location with very moderate layout change. Placement and overall design quality is most dependent on the global placement performance. Early techniques for placement of integrated circuits can be categorized as combinatorial optimization. For IC designs with thousands or tens of thousands of components, simulated annealing methodologies such as TimberWolf exhibits the best results. When IC designs grew to millions of components, placement leveraged hypergraph partitioning using nested partitioning frameworks such as Capo. Combinatorial methods directly prevent component overlaps but struggle with interconnect optimization at large scale. They are typically stochastic and can produce very different results for the same input when launched multiple times. Analytical methods for global placement model interconnect length by a continuous function and minimize this function directly subject to component density constraints. These methods run faster and scale better than combinatorial methods, but do not prevent component overlaps and must be postprocessed by combinatorial methods for detailed placement. Quadratic placement is an early analytical method that models interconnect length by a quadratic function and uses high performance quadratic optimization techniques. When it was developed, it demonstrated competitive quality of results and also stability, unlike combinatorial methods. GORDIAN formulates the wirelength cost as a quadratic function while still spreading cells apart through recursive partitioning. The algorithm models placement density as a linear term into the quadratic cost function and solves the placement problem by pure quadratic programming. A common enhancement is weighting each net by the inverse of its length on the previous iteration. Provided the process converges, this minimizes an objective linear in the wirelength. The majority of modern quadratic placers (KraftWerk, FastPlace, SimPL) follow this framework, each with different heuristics on how to determine the linear density force. Nonlinear placement models wirelength by exponential (nonlinear) functions and density by local piece wise quadratic functions, in order to achieve better accuracy thus quality improvement. Follow up academic work includes APlace and NTUplace. ePlace is a state of the art global placement algorithm. It spreads instances apart by simulating an electrostatic field, which minimizes quality overhead thus achieves good performance. In 2021, Google Brain reported good results from the use of AI techniques (in particular reinforcement learning) for the placement problem. However, this result is quite controversial, as the paper does not contain head to head comparisons to existing placers, and is difficult to replicate due to proprietary content. At least one initially favorable commentary has been retracted upon further review.