Файл: Лекции 45 31. Особенности алгоритмов размещения при многоцелевой оптимизации модулей Мб лк 3 но там дрочь.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 46
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Приписание путевых координат производят на этапе распространения волны.
При проведении пути движение от ячейки к ячейке осуществляют по путевым координатам.
Достоинства алгоритма:
- позволяют легко учитывать технологическую специфику печатного монтажа со всей совокупностью конструктивных ограничений.
- всегда гарантируют построение трассы, если путь для нее существует
Недостатки алгоритма:
- невысокое быстродействие;
- большой объем оперативной памяти, необходимый для хранения информации о текущем состоянии всех ячеек коммутационного поля;
- возможность построения лишь соединений типа «вывод - вывод».
40. Модификация волнового алгоритма. Метод встречной волны
Источниками волн являются обе ячейки, подлежащие электрическому объединению.
1) На каждом k-ом шаге поочередно строят соответствующие фронты первой и второй волн, распространяющихся из этих ячеек.
2) Процесс продолжается до тех пор, пока какая-либо ячейка из фронта первой волны не попадет во фронт второй волны или наоборот.
3) Проведение пути осуществляют из данной ячейки в направлении обоих источников по правилам, описанным в волновом алгоритме Ли.
Достоинства алгоритма:
- время, затрачиваемое на этапе распространения волны, уменьшаются примерно вдвое.
Недостатки алгоритма:
- необходимость выделения дополнительного разряда памяти на каждую рабочую ячейку поля для хранения информации о принадлежности ее к первой или второй волне.
- возможность построения лишь соединений типа «вывод – вывод»
41. Модификация волнового алгоритма. Метод соединения комплексами
В качестве источника выбирают не только точку – источник волны, но и только что построенный проводник.
Достоинства алгоритма:
- возможность присоединения каждой очередной точки (начиная с третьей), к любой точке ранее построенных соединений,
- сокращение общей длины печатных проводников
- увеличение числа разводимых цепей
- возможность построения соединений типа «вывод - проводник» и «проводник - проводник».
Недостатки алгоритма:
- больший по сравнению с классическим требуемый объем памяти
42. Модификация волнового алгоритма. Лучевой алгоритм трассировки
Выбор ячеек для определения пути между соединяемыми точками А и В производят по заранее заданным направлениям, подобным лучам.
Достоинства алгоритма:
- Сокращение числа просматриваемых алгоритмом ячеек, а следовательно, и время на анализ и кодировку их состояния.
Недостатки алгоритма:
- приводит к снижению вероятности нахождения пути сложной конфигурации (Обычно с помощью лучевого алгоритма удается построить до (70-80)% трасс)
- усложняет учет конструктивных требований к технологии печатной платы.
Задается число лучей, распространяемых из точек А и В, а также порядок присвоения путевых координат (обычно число лучей для каждой ячейки-источника принимается одинаковым).
Лучи А(1), А(2), ..., А(n) и В(1), В(2),..., В(n) считают одноименными, если они распространяются из одноименных источников А или В.
Лучи А(i) и В(i) являются разноименными по отношению друг к другу.
Распространение лучей производят одновременно из обоих источников до встречи двух разноименных лучей в некоторой ячейке С.
Путь проводится из ячейки С и проходит через ячейки, по которым распространялись лучи.
43. Эвристический алгоритм трассировки
основаны на эвристическом приеме поиска пути в лабиринте. При этом каждое соединение проводится по кратчайшему пути, обходя встречающиеся на пути препятствия.
Достоинства алгоритма:
- наиболее быстродействующие и простые в программировании.
Недостатки алгоритма:
- заложенный в их основу приоритетный (постоянный) порядок построения трассы и обхода препятствий влечет за собой неоптимальность получаемого результата
44. Особенности автоматизированной трассировки соединений в многослойных печатных платах
45. Классификация задач конструкторского проектирования
ДРОЧЬ ГУГЛИМ