Трассировка в коммутационном блоке на основе генетических процедур

Б. К. Лебедев

Введение

Ввиду грандиозной сложности трассировка СБИС разбивается на два этапа: глобальная и детальная. При глобальной трассировке решается две задачи: разбиение коммутационного поля на области и распределение соединений по областям. Детальная трассировка заключается в проектировании топологии соединений внутри областей. Традиционно коммутационное поле разбивается на два типа областей: канал и коммутационный блок (switch box). 

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

Обычно проблема решается с дополнительно наложенными ограничениями, одним из которых является число слоев. В работе рассматривается двухслойная трассировка.

Задача трассировки в ограниченной прямоугольной области является NP-полной. Поэтому несмотря на обилие разработок, проблема построения эффективного трассировщика является актуальной.

Большинство алгоритмов трассировки в коммутационном блоке основываются на эвристиках, реализующих в той или иной степени идею последовательной трассировки [1,2,3,4]. В процессе прокладки на каждом шаге используются правила направленные на минимизацию воздействия прокладываемой цепи на непроложенные. Однако в полной мере проэкстраполировать все ситуации не представляется возможным. Это приводит к необходимости дополнительной трассировки. Основу этих алгоритмов составляют два принципа: локальная деформация, разрыв части соединений и перетрассировка их различными методами [2]. Но к сожалению и здесь возникает проблема очередности перетрассируемых соединений. В связи с этим интерес представляют комбинаторные алгоритмы, оперирующие со всеми соединениями. Среди математических методов обеспечивающих комбинаторный подход к решаемой задаче в последнее время наибольшее распространение получили методы моделирования отжига и эволюционного программирования. Особый интерес представляют генетические алгоритмы, основанные на механизмах природной селекции и генетики [5,6].

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

1. Формулировка задачи, основные термины и обозначения

Дадим формальное описание задачи трассировки коммутационного блока (ЗТКБ). Даны: верхний ряд контактов К1={к1i} и нижний ряд контактов К2={к2i}, пронумерованные слева направо, левый ряд контактов К3={к3i}  и правый ряд контактов К4={к4i}, пронумерованные сверху вниз, и расположенные на сторонах прямоугольника. К ним соответственно подходят множества цепей N1={n1i},  N2={n2i},  N3={n3i}, N4={n4i}, N=N1 È N2 È N3 È N4 - общее множество цепей. На область трассировки (ОТ) наложена сетка (рис.1). Терминалы (контакты) совпадают с линиями сетки.  Соединения подходят к контактам и распространяются в области трассировки только по линиям сетки.

На рис.1в ОТ2 представляет собой развернутое на 90° ОТ1 на рис.1а. Каждая цепь представляется в виде связного набора вертикальных и горизонтальных фрагментов. Не допускаются наложения друг на друга вертикальных и горизонтальных фрагментов, принадлежащих различным цепям, не допускается их пересечение в совместном эскизе топологии. Каждая цепь разбивается на двухтерминальные соединения (ДС). В простейшем случае разбиение на ДС осуществляется при последовательном просмотре столбцов сетки слева направо, начиная с крайнего слева столбца. На рис.1 цепь 1 подходит к терминалам (11,12,13), цепь 2 к (21,22,23), цепь 3 к (31,32,33), цепь 4 к (41,42), цепь 5 к (51,52). На рис.1 цепь 1 разбивается на ДС11=(11,12) и ДС12=(11,13), цепь 2 на ДС21=(21,22) и ДС22=(22,23), цепь 3 на ДС31=(31,32) и ДС32=(32,33).

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

Обозначим через S={si | i=1,2,...,n} множество всех ДС. Пусть в области трассировки реализовано с соблюдениями всех ограничений множество ДС  S1, S1ÌS, и пусть S2 множество ДС, которые не могут быть реализованы без нарушений в ОТ, заполненной S1, S2ÌS, S1ÈS2=S. Обозначим через d - мощность S2, т.е. d=½S2½.

В качестве оценки качества трассировки будет использоваться критерий:

Цель оптимизации - максимизация F совпадает с минимизацией d, где d число нереализованных ДС.

В случае полной реализации цепей, т.е. при d=0 (или F=1), оценкой качества служит критерий:

где li суммарная длина реализованной (протрассированной) цепи ni и L - суммарная длина всех цепей.

2. Генетический алгоритм трассировки в коммутационном блоке

Особенностью генетического алгоритма, моделирующего процесс естественной эволюции, является то, что оперирование производится с кодами решений. Каждому решению соответствует одна или несколько хромосом. Хромосомы состоят из генов. Гены могут иметь различные значения. Генетические алгоритмы работают с популяцией решений. Решения получаются на основе декодирования хромосом. Разработка генетического алгоритма включает этапы разработки структуры хромосом и принципов их кодирования и декодирования, генетических операторов, методики формирования исходной популяции и ее селекции, общей структуры генетического поиска.  

2.1. Структура хромосом, их кодирование и декодирование

Построим множество  горизонтальных участков iÎ, являющихся проекциями всех двухтерминальных соединений iÎ, т.е. каждому i соответствует i. На рис.2а и 2б приведены множества  для ОТ1 и ОТ2.

Обозначим через O(li) и O(ri) координаты по горизонтали левого и правого конца участка i. 

Разобьем множество , на подмножества k, в соответствии со следующими правилами:

   1.  , " (ij) [i Çj =0]

   2.  В пределах каждого  k все участки накладываются друг на друга, т.е

" (ij ½i Îk & j Îk) [(O(lj) £ O(li) £ O(rj))Ú((O(lj) £ O(ri) £ O(rj))].

Подмножество k пронумерованы и сформированы так, что все левые          концы участков k расположены левее левых концов участков k+1, т.е.          " (ij ½i Îk & j Îk+1) [(O(li) < O(lj) )].

