Методы и алгоритмы компоновки, размещения и трассировки печатных плат — страница 12

  • Просмотров 3977
  • Скачиваний 310
  • Размер файла 60
    Кб

порядком проведения пути сверху, справа, снизу и слева, то коды соответствующих путевых координат будут 00, 01, 10, и 11. Приписание путевых координат производят на этапе распространения волны. При проведении пути движение от ячейки к ячейке осуществляют по путевым координатам. SHAPE * MERGEFORMAT Существенными недостатками волнового алгоритма являются малое быстродействие и большой объем оперативной памяти ЭВМ, необходимый для хранения

информации о текущем состоянии всех ячеек коммутационного поля, возможность построения лишь соединений типа «ввод-вывод». Попытки устранить указанные недостатки привели к созданию ряда модификаций волнового алгоритма. Модификации алгоритма Ли     Метод встречной волны   В данном методе источниками волн являются обе ячейки, подлежащие электрическому объединению. При этом на каждом k-ом шаге поочередно строят

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

источников одной или двух объединяемых точек. Пусть расстояние между этими точками R. Тогда для первого случая в момент достижения волной ячейки-приемника площадь просмотренной окрестности имеет величину (знак равенства соответствует отсутствию преград пути распространения волны). Для второго случая в момент встречи фронтов двух волн площадь просмотренной окрестности Таким образом, при использовании метода встречной волны

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

случаях, когда это позволяет объем оперативной памяти ЭВМ. Лучевой алгоритм трассировки     В данном алгоритме, предложенным Л.Б. Абрайтисом, выбор ячеек для определения пути между соединяемыми точками A и B производят по заранее заданным направлениям, подобным лучам. Это позволяет сократить число просматриваемых алгоритмом ячеек, а следовательно, и время на анализ и кодировку их состояния, однако приводит к снижению