ВУЗ:
Составители:
Рубрика:
6
Теоретическая часть
1. Постановка задачи размещения
В общем виде задача размещения заключается в определении опти-
мального в смысле некоторого критерия положения элементов и связей
между ними в монтажном пространстве типовой конструкции. При этом
должны быть удовлетворены заданные конструктивно-технологические
ограничения. В такой постановке задачу размещения можно сформулиро-
вать как целочисленное программирование, однако из-за большой размер-
ности
ее практическая реализация нецелесообразна. Задачу размещения
условно разбивают на две: размещение конструктивных элементов и трас-
сировка связей между ними.
При таком подходе задача размещения сводится к нахождению оп-
тимального положения элементов и внешних контактов в монтажной об-
ласти типовой конструкции. В ряде алгоритмов размещение элементов вы-
полняется без учета их
связей с внешними выводами, поэтому элементы,
имеющие связи с внешними выводами, могут оказаться на значительном
удалении от них, что затруднит последующую трассировку соединений.
Исходные данные для задачи размещения: схема соединения элемен-
тов, метрические параметры и топологические свойства монтажного про-
странства. Для типовых конструкций ЭВМ, начиная с субблока, характер-
но регулярное
монтажное пространство. Тогда задачу размещения можно
сформулировать следующим образом. Имеются множество конструктив-
ных элементов E={e
i
/ i=1, N} и множество соединяющих их цепей Q={q
k
/
k=1, K}. Монтажное пространство определено множеством фиксирован-
ных позиций для установки элементов T={t
j
/ j=1, M}, причем M ≥ N. Най-
ти такое отображение множества Е в множество Т, при котором достигает-
ся экстремум целевой функции F.
Главная цель размещения – создание наилучших условий для трас-
сировки. Из-за условности разделения задач размещения и трассировки
трудно установить для задачи размещения такой критерий оптимизации,
который в достаточной мере удовлетворял бы требованиям
трассировки. В
настоящее время используют критерии: минимум суммарной длины всех
соединений или длины самой длинной связи; минимум числа пересечений
связей при произвольной их конфигурации; максимум числа цепей с воз-
можно более простой конфигурацией; максимально близкое расположение
модулей, имеющих наибольшее количество связей между собой. Указан-
ные критерии лишь качественно способствуют решению
главной задачи
размещения. Наиболее распространен критерий минимума суммарной
длины соединений, так как при его оптимизации косвенно минимизируют-
ся длина связей и число их пересечений, снижаются искажения сигналов.
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
