Материал: Lab 7 Z

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждения высшего образования «УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Радиотехнический факультет Кафедра «Проектирование и технология электронных средств»

Дисциплина: «Математическое обеспечение САПР»

Лабораторная работа №7:

«ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

ТРАССИРОВКИ ПЕЧАТНЫХ И ПЛЕНОЧНЫХ СОЕДИНЕНИЙ»

Работу выполнил: Проверил: Студент группы Рбд-31 профессор Зарипов Т.Р. Мактас М.Я.

Ульяновск 2021

1. Цель работы.

Цель работы – исследовать эффективность алгоритмов трассировки печатных и пленочных соединений; освоить особенности алгоритмизации и программирования задач трассировки печатных соединений на современных ЭВМ волновыми и лучевым алгоритмами; приобрести навык построения математических моделей объектов конструирования, реализации и исследования их при решении задачи трассировки в САПР.

2. Волновой алгоритм Ли.

Многие методы трассировки печатных соединений основаны на идеях волнового алгоритма, предложенного С. Ли [1 – 4]. Он представляет собой развитие алгоритмов построения кратчайших путей в сети и позволяет находить маршруты соединений, оптимальные по ряду параметров. Данный алгоритм является классическим примером использования методов динамического программирования.

Монтажное поле разбивается на элементарные ячейки. Размеры ячеек и их количество определяются площадью поля, допустимой плотностью расположения выводов элементов и проводников. В простейшем случае ячейка представляет собой квадрат со стороной h, равной расстоянию между средними линиями двух соседних печатных проводников.

Если размеры поля по горизонтали и вертикали соответственно A_x и B_y, то получим дискретное рабочее поле (ДРП) с N_x × N_y ячейками:

N_x = {A_x/h}, N_y = {A_y/h} (7.1)

где {} – символ ближайшего большего целого.

В данном ДРП определяется множество занятых ячеек, соответствующее зонам, запрещенным для проведения соединений: выводы элементов, технологические области, ранее проведенные соединения и т. д. По мере проведения соединений множества занятых и свободных ячеек изменяются.

Основу всех модификаций волнового алгоритма С. Ли составляет процедура построения оптимального в заданном смысле пути между двумя известными ячейками ДРП. Процедура состоит из двух этапов: поиска пути и проведения пути.

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

В первом случае искомый путь существует, во втором – нет.

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

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

3. Распространение числовой волны.

Образование очередного фронта волны Ф_k (k = 1, 2, ...) начинается с присвоения всем свободным, ранее не помеченным ячейкам, соседним с ячейками предыдущего фронта Ф_k-1, веса p_k = k.

Соседними с данной ячейкой c_i (x_i , y_i ) могут быть ячейки двух видов:

1. Ячейки ДРП, которые имеют с ней общее ребро (рис. 1): c_i¹ (x_i - 1, y_i); c_i² (x_i, y_i + 1); c_i³ (x_i + 1, y_i); c_i⁴ (x_i, y_i - 1). Очередной фронт волны распространяется по четырем направлениям.

Рис. 1. Распространение волны по четырем направлениям.

2. Ячейки ДРП, которые имеют с ней хотя бы одну общую точку (рис.2) c_i¹ (x_i - 1, y_i); c_i² (x_i - 1, y_i + 1); c_i³ (x_i, y_i + 1); c_i⁴ (x_i + 1, y_i + 1); c_i⁵ (x_i + 1, y_i); c_i⁶ (x_i + 1, y_i - 1); c_i⁷ (x_i, y_i - 1); c_i⁸ (x_i - 1, y_i - 1). Очередной фронт волны распространяется в свободные ячейки по восьми направлениям.

Рис. 2. Распространение волны по восьми направлениям.

Для сокращения числа поворотов пути на этапе проведения может быть принято следующее правило приоритета. При переходе от ячейки фронта Ф_k к ячейке фронта Ф_k-1 следует, по возможности, сохранять направление, определяемое переходом от ячейки Ф_k-1 к ячейке Ф_k. Вес, присваиваемый ячейке фронта Ф_k, равен расстоянию этой ячейки от источника.

Чтобы исключить неопределенность при проведении пути для случая, когда несколько ячеек имеют одинаковый минимальный вес, вводят понятие путевых координат, задающих предпочтительность проведения трассы. Каждое направление кодируют двоичным числом по mod q , где q – число просматриваемых соседних ячеек. При этом чем более предпочтительно то или иное направление, тем меньший числовой код оно имеет. Например, если задаться приоритетным порядком проведения пути сверху, справа, снизу и слева, то коды соответствующих путевых координат будут 00, 01, 10 и 11. Присвоение путевых координат производят на этапе распространения волны. При проведении пути движение от ячейки к ячейке осуществляют по путевым координатам.

4. Построение пути минимальной длины по алгоритму Ли.

Пусть задано множество ячеек дискретного поля, на котором построено некоторое число проводников. Требуется построить новый проводник между точками A и B так, чтобы он не пересекал ранее построенные проводники и имел минимально возможную длину.

Распространение волны начинаем из источника – точки A, вес которой положим равным нулю. Строим расширяющийся фронт волны влияний, распространяющийся на все соседние свободные с этой точкой ячейки. Каждая ячейка фронта генерирует следующий фронт волны, который занимает все соседние свободные с первым фронтом ячейки и т. д. Вес ячейки k-го фронта считается равным весу соседней ячейки (k – 1)-го фронта плюс единица, т. е. p_k = p_k-1 + 1. Процесс распространения волны продолжаем до тех пор, пока не достигнем ячейки с точкой B (целью). Процесс поиска пути из A в B в соответствии с рассмотренным алгоритмом для данного варианта трассировки показан на рис. 3. В каждой ячейке указаны приписанные ей на этапе распространения волны веса. Ячейка B достигается при построении 12-го фронта волны.

Рис. 3. Построение пути минимальной длины по алгоритму Ли при распространении волны в четырех направлениях.

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

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

Достоинства волнового алгоритма: возможность нахождения пути минимальной длины в любом лабиринте, если существует хотя бы один путь в нем.

Недостатками волнового алгоритма Ли являются малое быстродействие и большой объем оперативной памяти ЭВМ, необходимый для хранения информации о текущем состоянии всех ячеек коммутационного поля.

Рис. 4. Построение пути минимальной длины по алгоритму Ли при распространении волны в восьми направлениях.