Алгоритмы решения задач компоновки

 Под задачей компоновки КС понимаются задачи объединения модулей низшего (i — 1)-го уровня в модули более высокого i-го уровня по заданному критерию или набору критериев оптимизации и при наличии заданных ограничений.

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

 число образующихся блоков;

 число межузловых соединений или внешних выводов на блоках;

 задержки в распространении сигналов;

 электро-магнито — тепловая совместимость элементов и т. д.

 Задачи такого вида возникают при разбиении КС на блоки большей степени сложности, к которым не предъявлены требования в отношении схемной унификации. Это задачи распределения ТЭЗ по панелям, микросборок по печатным платам, разбиение КС на БИС, СБИС. К первому классу задач компоновки относят такие, в которых критерии оптимизации и ограничения могут быть сведены к определенным конструктивным параметрам расположения отдельных элементов и их межсоединений. Эти задачи называются задачами компоновки конструктивных частей (блоков).

 Второй класс образуют такие методы, в которых кроме конструктивных характеристик образующихся частей существенны и их функциональные характеристики. Они возникают на этапе перехода от функциональных (логических) схем ЭВА к КС, ориентированным на заданную систему элементов, состоят в назначении элементов логической схемы в типовые модули из заданного набора. Указанный класс называют методом покрытия или задачами компоновки типовых блоков. Основными критериями при покрытии схем являются следующие:

число модулей, необходимых для покрытия исходной схемы;

число межмодульных соединений;

число типов используемых модулей;

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

 В качестве ограничений выступают конструктивные и функциональные характеристики типовых модулей, такие как:

 максимально допустимое число элементов (i—1)-го уровня в модулях

i-го уровня;

 максимально допустимое число выводов модуля i-го уровня;

 ограничения на совместную работу модулей (i— 1)-го уровня и т. д.

 Задачи компоновки являются классическими примерами многокритериальной оптимизации (ЗМО).

 Для алгоритмизации и формального решения задачи производится переход от КС к графу, к мультиграфу, к гиперграфу.