Ликвидация вертикальных конфликтов межсоединений в канале перед трассировкой (стр. 1 из 2)

А.В. Мухлаев, С.Н. Щеглов, М.Д. Сеченов

Введение

Низкая временная и пространственная сложность алгоритмов канальной трассировки делает их наиболее приемлемыми в САПР электронных систем, где решаются задачи огромной размерности (несколько миллионов транзисторов). Указанное обстоятельство обусловило повышенный интерес разработчиков САПР к группе канальных алгоритмов и, как следствие, большое число различных типов канальных трассировщиков.

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

– позволяют получать решения наиболее быстро ;

– хорошо апробированы и применяются на практике ;

– достаточно качественно и эффективно решают задачу трассировки в двустороннем канале.

1. Классификация, критерии и постановка задачи канальной трассировки

Ввиду того, что задача канальной трассировки в сводится к задаче трассировки горизонтального канала, сверху и снизу ограниченного подлежащими соединению контактами, запишем формальную постановку задачи и дадим традиционные определения плотности и графа вертикальных ограничений (ГВО) (рис. 1).

Пусть задана декартова система координат и на оси Х с ша-гом n отложены точки P^l₁, P^l₂, ...,P^l_n , образующие кортеж B и соответствующие нижнему ряду контактов горизонтального канала, а на некоторой линии m_i (линии m_j откладываются с шагом b ), параллельной оси Х отложены точки P^t₁, P^t₂, ...,P^t_n образующие кортеж Т и соответствующие верхним контактам горизонтaльного канала.

Выделим подмножества P^l_ij,P^t_ij,j=1,f,i=1,f,P^l_j,P^t_i¹0}, каждое из которых составлено из P^l_j и P^t_i равных между собой, т.е. соответствующих одной цепи (f- число цепей). На их основе сформируем множество отрезков Q={q₁,q₂,...,q_n}левые координаты которых равны минимальной координате P^l_jÚP^t_i из соответствующего подмножеcтва Pi-X_q¹_i=min Хрi, а правые координаты-максимальной координате P¹_jÚP^t_j-Xq²_i=maxXp_i

Необходимо распределить q_f отрезков по магистралям таким образом, чтобы требуемое для трассировки число магистралей было минимально: m_k®min и выполнялось ограничение (1)

"(i,j)=1,f:q₁*nq_j=Æ ( 1)

а также ограничения, задаваемые с помощью графа вертикальных ограничений (ГВО), множество вершин которого соответствует P_i,j=1,f ,т.е. соответствует множеству цепей, а две его вершины P_i и P_j соединяются ориентированным ребром, что означает принудительное расположение отрезка q_iвыше, чем q_j в том случае, если

"P^t_ijÎTÞP^t_ij¹P^l_ijÎB

Следует отметить, что условие (1) несомненно приоритетно по сравнению с другими критериями трассировки (см. рис. 1), однако, может носить и аддитивный и мультипликативный характер. Отметим, что плотность Ui колонки i канала будем называть число горизонтальных сегментов Sq_i, пересекающих i ко-лонку. Максимальной плотностью Umax назовем Ui :

j=1,n

Широко известны и применяются на практике алгоритмы "Левого края" и раскраски графа ограничений комбинаторные, дающие решения очень быстро. К наиболее эффективным алгоритмам этой группы следует отнести алгоритм Йошимуры, где каждому горизонтальному сегменту цепи q_i ставится в соответствие интегральная характеристика.

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

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

– модульность;

– понятность работы для операэвора;

– легкость ведения и дополнения БЗ;

– описание правил - продукции на профессиональном языке.

Отметим, что более 70% современных ЭС строятся на основеметода систем продукций /86,87/, и среди них такие известные как MYCIN,OPSS,VIREX,SMALL ТАLK и др.

2. Разработка стратегии управления процессомканальной трассировки

