Ликвидация вертикальных конфликтов межсоединений в канале перед трассировкой

Категория реферата: Рефераты по информатике, программированию
Теги реферата: скачать диплом, рассказы
Добавил(а) на сайт: Karateev.

Правило 4

Если существует свободная от вертикальных сегментов слева  (справа) от зоны n-звенного ВК с координатой Хa. И эта колонка ближайшая среди всех свободных колонок к зоне ВК ТО в точке PtxaÎT вводится псевдоконтакт - 1 ( -n ) и все остальные  P1 Î T (Pn Î T) получают статус - 1 (-n), а в координате PlxaÎL вводится псевдоконтакт 1(n). Решение может быть получено, если Xa располагается слева от зоны ВК и решение получается, если Xa - справа от зоны ВК. Получение двух различных решений, в зависимости от того, с какой стороны ВК располагается ближайшая свободная колонка, связано с тем, чтобы одновременно с ликвидацией ВК минимизировать длину соединений.

Дальнейшие правила по ликвидации ВК 3-го типа полностью совпадают с правилами № 4, 5, 6 ддя ликвидации ВК 1-го, 2-го  рода. Только в данном случае дни получат номера соответственно 5, 6, 7.

Особо стоит вопрос о ликвидации ВК 4-го типа. Несмотря на то, что в практических задачах ВК 4-го типа встречаются крайне редко, их ликвидация представляет наибольшие сдожности. В рабо-те предлагается подход к решению указанных ВК на основе их де-композиции и приведению к ВК 1-го, 2-ro и 3-го типов с после-дующей ликвидацией последних на основе вышеописанной технологии.

Отметим, что возможны два варианта ВК 4-го типа. Для того, чтобы определить вариант ВК 4-го типа необходимо организовать просмотр направленных дуг ГВО. Если из последней по номеру вершины ГВО существует направленное ребро к первой вершине, то ВК вложенного типа. Если  такого ребра не существует, то ВК секционного типа с числом секций равным числу ребер, организующим путь из n-вершины в 1-ю, при этом на каждом шаге выбирается то ребро среди альтернативных, которое ведет к вершине с минимально возможным номером.

Решение секционных ВК 4-го рода очевидно. Необходимо разбить такой ВК на секции и обрабатывать каждую секцию по отдельности (заметим, что ВК может быть 1-го, 2-го, 3-го, а так же ВК 4-го рода вложенного типа).

ВК вложенного типа можно решить последовательным "раскрытием" внешних ВК. На первом шаге применено правило 4 для ВК 3-го типа. На втором шаге ликвидирован ВК 1-го типа путем применения правила 2 для ликвидации ВК 1-го типа

В результате произведен анализ существующих алгоритмов канальной трассировки и на его основе сделан выбор в пользу применения в САПР безизломных канальных трассировщиков ввиду того, что в мире разработано большое число безизломных канальных трассировщиков с широким спектром характеристик от очень быстрых с низким качеством  решения до точных получающих решения близкие к оптимальным. Такая ситуация дает возможность гибкой тактике применения различных трассировщиков. Кроме того безизломные канальные трассировщики наиболее щироко применяються практически. Ввиду того, что безизломные канальные трассировщики имеют резервы повышения качества решения, а также исключают возможность решения ВК предлагается повышение качества автоматической трассировки на основе метода систем продукций. Предлагаемая система содеркит эвристические полиномиальные процедуры ликвидации ВК.4 Разработаны группы решающих правил по форме "ЕСЛИ" - "ТО" для ликвидации ВК и сокращения m* за счет свойств ВК и декомпозиции горизонтальных сегментов. Форма представления правил позволяет легко их модифицировать или изменить в случае появления новых знаний о предметной области.

Поделитесь этой записью или добавьте в закладки