Линейный алгоритм разбиения представлен в работе [7]. Разбиению  соответствует разбиение  S.

       Для участков, представленных на рис.2а, разбиение S имеет вид:

  S1={21,31,11} ,S2={32,4,12,22,5};

Для участков, представленных на рис.2б, разбиение S имеет вид:

  S1={11,21,4,31},  S2={22,32},  S3={12,5}.

Для ОТ1, представленной на рисунке 1а, m=5, для ОТ2, представленной на рис.1б, m=6, где m - число горизонтальных линий на ОТ.

Формируем на основе каждого Sk вектор Vk путем добавления в Sk нулевых элементов, так, чтобы мощность Vk была равна m, и фиксируем взаимное расположение элементов.

Для ОТ1:   V1=; V2=.

Для ОТ2: V1=; V2=; V3=.

Полученный после дополнения набор векторов V={Vi} будем называть решением задачи трассировки коммутационного блока.

Представим решение в виде хромосомы. Хромосома Hm является упорядоченной совокупностью генов . Ген  является одним из вариантов вектора Vi, т.е. значением  является некоторый вектор . Гены  и  хромосом Hm и Hl гомологичны, они одинаковы по составу элементов, соответствуют одному и тому же подмножеству Si двухтерминальных соединений, но отличаются порядком расположения элементов.

Декодирование хромосомы осуществляется с помощью процедуры декодирования, использующей идеи алгоритма «левого конца» при канальной трассировке. Как и при канальной трассировке будем называть горизонтальные линии опорной сетки ОТ магистралями, пронумерованными сверху вниз.

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

Порядок в котором ДС выбирают для заполнения магистралей задается соответствующей хромосомой и фактически определяется порядком расположения элементов в генах.

Заполнение магистралей двухтерминальными соединениями базируется на трех основных процедурах: укладки, трансформации, резервации.

В процессе укладки  ДС в заполняемую магистраль оно может быть уложено либо полностью, либо частично, либо не укладываться вообще.

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

Вертикальный столбец считается занятым (зарезервированным) для любой цепи ni не равной nf если в нем расположен выше заполняемой магистрали терминал, помеченный цепью nf и еще не связанный. Если терминал, расположенный выше n-ой магистрали, связывается по вертикали с горизонтальным участком, расположенным на n-ой магистрали, то столбец начиная с магистрали n+1, считается свободным. Изначально все столбцы, подходящие к помеченным цепями терминалам, расположенным на верхней стороне ОТ, считаются занятыми (зарезервированными). Например на рис.3а полностью размещены ДС1, ДС2 ДС3. На рис.3б частично размещены ДС1,ДС2,ДС4. При частичной укладке вводится точка разрыва ДС. Частично уложенное ДС связывает точку разрыва с одним из терминалов исходного ДС.

Точка разрыва вводится таким образом, чтобы у горизонтальной составляющей была максимально возможная длина.

После частичного размещения ДС проводится его трансформация, заключающаяся в том, что терминал, связанный с частично размещенным ДС переносится в точку разрыва. В дальнейшем ДС рассматривается как ДС, связывающее еще не связный терминал с терминалом в точке разрыва.

Возможно введение двух точек разрыва ДС. При этом два фрагмента ДС, связывающие каждый точку разрыва с терминалом исходного ДС, будут уложены, а третий фрагмент, связывающий две точки разрыва, будет укладываться в последующих магистралях. Таким образом исходное ДС трансформируется в ДС, связывающее две точки разрыва. Отметим, что ДС может в процессе укладки подвергаться нескольким последовательным трансформациям. На рис.3б в дальнейшем ДС1, ДС2, ДС4 будут рассматриваться, как ДС связывающие пары несвязных терминалов, помеченных соответственно (11,1¢2), (21,2¢2),(4¢1,4¢2).

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

На рис.4а проведены горизонтальные фрагменты от терминалов 11 до 1¢1 и от 21 до 2¢2. В дальнейшем ДС1 и ДС2 трансформируются, т.е. они будут инцидентны терминалам 1¢1  и  2¢2 соответственно. Перед резервацией анализируется состояние столбцов и если необходимо и существует возможность формируется ближайший к терминалу свободный столбец.

Если есть несколько столбцов, занятых терминалами одной цепи и эти терминалы уже связаны, то их можно объединить в один терминал, что приводит к освобождению столбцов. Например на рис.4в при резервации терминала 23 два столбца заняты терминалами 1¢2 и 12. 1¢2 входит в ДС(1¢1 , 1¢2), 12 входит в ДС (12, 13), но они связаны и их можно объединить в один терминал1¢2, при этом ДС(12,13) трансформируется в ДС (1¢2, 13). Это приводит к освобождению столбца в который можно поместить терминал 2¢3, связанный горизонтальным фрагментом с резервируемым терминалом 23.

Представим хромосому Hk виде матрицы Vk, где каждый столбец соответствует гену. Магистрали заполняются последовательно, начиная с первой. Заполнение магистралей осуществляется следующим образом. Вначале осуществляется резервация терминалов левой и правой сторон ОТ, лежащих на магистрали. Затем последовательно по строкам, начиная с первой в пределах строки слева направо просматриваются элементы матрицы Vk. Для каждого выбранного элемента матрицы (ДС) определяется возможность его размещения в формируемой магистрали. Если возможно, то ДС полностью или частично помещается в формируемую магистраль. Если ДС полностью помещается, то оно удаляется из матрицы Vk. Если ДС помещается частично, то трансформируется и остается в матрице. По окончании просмотра матрицы Vk осуществляется сжатие всех столбцов, из которых удалялись ДС, снизу вверх. После этого осуществляется переход