Lektsii_Karmanov

АЛГОРИТМИЧЕСКИЕ МЕТОДЫ КОНСТРУИРОВАНИЯ ЭВС

§ 1. ОБЩАЯ ХАРАКТЕРИСТИКА ОСНОВНЫХ ЗАДАЧ ЭТАПА КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ
В основу построения современных вычислительных комплексов положен модульный принцип. Он предполагает иерархическое построение ЭВС из модулей, разбитых на несколько конструктивных уровней (рис. 1.1).
13 SHAPE \* MERGEFORMAT 1415
Рис. 1.1. Иерархия конструктивных уровней.
К числу основных конструкторских задач, типовых для всех уровней конструктивной иерархии, относятся:
компоновка конструктивных модулей;
размещение модулей низших иерархических уровней в монтажном пространстве модулей следующих уровней иерархии;
трассировка монтажных соединений;
получение конструкторской документации;
тестирование аппаратуры.
Компоновка – этап конструкторского проектирования, заключающийся в распределении всех функциональных элементов схемы в группы, соответствующие конструктивным единицам различного ранга, из которых реализуются разрабатываемые ЭВС. На этапе компоновки осуществляется распределение элементов в микросхемы (МС), МС в ячейки, ячеек в панели, панелей в шкафы и т.д.
В дальнейшем будем называть конструктивную единицу низшего ранга – элементом, конструктивную единицу высшего ранга – блоком.
Возможны два варианта практической постановки задачи компоновки:
компоновка схемы конструктивно унифицированными блоками, состав которых формируется непосредственно в процессе компоновки (количество выводов и элементов блока известно заранее);
компоновка схемы функционально типизированными блоками из заданного набора.
В первом случае задача заключается в разбиении схемы устройства на блоки заданного размера с известным числом элементов и количеством внешних выводов. Это так называемая задача разбиения. Задачами такого типа являются задачи разбиения по ТЭЗам, ТЭЗов по панелям, разбиение БИС на ИС частного применения.
При решении задачи компоновки обычно используются следующие критерии качества:
минимальное число межблочных связей;
минимальное количество блоков;
минимальное число типов используемых блоков;
возможно более полное использование каждого блока.
В качестве основных ограничений в задаче компоновки обычно выступают:
максимальное число элементов в блоке;
максимальное число внешних выводов блока;
ограничения на совместную или раздельную компоновку некоторых элементов, обусловленные тепловыми требованиями, требованиями помехозащищенности и т.д.

Размещение – задача определения такого местоположения элементов в заданном монтажном пространстве, при котором наилучшим образом удовлетворяются некоторые требования. В качестве элемента здесь могут выступать радиодетали, ИС, ячейки, панели, шкафы. При этом предполагается, что элементы в монтажном пространстве определенным образом соединяются между собой. Эти соединения могут быть выполнены посредством навесных или печатных проводников, жгутовых соединений или других информационных магистралей.
Имеются два типа задач размещения:
размещение однотипных элементов на заранее заданных и регулярно размещенных позициях;
размещение элементов разного типа, разногабаритных, когда установочные места заранее не определены, а установка элементов осуществляется в процессе размещения (БИС).
Задача размещения носит в общем случае многоцелевой характер, и при ее решении должна производится оптимизация по совокупности критериев качества. Однако, в каждом конкретном случае обычно удается выделить наиболее важный критерий, учитывая другие показатели в качестве ограничений задачи. Известные алгоритмы размещения оптимизируют следующие показатели качества:
суммарную длину всех соединений;
длину самой длинной связи;
число связей между модулями, находящимися в соседних позициях (максимизация);
число пересечений проводников;
число цепей с возможно более простой конфигурацией.
Трассировка монтажных соединений – задача реализации соединений между выводами модулей предыдущего ранга в монтажном пространстве модуля следующего ранга в соответствии со схемой и с учетом конструктивно-технологических ограничений.
Имеются два типа задач трассировки:
трассировка проводного монтажа;
трассировка печатного монтажа.
Критерии оптимизации:
минимум суммарной длины проводников;
минимальное число переходных отверстий;
минимальное число слоев;
максимальная удаленность проводников друг от друга (снижение значений паразитных емкостей).
Ограничения:
отсутствие пересечений проводников в одном слое для печатного монтажа;
ограниченное число паек к одному контакту при проводном монтаже.
Примечание 1. Крысиная цепь – кратчайшая цепь.
Примечание 2. При втором варианте компоновки (компоновка схемы функционально типизированными блоками из заданного набора) номенклатура блоков известна заранее, и задача заключается в представлении исходной схемы совокупностью связанных между собой блоков из заданного набора. Данная задача возникает при переходе от функциональной схемы к принципиальной – так называемая задача покрытия. Она состоит в привязке элементов функциональной схемы к конкретным типовым модулям из заданного набора. При этом каждый модуль может включать в себя несколько типовых элементов, в общем случае связанных между собой.


§ 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ СХЕМ ЭВС
Для описания функционально-логических схем цифровых устройств и принципиальных электрических схем аналоговых устройств используются три основные математические модели (ММ):
граф коммутационной схемы (ГКС);
гиперграф (ГГ);
взвешенный неориентированный граф (ВНГ).
Граф коммутационной схемы
Введем следующие обозначения:
13 EMBED Equation.DSMT4 1415 – множество элементов схемы, причем e0 соответствует фиктивному элементу, например, разъему.
13 EMBED Equation.DSMT4 1415 – множество цепей схемы.
13 EMBED Equation.DSMT4 1415 – множество контактов i-го элемента.
13 EMBED Equation.DSMT4 1415 – множество контактов всех (n+1) элементов схемы.
13 EMBED Equation.DSMT4 1415
ГКС – треххроматический граф с вершинами трех типов («элемент», «контакт», «цепь») и ребрами двух типов W и F («элемент–контакт» – W, «контакт–цепь» – F).
Для примера рассмотрим схему, приведенную на рисунке 2.1.
13 SHAPE \* MERGEFORMAT 1415
Рис. 2.1.
ГКС для схемы рис. 2.1 приведен на рисунке 2.2.
13 SHAPE \* MERGEFORMAT 1415
Рис. 2.2.
Для описания ГКС можно использовать списковые структуры (динамические массивы). Различают два вида списков:
списки элементов по цепям;
списки цепей по элементам.
Список элементов по цепям представляется последовательностью пар чисел, первое из которых описывает элемент схемы, подключенный к некоторой цепи, а второе число задает номер контакта этого элемента, при помощи которого он подключен к цепи. Последовательность элементов списка, отделенная знаком “;” (точка с запятой), описывает одну цепь схемы. Список элементов по цепям для схемы рис. 2.1 имеет вид:
13 EMBED Equation.DSMT4 1415
Наиболее удобным является список цепей по элементам, из которого сразу видно какие цепи подключены к элементу, а именно: каждая из пар чисел первым числом описывает номер контакта некоторого элемента, а вторым – номер цепи, к которой подключен элемент при помощи данного контакта. Последовательность элементов списка, отделенная знаком “;” (точка с запятой), описывает один элемент схемы. Список цепей по элементам для схемы рис. 2.1 имеет вид:
13 EMBED Equation.DSMT4 1415
ГКС может быть описан с помощью специальных языковых средств:
13 EMBED Equation.DSMT4 1415,
где L – признак элемента; далее, не менее чем через один пробел, следуют номер элемента – 1, тип элемента – 2, а также список цепей, в котором через запятую перечисляются номера цепей, инцидентных данному элементу, с указанием в скобках за номерами цепей, номеров контактов, подключающих цепь к элементу.
Для описания ГКС можно использовать матрицы инцидентности (A и B), определяющих множество ребер типа F («контакт–цепь») и типа W («элемент–контакт»).
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
Для схемы рис. 2.1 матрица A будет иметь следующий вид:



k01
k02
k11
k12
k13
k21
k22
k31
k32



v1
1
0
1
0
0
0
0
0
0

A
=
v2
0
0
0
0
1
1
0
1
0



v3
0
0
0
1
0
0
0
0
1



v4
0
1
0
0
0
0
1
0
0

Для схемы рис. 2.1 матрица B будет иметь следующий вид:



k01
k02
k11
k12
k13
k21
k22
k31
k32



e0
1
1
0
0
0
0
0
0
0

B
=
e1
0
0
1
1
1
0
0
0
0



e2
0
0
0
0
0
1
1
0
0



e3
0
0
0
0
0
0
0
1
1


ГКС может быть описан с помощью таблицы контактов:
13 EMBED Equation.DSMT4 1415

·max – наибольшее число контактов у одного элемента.
Таблица контактов для примера рис. 2.1 выглядит следующим образом:

1
2
3

e0
1
4


e1
1
3
2

e2
2
4


e3
2
3



ГКС является наиболее точной моделью и обычно используется при решении задач трассировки и размещения разногабаритных элементов.
Гиперграф
ГГ такое обобщение графа, в котором каждому ребру соответствует не пара вершин как в обычном графе, а произвольное подмножество вершин.
Данная модель обычно используется при решении задачи компоновки. Это связано с тем, что при компоновке контакты всегда распределяются в блок вместе с элементами, которым они инцидентны. Поэтому на ГКС можно исключить множество элементарных ребер W и F. При этом каждая цепь описываемая множеством контактов будет описываться множеством инцидентных ей элементов.
13 EMBED Equation.DSMT4 1415,
где E – множество элементов схемы;
U – множество ребер, при этом каждое ребро представляет собой подмножество элементов, инцидентных цепи vi. Для схемы примера (рис. 2.1) эти подмножества имеют вид:
13 EMBED Equation.DSMT4 1415
ГГ для схемы примера (рис. 2.1) представлен на рисунке 2.3.
13 SHAPE \* MERGEFORMAT 1415
Рис. 2.3
ГГ может быть описан с помощью матрицы инцидентности H.
13 EMBED Equation.DSMT4 1415
Для схемы примера (рис. 2.1) матрица инцидентности имеет вид:



v1
v2
v3
v4



e0
1
0
0
1

H
=
e1
1
1
1
0



e2
0
1
0
1



e3
0
1
1
0


Более удобно описывать ГГ с помощью списка цепей по элементам и списка элементов по цепям.
Список цепей по элементам представляется последовательностью чисел, определяющих номера цепей, причем подпоследовательность чисел, выделенная знаком “;” (точка с запятой), содержит номера цепей инцидентных одному элементу схемы.
13 EMBED Equation.DSMT4 1415
Список элементов по цепям каждой подпоследовательностью чисел задает номера элементов, инцидентных некоторой цепи.
13 EMBED Equation.DSMT4 1415
Вместо одного списка элементов по цепям с разделителями (“;”) можно использовать два списка SP и RSP вида:
13 EMBED Equation.DSMT4 1415
Аналогично для списка цепей по элементам:
13 EMBED Equation.DSMT4 1415
При использовании пар списков SP–RSP или ST–RST в позициях начиная с RSP[i] (RST[i]) до RSP[i+1]-1 (RST[i+1]-1) в списке SP (ST) определяются номера элементов (цепей), инцидентных i–й(–му) цепи (элементу).

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

Взвешенный неориентированный граф
ВНГ это граф вида 13 EMBED Equation.DSMT4 1415, где E – множество вершин графа, соответствующих множеству элементов схемы; U – множество ребер графа, при этом каждое ребро 13 EMBED Equation.DSMT4 1415 взвешено некоторым числом 13 EMBED Equation.DSMT4 1415, определяющим степень связности элементов ei и ej. Другими словами, cij – количество общих цепей, связывающих элементы ei и ej.
ВНГ для схемы примера (рис. 2.1) показан на рисунке 2.4.
13 SHAPE \* MERGEFORMAT 1415
Рис. 2.4
ВНГ описывается с помощью матрицы смежности C.
13 EMBED Equation.DSMT4 1415
Для схемы рис. 2.1 матрицы смежности C имеет вид:



e0
e1
e2
e3



e0
0
1
1
0

С
=
e1
1
0
1
2



e2
1
1
0
1



e3
0
2
1
0


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



e0
e1
e2
e3



e0
2
1
1
0

С'
=
e1
1
3
1
2



e2
1
1
2
1



e3
0
2
1
2

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

§ 3. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ КОМПОНОВКИ СХЕМ КОНСТРУКТИВНО УНИФИЦИРОВАННЫМИ МОДУЛЯМИ
Пусть имеется схема, состоящая из n элементов: 13 EMBED Equation.DSMT4 1415, где e0 – разъем.
Данную схему необходимо скомпоновать в r блоков: 13 EMBED Equation.DSMT4 1415.
Обозначим через 13 EMBED Equation.DSMT4 1415 вес – число элементов j-го блока.
Ставится задача разбить схему на блоки так, чтобы суммарный вес каждого блока был бы не больше некоторой заданной величины 13 EMBED Equation.DSMT4 1415, т.е. 13 EMBED Equation.DSMT4 1415, а число внешних выводов 13 EMBED Equation.DSMT4 1415 каждого блока не превышало бы заданное 13 EMBED Equation.DSMT4 1415, т.е. 13 EMBED Equation.DSMT4 1415. Если все блоки одинаковые, то 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415.
При решении этой задачи необходимо выработать критерий разбиения:
минимальное число межблочных связей;
минимальное число внешних выводов каждого блока;
любой другой критерий.
Математическая постановка задачи компоновки зависит от выбора исходной ММ схемы, оптимизирующего критерия качества и от учета тех или иных ограничений.
Математическая постановка задачи компоновки с использованием модели ВНГ
Критерий оптимизации – число межблочных связей. ВНГ будем представлять в виде матрицы C.
Введем в рассмотрение матрицу решений
·, которая определяет вариант компоновки элементов схемы в блоки.
13 EMBED Equation.DSMT4 1415
На элементы матрицы решений накладываются следующие ограничения:
Т.е. каждый элемент может быть расположен только в одном блоке.

Число элементов в блоке должно быть не больше заданного.
Выведем формулу для числа внешних выводов блока.
Очевидно, что выражение 13 EMBED Equation.DSMT4 1415 означает число межблочных связей, которые выходят из блока bj от элемента ei на элемент ek ,расположенный вне блока bj.
Очевидно, что выражение 13 EMBED Equation.DSMT4 1415 означает число межблочных связей, выходящих из блока bj от элемента ei на все остальные элементы схемы, расположенные вне блока bj, включая элемент e0.
Для того, чтобы получить общее число выводов от блока bj, необходимо просуммировать предыдущее выражение по i:
13 EMBED Equation.DSMT4 1415
Теперь получим формулу для суммарного числа межблочных связей:
13 EMBED Equation.DSMT4 1415
С учетом выражения (3.2) второй член выражения (3.5) перепишем в виде:
13 EMBED Equation.DSMT4 1415 – число связей с внешним разъемом схемы.
Поэтому в качестве можно взять первую часть целевой функции (3.5). Т.о., необходимо найти такую матрицу решений
·, удовлетворяющую ограничениям (3.2)–(3.4), для которой обеспечивается минимум целевой функции (3.5). Данная задача является задачей квадратичного целочисленного программирования с булевыми переменными cij.
В связи с тем, что модель ВНГ является грубой моделью, то и полученные формулы (3.4), (3.5) носят грубый характер.
Для примера рассмотрим схему, приведенную на рисунке 3.1.
13 SHAPE \* MERGEFORMAT 1415
Рис. 3.1
ВНГ для данной схемы приведен на рисунке 3.2 (примечание: вес ребра на рисунке обозначен количеством связей).
Пусть требуется разбить приведенную схему на блоки с ограничениями:
13 EMBED Equation.DSMT4 1415.
Из рассмотрения ВНГ нетрудно видеть, что по данной модели невозможно разбить схему не только на два, но и на четыре блока. На самом же деле это не так (см. схему). Это говорит о неточности данной модели.
Математическая постановка задачи компоновки с использованием модели ГГ
Рассмотрим ту же задачу, т.е. задачу нахождения матрицы решений
· для данного варианта разбиения. На элементы матрицы
·ij накладываются те же ограничения (3.2 и 3.3), что и выше.
Отметим, что каждая цепь vk в блоке bj может потребовать либо один, либо ноль выводов. Для того чтобы цепь vk потребовала один вывод необходимо и достаточно, чтобы хотя бы один элемент, инцидентный данной цепи, был бы расположен в блоке bj, и хотя бы один элемент, инцидентный данной цепи, включая элемент e0, был бы расположен вне блока bj.
Математически вышесказанное записывается следующим образом.
– сумма элементов, инцидентных цепи vk и расположенных в блоке bj.

