Алгоритмы компоновки (постановка задач)

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

Компоновка может выполняться «снизу-вверх» и «сверху-вниз». В первом случае осуществляется последовательная компоновка конструктивов низших иерархических уровней (микросхем, ТЭЗ, устройств, блоков, стоек и т.д.), в конструктивы высших иерархических уровней, а во втором случае конструктивы высшего уровня последовательно разбиваются на конструктивы низшей сложности до тех пор, пока не будет получена схема связи конструктивов низшего уровня, вошедших в конструктивы высокого уровня.

При решении задач компоновки возможны следующие условия:

1. номенклатура (число типов), модулей неизвестна и необходимо разбить исходную схему на модули, минимизируя число разных типов модулей при выполнении ограничений на число выводов каждого модуля;

2. Номенклатура модулей низшего типа известна (существует описание типов модулей в Банке Данных) и требуется покрыть исходную схему модулями из заданного набора при максимальном использовании функциональных возможностей и выводов в заданных модулях;

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

Таким образом, задачей компоновки является разрезание большой схемы (функциональной, логической, принципиально электрической) на части. В зависимости от целей и условий компоновки можно выделить три постановки задачи:

1. типизация – разбиение схемы на конструктивные элементы (или топологические компоненты в ИМС) различных типов и определение минимальной номенклатуры их;

2. покрытие – преобразование исходной схемы в схему соединений элементов (модулей), номенклатура которых задана;

3. разрезание – разбиение исходной схемы на части (микросборки ТЭЗы, узлы и т.п.), типы которых либо заданы, либо должны быть определены в процессе решения с минимизацией числа связей между ними.

Среди различных вариантов результатов компоновки выбираются те, которые имеют минимальное число типов модулей (ячеек, элементов) и останавливаются на том, у которого между модулями будет минимальное число связей. Кроме названных критериев – числа типов модулей и числа межмодульных связей используется:

• общее число модулей;

• число используемых элементов во всех модулях скомпонованной схемы;

• суммарная площадь, занимаемая элементами и соединениями;

• электромагнитная совокупность элементов в модуле;

• параметры теплообмена между элементами в узле.

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

Известные алгоритмы компоновки можно условно разбить на пять групп:

• алгоритмы, использующие методы целочисленного программирования;

• последовательные алгоритмы;

• итерационные алгоритмы;

• смешанные алгоритмы;

• алгоритмы, основанные на методе ветвей и границ.

1. Алгоритмы первой группы могут обеспечить точное решение, но из-за их сложности и больших затрат машинного времени они не нашли практического применения. Более распространены алгоритмы 2, 3, 4 – групп.

Как правило, в алгоритмах компоновки математической моделью объекта обычно является граф, вершины которого соответствуют модулям, а ребра – межмодульным соединениям.

2. В последовательных алгоритмах сначала выбирается первая вершина графа и последовательным присоединением к ней других вершин из числа нераспределенных (при условии удовлетворений заданным критериям) формируется первый кусок графа (модуль, ячейка). Затем набирается второй кусок графа и т.д. до полного разрезания.

3. Итерационные алгоритмы применяются для улучшения либо результатов компоновки, полученных последовательными алгоритмами, либо начального произвольного разрезания графа на куски путем перестановки (парной или групповой) вершины графа из различных кусков с проверкой улучшения заданных критериев при перестановке.

Задача компоновки чаще всего решается в два этапа с помощью смешанных алгоритмов– последовательного и итерационного.