Материал: Автоматизация оптимальной компоновки модулей РЭС. методические указания к выполнению лабораторных работ по дисциплине «Основы автоматизированного проектирования РЭС». Макаров О.Ю., Бобылкин И.С

АВТОМАТИЗАЦИЯ ОПТИМАЛЬНОЙ КОМПОНОВКИ МОДУЛЕЙ РЭС

Цель работы: углубление и закрепление знаний по вопросам оптимизации межблочных соединений при компоновке РЭС методом парных перестановок и получение практических навыков использования ЭВМ IBM PC для решения таких задач.

Характеристика содержания работы: в процессе выполнения лабора-

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

-составления исходных данных и решения на ЭВМ задач оптимизации межблочных соединений при компоновке РЭС;

-решения вопросов оптимизации с помощью алгоритма парных перестановок;

-исследования и оценки эффективности алгоритма парных перестановок при оптимизации межблочных соединений модулей.

На выполнение лабораторной работы отводится четыре часа. Перед лабораторным занятием студент должен самостоятельно выполнить домашнее задание в соответствии с данными методическими указаниями.

Студент, явившийся на занятия, должен иметь методические указания по данной лабораторной работе, полученные в библиотеке. В начале занятия преподаватель проверяет выполнение студентом домашнего задания и наличие заготовки отчета по данной лабораторной работе в его рабочей тетради.

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

1. ДОМАШНЕЕ ЗАДАНИЕ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ЕГО ВЫПОЛНЕНИЮ

При выполнении домашнего задания студент должен ознакомиться с алгоритмами оптимизации межблочных соединений при компоновке РЭС. Для этого необходимо воспользоваться литературой [I, с. 188-212]. В связи с тем, что в литературе вопрос оптимизации межблочных соединений методом парных перестановок рассматривается недостаточно подробно необходимо проработать также следующий материал.

При оптимизации компоновки радиоэлектронных средств обычно решается задача оптимального разделения схемы на несколько блоков. Эта задача известна еще как задача о разрезании графа.

Пусть какое-либо устройство имеет Х элементов (модулей первого уровня, например, микросхем) и каждый i - й элемент имеет с j - м элементом Cij соединений. Схема такова, что ее не разместить на одной плате, то есть требуется всё устройство разделить на составные части (например, на модули 2 - го уров-

3

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

-снижение количества используемого монтажного провода (экономический эффект);

-увеличение надежности изделия;

-снижение массы и трудоемкости изготовления изделия;

-уменьшение паразитных взаимосвязей.

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

Число возможных сочетаний элементов определяется по формуле :

n

где Cm - число сочетаний из m элементов по n элементов,

m - число всех элементов; n - число элементов в одном блоке.

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

1.1 Метод парных перестановок

Пусть в результате произвольного начального распределения нами сформированы Z блоков. Обозначим их через X , X , X ,...,XZ. Подсчитав количество соединений между двумя блоками, например, между блоком Х и блоком Х , меняем взаимно местами по одному модулю из блока Х и из блока Х . После этого вновь считаем количество соединений между блоками. Если после перестановки количество соединений уменьшилось, то перестановка целесообразна. Если же увеличилось или осталось прежним, по перестановка не целесообразна. Можно производить перестановку каждого модуля блока Х с каждым модулем блоков Х , Х , ..., Хz, а затем каждого модуля блока Х с каждым модулем остальных блоков и т.д. В результате можно получить минимизацию соединений между блоками.

Целесообразность перестановки i - го элемента, находящегося в блоке Х , с j - м элементом, находящимся в блоке Х , определяется по формуле:

4

элементами этого же блока;

m i j - количество общих (прямых) соединений между переставляемыми эле-

ментами x i и x j .

- первый блок ; Х - множество элементов блока (обозначаются буквой i).- второй блок ; Х - множество элементов блока (обозначаются буквой j).

Если Fx i x j 0, то перестановка этих элементов нецелесообразна,

то есть эта перестановка не ведет к уменьшению числа межблочных соединений, а ведет к их возрастанию или не изменяет их количество. Если Fx i x j

> 0, то перестановка целесообразна. Далее, подсчитав функционалы всех пар элементов и произведя перестановку двух элементов, для которых функционал имеет максимальное положительное значение, вновь производят вычисления всех функционалов для этих двух блоков. Если окажется, что для каких-либо двух элементов функционал больше нуля, то снова производят перестановку и так несколько раз, до тех пор, пока все функционалы будут равны или меньше нуля. Следует подчеркнуть, что после каждой перестановки все функционалы вычисляются вновь. В результате таких перестановок достигается обычно локальный минимум межблочных соединений. Близость его к глобальному минимуму, то есть степень оптимизации, существенно зависит от начального (исходного) распределения элементов между блоками.

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

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

Если F’ > 0, то перестановка целесообразна.

5