– сумма элементов, инцидентных цепи vk и расположенных вне блока bj.
Введем в обозначения функцию: 13 EMBED Equation.DSMT4 1415
С учетом данного обозначения выражение
13 EMBED Equation.DSMT4 1415
будет справедливо, если цепь vk содержит хотя бы один элемент ei в блоке bj. Выражение
13 EMBED Equation.DSMT4 1415
справедливо, если цепь vk содержит хотя бы один элемент вне блока bj.
Число внешних выводов блока bj, которые требуют цепи vk, определяется из выражения:
13 EMBED Equation.DSMT4 1415.
Теперь получим формулу для числа межблочных связей. Очевидно, что выражение
13 EMBED Equation.DSMT4 1415
определяет количество блоков, в которых содержатся элементы, инцидентные цепи vk. Количество межблочных связей, которые требует цепь vk (без учета элемента e0), определяется из выражения:
13 EMBED Equation.DSMT4 1415.
Количество межблочных связей, которые требует цепь vk с учетом внешнего разъема e0, определяется из выражения:
13 EMBED Equation.DSMT4 1415.
Для определения суммарного числа межблочных связей просуммируем выражение (3.13) по всем цепям vk 13 EMBED Equation.DSMT4 1415.
13 EMBED Equation.DSMT4 1415
Задача (3.14) это задача нелинейного целочисленного программирования с булевыми переменными.
Теперь вернемся к нашему примеру (рис. 3.1).
Матрица инцидентности (цепей) ГГ имеет вид:



v1
v2
v3
v4
v5
Т.о., элементы hik известны.



e0
1
0
1
1
1


H
=
e1
1
1
0
0
0




e2
1
1
1
0
0




e3
0
1
0
1
0




e4
1
0
0
0
1



Матрица решений
· для нашего примера имеет вид:



b1
b2







e1

·11

·12

1
0
Т.о., элементы
·ij для нашего варианта компоновки тоже известны.


·
=
e2

·21

·22
=
1
0




e3

·31

·32

0
1




e4

·41

·42

0
1



Формула (3.13), примененная для каждой цепи vk, показывает, что каждая из них требует только один вывод.
Формула (3.14) для нашего варианта разбиения (компоновки) дает следующее число межблочных связей: 13 EMBED Equation.DSMT4 1415
Блочная организация схемы рисунка 3.1 при таком варианте размещения приведена на рисунке 3.3.









Общая характеристика алгоритмов компоновки конструктивных модулей
Все существующие алгоритмы компоновки конструктивных модулей можно разделить на два основных класса: точные и приближенные алгоритмы, которые, в свою очередь представлены несколькими подклассами (см. рис. 3.4).
13 SHAPE \* MERGEFORMAT 1415
Рис. 3.4 Классификация алгоритмов компоновки
Алгоритмы Лаурера основаны на сведении задачи компоновки к так называемой задаче покрытия, возникающей при минимизации булевых функций. Эти алгоритмы в качестве модели схемы используют гиперграф (матрицу H).
Существует несколько модификаций алгоритмов на основе метода ветвей и границ, в которых в качестве модели схемы используются ГГ или ВНГ. Они отличаются способом вычисления оценки.
При современном быстродействии ЭВМ точные алгоритмы позволяют решать задачи с числом переменных не более 20-ти. В связи с этим на практике широко применяются приближенные, эвристические алгоритмы, математически слабо обоснованные, но дающие неплохие результаты. Суть последовательных алгоритмов – последовательное заполнение блоков еще не распределенными в блоки элементами. В качестве очередного элемента выбирается элемент максимально связанный с элементами, уже включенными в формируемый блок. Процесс заполнения блока элементами продолжается до тех пор, пока не нарушаются ограничения на модульную (13 EMBED Equation.DSMT4 1415) и контактную (13 EMBED Equation.DSMT4 1415) емкости блока. Имеются различные модификации таких алгоритмов, отличающиеся выбором критерия для кандидата на включение и способом вычисления оценки.
Суть параллельно-последовательных алгоритмов: здесь сначала выделяются некоторые группы элементов, например, сильно связанные между собой, а затем эти группы параллельно распределяются по блокам с учетом контактных и модульных ограничений.
Итерационные алгоритмы служат для улучшения некоторого начального варианта компоновки, полученного либо вручную, либо с помощью последовательных алгоритмов, и состоят в обмене (перестановках) элементов, принадлежащих разным блокам. При этом осуществляются одинарные, двойные и, в общем случае, групповые перестановки элементов.

§ 4. ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ КОМПОНОВКИ
Будем описывать схему с помощью ГГ: 13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415,
13 EMBED Equation.DSMT4 1415
Задача: требуется разбить схему на блоки 13 EMBED Equation.DSMT4 1415 так, чтобы каждый блок содержал не более чем заданные число элементов 13 EMBED Equation.DSMT4 1415 и число внешних выводов 13 EMBED Equation.DSMT4 1415.
В рассматриваемом алгоритме процесс формирования очередного блока начинается с выбора первого, так называемого базового элемента (БЭ). В качестве БЭ выбирается элемент, имеющий максимальное число общих цепей со всеми еще нераспределенными элементами (элемент e0 уже распределен). далее блок последовательно заполняется элементами из числа еще нераспределенных. Для этого из множества всех нераспределенных элементов выделяется подмножество таких элементов, распределение которых в блок не приводит к превышению заданного числа выводов из блока. Из них в блок распределяется элемент, имеющий максимальное число общих цепей со всеми элементами, уже распределенными в блок. Если таких элементов несколько, то среди них выбирается элемент, при добавлении которого в блок число выводов из блока минимально. Если и таких элементов несколько, то выбирается элемент с максимальным порядковым номером (для формализации задачи).
Рассмотрим более подробно процедуру формирования блока bj. Будем считать, что блоки b1, b2, , bj-1 уже сформированы. Пусть Ij – множество элементов, нераспределенных в эти предшествующие блоки, т. е.
13 EMBED Equation.DSMT4 1415,
где E(bk) – множество элементов блока bk.
Последовательный алгоритм компоновки можно представить в следующем виде.
П. 1.
При выборе БЭ для всех элементов 13 EMBED Equation.DSMT4 1415 вычисляется оценка L1(x).
13 EMBED Equation.DSMT4 1415,
13 EMBED Equation.DSMT4 1415
Здесь qk – связи элемента со всеми нераспределенными элементами,
V(x) – множество цепей, инцидентных элементу x,
E(vk) – множество элементов, инцидентных цепи vk,
L1(x) – число связей элемента x со всеми еще неразмещенными элементами.
В блок распределяется элемент с максимальной оценкой L1(x). Если таких элементов несколько, то выбирается элемент с большим порядковым номером (для формализации задачи).
П. 2.
Пусть на t-м шаге формирования блока bj имеется множество элементов 13 EMBED Equation.DSMT4 1415, распределенных к этому шагу в блок bj (13 EMBED Equation.DSMT4 1415). При определении очередного элемента для всех нераспределенных элементов 13 EMBED Equation.DSMT4 1415 вычисляется оценка L2(x).
13 EMBED Equation.DSMT4 1415,
13 EMBED Equation.DSMT4 1415
Здесь 13 EMBED Equation.DSMT4 1415 – множество цепей, инцидентных всем элементам блока bj к шагу t, включая элемент x,
L2(x) – число выводов блока bj на шаге t с учетом элемента x.
П. 3.
Для всех элементов x, для которых выполняется условие 13 EMBED Equation.DSMT4 1415, вычисляется оценка L3(x) – число связей элемента x с формируемым блоком 13 EMBED Equation.DSMT4 1415.
13 EMBED Equation.DSMT4 1415,
13 EMBED Equation.DSMT4 1415
В блок bj включается элемент с максимальной оценкой L3(x). Если таких элементов несколько, то среди них выбирается элемент с минимальной оценкой L2(x). Если и таких элементов несколько, то выбирается элемент с максимальным порядковым номером (для формализации задачи).
П. 4.
Если ни для одного элемента 13 EMBED Equation.DSMT4 1415 условие 13 EMBED Equation.DSMT4 1415 не выполняется, то дополнение блока bj прекращается и начинается формирование следующего блока (переход к п.1).
П. 5.
Алгоритм заканчивает работу когда все элементы схемы распределены в блоки.
При практической реализации алгоритма вместо формулы (4.2) для определения числа выводов из блока удобно использовать формулы для приращения числа выводов из блока bj при добавлении в него элемента x.
13 EMBED Equation.DSMT4 1415,
где 13 EMBED Equation.DSMT4 1415 – количество выводов блока bj до добавления в него элемента x.
13 EMBED Equation.DSMT4 1415,
13 EMBED Equation.DSMT4 1415
Последнее выражение (для
·pk) можно пояснить с помощью рисунка 4.1.
13 SHAPE \* MERGEFORMAT 1415
Рис. 4.1.
Рассмотрим работу последовательного алгоритма компоновки на примере.
Пусть необходимо разбить схему, приведенную на рисунке 4.2 на типовые блоки с числом элементов 13 EMBED Equation.DSMT4 1415 и числом выводов 13 EMBED Equation.DSMT4 1415, минимизируя при этом количество межблочных связей.
Перед началом компоновки множество нескомпонованных элементов I1 содержит все элементы схемы кроме e0 (элемент e0 уже распределен).
13 SHAPE \* MERGEFORMAT 1415
Рис. 4.2.
Для выбора БЭ вычислим оценку L1(x) по формуле (4.1) для всех элементов множества I1.
13 EMBED Equation.DSMT4 1415
В соответствии с формулой (4.1) 13 EMBED Equation.DSMT4 1415.
Вычисляя подобным образом оценки L1(x) для элементов e2, e3, , e9 определим, что максимальным числом связей со всеми еще неразмещенными элементами обладает элемент e7 – 13 EMBED Equation.DSMT4 1415.
Аналогично вычисляются оценки L2(x) и L3(x). Вычислим, например, L3(e9) – связи элемента e9 с элементами формируемого блока, в который вошли элементы e7 и e8 (см. ниже).
13 EMBED Equation.DSMT4 1415
Таким образом .
Результаты вычислений удобно свести в таблицу.

L1
L2
L2
L3
L1
L2
L1
L2
L3

1
2
3
4
5
6
7
8
9
10

e1
4
5+3>6
4+3>6
––
4*
––
––
––
––

e2
3
5+3>6
4+3>6
––
3
4+1
2
4+1
2*

e3
3
5+3>6
4+2=6
1
3
4+3
––
4+3
––

e4
4
5+2>6
4+2=6
2
3
4+0
3*
––
––

e5
3
5+2>6
4+0<6*
2
––
––
––
––
––

e6
2
5+2>6
4+2=6
0
2
4+1
1
4+1
1

e7
5*
––
––
––
––
––
––
––
––

e8
4
5-1<6*
––
––
––
––
––
––
––

e9
2
5+3>6
4+2=6
1
2
4+2
1
4+2
1


В качестве БЭ блока b1 выбираем элемент e7 с максимальной оценкой L1(x)=5.
Для остальных элементов схемы вычисляем оценку L2(x) – выводы. Результаты сведем в графу 3 таблицы.
Всего один элемент e8 может быть включен в блок b1 без нарушения контактного ограничения 13 EMBED Equation.DSMT4 1415. Таким образом, 13 EMBED Equation.DSMT4 1415, количество выводов из блока – четыре.
Для выбора очередного элемента блока b1 вычислим оценки L2(x) для нескомпонованных элементов (графа 4 таблицы).
Для элементов (13 EMBED Equation.DSMT4 1415) e3, e4, e5, e6, e9 вычислим оценки L3(x) – связи (графа 5таблицы).
При одинаковых максимальных оценках L3max=2 элемент e5 дает меньшее число выводов из блока (четыре) чем элемент e4, поэтому состав блока b1={e7, e8, e5}; P1=4, S1=3.
Формирование второго блока проведем аналогично первому (графы 6 – 10).
Состав b2={e1, e4, e2}.
Оставшиеся элементы распределим в блок b3 с P3=6.
Количество межблочных связей при данном варианте компоновки – десять.
При решении задачи компоновки на ПЭВМ целесообразно использовать списки элементов по цепям и списки цепей по элементам с соответствующими разделителями (13 LINK \l "_Гиперграф" 14см. § 2, Гиперграф15).
Для схемы рис. 4.2 список элементов по цепям и соответствующий список разделителей имеют следующий вид:
13 EMBED Equation.DSMT4 1415
13 EMBED Equation.DSMT4 1415
Аналогично составляются список цепей по элементам ST и список разделителей RST.
Схема последовательного алгоритма компоновки приведена на рисунке 4.3.
13 SHAPE \* MERGEFORMAT 1415
Рис. 4.3. Схема последовательного алгоритма компоновки
§ 5. ЗАДАЧА РАЗМЕЩЕНИЯ КОНСТРУКТИВНЫХ МОДУЛЕЙ
Различают два типа задач размещения:
размещение конструктивных элементов в заранее фиксированные позиции;
размещение элементов в непрерывном монтажном пространстве, когда позиции заранее не определены, а определяются в процессе размещения (например, проектирование БИС).
Рассмотрим первую задачу.
Пусть имеется регулярное монтажное пространство с уже фиксированными позициями 13 EMBED Equation.DSMT4 1415, а также имеется количество 13 EMBED Equation.DSMT4 1415 элементов для размещения.
Будем считать, что длина связей определяется расстоянием между геометрическими центрами соответствующих позиций, т. е.
13 EMBED Equation.DSMT4 1415
Чаще всего такая метрика используется тогда, когда последующая трассировка соединений осуществляется с помощью проводного монтажа «в навал» (провода с изоляцией). При использовании печатного или жгутового монтажа используются соответственно метрики (5.б) и (5.в):
13 EMBED Equation.DSMT4 1415
где t – количество проводников в жгуте.
Метрики (5.б) и (5.в) обычно используют тогда, когда наряду с минимизацией суммарной взвешенной длины связей стараются минимизировать также длину наиболее длинной связи (она определяет время задержки схемы).

Если для простоты рассуждений положить m=n, то вариантов размещения будет n!, при этом любой вариант размещения может быть задан перестановкой 13 EMBED Equation.DSMT4 1415, где
·(i) – номер позиции, в которую устанавливается элемент ei.
Сформулируем математическую постановку задачи размещения.
Пусть L(
·) – суммарная длина межэлементных соединений, соответствующая некоторому варианту размещения
·.
Пусть ES – множество директивно размещенных элементов, к числу которых, в частности, относятся разъемы и внешние контактные площадки. Здесь S – множество индексов директивно размещенных элементов.
Рассмотрим некоторый произвольный заранее не размещенный элемент. Определим суммарную длину его связей со всеми директивными элементами. Обозначим эту длину как:
13 EMBED Equation.DSMT4 1415
где cis – элемент матрицы смежности 13 LINK \l "_Взвешенный_неориентированный_граф" 14ВНГ15.
Суммарная взвешенная длина межсоединений недирективно размещенных элементов ei и ej определяется как:
13 EMBED Equation.DSMT4 1415
С учетом (5.1) и (5.2) суммарная взвешенная длина межсоединений для варианта размещения
· будет определяться из выражения (5.3):
13 EMBED Equation.DSMT4 1415
Таким образом, необходимо найти такой вариант размещения 13 EMBED Equation.DSMT4 1415 при котором обеспечивается минимум целевой функции (5.3). Это комбинаторная задача размещения.
Теперь рассмотрим постановку задачи целочисленного программирования.
Пусть перестановочная матрица (матрица решений) имеет вид:
13 EMBED Equation.DSMT4 1415
На элементы матрицы решений X можно наложить следующие ограничения:
Т.е. каждому элементу соответствует одна позиция.

