Новгородский государственный университет имени Ярослава Мудрого

Рассмотрим работу алгоритма при трассировке на однослойной ПП, когда критерием оптимизации является минимум длины соединения, и пересечение имеющихся проводников с помощью перемычек не допускается. В этом случае вес, приписываемый ячейке, просто совпадает с номером фронта, в который она в процессе распространения волны оказывается включенной. При этом считается, что в первый фронт Ф₁ включена только ячейка-источник, во второй фронт Ф₂ – соседние с источником незанятые ячейки. Если ячейка е включена во фронт Ф_i-1, то соседние с ней непомеченные ячейки включаются во фронт Ф_i и им присваивается вес w=i. Здесь соседними для ячейки с координатами (х, у) считаются ячейки, имеющие координаты (х+1, у), (х, у+1), (х-1, у), (х, у-1).

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

Х

Х

Х

Х

Х

Х

●1

Х

Х

●

●

Х

Х

●

Х

Х

Х

Х

Х

Х

3

Х

Х

Рис.7.5.2.1 Пример распространения волны и проведения трассы:

●- соединяемые ячейки; Х – занятые ячейки.

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

Существуют различные модификации основного алгоритма, которые уменьшают объем оперативной памяти. Например:

· использование путевых координат см рис.7.5.2.2. Распространяется не цифровая волна, а соседним с источником ячейкам задают координаты: ←, ↑, →, ↓;

· кодирование весов по модулю см рис.7.5.2.3. Ячейкам ДРП, включенным в очередной фронт приписывается не само значение веса k, а отметку 1, 2, или 3.

Рис.7.5.2.2 Рис.7.5.2.3

Самое большое преимущество волнового алгоритма в том, что если путь существует, то он будет найден.

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

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

Для трассировки схем с одним слоем коммутации наиболее перспективны графотеоретические методы трассировки.

В настоящее время отсутствуют алгоритмические методы трассировки, которые гарантировали бы 100%-ную разводку соединений для любой частной задачи. Поэтому целесообразно в любой автоматизированной системе конструирования иметь несколько программ трассировки, реализующих различные алгоритмы. Выбор определенного сочетания этих программ и последовательность их применения зависит от особенностей решаемой задачи. Так, для трассировки двухсторонних печатных плат с однотипными элементами целесообразно вначале применить один из быстрых алгоритмов трассировки по каналам или по магистралям, а затем волновой алгоритм для трассировки не разведенных соединений.

Новгородский государственный университет имени Ярослава Мудрого