Как известно, продукционные системы включают три основныхкомпонента; глобальную базу данных (ГБД), набор решающих правил (НРП) и стратегию управления (СУ). Именно стратегия управления выбирает какое именно правило продукций следует применять в сложившейся ситуации к глобальной базе данных и останавливает процесс, если глобальная база данных удовлетворяет априори заданным условиям.

В нашем случае ГБД состоит из двух кортежей: T=<P^t₁,P^t₂,…,P^t_n> и B=<P^l₁,P^l₂,…,P^l_n> описывающих контакты канала и множества Q={q₁,q₂,…,q_n}, описывающего цепи (горизонтальные сегменты), подлежащие распределению по магистралям.

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

3. Разработка информационного содержания базы знаний для решения вертикальных конфликтов

БЗ для решения вертикальных конфликтов (ВК) в процессе трассировки строится на основе продукционных правил. Ввиду того, что возможны различные варианты вертикальных конфликтов, целесообразным представляется проведение классификации ВК по группам таким образом, чтобы к каждой такой группе ВК была применима соответствующая группа продукционных правил (ПП).

3.1. Классификация ВК

Дадим строгое определение ВК 1-типа.

Определение ВК первого типа называется ситуация, когда в исходных спецификациях трассировки $q_i,q_j,i¹j:Xq¹_i=Xq¹_j; Xq²_i=Xq²_j, а также P¹_xiÎT, P²_xiÎL и P¹_xjÎL, P²_xjÎT.

Некоторым обобщением ВК 1-го типа являются ВК второго типа В этом случае допускается произвольное число конфликтующих контактов.

Определение ВК второго типа называется ситуация в исход-

ных спецификациях трассировки, когда $qi,q_j,i¹j:$P^a_aiÎq_i,$P^a_ajÎq_j: a=1,2,…: Xp^a_i= Xp^a_j и некоторые подмножества , а соответствующие Конфликты третьего типа образуют в соответствующем ГВО цикл, в котором может быть произвольное число вершин больше двух.

Определение ВК третьего типа называется ситуация в исходных спецификациях трассировки, когда $q₁,q₂,…,q_n: X¹q₁=X¹q₂: X²q₂=X¹q₃ , …,X²q_n-1=X¹q_n , X²q_n=X²q₁ и одновременно "P¹x_i, i=2,3,…,nÎL, "P²x_i ,i=2,3,…, nÎT , а P¹_x1ÎT и P²_x1ÎL.

ВК четвертого типа можно назвать комбинированными, так как они могут включать в один конфликтный узел ГВО одновременно произвольное число конфликтов 1-го, 2-го, 3-го типов.

3.2. Ликвидация ВК на основе технологии ИИ

После того, как ВК идентифицирован, необходимо ликвидировать его с помощью применения правил предикатного типа. Такие правила полученые в результате экспертных исследований при трассировке и иерархичеоки организованных БЗ. Общий вид правила следующий:

Правило N1

ЕСЛИ (условие)

И (условие)

И (условие)

ТО ( рекомендуемое действие )

ЕСЛИ решение задачи с помощью текущего i -го правила невозможно, т.к. не выполняется какое-либо из его условий, то происходит вызов /i+1/-го правила и так до тех пор, пока не будет получено решение. В противном случае при данном наполнении БЗ получить решение невозможно. Одним из важных достоинств такого подхода является легкая модификация или дополнение правил БЗ, если получена свежая экспертная информация.

Таким образом возможна перманентная передача знаний системе трассировки и, как следствие, повышение качества проектирования.

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

Вначале рассмотрим группу правил, предназначенных для ликвидации ВК 1-го и 2-го типов

Правило 1 (Правило наложения)

Если зона канала между самой левой x¹_ij/min и самой правой x²_ij/max координатами конфликтующих соединений не содерхит других горизонтадьных сегментов. То расположить целиком j и i соединения в разных слоях.

Однако, такое правило сравнительно редко может быть применено в реальных задачах. Чаще возможно применение правила 2