Каждый элемент может занимать только одну позицию.

При таком подходе суммарная взвешенная длина межсоединений может быть представлена следующим образом:
13 EMBED Equation.DSMT4 1415
В выражении (5.7) первый член это суммарная взвешенная длина межсоединений между собой недирективно размещенных элементов, второй член – суммарная взвешенная длина межсоединений между недирективно размещенными и директивно размещенными элементами.

Необходимо найти такую булеву матрицу решений X, которая удовлетворяла бы ограничениям (5.4) и (5.6) и обеспечивала минимум целевой функции (5.7). Эта задача является квадратичной задачей целочисленного программирования.

В случае когда элементы не связаны между собой и заранее не фиксированы, а связаны лишь с директивно размещенными элементами, соответствующая задача является задачей линейного назначения. Этот факт используется в ряде приближенных алгоритмов размещения.
В настоящее время разработано много алгоритмов размещения, классификация которых приведена на рисунке 5.1.
13 SHAPE \* MERGEFORMAT 1415
Рис. 5.1. Классификация алгоритмов размещения.
§ 6. КОНСТРУКТИВНЫЕ АЛГОРИТМЫ РАЗМЕШЕНИЯ
Среди конструктивных алгоритмов размещения выделяют последовательные и параллельно-последовательные алгоритмы.
В последовательном алгоритме используется n–шаговый процесс принятия решения. На каждом шаге здесь размещается один элемент. В параллельно-последовательном алгоритме на каждом шаге размещается группа элементов (или даже все элементы).
Среди последовательных алгоритмов различают последовательные алгоритмы размещения по связности и матричные алгоритмы.
Последовательные алгоритмы размещения по связности
Сущность этого многошагового алгоритма сводится к последовательному размещению очередного модуля (элемента) в определенный узел платы. Предполагается что часть модулей (или хотя бы один) заранее размещены на монтажной плоскости. В качестве таких модулей могут быть выбраны либо контакты разъема, либо модули, фиксированные в определенных позициях в соответствии с директивными указаниями разработчика. При выборе очередного модуля оптимизируется целевая функция, учитывающая связи этого модуля с множеством ранее размещенных и неразмещенных модулей. В качестве такой функции, например, может быть выбрана следующая:
13 EMBED Equation.DSMT4 1415
где cij – элемент матрицы смежности 13 LINK \l "_Взвешенный_неориентированный_граф" 14ВНГ15; 13 EMBED Equation.DSMT4 1415 – соответственно множества размещенных и неразмещенных на k–м шаге алгоритма модулей.
Задача размещения при этом сводится к максимизации оценки (6.1) по всем модулям, принадлежащим множеству 13 EMBED Equation.DSMT4 1415.
Далее для выбранного модуля находится наиболее приемлемая позиция на плате. Для выбора такой позиции используется критерий минимальности длины связей размещаемого модуля с уже размещенными модулями. При этом, очевидно, нет необходимости рассматривать все незанятые на этом шаге позиции, а достаточно оценить лишь множество позиций, соседних с занятыми. При этом позиция pi, в которую необходимо поместить i–й модуль, определяется из условия минимизации следующего выражения:
13 EMBED Equation.DSMT4 1415
где cij – элемент матрицы смежности 13 LINK \l "_Взвешенный_неориентированный_граф" 14ВНГ15; Rk –множество позиций, соседних с занятыми, на k–м шаге.
Рассмотрим работу последовательного алгоритма размещения по связности на примере (рис. 6.1).
13 SHAPE \* MERGEFORMAT 1415
Рис. 6.1.
Пусть элемент e2 директивно помещается в 6-ю позицию, элемент e3 директивно помещается в 9-ю позицию.
Чтобы выбрать очередной размещаемый модуль, необходимо в соответствии с (6.1) найти модуль с максимальной оценкой J.
П. 1.
Вычисляем оценки по связности для каждого неразмещенного модуля:
13 EMBED Equation.DSMT4 1415
Элементы e1 и e5 имеют максимальную оценку, равную +1. Для дальнейшего анализа выбираем элемент e1 (с меньшим порядковым номером).
П. 1.1.
Модуль e1 в соответствии с (6.2) размещаем во 2-ю позицию (с меньшим порядковым номером) (см. ниже).
13 EMBED Equation.DSMT4 1415
Определим F, предполагая, что модуль e1 размещен
13 EMBED Equation.DSMT4 1415
Окончательно размещаем e1 во 2-ю позицию (с меньшим порядковым номером) и корректируем массив соседних позиций.
13 EMBED Equation.DSMT4 1415



П. 2.
Определим следующий модуль для размещения.
13 EMBED Equation.DSMT4 1415
Модуль e5 имеет максимальную оценку, равную +1. в соответствии с (6.2) он помещается в 5-ю позицию.
И т. д. и т. п.
Окончательный вариант размещения представлен на рис. 6.2.
13 SHAPE \* MERGEFORMAT 1415
Рис. 6.2.
Укрупненная схема последовательного алгоритма размещения приведена на рисунке 6.3.
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
Рис. 6.3. Схема последовательного алгоритма размещения.
Замечание: соседние позиции.



Приведем краткий перечень идентификаторов для реализации последовательного алгоритма размещения.
L – число элементов;
D – число директивных элементов;
M – число позиций по горизонтали;
N – число позиций по вертикали;
E(I) – массив директивных элементов;
P(I) – массив директивных позиций;
POS(LI) – номер позиции, в которую размещается элемент с номером LI;
Z(I) – массив соседних позиций;
SP1 – список элементов, связанных с данным элементом;
SP2 – список количества связей между элементами;
RSP – список, устанавливающий связность SP1 и SP2.

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

13 SHAPE \* MERGEFORMAT 1415

Учтем, что списки имеют вид SP1=(2,4,9), SP2=(1,1), RSP(1)=0, RSP(1+1)=1, RSP(2)=3 от E(1) переходим к E(4).
При выборе позиции элемента ei часто используется не модель ВНГ а модель ГГ в этом случае при определении позиции можно учесть взаимное расположение элемента в цепи, а также использовать в качестве оценки для позиции критерий минимизации многоугольника охватывающего элементы цепи.
Тема Параллельно-последовательное размещение
Метод обратного размещения.
Для каждого из неразмещенных элементов ei принадлежащих E(I) I=13 EMBED Equation.3 1415 вычисляется некоторая оценка.
Вычисляется также некоторая оценка и для каждого посадочного места. Все элементы и посадочные места упорядочиваются и осуществляется одновременное размещение всех элементов в позиции.
Пусть матрица С=||сij||m*n; D=||dij||n*n-матрицы расстояний между позициями.
В соответствие с указанным методом для каждого элемента ei рассчитывается суммарное число связей i-го элемента с остальными частями схемы 13 EMBED Equation.3 1415 (1)
Для каждого посадочного места вычисляется суммарная длина расстояний j-ого посадочного места со всеми остальными позициями 13 EMBED Equation.3 1415
Все оценки связанности 13 EMBED Equation.3 1415 упорядочиваются по возрастанию, а оценки длины 13 EMBED Equation.3 1415 - по убыванию:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Элемент 13 EMBED Equation.3 1415 устанавливается в позицию Pj(1), 13 EMBED Equation.3 1415Pj(2) и т.д. Это связано с тем, что min скалярное умножение двух векторов будет тогда, когда компоненты первого вектора упорядочены по возрастанию, а элементы другого по убыванию.
Пример:









Распишем матрицы С и D
e1 e2 e3 e4 e5
e1
e2
e3
e4
e5

P1 P2 P3 P4 P5
P1
P2
P3
P4
P5

Lначальное=1+10+6+4+1+1+1=24
Упорядочим сi по возрастанию, di по убыванию.
с1э=10 с2э=2 с3э=2 с4э=7 с5э=7
d1п=6 d2п=5 d3п=7 d4п=6 d5п=8
таким образом второй элемент размещаем в 5-ю позицию, 3ий в 3ю позицию, 4й в 1ю, 5й в 4ю, 1й в 2ю.
Окончательный вариант размещения приведен на рисунке:

Lсуммарная=18 (18<24!)- что и требовалось доказать






Итерационные алгоритмы размещения
Эти алгоритмы предполагают заданным некоторое начальное размещение, которое может быть получено некоторым конструктивным алгоритмом размещения. Исследуются некоторое множество возможных вариантов размещения близких в некотором смысле к начальному и находящие размещение с меньшим значением целевой функции Lсуммарное. Найденное размещение принимается за исходное и процесс повторяется. Алгоритм заканчивает работу если в окрестности полученного размещения отсутствуют варианты с меньшими значениями целевой функции.
Различают 2 группы итерационных алгоритмов:
алгоритмы парных перестановок
алгоритмы групповых перестановок
Алгоритм парных перестановок.
Суть: Последовательное целенаправленное улучшение произвольного начального размещения модулей на плате по выбранному критерию путем парных перестановок. С этой целью на каждой итерации алгоритм осуществляет вычисление приращенной суммарной длины всех связей для всевозможных парных перестановок модулей. Из всего множества перестановок дающих отрицательное приращение выбирается подмножество которое удовлетворяет следующим требованиям:
выбранное подмножество перестановок позволяет max уменьшить суммарную длину всех связей.
подмножество образует лишь независимые перестановки в которых модули несвязанны с модулями других переставляющихся пар.
Далее осуществляется перестановки выделенных таким образом пар модулей и переход к следующей итерации.
Описанный итерационный процесс сходится к локальнооптимальному размещению модулей на плате. Выведем формулы для суммарной длины L всех связей и ее приращение 13 EMBED Equation.3 1415 при перемещение модулей.
Пусть имеется плоское или объемное плато с узлами предназначенными для установки модулей, задана матрица расстояний D=||dij||n*n где dij определяется в обычной или ортогональной метриках.
Даны некоторые совокупности модулей подлежащих размещению и матрица C=||cij||n*m числа связей этих модулей между собой.
Пусть на некоторой итерации имеется следующее размещение модулей на плате:
1 2 3 e n
мод t1 t2 t3 te tn
te- номер модуля оказавшегося размещенным в узле платы.
Поставим в соответствие этому варианту размещения матрицу связей R=||rij||n*n. Элемент rij=числу связей между модулями ti и tj находится на данной итерации в узлах i и j соответственно.
Так как расстояние между узлами i и k равно dik то суммарная длина связей между модулями ti и tk:
lik=rik*dik (1)
отсюда суммарная длина связей ti модуля расположенного в i-ом узле связаны со всеми модульными схемами равна:
13 EMBED Equation.3 1415 (2)
Для суммарной длины всех связей при данном варианте получаем формулу:
13 EMBED Equation.3 1415 (3)
Примечание: пусть i=k=13 EMBED Equation.3 1415 тогда 13 EMBED Equation.3 1415
Найдем формулу для приращения суммарной длины всех связей при перестановке мудулей ti и tj расположенных в узлах i и j соответственно.
Для суммарной длины связей ti и tj со всеми остальными модулями имеем:
13 EMBED Equation.3 1415 (4)
Замечание: пусть n=4 i=2 j=3
13 EMBED Equation.3 1415
Найдем формулу для приращения суммарной длины всех связей при перестановке модулей ti и tj расположенных в узлах i и j соответственно. Для суммарной длины связей ti и tj модулей со всеми оставшимися модулями имеем:
13 EMBED Equation.3 1415 (5)
Заметим, что за n-ое число перестановок модулей ti и tj соответствует перестановке строк и столбцов с номером i и j в матрице R. Вычитая из (5) выражение (4) определим приращение суммарной длины всех связей после перестановки модулей с номером ti и tj.
13 EMBED Equation.3 1415 i,j=13 EMBED Equation.3 1415 (6)
Введем в рассмотрение матрицу P=RxD,
13 EMBED Equation.DSMT4 1415.
Полусумма диагональных элементов матрицы P (полуслед) равна суммарной длине всех связей, определяемой формулой (3). С помощью элементов матрицы P могут быть легко вычислены элементы
·Lij матрицы приращений для всех парных перестановок. С учетом симметричности матрицы D выражение (6) преобразуется к виду:
13 EMBED Equation.DSMT4 1415;
где 13 EMBED Equation.DSMT4 1415
Вычисляя по выражениям (8) и (9) элементы матрицы приращений
·L можно выбрать подмножество перестановок, удовлетворяющих вышеперечисленным требованиям.


Пример.
Пусть начальное размещение связано с системой модулей на плате с 6-ю узлами имеет вид, представленный на рисунке:
13 SHAPE \* MERGEFORMAT 1415
Во втором узле размещен разъем, который запрещено переносить на другую позицию. Если расстояния dij между узлами i и j определены в ортогональной метрике, то матрица D будет иметь вид:



p1
p2
p3
p4
p5
p6



p1
0
1
2
1
2
3



p2
1
0
1
2
1
2

D
=
p3
2
1
0
3
2
1



p4
1
2
3
0
1
2



p5
2
1
2
1
0
1



p6
3
2
1
2
1
0





e1
e2
e3
e4
e5
e6



e1
0
1
0
1
0
0



e2
1
0
0
5
0
0

R
=
e3
0
0
0
0
6
1



e4
1
5
0
0
1
3



e5
0
0
6
1
0
1



e6
0
0
1
3
1
0

Составим соответствующую начальному размещению матрицу P=RxD. Элемент p11 определяется из выражения: p11=r11d11+r12d21+r13d31+r14d41+r15d51+ +r16d61=0+1
·1+0+1
·1+0+0=2 и т. д. и т. п.



1
2
3
4
5
6



1
2
2
4
2
2
4



2
5
11
17
8
7
13

P
=
3
15
8
13
8
1
6



4
16
8
12
18
10
14



5
16
10
4
20
14
8



6
7
8
11
4
5
8

Суммарная длина всех связей в начальном размещении равна полуследу матрицы P: 13 EMBED Equation.DSMT4 1415.
Вычислим далее последовательно матрицы
·,
·*, Q и
·L:





1
2
3
4
5
6





1
0
0
2
0
0
2





2
-6
0
6
-3
-4
2


·
=
||pij–pii||
=
3
2
-5
0
-5
-12
-7





4
-2
-10
-6
0
-8
-4





5
2
-4
-10
6
0
-6





6
-1
0
3
-4
-3
0









1
2
3
4
5
6







1
0
-6
2
-2
2
-1







2
0
0
-5
-10
-4
0


·*
=
||pij–pii||
=

·T
=
3
2
6
0
-6
-10
3







4
0
-3
-5
0
6
-4







5
0
-4
-12
-8
0
-3







6
2
2
-7
-4
-6
0







1
2
3
4
5
6





1
0
-6
4
-2
2
1





2

0
1
-20
-8
1

Q
=

·+
·*
=
3


0
-11
-22
-4

симметр.
4



0
-2
-8





5




0
-9





6





0





1
2
3
4
5
6



1
0
––
––
0
––
––



2

0
––
––
––
––


·L
=
3


0
-11
2
-2

симметр.
4



0
0
0



5




0
-7



6





0


