- •Алгоритмические методы конструирования эвс § 1. Общая характеристика основных задач этапа конструкторского проектирования
- •§ 2. Математические модели схем эвс
- •Граф коммутационной схемы
- •Гиперграф
- •Взвешенный неориентированный граф
- •§ 3. Математическая постановка задачи компоновки схем конструктивно унифицированными модулями
- •Минимальное число межблочных связей;
- •Математическая постановка задачи компоновки с использованием модели внг
- •Математическая постановка задачи компоновки с использованием модели гг
- •Общая характеристика алгоритмов компоновки конструктивных модулей
- •§ 4. Последовательный алгоритм компоновки
- •§ 5. Задача размещения конструктивных модулей
- •§ 6. Конструктивные алгоритмы размешения
- •Последовательные алгоритмы размещения по связности
- •Тема Параллельно-последовательное размещение Метод обратного размещения.
- •Итерационные алгоритмы размещения
- •§ Задача покрытия схем набором конструктивных модулей.
- •Трассировка печатных соединений
- •Волновой алгоритм решения задачи трассировки.
- •Лучевой алгоритм трассировки.
- •Алгоритм Рабина.
- •Алгоритм слежения за целью.
- •Алгоритм Прима.
- •Генетические алгоритмы Основные понятия и определения
- •Генетические алгоритмы
- •Постановка задачи поиска оптимальных решений с помощью генетических алгоритмов
- •Простой генетический алгоритм
- •Выбор родителей
- •Скрещивание
- •Селекция
- •Разновидности ген. Операторов
- •Мутации
- •Селекция
- •Особенности генетических алгоритмов
- •Генетические алгоритмы для трассировки двухслойных каналов
- •Задача канальной трассировки классической постановки
- •Описание каналов
- •Генетические алгоритмы для канальной трассировки
- •Стандартная схема генетического поиска. Структура г.А.
- •Генетическое опер-и прим-е в алгоритме канальной трассировки. Кодирование хромосомы
- •Кроссовер и мутация
§ Задача покрытия схем набором конструктивных модулей.
В результате решения задачи покрытия каждый элемент схемы привязывается к некоторому конструктивному модулю из набора Q={Q1, Q2, …,Qm}.
Математическая постановка задачи покрытия зависит от типа конструктивных модулей набора. Различают 3 типа конструктивных модулей:
-
Каждый модуль содержит базовые логические элементы одного типа, при этом все входы и выходе логических элементов являются выводами модуля.
Например:
-
Тоже что и предыдущий тип, однако в одном конструктивном модуле могут содержаться разнотипные логические элементы.
Модули 1-го и 2-го типов называются модулями с несвязанными элементами.
-
Конструктивный модуль в общем случае содержит связанные между собой разнотипные элементы и не все входные и выходные выводы элементов имеются на внешних контактах конструктивного модуля.
Рассмотрим математическую постановку задачи покрытия схемы конструктивными модулями с несвязанными элементами (1-го и 2-го типов).
Обозначим через bi количество логических элементов ti типа, содержащихся в функционально-логической схеме (ФЛС). При таком подходе состав ФЛС может быть описан матрицей-столбцом: B=||bi||n, где n – число типов логических элементов схемы, bi – число логических элементов ti типа в ФЛС. Будем считать, что каждый тип конструктивного модуля Qj в общем случае содержит несколько типов ti базовых элементов, а весь набор конструктивных модулей Q может быть описан матрицей A=||aij||nxm, где aij – количество базовых логических элементов типа ti в конструктивном модуле типа Qj ().
Пример.
-
Q1
Q2
Q3
t1
2
0
1
A
=
t2
1
1
0
t3
0
1
0
t4
0
0
1
В качестве критерия оптимизации будем использовать минимум стоимости покрытия. Обозначим cj стоимость конструктивного модуля Qj.
Пусть для покрытия ФЛС необходимо выделить yj конструктивных модулей Qj, тогда в качестве целевой функции можно взять функцию вида:
.
Будем считать, что каждый тип базового логического элемента схемы может быть реализован как базовый логический элемент того же набора, так и БЛЭ другого типа набора. Например:
Обозначим через xki количество логических элементов типа tk, которое идет на покрытие логических элементов схемы типа ti. Возможность замены БЛЭ типа tk на БЛЭ типа ti будем описывать матрицей W=||wki||nxn,
Очевидно, что xki>0 если wki=1.
Учитывая введенные обозначения, задачу покрытия можно сформулировать следующим образом: если yj количество требуемых конструктивных модулей типа Qj, а в каждом Qj конструктивном модуле содержится aij элементов типа ti, то определяет количество логических элементов типа ti, содержащихся во всем выделенном для покрытия ФЛС наборе конструктивных модулей.
Очевидно, что для покрытия всей ФЛС необходимо выполнение следующего условия:
,
где второе слагаемое – количество логических элементов других типов, которые идут в покрытии на реализацию логических элементов типа ti; последнее слагаемое – количество логических элементов типа ti, которые идут на реализацию логических элементов других типов.
Т. о., ставится задача отыскания таких значений yj и xki, удовлетворяющих (**), чтобы обеспечивался минимум целевой функции (*) – стоимости покрытия. На практике используются приближенные методы, опирающиеся на специфику используемых конструктивных модулей. Если имеем дело с несвязанными элементами конструктивного модуля, то здесь в результате определения требуемого числа модулей не осуществляется привязка логических элементов схемы к конструктивным модулям, отсюда появляется возможность оптимизации по другому критерию, в частности по критерию минимума межблочных связей.
Пример Q={Q1, Q2, Q3}, t={t1, t2, t3, t4} приведен нами выше. Требуется покрыть ФЛС, описываемую вектором B={5, 4, 1, 1}, заданным набором конструктивных модулей.
Блок-схема алгоритма определения требуемого числа конструктивных модулей по критерию минимума стоимости покрытия приведена на рисунке.
Требуемое число корпусов модуля j-го типа определяется из выражения:
(1)
Для нашего примера:
Так как a31=0 и a41=0, то в качестве коэффициента
Полагаем, что j=2 и вычисляем
, и следовательно
j=3
Переходим к :
, (остальные bi=0)
Т.о. имеем , , , .
Эти данные подставляем в выражение (1) и определяем:
,
,
.
После определения требуемого числа корпусов, можно осуществить привязку элементов к корпусам. Для этого могут быть использованы рассмотренные ранее алгоритмы решения задач компоновки (задачи разбиения).