Ликвидация вертикальных конфликтов межсоединений в канале перед трассировкой (стр. 2 из 2)
Правило 2
Если имеется свободная колонка в зоне между x1ij/min и x2ij/max с координатой Xn3 , То в точке Pxtn3ÎT вводится псевдоконтакт -j и все остальные Pj Î T получают статус -j, а в координате Pxln3ÎL вводится псевдоконтакт j.
Таким образом, путем введения "излома" в области конфликта возможна его ликвидация Отметим, что введение излома будет произведено там, где совпадут абсциссы отрезков j и -j в области введения псевдоконтактов.
Правило 3 во многом сходно с правилом 2. Однако, в отличие от последнего, поиск свободной колонки осуществляется не в области конфликта, а вне его. При этом поиск производится последовательно слева - справа от зоны конфликта. Таким образом обеспечивается нахождение ближайшей к зоне свободной колонки.
Правило 3
Если существует свободная колонка от вертикальных сегментов слева (справа) от зоны ВК с координатой Xn3. И эта колонка ближайшая среди всех свободных колонок в зоне конфликта. То в точке Pxtn3ÎT вводится псевдо контакт –j и все остальные Pj Î T получают статус –j, а в координате Pxln3ÎL вводится псевдоконтакт j.
В том случае, когда свободные колонки в области канала отсутствуют, необходимо вводить излом в области ВК, но для того, чтобы избежать наложения отрезков в одинаковых слоях, необходима будет соответствующая модификация ГВО.
Ввиду того, что такое решение предусматривает увеличение плотности участка ВК, то правило содержит соответствующую проверку значений плотности.
Правило 4
Если Dmаxk в области конфликта меньше, чем Dmax, То проиэвольному Pk Î Т назначается дополнительный индекс -j и всем Рj Î Т назначается -j, а Pj Î L назначается дополнительный индекс j, Xpk = Xpl. При этом отрезок k в ГВО должен располагаться выше, чем -j, а отрезок l выше, чем i.
Правило 5 напоминает правило 4, однако вводит излом в той колонке i, в которой не произойдет увеличение плотности Di до Dmax. Делался это в целях минимизации ширины канала.
Правило 5
Если колонка, для которой Di = Dmax располагается в области ВК И существует колонка S вне области ВК, для которой Dmax–Ds ³ 2 И такая колонка ближайшая среди всех, удовлетворяющих ранне приведенным условиям к области ВК. ТО в колонке S назначаются доподнительные индексы -j и j с соответствующей корректировкой ГВO, а также всем Pj Î Т назначается -j. И, наконец, последнее правило, предлагаемое в работе:
Правило 6
Если существует конфликт. ТО слева (справа) от области канала ввести дополнительную колонку S, при этом Ps Î Т назначить -j и всем Pj Î T назначить -j, a Ps Î L назначить j.
На этом заканчиваются правила БЗ для решения ВК 1-го и 2-го типов, что естественно не исключает возможность их модификации или дополнения БЗ новыми правилами. Иерархия правил, и, следовательно, последовательность обращения СУ к ним соответ-ствует их порядковому номеру. Такая иерархия необходима для оп-тимизации получаемого решения с точки зрения ширины канала и длины получаемых отрезков.
Теперь опишем группу правил, позволяющих производить лик-видацию циклов 3-го типа. Как и прежде работу эвристическихправил рассмотрим на примерах.
Правило 1
Если между координатами n - конфликтующих отрезков x1i/min и x2i/max , где i = 1, 2, …,n не существует отрезков с номерами, отличными от 1, 2, …, n ТО расположить 1e и 2, …,ne соединения целиком в разныхслоях с наложением горизонтальных сегментов.
Работа правила проиллюстрирована на рис. 2. Правило эф-фективно, т.к. для разрешения конфликта n -соединений требует ( п-1 ) магистралей. Однако, такие ситуации сравнительно редко возникают на практике.
Рассмотрим следующее правило.
Правило 2
Если " из колонок с координатами x11/min=x1n/min или x21/max=x2n/max не существует пересекающих ее горизонтальных сегментов ТО расположить вертикальные и горизонтальные сегменты соединений 1 и n соответствующей колонки в разных слоях. Работа правила поясняется на рис. 1.3, откуда видно, что для решения n-звенного конфликта 3-го типа требуется n- магистралей. Заметим, что хотя Правило 2 используется чаще, чем Правило 1, но такие ситуации также сравнительно редки.
Гораздо чаще работает следующее правило. Заметим, что работа нижеследующих правил во многом совпадает с аналогичными правилами для ликвидадии ВК 1-го и 2-го типов, в тоже время, имея существенные отличия.
Правило 3
Если существует свободная колонка в зоне между x1i/min и x2i/max где i=1,2,...,n с координатой Xa
ТО в точке PtxaÎT вводится псевдоконтакт - 1 и все остальные P1Î Т получают статус - 1, а в координате PlxaÎL вводится псевдоконтакт 1.
Правило 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* за счет свойств ВК и декомпозиции горизонтальных сегментов. Форма представления правил позволяет легко их модифицировать или изменить в случае появления новых знаний о предметной области.