·Lij=2rijdij(>0)+qij(>, <, =0)
В матрице
·L прочерком указаны элементы, которые заведомо являются положительными в силу положительности соответствующих элементов матрицы Q, а также элементы отвечающие недопустимому переразмещению модуля 2 (разъема). Из рассмотрения матрицы
·L видно, что к уменьшению суммарной длины всех связей приводят взаимные перестановки пар модулей, расположенных в начальном размещении в следующих узлах: 3 и 4 (
·L=-11), 3 и 6 (
·L=-2), 5 и 6 (
·L=-7).
Примечание. Пары модулей {ei и ej} и {ek и eq} являются независимыми если элементы матрицы связей R равны нулю. Для нашего примера допустимой является лишь одна перестановка (пара 3 и 4), обеспечивающая |
·Lmax|=11.
Производим перестановку элементов e3 и e4 (см. рис.):
13 SHAPE \* MERGEFORMAT 1415
Для нового варианта размещения находим матрицы R и P. С этой целью необходимо в матрице R, соответствующей начальному варианту размещения поменять местами элементы 3-го и 4-го столбцов и 3-ей и 4-ей строк. Матрица P получается умножением новой матрицы R на старую D.



1
2
3
4
5
6



1
3
1
1
5
3
3



2
10
6
2
16
12
8

P
=
3
16
8
12
18
10
14



4
15
8
13
8
1
6



5
11
15
19
5
9
18



6
9
6
5
10
7
6

Суммарная длина всех связей нового варианта
13 EMBED Equation.DSMT4 1415.
Выполним следующую итерацию.



1
2
3
4
5
6



1
0
-2
-2
2
0
0



2
4
0
-4
10
6
2


·
=
3
4
-4
0
6
-2
2



4
7
0
5
0
-7
2



5
2
6
10
-4
0
4



6
3
0
-1
4
1
0





1
2
3
4
5
6



1
0
2
2
0
2
3



2

0
-8
10
12
2

Q
=
3


0
11
8
1



4



0
-11
2



5




0
5



6





0





1
2
3
4
5
6



1
0
––
––
––
––
––



2

0
––
––
––
––


·L
=
3


0
––
––
––



4



0
1
––



5




0
––



6





0

Матрицы
·L не имеет ни одного отрицательного элемента, поэтому процесс улучшения начального размещения закончен. Т. о., размещение, изображенное на последнем рисунке соответствует локальному оптимуму.
Блок-схема алгоритма парных перестановок.
13 SHAPE \* MERGEFORMAT 1415
§ ЗАДАЧА ПОКРЫТИЯ СХЕМ НАБОРОМ КОНСТРУКТИВНЫХ МОДУЛЕЙ.
В результате решения задачи покрытия каждый элемент схемы привязывается к некоторому конструктивному модулю из набора Q={Q1, Q2, ,Qm}.
Математическая постановка задачи покрытия зависит от типа конструктивных модулей набора. Различают 3 типа конструктивных модулей:
Каждый модуль содержит базовые логические элементы одного типа, при этом все входы и выходе логических элементов являются выводами модуля.
Например:
13 SHAPE \* MERGEFORMAT 1415
Тоже что и предыдущий тип, однако в одном конструктивном модуле могут содержаться разнотипные логические элементы.
13 SHAPE \* MERGEFORMAT 1415
Модули 1-го и 2-го типов называются модулями с несвязанными элементами.
Конструктивный модуль в общем случае содержит связанные между собой разнотипные элементы и не все входные и выходные выводы элементов имеются на внешних контактах конструктивного модуля.
13 SHAPE \* MERGEFORMAT 1415
Рассмотрим математическую постановку задачи покрытия схемы конструктивными модулями с несвязанными элементами (1-го и 2-го типов).
Обозначим через bi количество логических элементов ti типа, содержащихся в функционально-логической схеме (ФЛС). При таком подходе состав ФЛС может быть описан матрицей-столбцом: B=||bi||n, где n – число типов логических элементов схемы, bi – число логических элементов ti типа в ФЛС. Будем считать, что каждый тип конструктивного модуля Qj в общем случае содержит несколько типов ti базовых элементов, а весь набор конструктивных модулей Q может быть описан матрицей A=||aij||nxm, где aij – количество базовых логических элементов типа ti в конструктивном модуле типа Qj (13 EMBED Equation.DSMT4 1415).
Пример.
13 SHAPE \* MERGEFORMAT 1415



Q1
Q2
Q3



t1
2
0
1

A
=
t2
1
1
0



t3
0
1
0



t4
0
0
1

В качестве критерия оптимизации будем использовать минимум стоимости покрытия. Обозначим cj стоимость конструктивного модуля Qj.
Пусть для покрытия ФЛС необходимо выделить yj конструктивных модулей Qj, тогда в качестве целевой функции можно взять функцию вида:
13 EMBED Equation.DSMT4 1415.
Будем считать, что каждый тип базового логического элемента схемы может быть реализован как базовый логический элемент того же набора, так и БЛЭ другого типа набора. Например:
13 SHAPE \* MERGEFORMAT 1415
Обозначим через xki количество логических элементов типа tk, которое идет на покрытие логических элементов схемы типа ti. Возможность замены БЛЭ типа tk на БЛЭ типа ti будем описывать матрицей W=||wki||nxn,
13 EMBED Equation.DSMT4 1415
Очевидно, что xki>0 если wki=1.
Учитывая введенные обозначения, задачу покрытия можно сформулировать следующим образом: если yj количество требуемых конструктивных модулей типа Qj, а в каждом Qj конструктивном модуле содержится aij элементов типа ti, то 13 EMBED Equation.DSMT4 1415 определяет количество логических элементов типа ti, содержащихся во всем выделенном для покрытия ФЛС наборе конструктивных модулей.
Очевидно, что для покрытия всей ФЛС необходимо выполнение следующего условия:
13 EMBED Equation.DSMT4 1415,
где второе слагаемое – количество логических элементов других типов, которые идут в покрытии на реализацию логических элементов типа ti; последнее слагаемое – количество логических элементов типа ti, которые идут на реализацию логических элементов других типов.
Т. о., ставится задача отыскания таких значений yj и xki, удовлетворяющих (**), чтобы обеспечивался минимум целевой функции (*) – стоимости покрытия. На практике используются приближенные методы, опирающиеся на специфику используемых конструктивных модулей. Если имеем дело с несвязанными элементами конструктивного модуля, то здесь в результате определения требуемого числа модулей не осуществляется привязка логических элементов схемы к конструктивным модулям, отсюда появляется возможность оптимизации по другому критерию, в частности по критерию минимума межблочных связей.
Пример Q={Q1, Q2, Q3}, t={t1, t2, t3, t4} приведен нами выше. Требуется покрыть ФЛС, описываемую вектором B={5, 4, 1, 1}, заданным набором конструктивных модулей.
Блок-схема алгоритма определения требуемого числа конструктивных модулей по критерию минимума стоимости покрытия приведена на рисунке.
13 SHAPE \* MERGEFORMAT 1415


Требуемое число корпусов модуля j-го типа определяется из выражения:
13 EMBED Equation.3 1415 (1)
Для нашего примера:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Так как a31=0 и a41=0, то в качестве коэффициента 13 EMBED Equation.3 1415
Полагаем, что j=2 и вычисляем
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415и следовательно 13 EMBED Equation.3 1415
j=3 13 EMBED Equation.3 1415
Переходим к 13 EMBED Equation.3 1415:
13 EMBED Equation.3 141513 EMBED Equation.3 1415, (остальные bi=0) 13 EMBED Equation.3 1415
Т.о. имеем 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Эти данные подставляем в выражение (1) и определяем:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
После определения требуемого числа корпусов, можно осуществить привязку элементов к корпусам. Для этого могут быть использованы рассмотренные ранее алгоритмы решения задач компоновки (задачи разбиения).
Трассировка печатных соединений
Исходными данными для решения задачи трассировки печатного монтажа являются: принципиальная схема соединений; таблица размещения элементов; конструкторско-технологические ограничения:
размеры печатной платы
количество слоёв многослойной печатной платы (МПП)
области, запрещенные для прокладки проводников
минимальная ширина проводников
минимальное расстояние между проводниками
типы и размеры контактных площадок
шаг координатной сетки
При этих исходных данных необходимо реализовать все соединения так, чтобы соединения, принадлежащие разным цепям в одном слое не имели пересечений. Дополнительно необходимо оптимизировать следующие показатели качества:
минимум суммарной длины проводников (из-за 13 EMBED Equation.3 1415)
минимум числа переходных отверстий (электрическая надежность и механическая прочность)
минимальная длина параллельных участков соседних проводников
максимальная удаленность проводников друг от друга ( Lпар и Cпар должны быть минимальными)
равномерное распределение проводников в монтажной плоскости
Трассировка печатных соединений предполагает выполнение следующих этапов:
Определение порядка соединения выводов внутри цепи (построение кратчайшего связывающего дерева - КСД).
Распределение соединений по слоям МПП.
Нахождение последовательности проведения соединений в каждом слое.
Получение конфигурации проводников.

Первый этап: Определение порядка соединения выводов внутри цепи
Задача сводится к построению КСД. При печатном монтаже соединения можно выполнять не только по эквипотенциальным выводам, но и в любой точке проводника, поэтому построение КСД здесь формируется как задача Штейнера:
К множеству P={P1,P2,,Pn}, i=1,n основных точек добавить множество S={S1,S2Sm} дополнительных точек и построить КСД. Множество P основных точек сопоставлено выводам цепи, а дополнительные точки представляют собой места соединений типа проводник-проводник. При определении положения дополнительных точек можно рассматривать только узлы координатной сетки, построенной на n заданных точках. Тогда число таких точек Q<=n-2.
Метод точного решения задачи Штейнера для реальных цепей требует больших затрат машинного времени.
Второй этап: Распределение соединений по слоям.
В результате выполнения первого этапа трассировки электрическая цепь представляется КСД, являющимся плоским графом. Но совокупность КСД (МС) может иметь пересечения между ребрами, принадлежащими разным деревьям, так как последние строятся на фиксированных вершинах и существуют ограничения на размер монтажного поля, ширину проводников и зазоры между ними, в тоже время в каждом слое печатные проводники не должны пересекаться.
При ортогональной трассировке возможно распределение соединений по двум слоям, при этом каждая цепь представляется в виде ортогонального покрывающего дерева, вертикальные ветви которого находятся в одном слое, а горизонтальные – в другом. На рисунках показано КСД (1а ) и ортогональное Штейнерово дерево (1б).



















В узлах дерева Штейнера необходимо делать межслойные переходы, при этом количество переходов может быть весьма большим, что ухудшает механические параметры печатной платы и снижает надёжность схемы.
В общем случае распределение соединений по слоям может быть сформулировано как задача правильной раскраски вершин графа пересечений (см. ниже).
При ортогональной трассировке на вершинах каждой цепи строится минимальный охватывающий прямоугольник (рис. 1в). Считается, что два соединения пересекаются, если перекрываются соответствующие им многоугольники.
При представлении цепи КСД необходимо определять пересекается ли каждая пара ветвей этих деревьев. Для пары ветвей при известных координатах вершин составляются уравнения прямых линий и исследуются эти уравнения, методами аналитической геометрии определяют возможность пересечения соответствующих соединений.
Отметим, что перекрытие многоугольников, построенных на вершинах цепей или пересечений КСД, ещё не означает, что соответствующие цепи нельзя трассировать на одном слое без пересечений.
На рис.1г показаны перекрывающиеся прямоугольники и пересекающиеся цепи, соединяющие охватываемые ими вершины, пересекающиеся КСД (1д) и не пересекающиеся трассы, соединяющие те же вершины.
При учете возможности проведения конфликтующих проводников без пересечения за счет огибания, распределение соединений по слоям может быть сделано путем объединения проводников, идущим под некоторым углом друг к другу в группы. Каждая такая группа затем трассируется в своем слое. Например, при ортогональной трассировке ребро Hij КСД относится к группе горизонтальных, если |xi-xj|>=|yi-yj| и к группе вертикальных в противном случае.
Для МПП проводники могут группироваться в соответствии с их принадлежностью некоторым секторам, заданным для каждого слоя.
Третий этап: Задача нахождения последовательности проведения соединений в каждом слое.
Трассировка соединений выполняется последовательно, и каждая проложенная трасса является препятствием для всех не проведенных.
Сформируем условия отсутствия пересечения двух ребер и методику определения последовательности их проведения.
Координаты пересечения двух кривых определяются из выражения:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


где
13 EMBED Equation.3 1415
Ребра пересекаются если 0<=13 EMBED Equation.3 1415<=1 и 0<=13 EMBED Equation.3 1415<=1

Пример: 1) xi=1, yi=1, xk= 3, yk=6,
xj=8, yj=8, xp=7, yp=4,
13 EMBED Equation.3 1415=3/7; 13 EMBED Equation.3 1415=0,5 – прямые пересекаются
2) xi=1, yi=1, xk= 3, yk=6,
xj=4, yj=4, xp=7, yp=4,
13 EMBED Equation.3 1415= -1/3 (<0); 13 EMBED Equation.3 1415=0,5 – прямые не пересекаются
На основании выражения (1) определяется список пересекающихся ребер. Непересекающиеся ребра можно трассировать в произвольном порядке. Для определения последовательности проведения пересекающихся ребер составляют уравнения удлинения при огибании считая, что огибающий проводник может проходить сколь угодно близко от вершины. Эти уравнения составляются для всех пар пересекающихся ребер. Для каждого ребра подсчитывается число огибаний и удлинение. Список ребер ранжируется в порядке возрастания числа огибаний. Если у некоторых групп ребер число огибаний одинаково, то первыми проводятся ребра с меньшим удлинением.
На рисунке 2 изображены два ребра. Если первым провести ребро Hij, то удлинение второго ребра lkp при огибании вершин i и j будет определяться: 13 EMBED Equation.3 1415
Так как пересечение рассматривается только для пары ребер, то необходимо дополнительно проверять отсутствие пересечений с другими близлежащими ребрами.
Этап 4: Трассировка отдельных соединений.
Чаще всего эта задача решается в два этапа. В начале осуществляется предварительная приближенная трассировка, а затем окончательная.
Приближенная трассировка представляет собой стадию планирования окончательной трассировки, на которой определяется по каким областям (каналам) должны следовать отдельные соединения. Предварительная трассировка осуществляется на макромодели.
Цель её – равномерно распределить соединения без превышения пропускной способности областей каналов. Чаще всего она осуществляется за два прохода:
На первом проходе допускается превышение пропускной способности и в расчет принимается только кратчайшие расстояния между соединениями. После первого выявляются критические каналы области, и регистрируется превышения пропускной способности.
Второй этап обычно состоит из нескольких итераций, на каждой из которых вводятся прогрессирующие штрафы за превышение пропускной способности.
В результате выполнения приближенной трассировки окончательная трассировка распадается на ряд боле простых задач, имеющих меньшую размерность. Методы окончательной трассировки могут быть разбиты на три группы:
волновой алгоритм и его модификации.
алгоритм трассировки по магистральным каналам.
комбинированные алгоритмы.
Математические модели монтажного пространства
Под монтажной областью типовой конструкции понимается метрическое пространство, в котором устанавливаются входящие в неё типовые конструкции предыдущих уровней, и выполняется электронное соединение выводов. Формальная постановка и решение задач в топологическом конструировании невозможны без получения математической модели монтажного пространства. К которой предъявляются требования высокой степени формализации и наиболее точного и полного отображения метрических параметров и топологических свойств конструкции.
Метрическими параметрами являются габаритные размеры зоны монтажа, допустимая ширина проводников и зазоры между ними, координаты и размеры внешних контактных площадок, шаг установки и размер модулей, координаты и размеры полей их контактов.
К топологическим свойствам относятся: число слоев МПП и переходов со слоя на слой;
наличие замкнутых областей, запрещенных для проведения соединений; ограничение на взаимное расположение соединений; количество монтажных проводов, проводимых к одному выводу цепи.
В качестве математической модели монтажного пространства используется неориентированный топологический граф Gr (граф решетки). При этом плоскость монтажного пространства разбивается на элементарные площадки, стороны которых равны шагу проложения проводника по соответствующему направлению. Для печатного монтажа элементарная площадка – квадрат. Каждой элементарной площадке ставится в соответствие вершина графа решетки. Две вершины графа соединяются ребром, если между соответствующими площадками может быть проведено соединение с учетом метрических и топологических параметров конструкции.
Пример ортогонального монтажа.
13 SHAPE \* MERGEFORMAT 1415
ВОЛНОВОЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
ТРАССИРОВКИ.
Большинство алгоритмов конфигурации печатных проводников используют идею волнового алгоритма Ли, который представляет собой процедуру нахождения кратчайшего пути в графе.
В работе Ли плоскость монтажа разбивается на элементарные прямоугольники (ячейки), со стороной равной расстоянию между осями соседних печатных проводников. Минимальная величина прямоугольника (ячейки) определяется технологическим оборудованием.
При использовании ДРП, включение элементарной ячейки в путь означает проведение печатного проводника, так как показано на рисунке 1.








