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

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

Введение

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

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

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

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

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

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 :

Широко известны и применяются на практике алгоритмы "Левого края" и раскраски графа ограничений комбинаторные, дающие решения очень быстро. К наиболее эффективным алгоритмам этой группы следует отнести алгоритм Йошимуры, где каждому горизонтальному сегменту цепи 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.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--