Компоновка - одна из основных процедур, выполняемых при конструкторском проектировании в маршрутах проектирования СБИС и РЭА.
Процесс перехода от электрической схемы к конструктивному распределению (разбиению) всех элементов на группы, соответствующие конструктивам различных уровней, т. е. процесс преобразования функционального описания аппаратуры в конструктивное, называется компоновкой.
Компоновка в ECAD может выполняться «снизу вверх» и «сверху вниз». В первом случае осуществляется последовательная компоновка конструктивов низших иерархических уровней (микросхем, ТЭЗ, устройств, блоков, стоек и т. д.) в конструктивы высших иерархических уровней, а во втором случае конструктивы высшего уровня последовательно разбиваются на конструктивы меньшей сложности до тех пор, пока не будет получена схема связей конструктивов низшего уровня, вошедших в конструктив более высокого уровня. На практике применяются оба способа и различные их комбинации.
Во всех случаях в результате решения задачи компоновки исходная схема преобразуется в схему соединений элементов, определяется состав конструктивов и связи между ними на различных иерархических уровнях.
При решении задач компоновки возможны следующие условия:
Таким образом, задачей компоновки является разрезание большой схемы, которой может быть структурная, функциональная, логическая, электрическая принципиальная, на части. В зависимости от целей и условий компоновки можно выделить три постановки задачи:
типизация — разбиение схемы на конструктивные элементы (или топологические компоненты в ИМС) различных типов и определение минимальной номенклатуры их;
покрытие — преобразование исходной схемы в схему соединений элементов (модулей), номенклатура которых задана (возможно одновременное решение задачи введения поэлементного резервирования на заданную глубину);
разрезание — разбиение исходной схемы на части (микросборки, ТЭЗы, узлы и т. п.), типы которых либо заданы, либо должны быть определены в процессе решения), с минимизацией числа связей между ними.
Это деление условно и могут решаться все три задачи в комплексе, либо отдельные из них. Среди различных вариантов результатов компоновки выбираются те, которые имеют минимальное число типов модулей (ячеек, элементов) и останавливаются на том, у которого между модулями будет минимальное число связей. Кроме названных критериев числа типов модулей и числа межмодульных связей, используются следующие:
Оптимизация по этим критериям выполняется с учетом ограничений на длину определенных критических соединений, влияющую на процесс передачи информации, и с условием распределения некоторых элементов в пределах одного узла.
Все эти критерии применяются в разных сочетаниях. Наиболее благоприятными условиями для автоматизации конструкторского проектирования являются унификация и стандартизация конструктивов всех уровней от элементов до панелей и стоек.
Алгоритмы компоновки можно условно разбить на следующие группы: 1) алгоритмы, использующие методы целочисленного программирования; 2) алгоритмы, основанные на методе ветвей и границ; 3) последовательные алгоритмы; 4) итерационные алгоритмы; 5) смешанные алгоритмы; 6) эволюционные алгоритмы.
Алгоритмы первых двух групп могут обеспечить точное решение, но из-за их сложности и больших затрат машинного времени они не нашли практического применения. Более распространены алгоритмы остальных групп, которые хотя и являются приближенными, но приводят к удовлетворительным результатам и позволяют учесть основные критерии компоновки.
Как правило, в алгоритмах компоновки математической моделью объекта является граф, вершины которого соответствуют модулям, а ребра — межмодульным соединениям.
В последовательных алгоритмах сначала выбирается первая вершина графа и последовательным присоединением к ней других вершин из числа нераспределенных (при условии удовлетворения заданным критериям) формируется первый кусок графа (модуль, ячейка и т. п.). Затем набирается второй кусок графа и т. д. до полного разрезания.
Итерационные алгоритмы применяются для улучшения либо результатов компоновки, полученных последовательными алгоритмами, либо начального произвольного разрезания графа на куски путем перестановки (парной или групповой) вершин графа из различных кусков с проверкой улучшения заданных критериев при перестановке.
Задача компоновки чаще всего решается смешанными алгоритмами в два этапа: начальная компоновка последовательными алгоритмами и улучшение результатов начальной компоновки итерационными процедурами до удовлетворения принятых критериев.