Рис. 1
Считаем, что основная координатная сетка смещена на h/2, чтобы пути следовали из ячейки в ячейку, а не по координатным линиям ДРП.
На каждом шаге алгоритма некоторые ячейки ДРП – заняты. Ячейки, попадающие в область запрещённых для трассировки: краевые поля платы, зоны размещения элементов и их выводы, ранее проведённые проводники.
Основа алгоритма Ли – процедура поиска оптимального, в смысле некоторого критерия, пути между двумя ячейками, при соблюдении ряда условий:

А






(












В



Первая часть алгоритма моделирует процесс распространения волны от элементарной площадки А по свободным ячейкам ДРП. При распространение волны от А, алгоритм последовательно строит Ф1(А), Ф2(А), , Фk(А) её фронты. Множество ячеек входящих в i-е фронты для всех i
·k – это окрестность ячейки А. Оk(А).
Если проведение пути возможно, то на k+1 шаге окажется, что В(Оk+1(А), если в следующий фронт не удаётся включить ни одной свободной ячейки, т.е.
Оk(А)= Оk+1(А) , то при данных условиях путь провести невозможно.
Т.о. первая часть алгоритма Ли определяет возможность проведения пути между А и В.
Во второй части алгоритма Ли, начиная с В по определённым правилам выполняем переход от ячейки k-го фронта к ячейки k-1 фронта, до тех пор, пока не будет достигнута А. Пройденные ячейки – искомый путь.
Условия, которые д.б. выполнены при проведении пути и возможность оценки его оптимальности д.б. заложены в правила, по которым происходит движение фронта.
Для ячеек ДРП устанавливается отношения соседства (общее ребро). Распространение волны заключается в присваивании соседним ячейкам значения весовой функции. Вес ячейки k-го фронта Pk является функцией веса ячейки k-1 фронта. В общем случае к весам ячеек предъявляются следующие требования: Pk-1( Pk ( Pk+1 , в большинстве модификаций алгоритма Ли на веса ячеек накладывается ограничение: Pk> Pk-1. В этом случае проведение пути заключается в переходе от А к В, т.о. чтобы Pk монотонно убывало. При этом возможен вариант, когда несколько ячеек соседних с данной имеют одинаковый вес. Для однозначного выбора при учёте критерия минимального кол-ва изгибов проводника следует сохранить направление движения. Если приходится делать поворот, то учитываем заранее заданный порядок предпочтений.
Например, пусть Pk= Pk-1+1 – т.е. равно расстоянию k-й ячейки от исходной ячейки А в ортогональной метрике (с учётом запрещённых ячеек). Работа алгоритма для этого случая приведена на рисунке:

1
2
3
4
5
6
7
8
9
10
11
12

1
4
3
2
3
4
5
6
7
8
9
10
#

2
3
2
1
2
3
4
5
6
7
8
9
#

3
2
1
A
1
2
#
6
7
8
9
10
#

4
3
2
1
2
3
#
7
8
9
10
11
#

5
4
3
2
3
4
#
8
9
10
#
#
#

6
5
4
3
4
5
#
9
10
11
B



7
6
5
4
5
6
7
8
9
10
11



8
7
6
5
6
7
8
9
10
11




Рис. 2.
Волна распространяется из А, PA =0 фронт волны доходит до В на 12 шаге. В ходе построения пути из ячейки (6,9) с Р=11, можно перейти в 3 соседние ячейки с Р=10. здесь переход осуществляется сохраняя направление влево – вверх, аналогично из ячейки с Р=10, у ячейки Р=9, 2 соседних ячейки Р=8, т.к. в этом случае приходится изменять направление движения, то переходим по предпочтённому направлению – вверх. Т.к. вес k-й ячейки в данном варианте равен расстоянию от А, то найденный путь – оптимальный, в смысле его длины. Т.к. алгоритм Ли представляет собой алгоритм нахождения кратчайшего пути в графе, то он легко распространяется на многослойный печатный монтаж, при использовании модификации в виде графа. При наличии ограничения на переходы со слоя в слой можно увеличить вес ребра, соединяющего две смежные вершины графа на соседних слоях, по сравнению с весом ребра графа соединяющего вершины в одном слое. В общем случае весовая функция может зависить от параметров учитывающих длину пути, числа переходов из слоя в слой, степень близости пути к другому и т.д. Например, в виде аддитивной функции:
13 EMBED Equation.3 1415
аi – весовой коэффициент, учитывающий важность i-го параметра.
Pi(k) – значение учитываемого параметра.
Усложнение функции веса увеличивает объём информации на одну ячейку ДРП и время работы 1-й части алгоритма. При практической реализации алгоритма Ли важная проблема – сокращение объёма памяти необходимого для запоминания весов ячеек. При вычислении весов ячеек по выражению: Pk=Pk-1+1ячейка м.б. в следующих состояниях: свободна, занята или имеет вес от 1 до L (максимально возможная длина пути, определяемое как кол-во ячеек ДРП в пути).
Необходимое, для запоминания состояния одной ячейки, число 2-х разрядов памяти:
13 EMBED Equation.3 1415
«Замечание: перед логарифмом стоит символ = зеркальное отражение Г»
Наиболее эффективным способом кодирования состояния ячеек ДРП является: метод путевых координат по модулю 3. При выборе последовательности, ячеек на этапе построения пути по методу путевых координат, для каждой ячейки, начиная с В (в случае соседства по рёбрам), достаточно знать от какой соседней ячейки в неё пришла волна: ((3), ((2), ((1), ((4). Т.о. ячейка здесь может иметь следующие признаки: свободна, занята, одна из путевых координат, следовательно, число разрядов для кодирования состояния ячеек равно 3.
Путевой координатой Ci фронта Фk является та соседняя с ней ячейка Cj фронта Фk-1, от которой Ci получила свой вес.
При использовании метода путевых координат соседним ячейкам присваиваются веса в соответствии с пожеланиями пользователя. При проведении пути следует двигаться направлении противоположном распространению волны, в соответствии с путевыми координатами.

Кодирование весов ячеек по mod3.
Оно базируется на том, что Pk-1( Pk ( Pk+1. Ячейкам включённым в последующие фронты можно присваивать не сами веса, а их значения по mod3 (1,2,3,1,2,3). Кол-во разрядов на кодирование состояний ячеек равно 3. На практике используется понятие вертикальной и горизонтальной полузанятости ячейки, эти состояния также нужно кодировать.
Проведение пути заключается в отслеживание отметок (1,2,3). Если ячейка имеет несколько соседних ячеек с одинаковыми метками, то используется правило приоритетных направлений.
При движении от ячейки В на рис. 3 используется следующие правило приоритетов:(, (, (, (.


1
2
3
4
5
6
7
8
9
10
11
12

1
2
1
3
2
3
1
2
3
1
2
3
#

2
1
3
2
1
2
3
1
2
3
1
2
#

3
3
2
1
А
1
2
#
3
1
2
3
#

4
1
3
2
1
2
3
#
1
2
3
1
#

5
2
1
3
2
3
1
#
2
3
#
#
#

6
3
2
1
3
1
2
#
3
1
B



7
1
3
2
1
2
3
1
2
3
1



8
2
1
3
2
3
1
2
3
1




Рис. 3.

ЛУЧЕВОЙ АЛГОРИТМ ТРАССИРОВКИ.
В этом алгоритме уменьшение временных затрат достигается за счёт распространения волны не по всему полю платы, а только вдоль лучей. Идея: при распространении волны фронт занимает не все свободные соседние ячейки ДРП, а лишь одну, т.о. последовательность фронтов – луч.
Во-вторых, лучевой алгоритм трасс Абрайтеса из начала А и конца В трассы распространяются навстречу друг другу по двум лучам А1, А2, В1, В2.
Лучи А1,2 и В1,2 называются разноимёнными, лучи поочерёдно распространяются (шагают) до тех пор, пока разноимённые лучи не пересекутся или пока 4 луча не смогут продвигаться дальше, т.е. окажутся в тупике. В первом случае, осуществляется переход ко второму этапу – проведению трассы. Для этого от пересечения лучей осуществляют возврат по ячейкам, принадлежащим лучам , в исходные А и В ячейки трассы (используя метод путевых координат). Во втором случае, трассу проложить невозможно.
Пример приведён на рисунке:
8











7





(
(
(
(
(

6

А
(А2
(
(
((
#
#
(


5

(А1



((
#
((В1
(В2


4

(



((
#
((
В


3

(



((
#
(



2

(


#
#
#
(



1

(
(
(
(
(
(
(




1
2
3
4
5
6
7
8
9
10


Прежде всего, необходимо выбрать приоритетные направления движения лучей:
Для луча А1 – вниз (основное), вправо (дополнительное);
А2 – вправо(основное), вниз (дополнительное);
В1 – влево (основное), вверх (дополнительное);
В2 – вверх (основное), влево (дополнительное).
Каждый луч осуществляет шаг движения по своему основному направлению или, если соответствующее этому направлению соседняя ячейка занята – по дополнительному.
После выполнения очередного шага всеми лучами, производится проверка на пересечение разноимённых лучей.
Вывод луча из тупика осуществляется следующим образом: луч возвращается в ту ячейку, где он изменил направление движения с основного на дополнительное. Затем, продвигается на шаг в направлении, противоположном дополнительному и делается попытка продвижения его по основному направлению.
Если луч снова оказался в тупике, делается ещё один шаг в направлении, противоположном дополнительному.
Эта процедура повторяется до тех пор, пока луч не получит возможность продвигаться по своим приоритетным направлениям или не будет заблокировано направление, противоположное дополнительному. В последнем случае продвижение луча прекращается.
Если все 4 луча будут заблокированы, то трассу проложить нельзя.
Отметим, что при выводе i-го луча из тупика, другие лучи останавливаются для того, чтобы продвижение лучей было равномерным.
На рисунке луч В1 после 3-х шагов оказывается в тупике в ячейке с координатами (8,6).
При выводе из тупика, В1 сначала возвращается в ячейку (8,4), затем делает шаги в ячейке (8,3) и (8,2) и далее продвигается по своему основному направлению до встречи с лучом А1.
Лучевой алгоритм трассировки осуществляет проведение пути минимальной длины без пересечений.
Вероятность нахождения пути этим алгоритмом меньше, чем алгоритмом Ли.
Методы ускорения работы волнового алгоритма.
Волновой алгоритм характеризуется высокой эффективностью нахождения пути за счёт исследования всех свободных ячеек ДПР, но требует значительного времени t на распространение волны.
Используются различные методы ускорения выполнения 1-го этапа алгоритма.
1).Одним из них является правильный выбор начала точки трассы.
13 SHAPE \* MERGEFORMAT 1415
Рис.1.
Из-за рассмотрения рис.1 видно, что при выборе в качестве источника распространения волны ячейки А, максимально удалённой от центра платы, просматривается меньшее число свободных ячеек ДПР. Это становится очевидным по мере роста числа протрассированных цепей.
2). Более эффективен метод встречной волны (рис.2)
13 SHAPE \* MERGEFORMAT 1415
13EMBED Equation.31415 - выигрыш в количестве ячеек.
Для реальных состояний ДРП выигрыш во времени будет отличаться от 2. Однако, в среднем, оценка является объективной.
Использование данной идеи приводит к усложнению алгоритма.
3). Поле распространения волны можно уменьшить, ограничивая его охватывающим прямоугольником, внутри которого находятся ячейки А и В.
Начальная площадь прямоугольника (печатной платы) обычно на 10-20% больше площади прямоугольника, проходящего через ячейки А и В. Если при этом соединение найти не удалось, то границы охватываемого прямоугольника рассматриваются. Данный метод обладает большей эффективностью ускорения работы алгоритма по сравнению с методами 1 и 2.
Алгоритм Рабина.
Увеличение быстродействия в алгоритме Рабина достигается за счёт преимущественного распространения волны в направлении ячейки-цели.
В алгоритме Ли, который является реализацией метода динамического программирования, такая целенаправленность отсутствует.
Алгоритм Рабина, который реализует метод ветвей и границ, позволяет также, как и алгоритм Ли, находить глобальный оптимум целевой функции (Lmin).
Пусть требуется найти путь min длины между ячейками А и В.
Рассмотрим некоторую ячейку Сi , включаемую в очередной фронт волны. Значение волновой функции Сi , приписываемое Сi ячейки фронта, определяется из выражения:
13EMBED Equation.31415 ,
где L(I,A) – длина пройденного волной пути из ячейки А в ячейку Сi , а
13EMBED Equation.31415- расстояние между Сi,В в ортогональной метрике.
Нетрудно увидеть, что 13EMBED Equation.31415 является нижней оценкой пути из Сi в В, полученной в предположении отсутствия препятствий на этом пути.
Отсюда, выражение (1) в целом представляет собой нижнюю оценку пути из А в В, проходящую в ячейку Сi .
Согласно методу ветвей и границ, оптимальное решение следует искать в подмножестве решений, имеющем наилучшую оценку. В соответствии с этим в сформированном очередном фронте волны выделяют подмножество ячеек с min оценкой 1 и распространение волны на следующем шаге осуществляется из ячеек этого подмножества.
Заметим, что для сокращения зоны поиска, распространение волны в алгоритме Рабина осуществляется в первую очередь, из тех ячеек с min оценкой, которые получили эту оценку последними.
Последовательность просмотра соседних ячеек та же, что и в алгоритме Ли (например: , , , ) - построение пути осуществляется с использованием путевых координат.
Эффективность алгоритма Рабина по сравнению с алгоритмом Ли показана на рис.3, на котором для каждой ячейки ДПР указано значение весовой функции Pi . Цифрами в правых углах ячеек обозначена последовательность рассмотрения ячеек на этапе распространения волны.
рисунок

Алгоритм слежения за целью.
Возможно дальнейшее сокращение зоны поиска при трассировке в случае приближений реализации метода ветвей и границ, получивших название «алгоритм слежения за целью». В этом алгоритме в качестве значений весовой функции для ячейки Сi на этапе распространения волны используется выражение (2).
Здесь распространение волны происходит из тех ячеек очередного фронта, которые ближе расположены к ячейке – зоне (запрещённые ячейки не учитываем). При этом сокращается зона поиска. Однако, из-за приближённого вычисления нижней оценки для подмножества путей, ведущих из А в В через С-пути, возможна потеря глобального минимума.
Проведение пути с помощью алгоритма слежения за целью основано на использовании метода путевых координат.
Примечание. В этом алгоритме распространение волны осуществляется от множества ячеек с минимальной оценкой, начиная с ячейки, которая получила эту минимальную оценку последней (или первой).
Пример: поле 12*8.
Ри сунок
Распределение соединений по слоям многослойной печатной платы.
Многослойный монтаж печатных (плёночных) соединений между компонентами электронной схемы позволяют сократить суммарную длину соединений (
·зад. min), уменьшить вес и габариты проектируемой аппаратуры.
При разработке многослойных структур возникает задача распределения по отдельным слоям печатных плат схемы соединений, претендующих на одни и те же области монтажного пространства (конфликтующих между собой).
Целью решения этой задачи является обеспечение 100% трассировки соединений, уменьшение числа слоёв и межслойных переходов, наиболее рациональное использование объёма монтажного пространства.
Алгоритмическое распределение соединений по слоям может выполняться до, после или в процессе трассировки отдельных соединений.
Расслоение до трассировки связано с анализом схемы соединений с целью выявления тех соединений или групп соединений, распределение которых в 1 слой неизбежно приведёт к возникновению пересечений на этапе трассировки.
Наиболее общий подход к такому анализу предполагает использование топологических методов, позволяющих на основе исследования свойства планарности графа (гиперграфа) схемы выявить возможность её реализации без пересечений в заданном (минимальном) числе слоёв.
Несмотря на то, что требование планарности графа схемы является решающим условием её плоской реализации, тем не менее, ограничение метрического характера (ограниченные размеры конструкции, контроллера, длины проводников и т.д.) создают трудности при практическом использовании топологического подхода к рассмотрению.

Большинство приближенных алгоритмов расслоения до трассировки связана с введением определенных количественных оценок, конфликтуемости цепей при их распределении в 1 слой. Эти оценки вычисляются на основе инф-ии о расположении элементов и контактов цепей, полученных после решения задач размещения. Такого рода оценки могут зависеть от степени перекрытия минимальных прямоугольников, охватывающих контакты отдельных цепей, числа контактов цепей и т.д. После определения степени конфликтуемости каждой пары цепей строится взвешенный неор. граф конфликтов, в котором кажд.вершине hH соответствует некоторая цепь , а каждому ребру vi,j V соот-т наличие конфликта между цепями Hi и Hj.Вес принимается равным оценке конфликтуемости между соот-ми цепями. Далее осуществляется раскраска вершин графа G в заданное число цветов, при котором сумма весов ребер, соединяющих вершин одного цвета минимальна. Раскраска вершин графа конфликтов осуществляется различными эвристическими алгоритмами.
Расслоение после предварительной трассировки состоит в следующим. На 1-м этапе с помощью одного из алгоритмов построения кратчайших, связ-х деревьев(КСД) осуществляется предварительная трассировка соединений в одном слое. В процессе получения совмещенной топологии минимизируется такие геометрические размеры как длина, число перегибов, число пересечений. Далее также, как и в алгоритме расслоения до трассировки строится граф конфликтов, но не между цепями, а между отдельными двухконтактными соединениями(отрезками проводников) При этом граф конфликтов G=(X,V) явл-ся неорг-м графом, наличие ребра в котором между xi и yj соответствует пересечению отрезков в совмещенной топологии.
Пример
13 SHAPE \* MERGEFORMAT 1415
К=2(требуемое число слоев)
Вершина ГК раскрашивается в заданное минимальное число цветов так, что вершина первого цвета не имеет ни 1 единого ребра. Каждое подмножество, соответ-е вершинам 1-го цвета распределяется в 1 из слоев. Не вошедшие ни в 1 из подмножеств отрезки,( что м. иметь место при заданном К последовательно распределяется в те слои, в которых они имеют минимальное число пресечений).
Расслоение в процессе трассировки осуществляется одновременно с прокладкой соединений многослойным ДРП с помощью различных модификаций волнового алгоритма трассировки. Рассмотрим математическую постановку задачи по слоям после предварительной трассировки. Будем считать число слоев К. Пусть G=(X,Y)– граф пересечений, в котором каждой вершинеxi соответствует отрезок i , i=1,n, а ребру(xixj)соответствует n отрезков i и j в совмещенной топологии.
Требуется распределить отрезки по слоям, т.о., чтобы суммарное число пересечений было минимальным.
Введем в рассмотрение матрицу Y=[yij]n*k 1, отр-к xi помещен в слой j
yij= 0, в противном случае
При таком подходе задача расслоения может быть сформулирована:
Требуется минимизировать 13 EMBED Equation.3 1415 (*), где cij – соответствующий элемент матрицы смежности cij = 1, если i и p конфл-т между собой
0, в прот. Случае
На элементы i и j наложены ограничения:
13 EMBED Equation.3 1415 (любой отрезок может быть помещен в 1 из слоев)
Данная задача является квадратичной задачей целочисленного программирования с булевыми переменными (yij,ypj) Рассмотрим приближенный алгоритм ее решения.
Алгоритм расслоении МПП
В соответствие с результатами предварительной трассировки строится граф конфликтов отрезков в размещенной топологии схемы.
Из графа конфликтов последовательно удаляется вершины, имеющие локальную степень(число ребер, инцидентных вершине)Формируется список S1 отрезков, распределенных в 1-й слой. С этой целью в графе G1=(X1,V1), гдеX1=X\S; V1=V\Vs , гдеVs – множество ребер, инцидентных вершинам множества S . В этом графе находится максимальное число несмежных между собой вершин. При этом используется приближенная процедура. Из графа G1 последовательно удаляется вершины с максимальными локальными степенями до получения графа без ребер. Множество оставшихся при этом вершин графа включается в список S1. Очевидно, что соответствующие этому списку отрезки между собой не конфликтуют и могут быть расположены в 1-м слое без пересечений
Далее из графа G1, из которого исключены вершины списка S1 последовательно удаляются и заносятся в список S вершины, имеющие локальную степень <(K-1). Отрезки, соответ-ие этим вершинам всегда м.б. расположены в (К-1) слой (кроме 1-го) без пересечений. Получаем граф G2=(X2,V2) X2=X\(SUS1); V2=\(VsUVs1)
Аналогично формируются S1S2,S3,..,Sk . При этом м. остаться некоторое множество отрезков S*, которое нельзя реализовать без пересечений в 1-м слое.
Из списка S последовательно в порядке, обратно порядку включения в список выбирается очередной отрезок и включается в тот слой, в который он не имеет пересечений. Так слой найдется , что следует из процедуры формирования списка S.
Из списка S* последовательно выбирается очередной отрезок и распределяется в тот слой, где имеет минимальной число n. Если слоев несколько, то отрезок распределяется в слой с меньшим общим числом отрезков.
Пример: Пусть К=3. Граф конфликтов:
13 SHAPE \* MERGEFORMAT 1415
Последовательно удаляем вершины локальной степени, кот.<3. Формируем S={2,6,1,4,3,5,7} Строим G1=(X1,V1). Представим на рисунке13 SHAPE \* MERGEFORMAT 1415
Из графа G1 последовательно удаляем вершины с максимальной локальной степенью. Сначала исключается вершина 11, затем 12,13,9,8,10. Вершина списка S1={14,15} – образуют внутреннее устойчивое множество, т.е. максимальное несмежной между собой число вершин (п.3). Из графа G1 удаляется вершина S1; получаем
13 SHAPE \* MERGEFORMAT 1415
Из графа G2 последовательно удаляется вершины с максимальной локальной степенью (11,9,8,10) и получаем S2={12,13}. Назначаем им 2-й слой. Строим G3(без 12 и 13). Из G3 находим S3={8,10}, которое распределяем в 3-й слой. 13 SHAPE \* MERGEFORMAT 1415
Т.о. S1={14,15,7,5,6,3,11}
S2={12,13,4,2,} S3={8,10,1,9}
Трассировка проводного монтажа(провода с изоляцией)
Т.М. м. осуществляться по прямым, соединяющим выводы эл-ты (монтаж в навал) или с помощью жгутов, к-е прокладывается в специальных каналах. Ограничения: количество проводников, к-е можно подсоединить к 1 выводу и число проводов в каждом жгуте – пропускная способность каналов.
Т.П.М, заключается в определении порядка соединения выводов в соответствии со схемой или с учетом ограничений. Критерий качества – минимальной суммарной длиной проводников. Нахождение порядка соединения выводов модулей внутри цепи сводится к задаче нахождения КСД.
Будем использовать модель схемы(цепи) в виде графа, в к-м выводов элементов сопоставлены вершины и на этой вершине строится полный граф цепи. Число вершин графа = n, при этом число ребер полного графа r=n(n-1)\2
При таком подходе каждая цепь представляется отдельной компонентой связности.
Ставится задача построения КСД на тех комп-х связности число вершин которых>2.
Отметим, что на n вершинах полного графа можно построить tn деревьев.
13 EMBED Equation.3 1415
Точные решения задачи построения КСД методом полного перебора нецелесообразны. Существуют приближенные алгоритмы решения этой задачи, дающие результаты достаточно близкие к оптимальным.
Алгоритм Красккала
Пусть задан G=(X,V) i,j=1,n, i
·j
Каждому ребру Vij поставлено в соответствие число Cij – вес или длина данного ребра.
Ставится задача: среди всех деревьев (n-(n-2)), кот. м. выделить в данном графе, требуется найти дерево с минимальной длиной в дереве (n-1) ребро.
Пусть C=[cij]n*n матрица длины ребер графа.
Все ребра графа n(n-1)\2 упорядочива-ся п порядке убывания длины, начиная с ребра C1=mini,jCij

Cn=maxi,jCij
Последовательно просматривается рассматриваемое множество V* длин ребер на каждом шаге, включенным в дерево одно ребро. В качестве такого ребра выбирается ребро среди не включенных в дерево, имеющих минимальную длину и не образующих циклов с ребрами уже вошедших в дерево.
Отметим: при работе этого алгоритма возможно появление несвязных поддеревьев, которое затем соединяется, образуя одну компоненту связности.

Лекция 12
Требуется построить КСД для цепи содержащей 6 контактов. Полный граф на рис:










Пусть матрица длин ребер графа цепи имеет вид:
U=13 EMBED Equation.3 1415 n = 6; n*(n-1) = 15
рис.1
1. Упорядочивание длин ребер полного графа
13 EMBED Equation.3 1415 - 15 элементов.
2.1. Включаем в 13 EMBED Equation.3 1415 в дерево получаем 1-ую изолир-ую компоненту связности.
2.2. Включаем в дерево 13 EMBED Equation.3 1415, получаем 2-ую изолир. компоненту связности (2,3).
2.3. Включаем 13 EMBED Equation.3 1415- получаем 3-ю изолир. компоненту связности (4,5).
2.4. Включ. 13 EMBED Equation.3 1415 - получаем 4-ю изолир. компоненту связности (1,6,4,5).
Ребро 13 EMBED Equation.3 1415 образовывает цикл - брать нельзя.
Ребро 13 EMBED Equation.3 1415 тоже образовывает цикл - брать нельзя.
2.5. Вкл-м в дерево 13 EMBED Equation.3 1415. КСД построено.
Примечание: цикл образ-я тогда, когда обе вершины включаемого ребра ываываыавыавы
Недостатки:
Необходимо на каждом шаге проверять условия необраз-я цикла, а так же наблюд-е за различными компонентами связности.
Большое время уходит на упорядочивание ребер полного графа.
Алгоритм Прима.
Использует тот же принцип соединения ближайших вершин, что и алг. Краскала, но на каждом шаге к строящемосю дереву присоед-ся ближайшая изолированная вершина.
В основе лежат 2 теоремы:
T.1. Каждая вершина КСД непосредственно связана по крайней мере с 1 ближайшей вершиной.
Т.2. Каждый измеряемый фрагмент поддерева связан по крайней мере с 1 из излир-х фрагментов кратчайшим ребром.
В соответствии с Т.1. построение КСД м.б. начато с произвольной вершины графа:
1) Выбираем, например, x1 и находим кратчайшее ребро, инертное этой . Это б. ребро 13 EMBED Equation.3 1415.
2) Включаем в КСД, вычеркиваем 1 и 6 столбцы (чтобы не было циклов), помечаем 6 строку и выбираем из нее минимальный элемент 13 EMBED Equation.3 1415.
3) Включаем в КСД 13 EMBED Equation.3 1415, вычеркиваем 4 столбец, помечаем 4 строку и выбираем из нее минимальный элемент 13 EMBED Equation.3 1415=1.
4) Включаем в КСД 13 EMBED Equation.3 1415, помечаем строку 5, вычеркиваем 5 столбец, выбираем 13 EMBED Equation.3 1415=5.
5) Включаем в КСД, вычеркиваем 3 столбец, помечаем 3 строку и выбираем из неё 13 EMBED Equation.3 1415=1.
КСД построено.










Т.о. на Т шаге алг-ма исп. Т1, и далее Т2.
Здесь всегда Т компонента связности, т.е. Т разрастается по дереву.

Алгоритм Прима построения КСД при огран-х на лок-е степени вершины.
Лок. степени b13 EMBED Equation.3 1415 - число ребер графа, инцидентных этой b. Т.к. задача возникает при проектировании проводных соединений, когда ограничено число паек к 1 контакту. Чаще всего кол. паек к контакту = 2.
предположим, что зад. матрица U длины ребер графа цепи и необходимо построить КСД при 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415.
Для решения дан. задачи м. применить алг. Прима с вычеркиванием строки, соответ-ей вершине лок. степени кот. стан. =n.
Пр:


Генетические алгоритмы

Основные понятия и определения

Механизм генетического наследования. В каждой клетке любого животного содержится вся генетическая информация особи. Эта информация записана в виде набора молекул ДНК, каждая из которых представляет собой цепочку из молекул нуклеотидов четырех типов: А, T, Ц, Ж. Собственно информацию несет порядок следования нуклеотидов в ДНК.
Таким образом, генетический код особи - это длинная строка, где используются четыре символа: А, Т, Ц, Ж. В животной клетке каждая молекула ДНК окружена оболочкой. Такое образование называется хромосомой.
Каждое врожденное качество особи (цвет глаз, наследственные болезни, тип волос и т. д.) кодируются определенной частью хромосомы, которая называется геном этого свойства.
Различие значения гена называется аллелями.
При размножении особи происходит слияние двух родительских клеток, и их ДНК взаимодействуют, образуя ДНК потомка.
Основной способ взаимодействия кроссовер-скрещение. При кроссовере ДНК предков делится на две части, а затем обменивается своими половинами. При наследовании возможны мутации, в результате которых могут измениться некоторые гены в клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны они, скорее всего, сохранятся в данном виде. При этом произойдет скачкообразное повышение приспособляемости вида.

Генетические алгоритмы
Генетические алгоритмы – это последовательность управляющих действий и операций моделирующие эволюционные процессы на основе аналогов механизмов информационного наследования и естественного отбора.
Генетические алгоритмы на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.
В Генетических алгоритмах свойства объектов значениями полей, введенными в запись, названной хромосомой.
В генетических алгоритмах оперируют хромосомами, относящимися к множествам объектов- популяции.
имитация генетических принципов - вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новое поколение объектов на основе оценки цел. функциии, что ведет к эволюционному улучшению значению цел. функции F (функция полезности) от поколения к поколению.
Для поиска оптимального решения используются так же методы, которые в отличие от Генетических алгоритмов оперируют не с множеством хромосом, а с единственной хромосомой.
Так метод локального дискретного поиска основан на случайном изменении отдельных пар в значение генов в хромосоме, такие изменения называются мутацией.
После очередной мутации оценочное значение функции F и результат мутации сохраняются с некоторой вероятностью, зависящей от полученного значения F.
Постановка задачи поиска оптимальных решений с помощью генетических алгоритмов
Для применения Генетических алгоритмов необходимо:
Выделить совокупность свойств объекта, характерных внутренними параметрами и влияющих на его полезность, т. е. выделить множество управляющих параметров X=(x1, x2, ... , xn). Среди x типов могут быть величины различных типов. Наличие символьных величин обуславливает возможность решения задач не только пар-ой, но и структурной оптимизации.
Сформулировать количественную оценку полезности вариантов объектов – функцию F.
Если в исходном виде задача многокритериальная, то такая формулировка означает вывод скалярного критерия.
Разработать математическую модель объекта, представляющей собой алгоритм вычисления F для X.
Представить Х в форме хромосомы – записи вида: х1 х2 х3 ... хn

Используется следующая терминология:
Ген- управляемый параметр х;
Аллель – значение гена;
Локус - позиция, занимая геном в хромосоме;
Генотип – экземпляр хромосомы, представляющий собой совокупность внутренних параметров, проектируемого с помощью генетических алгоритмов объекта;
Генофонд – множество всех возможных генотипов;
Фенотип – совокупность генотипа и соответствующего значения F;
Под фенотипом понимают совокупность выходных пар-в, синтезируемого с помощью генетических алгоритмов объектов.

Простой генетический алгоритм





Вначале генерируются начальная популяция – несколько особей со случайным набором хромосом. Генетический алгоритм эмитирует эволюцию этой популяции, как циклический процесс скрещивания особей мутации и смены поколений (отбора). Вычислительный процесс начинается с генерации исходного поколения – множество, включенного N хромосом. N – размер популяции.
Генерация выполняется случайным выбором аллеями каждого гена. Далее организуется циклический процесс смены поколений.
for ( k =0; k for ( j=0; j{Выбор родительской пары хромосом}
Кроссовер
Мутации
Оценка F
Селекция
{Замена текущего поколения новым}
G – число повторений внешнего цикла.
Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на котором формируется экземпляры нового поколения.
На внутреннем цикле повторяется операция выбора родителей, кроссоверы, мутации, оценки приспособленности потомков, селекции хромосом.
Рассмотрим алгоритм выполнения операторов в простом г.а.
Выбор родителей
Этот оператор иллюстрирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями F более вероятен.

Пр. Пусть F треб. min-т., тогда Рi выбора родителя с хромосомой Ci вычисляется:
Fmax – наихудшее значения F среди экземпляров текущего поколения.
Fi –значения функции i-ого экземпляра.
(1) называется Правило колеса рулетки.
Если в колесе рулетки выделены секторы пропорциональные (Fmax – Fi), то вероятность попадания в них – суть Fi, определяется в соответствии с (1)

Пр. Пусть N = 4
Fi и Рi в таблице:
i
1
2
3
4

Fi
2
7
6
3

Fmax – Fi
5
0
1
4

Рi
0,5
0
0,1
0,4

Скрещивание
Скрещивание заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном кроссовере) хромосомы родителей разрываются в позиции одинаковой для обоих родителей. Место разрыва равновероятно. Далее рекомбинация, образовавшихся частей родительских хромосом, как в таблице 1, где разрыв подразделяется между 5 и 6 локусами.
Хромоссомы
Гены

А
f
a
c
d
g
k
v
e

В
a
b
c
d
e
f
g
h

С
f
a
c
d
g
f
g
h

D
a
b
c
d
e
k
v
e

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

Слекция
После каждого акта генерации пара потомков в новое поколение включается лучший экземпляр пары.
Внутренний цикл простого г.а заканчивается, когда число экземпляров нового поколения станет N.
Количество повторений G внешнего цикла, чаще всего определяется автоматически, по выявлению признаков вырождения (стагнации), но с условием не превышения лимита маш. t.

Разновидности ген. операторов
Кроссовер:
В-первых, допустимы схемы много точечного кроссовера
Во-вторых, отметаем ситуации, когда на состав аллель наложены дополнительные условия.

Например. Пусть задача разбиение графа число вершин в подграфе А1 и А2 должно быть N1 и N2. Пусть к-тый аллель равен 1. Это означает, что К попадает в А1, если же к-тый аллель равен 0, то в А2.

Очевидно, что число 1 в хромосоме должно быть равно N1, а число 0 N2.
При рекомбинации левый участок хромосомы берется от одного из родителей без изменений, а в правом участке от другого родителя н. соглас-ть число 1 с N1.
Один из способов – метод РМХ.

Для иллюстрации метода рассмотрим пример двух точечного кроссовера в задаче, когда в хромосоме должны присутствовать, причем только по одному разу, все значения генов из заданного набора.
Пусть в пр. набор включ-т от 1..9
1
2
3
4
5
6
7
8
9
Родители

3
7
1
9
2
4
8
6
5


1
2
1
9
2
6
7
8
9


1
2
3
9
5
6
7
8
4


В таблице третья строка содержит хромосому первого из потомков, сгенерированного в результате применения первого из кроссовер (после второго и пятого покус.). Полеченные хромосома не относиться к числу допустимых, так как в ней значение генов 1, 2, 9 встречаются второго рода, а значения 3, 2, 5 отсутствуют.
Четвертая строка показывает результат применения метода РМХ. В этом методе выделяются сопряженные пары аллелей в локусе в одной из рекомбинированных частей. В нашем примере это пары 3–1, 4–9, 5–2. Хромосома потомка просматривается слева на право. Если встречаются повторяющиеся значения, то они заменяются сопряженным значением. В пр., повторно встречающиеся аллели заменены значениями 3, 5, 4.

Мутации
Бывают точечные мутации (в первом гене), макромутаии (в нескольких генах) и хромосомные (появляются новые хромосомы)
Обычно вероятность появления мутаций указывается среди исходных данных, но можно авторегулировать число мутаций при их ...., когда их родительские хромосомы различаются не более чем в К генов.
Селекция
После определения и положительной оценки потомка он может быть сразу включен в текущую популяцию вместо худшего из родителей при этом из алгоритма исключается внешний цикл.
Другой вариант селекции – отбор после каждого операции скрещивания двух лучших экземпляров среди двух потомков и двух родителей.
Часто именно потомки с Fmin принужденно включаются в новое поколение, такой подход называется элипумом. Он способствует большей сходимости и локальному экстремуму. Но в многоэкстрем. Ситуации ограничивает возможность попадания в окрестности других локальных экстремумов.
Третий вариант селекции – отбор N экземпляров среди генов репродукции группы, которая состоит из родителей, потомков, мутантов, удовлетворяющих условию: Fi < t. t – порог значения функции полезности. Порог может быть равен ил среднему значению функции F в текущем поколении или значению F особи, занимающее определенное порядковое место. Суть мягкой схемы отбора – включение в новое поколение N лучших представителей репродукции группы.
Жесткая схема отбора – новое поколение экземпляры включаются с вероятностью, определяемое (1).
Четвертый вариант селекции – переупорядочивание – назначение переуп-е генов связывания со своими свойствами, носящими название эпистасис. Эпистасис имеет место если F зависит не только от значений генов, но и от их позиционирования. Связывание эпистасиса говорит о нелинейности функции F, что приводит к усложнению оптимизационной задачи.

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

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

Генетические алгоритмы для трассировки двухслойных каналов
В настоящее время получили распространение канальные алгоритмы трассировки, которые требуют меньше машинных ресурсов и большинстве случаев обеспечивают стопроцентное разведение цепей.
Большое распространение получили алгоритмы моделирования эволюции. Это хорошо известная оптимизированная методология, основанная на аналогии процессов натуральной селекции в биологии.
Поиск в поле структурных модификаций адаптированных систем осуществляется генетическими алгоритмами.
Основная особенность генетических алгоритмов состоит в том, что анализируется не одно решение, а некоторое подмножество квазиопытных решений, названных хромосомами или стрингами.
Для каждой хромосомы должна быть цел. функция F(n), названная эволюционной.
n- число элементов в хромосоме. Функция F(n) вычисляет определенный вес каждой хромосомы. В каждой популяции хромосомы могут подвергаться действиям различных опер-в: кроссовера, инверсии, мутации, сегрегации, транслокации и т. п.
Генетические алгоритмы обладают возможностью выхода из локальных оптимумов, что позволяет получать лучшие решения, чем при решении задач канальной трассировки старыми алгоритмами.

Задача канальной трассировки классической постановки
Канальные алгоритмы базируются на представлении о каналах и магистралях. Магистралью называется отрезок прямой, по которой проходит соединение в преимущественном напряжении.
Канал – область прямоугольной формы, на одной или нескольких сторонах которой расположены контакты с системой однонаправленных магистралей.
Каждая цепь – соединение эквипотенциальных контактов представлено как одиночный горизонтальный сегмент с несколькими вертикальными сегментами, которые соединяют горизонтальный сегмент с контактами цепи.
Горизонтальные сегменты располагаются в одном слое, вертикальные в другом. Соединения между горизонтальными и вертикальными делятся через переходные отверстия.
Основная задача канальной трассировки – выбор наименьшей трассировки канала, достаточной для размещения в нем всех соединений и назнач. соединений на магистралях.
Необходимо минимизировать суммарную длину соединений, число переходных отверстий и т. д.
Задача канальной трассировки в классической постановке основана трассировке двустороннего канала по верхней и нижней сторонам которого проходят линейки контактов.
Изломы (т. е. переходы) горизонтального участка с одной магистрали на другой не допускаются.

Описание каналов




























































Канал описывается двумя последовательностями top и bottom, в которых размещаются верхние и нижние линейки контактных площадок каналов. Размер обеих последовательностей равен С – число колонок в канале
Множество цепей определяется как Net = {N1, N2, , Nn} (n – это число цепей)

Пр.
top = {1, 0, 3, 1, 4, 2, 3, 2}; bottom = {6, 4, 6, 6, 3, 0, 5, 5}; n = 6; C = 8
Элемент 0 в top и bottom обозначают, свободный контакт на рисунке показан эскиз канала с разведенными цепями. Показан эскиз для хромосомы = (0, 0, 0) –
(см. ниже)


Горизонтальные и вертикальные ограничения
При канальной трассировке не допускается наложения вертикальных и горизонтальных сегментов цепей. Для решения этой задачи вводятся графы вертикальных и горизонтальных ограничений.
Вертикальные ограничения описываются ориентированным графом вертикальных ограничений (г.в.о.)
GV = {Enet, Ev}
Enet – множество вершин, соответствующих множеству цепей net
Ev – множество направляющих ребер.
Ребро (n, m) существует тогда, когда цепь n расположена выше цепи m для предотворощения наложения вертикальных сегментов цепей.
Для наших последовательностей г.в.о. на рис.:









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

Далее будем использовать расширенный г.в.о. (р г.в.о.)
GRV = {Enet, Erv}
Enet – множество вершин, соответствующих множеству цепей net
Erv – множество направляющих ребер.
Ребро (n, m) принадлежащее Erv существует тогда, когда в г.в.о. существует путь из вершины n в m.











На рисунке 2а в г.в.о. есть путь из 4 в 5 через 3. Следовательно, в р.г.в.о. существует ребро (4, 5) и (4, 6)
Горизонтальные ограничения представлены не ориентированным графом гориз. огран. (г.г.о)
GН = {Enet, Eн}
Eн – множество ребер.
Ребро (n, m) принадлежащее Eн существует тогда, когда магистрали для n и m разнесены для исключения наложения горизонтальных сегментов n и m.








На рисунке 2в г.г.о. есть путь из 1 в 6, значит, что цепь 1 должны быть расположена выше 6, чтобы не было горизонтальных наложений. Цепи 1 и 5 могут быть расположены на одной магистрали. Цепь 1 и 2 тоже.

Генетические алгоритмы для канальной трассировки
Генетические алгоритмы – итерационная процедура, которая обрабатывает гр. хромосом решений, названное популяцией.
Число хромосом в популяции – ее размер N. Каждая хромосома состоит из генов, каждый ген хромосомы может быть в нескольких состояниях – аллели.
Приведем соответ-е терминов генетических алгоритмов и классические задачи.
Денотип – топология расположения цепей на кристалле.
Генотип – генетическая схема кодирования топологии.
Хромосома – кодированное представление первого варианта топологии.
Ген – элемент хромосомы, задающий некоторый фрагмент топологии.
Популяция – набор хромосом.
Фитнеса – целевая функция, определяющая качество решения задачи.
Генерация – первый цикл работы генетических алгоитмов.
Генетические алгоритмы требуют, чтобы хромосомы оценивались с точки зрения F задач. Функция F оценивает к-л. качества решения, соответствующего данной хромосоме (длину цепей, сило магистралей).
Генетические алгоритмы обрабатывают популяцию решений, закодированную в хромосому. В процессе обработки популяции к ней последовательно применяются генетические операторы, так как кроссовер и мутация с заданными вершинами Р(с) и Р(m) и др.
Затем, проводится редукция (анализ) увеличивающейся популяции для отбора лучших решений, которые составят следующее поколение, после чего цикл (популяция) повторяется.
Число таких циклов называется числом генерации Т.

Стандартная схема генетического поиска. Структура г.а.
Определение размера популяции М, числа генерации Т, вероятности кроссовера Р(С), вероятности мутации Р(М).
Задание случайным образом начальной популяции П(0) размером М.
Т положить равным 0.
Выбор случайным образом М пар хромосом из популяции П(t) и применение кроссовера к каждой паре с заданной вероятностью Р(С)
Применение операции мутации к каждой хромосоме популяции П(t) с заданной вероятностью Р(m).
Отбор М хромосом с наилучшим значением F из получившейся популяции П(t) в новую популяцию П (t + 1)
t = t + 1
Если t < Т, то переход к пункту 4
Вывод хромосомы с наилучшими значениями.
Генетическое опер-и прим-е в алгоритме канальной трассировки.

Кодирование хромосомы
Пусть хромосома описывает взаимное расположение цепей канала. Для этого каждой паре цепей (n, m) ставиться соответствие ген, который может принимать 3 состояния: 0 – если m должна располагаться выше n, 1 – если m должна располагаться ниже n и * – если их взаимное расположение не имеет значения или определяется из взаимного расположения остальных цепей (это происходит если цепи не имеют горизонтальных ограничений)
Для нашего примера хромосома может иметь вид, приведенный в таблице:
цепь n
1
1
1
1
1
2
2
2
2
3
3
3
4
4
5

цепь m
2
3
4
5
6
3
4
5
6
4
5
6
5
6
6

ген
*
0
0
*
0
0
*
0
*
1
0
0
*
0
*


В строке «ген» записывается значение гена в хромосоме, задающий расположение цепей, показанное на рисунке 1.
Длина хромосомы L = N*(N–1)/2 = 6*5/2 = 15. длина хромосомы достаточно большая, что не приемлемо. Поэтому для понижения длины хромосомы используется анализ р.г.в.о и г.г.о (рис. 2)
Понижение длины хромосомы получаем за счет того, что взаимное расположение пар цепей уже зафиксировано р.г.в.о. и изменение этого расположения приводит к наложению вертикальных сегментов цепей в канале, это ведет к образованию «мертвых» хромосом, то есть такой, из которой нельзя получить решение, удовлетворяющее условиям задачи трассировки.
Второй прием позволяющий уменьшить длину хромосомы основывается на том, если цепи не имеют горизонтальных ограничений, то их взаимное положение либо не важно, либо определяется из соотношения с остальными цепями. Такие состояния отмечены «*». Таким образом длинна хромосомы может быть определена: L = NGO – NRVO, где NGO – число горизонтальных ограничений в г.г.о.(9), а NRVO – число вертикальных ограничений в р.г.в.о.(6).
Цепи 4 и 5 не зависят друг от друга, как по горизонтали так и по вертикали. Для пары цепей (1, 6) (2,5) (3,4) (3,5) (3,6) (4,6) взаимное расположение жестко задано р.г.в.о., а а взаиморасположение цепей в (1, 2) (1, 5) (2, 4) (2, 6) (4, 5) (5, 6) (см. г.г.о) не имеет значения, так как цепи в этих парах не конфликтуют по горизонтали.
В нашем примере хромосома будет выглядеть так:
цепь n
1
1
2

цепь m
3
4
3

ген
0
0
0






1 – должна быть выше 4, а 2 должна быть выше 3.


Получение из хромосомы эскиза канала с разведенными цепями
Для получения из хромосомы вида А=(а1, а2, а3,), где аi равна 0 или 1 эскиза канала с разведенными цепями используется граф топологии (ГТ). ГТ – ориентированный граф вида GT=(ENet, ET), где ENet – множество цепей, ET – множество направленных ребер, описывающих взаимное расположение цепей в канале.
Ребро 13 EMBED Equation.3 1415 существует тогда и только тогда, когда цепь m расположена в канале выше цепи n, т.е. на магистрали с меньшим номером. ГТ строится на основе РГВО, направленные ребра которого соответствуют параметрам цепей, взаимное расположение которых жестко задано с добавлением направленных ребер, соответствующих параметрам ветвей, образующих хромосому А. для нашего примера рис.1 ГТ будет иметь вид, приведенный на рис.3.
13 SHAPE \* MERGEFORMAT 1415
Цепь m
1
1
2

Цепь n
3
4
3

Ген
0
0
0


А=(0,0,0)
Граф топологии для хромосомы А=(0,0,0).
Канал восстанавливается из хромосомы следующим образом:
Шаг 1. Строим по хромосоме граф топологии.
Шаг 2. Полагаем i=0.
Шаг 3. Находим вершины (1 и 2 для нашего случая), у которых есть только исходящие дуги. Размещаем их на магистрали с номером i или на магистрали с меньшим номером, если это возможно и удаляем эти вершины с инцидентными им ребрами из ГТ.
Шаг 4. i=i+1
Шаг 5. Если ГТ не пуст, то возвращаемся к шагу 3.
Шаг 6. Не нарушая взаимного расположения, смещаем цепи по магистрали так, чтобы минимизировать длину вертикальных сегментных цепей.
Шаг 7. Возвращаем полученный образец размещения цепей в канале шириной i (см. алгоритм расслоение МПП).
Для хромосомы А=(0,0,0) имеем: на первом шаге находим вершины 1 и 2, у которых есть только исходные дуги. Цепи 1 и 2 размещаем на магистрали m1, получаем следующий граф топологии:
13 SHAPE \* MERGEFORMAT 1415

На втором шаге исключаем вершину 4, а цепь 4 размещаем на m2 получаем ГТ представленный на рис.5.
13 SHAPE \* MERGEFORMAT 1415
На третьем шаге исключаем вершину 3, а цепь 3 размещаем на магистрали 3.
На 4-ом шаге назначаем цепям 5 и 6 магистраль m4 (5 и 6 не конфликтуют ни по вертикали, ни по горизонтали).
На рис.1 показан полученный образец трассировки, который является оптимальным решением для нашего примера. Если хромосома А=(0,1,0) (отличие от представленного решения заключается в том, что цепь 4 располагается выше цепи 1), то граф топологии будет иметь вид:
13 SHAPE \* MERGEFORMAT 1415
Цепи 2 и 4 располагаем на магистрали m1(удаляем 1 и 4).
13 SHAPE \* MERGEFORMAT 1415
Цепь 1 располагаем на магистрали m2.
13 SHAPE \* MERGEFORMAT 1415
Цепь 3 располагаем на магистрали М3, 5 и 6 – на магистрали М4.
Эскиз канала с разведенными цепями для хромосомы А=(0,1,0) показан на рисунке:
13 SHAPE \* MERGEFORMAT 1415
Подсчитаем суммарную длину вертикального сегмента:13 EMBED Equation.3 1415
Целевая функция оценки хромосомы
Когда генетические алгоритмы применяются для решения оптимизационных задач, важнейшим требованием является разработка целевой функции (ЦФ) для полученных решений.
ГА обычно используют для минимизации (максимизации), но желательно, чтобы целевая функция была положительной. В нашем случае задача заключается в минимизации целевой функции. Принимая во внимание характеристики задач канальной трассировки целевая функция может быть определена следующим образом:
F(A)=(Used Track(A)+2)*C + Total Vert Seg(A)
C – число контактов ( 8 линеек Top или Bottom )
2 – число слоев печатной платы
Программная функция Used Track(A) определяет число магистралей (в нашем примере 4) занимаемые каналом, полученным при восстановлении хромосомы А, а программная функция Total Vert Seg(A) определяет длину вертикальных сегментов цепи в полученном решении.
Длина вертикального сегмента цепи определяется как расстояние между контактами и переходными отверстиями, которые соединяют вертикальные и горизонтальные сегменты. Например для канала приведенного на рис.1 занятых магистралей равно 4, длина вертикального сегмента равна 22, т.о.целевая функция хромосомы F(A)=(4+2)*8+22=70, а для канала с хромосомой А=(0,1,0) (рис.7) F(A)=72.
Данная методика определения F(A) направлена в первую очередь на минимизацию ширины канала, а во вторую на минимизацию суммарной длины соединений.

Кроссовер и мутация
Согласно структуре ГА все хромосомы (случайно полученные решения) оцениваются целевой функцией F(A). Далее, согласно процедуре селекции (отбора) производится построение списка упорядоченных хромосом. На основе анализа этого списка производится подбор пар хромосом на основе элитной селекции(хромосома с наилучшим значением целевой функции и случайно выбранной хромосомой).
После подбора пар применяется оператор кроссовера – ОК с вероятностью Pc к каждой паре хромосом. Исходная хромосома называется родительской, а хромосомы, полученные после операторов ГА – потомки.
Алгоритм применения ОК реализуется следующим образом:
Шаг 1. i=0
Шаг 2. Выбрать хромосом с наилучшим значением целевой функции как первого родителя.
Шаг 3. Выбрать произвольно второго родителя.
Шаг 4. Сгенерировать случайное число 13 EMBED Equation.3 1415.
Шаг 5. Если RNDШаг 6. i=i+1.
Шаг 7. Если iПод оператором кроссовера подразумевается обмен, скрещивание генетического материала между двумя различными хромосомами (потенциальными родителями). После окончания оператора кроссовера полученные потомки подвергаются мутации. В большинстве случаев может быть выбран стандартный двухточечный оператор кроссовера. Первая и вторая точки разрыва в таком операторе кроссовера выбираются случайно.
Часть первого родителя перед первой и после второй точки разреза копируется в аналогичные места в потомке 1. Место между первой и второй точкой разреза во втором родителе копируется в аналогичное место первого потомка. Второй потомок строится аналогично.
Рассмотрим пример реализации оператора кроссовера. Пусть вертикальная волнистая линия означает точку разреза оператора кроссовера.
Родитель 1
0
1
0
F(A)=72 (рис.7)

Родитель 2
1
0
1
F(A)=7

Потомок 1
0
0
0
F(A)=70 (рис.1)

Потомок 2
1
1
1
F(A)=77

Потомок 2 аналогичен родителю 2. В данном случае получен потомок 1 с лучшим значением целевой функции, чем значение целевой функции (72,77).
Мутация произвольно изменяет 1 ген выбранной хромосомы случайно изменяя значение гена с вероятностью РМ равной норме мутации. Алгоритм применения операции мутации выглядит следующим образом:
Шаг 1. i=i+1.
Шаг 2. Сгенерировать случайное число RND [0,1]
Шаг 3. Если RND< РМ, то применить ОМ к i-ой хромосоме М.
Шаг 4. i=i+1.
Шаг 5 если iСмысл ОМ введение добавочных изменений в популяцию. В простейшем случае может быть выбрана точечная мутация, она заключается в изменении произвольного гена в хромосоме с вероятностью РМ. Это происходит следующим образом: один из генов хромосомы выбирается случайно, а затем меняет свое значение на противоположное. Пример хромосомы (до применения ОМ): 0,(1),0. Значение целевой функции – 72.
Хромосома после применения ОМ: 0,(0),0, значение целевой функции – 70 – min. Выбранная точка мутации показана в скобках. После применения ОМ получается хромосома с лучшим значением целевой функции. Дальнейшее улучшение работы генетического алгоритма можно получить за счет сортировки гена в хромосоме или путем использования более сложной целевой функции. Кроме того, можно анализировать параллельные и последовательно – параллельные методы генетического поиска.
Теоретическая временная сложность рассмотренного генетического алгоритма составляет t*(M*Pc*2)*2*PM*O(N2)
O(N2) – временная сложность декодирования хромосомы;
M – число цепей;
t – число поколений.
v8


v11

v12


v10


v9


v1


v3


v4



·pk=1


·pk=0


·pk=–1

13 EMBED Equation.DSMT4 1415

x

x

x

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

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

Алгоритмы Лаурера

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

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

Последовательные алгоритмы

Приближенные алгоритмы

Точные алгоритмы

Алгоритмы компоновки

Рис. 3.3

e4

e3

b2

e2

e1

b1

b0
(e0)

v5

v4

v3

v1

v1

v2

13 EMBED Equation.DSMT4 1415

13 EMBED Equation.DSMT4 1415

Рис. 3.2


e3

e0

e1

e2

e4

v3

eo

e4

e3

e2

e1

v1

v4

v5

v2

13 EMBED Equation.DSMT4 1415

13 EMBED Equation.DSMT4 1415

1

2

1

1

1

e2

e1

e3

e0

v4

v3

v2

v1

e2

e1

e0

e3

k01

k02

k11

k12

k13

k21

k22

k31

k32

v1

v2

v3

v4

e0

e1

e2

e3

F

W

k01

e3

e2

e1

k11

k12

k13

k21

k02

k32

k31

k22

v1

v2

v3

v4

Элемент

(ТЭЗ)
Ячейка


Панель



Шкаф

ЭВС

MAX=-999;I=1;OC=0

POS(I,1)=0 ?

A:=RSP(I,1+1)
B:=RSP(I,1+1)
J1=A

I2=SP1(J1)

POS(I2)=0?

J(1)<=B?

OC=OC-SP2(J1)


OC=OC-SP2(J1)

MAX
MAX:=OC; LI:=I1

I1=I1+1

I1<=L

J1=J1+1

1 e1

2 e2

5 e5

4 e4

3 e3

1

5

2

1

1

1

3

13 EMBED Mathcad 1415

13 EMBED Mathcad 1415

1 e1

2 e2

5 e5

4 e4

3 e3

1

1

1

5

3

2

1

3

1

1

L
·=33

1

e1

1

e2

2

e3

3

e5

5

e4

4

e6

6

5

1

6

1

1

5

1

1

L
·=22

1

e1

1

e2

2

e4

3

e5

5

e3

4

e6

6

6

1

3

Да

НАЧАЛО

Вычисление матриц D и R

Вычисление суммарной длины всех связей (полуслед) и матрицы приращений
·L

Корректировка матрицы R или матрицы связей

Есть отрицат. эл-ты в
·L?

Выделение подмножества допустимых парных перестановок

КОНЕЦ

Вывод результатов

1

2

3

4

5

6

Нет

&

&

&

&

1

&

&

1

t1

t1

t2

t2


t3

––

t1

t4

Q1

Q2

Q3

t1 – 2ИЛИ-НЕ;
t2 – 3ИЛИ-НЕ;
t3 – простейший RS-триггер;
t4 – JK-триггер.

=

&



&



Нет

Да

НАЧАЛО

Упорядочивание конструктивных модулей по стоимости

B>0

КОНЕЦ

1

Нет

L=1

2

13 EMBED Equation.DSMT4 1415

13 EMBED Equation.DSMT4 1415

13 EMBED Equation.DSMT4 1415

j=j+1

j
·m

L=L+1

j=1

7

10

3

4

5

6

8

9

Рисунок 1

S1

P3

P4

P2

P3

P2

P4

P1

P1

а)

б)

в) г)

1

2

2

1

д) КСД 1 и 2 е) цепи 1 и 2

x

y

i

j

k

p

Рис.2

y

x

i

j

k

p

Cj

Cl

Cp

Ck

Ci

Cf Ck Cm


Ci Cj Cr
Cp Ci Cl


Граф решетки

h

h

В

В

А

А

А

В

r

h1

h4


h3

h2

h1 син h2 син


h4 красн h3красн

1

4

3

10

12

6

5

9

17

15

2

8

14

13

7

3 слой

2 слой

1 слой

3 слой


2 слой

1 слой

1 слой

2 слой

1 слой

1 сл.

3 слой

1 слой

2 слой

3 сл.

1 сл.

10

9

11

15

13

14

8

12

Список S здесь не дополняется, т.к. отсутствуют вершины локальной степени, которые <(K-1)=2
(п.4)

10

12

9

11

8

13

9

10

11

8

Вершина 9 и и11 включается в S*. Далее последовательно(в обратном порядке) распределяем по слоям отрезки из списка S.
7,5,3- в 1-й слой; 4 – 2-й слой; 1 – 3-й слой; 6 – 1-й слой; 2 – 2-й слой;
Распределяем изS*: 9 – 3-й слой(1-е пересечение); 11 – 1-й слой(1-е пересечение)

Создание начальной популяции

Скрещивание
(кроссовер)

Мутации

Отбор

ответ

(1)

13 EMBED Equation.3 1415

top

3
*

2
*

4
*

1
*

2
*

1
*

3
*

0
*

*
6

*
6

*
4

*
3

*
5

*
5

*
0

*
6

bottom

переходные отверстия

* контакт

1

6

5

2

3

4

рис. 2а

1

6

5

2

3

4

рис. 2б

1

6

5

2

3

4

рис. 2в

Рис.3

1

6

5

2

3

4

6

5

3

4

6

5

3

1

6

5

2

3

4

1

6

5

3

6

5

3

6

4

6

6

3

0

5

5

1

0

3

1

4

2

3

2

v6


v7


v5


v2


e2

e1

e3

e4

e5

e6

e7

e8

e9

Нет

Нет

Да

НАЧАЛО

Ввод данных

Выбор элемента, максимально связанного с нескомпонованными элементами (вычисление оценки L1(x))

Выбор нескомпонованных элементов, включение которых в блок не приводит к превышению 13 EMBED Equation.DSMT4 1415 (вычисление L2(x))

Выбор среди них элемента с максимальной оценкой L3(x) – связи элемента x с блоком 13 EMBED Equation.DSMT4 1415

Такой элемент один?

Выбор среди них элемента с минимальной оценкой L2(x)

Все возможные элементы вошли в блок?

Все блоки скомпонованы?

КОНЕЦ

Вывод результатов

1

2

3

4

5

6

7

8

9

Да

Да

Нет

13 EMBED Equation.DSMT4 1415

13 EMBED Equation.DSMT4 1415

Непрерывно-дискретные

Алгоритмы размещения

Дискретные

Точные методы решения соответствующей задачи целочисленного программирования

Конструктивные алгоритмы размещения

Алгоритмы регулярного поиска

Алгоритмы, основанные на силовых моделях

Метод ветвей и границ

Метод динамического программирования

Последовательные алгоритмы

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

Последоват. алгоритмы размещения по связности

Матричные алгоритмы

Алгоритмы обратного размещения

Алгоритм, использующий метод разбиения

1

1

3

2

2

1

1

1

1

1

1

e1

1

e2

2

e3

3

e5

5

e4

4

e6

6

e7

7

e8

8

e9

9

e10

10

e11

11

e12

12

2

3

L
·=34

e2









+

+

+

e3

+





e2

+


+






+

+

e1


e3

+





1

2

1

2

1

1

1

1

1

3

2

1

3

e9

1

e1

2

e8

3

e5

5

e4

4

e2

6

e12

7

e7

8

e3

9

e11

10

e10

11

e6

12

L
·=

Нет

Да

НАЧАЛО

Ввод данных

Размещение директивных модулей

Формирование массива соседних позиций

Выбор очередного неразмещенного элемента

Вычисление оценки J (6.1) по связности

?

Выбор модуля с максимальной оценкой J (6.1)

28
08

Все неразмещенные модули просмотрены?

01

02

03

04

05

06

07

28
14

Нет

Да

Выбор очередной соседней позиции

Вычисл-е длины связей F (6.2) модуля со всеми размещ-ми модулями

?

Все соседние позиции просмотрены?

27
07

08

09

Нет

10

Выбор позиции с минимальной длиной связи F (6.2)

11

Размещение модуля в позицию

12

Да

?

Все модули размещены?

13

Коррекция массива соседних позиций

14

Печать результатов

КОНЕЦ

27
04



 &*
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Root EntryeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 18301127
    Размер файла: 1 MB Загрузок: 1

Добавить комментарий