А.В. Мухлаев, С.Н. Щеглов, М.Д. Сеченов
Введение
Низкая временная и пространственная сложность алгоритмов канальной трассировки делает их наиболее приемлемыми в САПР электронных систем, где решаются задачи огромной размерности (несколько миллионов транзисторов). Указанное обстоятельство обусловило повышенный интерес разработчиков САПР к группе канальных алгоритмов и, как следствие, большое число различных типов канальных трассировщиков.
Наибольшее внимание исследователей традиционно привлекала группа канальных алгоритмов, относящихся к безизломным канальным трассировщикам. Подробнее остановимся на указанной группе алгоритмов и введем некоторые основные понятия, так как безизломные канальные трассировщики наиболее приемлемы в последующим причинам:
– позволяют получать решения наиболее быстро ;
– хорошо апробированы и применяются на практике ;
– достаточно качественно и эффективно решают задачу трассировки в двустороннем канале.
1. Классификация, критерии и постановка задачи канальной трассировки
Ввиду того, что задача канальной трассировки в сводится к задаче трассировки горизонтального канала, сверху и снизу ограниченного подлежащими соединению контактами, запишем формальную постановку задачи и дадим традиционные определения плотности и графа вертикальных ограничений (ГВО) (рис. 1).
Пусть задана декартова система координат и на оси Х с ша-гом n отложены точки Pl
1
, Pl
2
, ...,Pl
n
, образующие кортеж B и соответствующие нижнему ряду контактов горизонтального канала, а на некоторой линии mi
(линии mj
откладываются с шагом b ), параллельной оси Х отложены точки Pt
1
, Pt
2
, ...,Pt
n
образующие кортеж Т и соответствующие верхним контактам горизонтaльного канала.
Выделим подмножества Pl
ij
,Pt
ij
,
j=1,f,i=1,f,Pl
j
,Pt
i
¹0}, каждое из которых составлено из Pl
j
и Pt
i
равных между собой, т.е. соответствующих одной цепи (f- число цепей). На их основе сформируем множество отрезков Q={q1
,q2
,...,qn
}левые координаты которых равны минимальной координате Pl
j
ÚPt
i
из соответствующего подмножеcтва Pi-Xq
1
i
=min Хрi, а правые координаты-максимальной координате P1
j
ÚPt
j
-Xq2
i
=maxXpi
Необходимо распределить qf
отрезков по магистралям таким образом, чтобы требуемое для трассировки число магистралей было минимально: mk
®min и выполнялось ограничение (1)
"(i,j)=1,f:q1
*nqj
=Æ ( 1)
а также ограничения, задаваемые с помощью графа вертикальных ограничений (ГВО), множество вершин которого соответствует Pi
,
j
=1,f ,т.е. соответствует множеству цепей, а две его вершины Pi
и Pj
соединяются ориентированным ребром, что означает принудительное расположение отрезка qi
выше, чем qj
в том случае, если
"Pt
ij
ÎTÞPt
ij
¹Pl
ij
ÎB
Следует отметить, что условие (1) несомненно приоритетно по сравнению с другими критериями трассировки (см. рис. 1), однако, может носить и аддитивный и мультипликативный характер. Отметим, что плотность Ui колонки i канала будем называть число горизонтальных сегментов Sqi
, пересекающих i ко-лонку. Максимальной плотностью Umax назовем Ui :
j=1,n
Широко известны и применяются на практике алгоритмы "Левого края" и раскраски графа ограничений комбинаторные, дающие решения очень быстро. К наиболее эффективным алгоритмам этой группы следует отнести алгоритм Йошимуры, где каждому горизонтальному сегменту цепи qi
ставится в соответствие интегральная характеристика.
Наряду с указанными достоинствами беэизломные алгоритмы обладают и рядом недостатков, при этом один из основных- невозможность решения так называемых циклических конфликтов.
В связи с этим целесообразным представляется разработка подсистемы трассировки, базирующейся на методе систем продукций и содержащей интеллектуализированные процедуры решения циклических конфликтов. В качестве достоинств метода систем продукций отметим:
– модульность;
– понятность работы для операэвора;
– легкость ведения и дополнения БЗ;
– описание правил - продукции на профессиональном языке.
Отметим, что более 70% современных ЭС строятся на основеметода систем продукций /86,87/, и среди них такие известные как MYCIN,OPSS,VIREX,SMALL ТАLK и др.
2. Разработка стратегии управления процессомканальной трассировки
Как известно, продукционные системы включают три основныхкомпонента; глобальную базу данных (ГБД), набор решающих правил (НРП) и стратегию управления (СУ). Именно стратегия управления выбирает какое именно правило продукций следует применять в сложившейся ситуации к глобальной базе данных и останавливает процесс, если глобальная база данных удовлетворяет априори заданным условиям.
В нашем случае ГБД состоит из двух кортежей: T=<Pt
1
,Pt
2
,…,Pt
n
> и B=<Pl
1
,Pl
2
,…,Pl
n
> описывающих контакты канала и множества Q={q1
,q2
,…,qn
}, описывающего цепи (горизонтальные сегменты), подлежащие распределению по магистралям.
Задача ставится следующим образом. На основе экспертных знаний о ликвидации циклических конфликтов и перераспределении инвариантных контактов построить стратегию управления для преобразования ГБД к такому виду, который бы эффективно решался с помощью известных безизломных канальных трассировщиков. Иными словами - ГБД не должна содержать циклических конфликтов.
3. Разработка информационного содержания базы знаний для решения вертикальных конфликтов
БЗ для решения вертикальных конфликтов (ВК) в процессе трассировки строится на основе продукционных правил. Ввиду того, что возможны различные варианты вертикальных конфликтов, целесообразным представляется проведение классификации ВК по группам таким образом, чтобы к каждой такой группе ВК была применима соответствующая группа продукционных правил (ПП).
3.1. Классификация ВК
Дадим строгое определение ВК 1-типа.
Определение ВК первого типа называется ситуация, когда в исходных спецификациях трассировки $qi
,qj
,i¹j:Xq1
i
=Xq1
j
; Xq2
i
=Xq2
j
, а также P1
xi
ÎT, P2
xi
ÎL и P1
xj
ÎL, P2
xj
ÎT.
Некоторым обобщением ВК 1-го типа являются ВК второго типа В этом случае допускается произвольное число конфликтующих контактов.
Определение ВК второго типа называется ситуация в исход-
ных спецификациях трассировки, когда $qi,qj
,i¹j:$Pa
a
i
Îqi
,$Pa
a
j
Îqj
: a=1,2,…: Xpa
i
= Xpa
j
и некоторые подмножества , а соответствующие Конфликты третьего типа образуют в соответствующем ГВО цикл, в котором может быть произвольное число вершин больше двух.
Определение ВК третьего типа называется ситуация в исходных спецификациях трассировки, когда $q1
,q2
,…,qn
: X1
q1
=X1
q2
: X2
q2
=X1
q3
, …,X2
qn-1
=X1
qn
, X2
qn
=X2
q1
и одновременно "P1
xi
, i=2,3,…,nÎL, "P2
xi
,i=2,3,…, nÎT , а P1
x1
ÎT и P2
x1
ÎL.
ВК четвертого типа можно назвать комбинированными, так как они могут включать в один конфликтный узел ГВО одновременно произвольное число конфликтов 1-го, 2-го, 3-го типов.
3.2. Ликвидация ВК на основе технологии ИИ
После того, как ВК идентифицирован, необходимо ликвидировать его с помощью применения правил предикатного типа. Такие правила полученые в результате экспертных исследований при трассировке и иерархичеоки организованных БЗ. Общий вид правила следующий:
Правило N1
ЕСЛИ (условие)
И (условие)
И (условие)
ТО ( рекомендуемое действие )
ЕСЛИ решение задачи с помощью текущего i -го правила невозможно, т.к. не выполняется какое-либо из его условий, то происходит вызов /i+1/-го правила и так до тех пор, пока не будет получено решение. В противном случае при данном наполнении БЗ получить решение невозможно. Одним из важных достоинств такого подхода является легкая модификация или дополнение правил БЗ, если получена свежая экспертная информация.
Таким образом возможна перманентная передача знаний системе трассировки и, как следствие, повышение качества проектирования.
Набор правил-продукций должен удовлетворять следующим условиям
Вначале рассмотрим группу правил, предназначенных для ликвидации ВК 1-го и 2-го типов
Правило 1 (Правило наложения)
Если зона канала между самой левой x1
ij
/min и самой правой x2
ij
/max координатами конфликтующих соединений не содерхит других горизонтадьных сегментов. То расположить целиком j и i соединения в разных слоях.
Однако, такое правило сравнительно редко может быть применено в реальных задачах. Чаще возможно применение правила 2
Правило 2
Если имеется свободная колонка в зоне между x1
ij
/min и x2
ij
/max с координатой Xn3 ,
То в точке Pxt
n3
ÎT вводится псевдоконтакт -j и все остальные Pj Î T получают статус -j, а в координате Pxl
n3
ÎL вводится псевдоконтакт j.
Таким образом, путем введения "излома" в области конфликта возможна его ликвидация Отметим, что введение излома будет произведено там, где совпадут абсциссы отрезков j и -j в области введения псевдоконтактов.
Правило 3 во многом сходно с правилом 2. Однако, в отличие от последнего, поиск свободной колонки осуществляется не в области конфликта, а вне его. При этом поиск производится последовательно слева - справа от зоны конфликта. Таким образом обеспечивается нахождение ближайшей к зоне свободной колонки.
Правило 3
Если существует свободная колонка от вертикальных сегментов слева (справа) от зоны ВК с координатой Xn3
. И эта колонка ближайшая среди всех свободных колонок в зоне конфликта. То в точке Pxt
n3
ÎT вводится псевдо контакт –j и все остальные Pj Î T получают статус –j, а в координате Pxl
n3
Î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 - конфликтующих отрезков x1
i
/min и x2
i
/max , где i = 1, 2, …,n не существует отрезков с номерами, отличными от 1, 2, …, n ТО расположить 1e
и 2, …,ne
соединения целиком в разныхслоях с наложением горизонтальных сегментов.
Работа правила проиллюстрирована на рис. 2. Правило эф-фективно, т.к. для разрешения конфликта n -соединений требует ( п-1 ) магистралей. Однако, такие ситуации сравнительно редко возникают на практике.
Рассмотрим следующее правило.
Правило 2
Если " из колонок с координатами x1
1
/min=x1
n
/min или x2
1
/max=x2
n
/max не существует пересекающих ее горизонтальных сегментов ТО расположить вертикальные и горизонтальные сегменты соединений 1 и n соответствующей колонки в разных слоях. Работа правила поясняется на рис. 1.3, откуда видно, что для решения n-звенного конфликта 3-го типа требуется n- магистралей. Заметим, что хотя Правило 2 используется чаще, чем Правило 1, но такие ситуации также сравнительно редки.
Гораздо чаще работает следующее правило. Заметим, что работа нижеследующих правил во многом совпадает с аналогичными правилами для ликвидадии ВК 1-го и 2-го типов, в тоже время, имея существенные отличия.
Правило 3
Если существует свободная колонка в зоне между x1
i
/min и x2
i
/max где i=1,2,...,n с координатой Xa
ТО в точке Pt
x
a
ÎT вводится псевдоконтакт - 1 и все остальные P1
Î Т получают статус - 1, а в координате Pl
x
a
ÎL вводится псевдоконтакт 1.
Правило 4
Если существует свободная от вертикальных сегментов слева (справа) от зоны n-звенного ВК с координатой Хa
. И эта колонка ближайшая среди всех свободных колонок к зоне ВК ТО в точке Pt
x
a
ÎT вводится псевдоконтакт - 1 ( -n ) и все остальные P1
Î T (Pn
Î T) получают статус - 1 (-n), а в координате Pl
x
a
Î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*
за счет свойств ВК и декомпозиции горизонтальных сегментов. Форма представления правил позволяет легко их модифицировать или изменить в случае появления новых знаний о предметной области.