Реферат: Трассировка в коммутационном блоке на основе генетических процедур
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 =<31,0,11,21,0>; V2 =<32,4,12,22,5>.
Для ОТ2: V1 =<11,21,4,31,0,0>; V2 =<22,32,0,0,0,0>; V3 =<12,5,0,0,0,0>.
Полученный после дополнения набор векторов 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 осуществляется сжатие всех столбцов, из которых удалялись ДС, снизу вверх. После этого осуществляется переход к заполнению следующей магистрали. Процесс декодирования и заполнения магистралей показан на рис.5 и 6 для ОТ представленных соответственно на рис.1а и 1б. Отметим, что это фактически одна и та же задача трассировки.
Рассмотрим сначала процесс укладки в ОТ1, показанный на рис.1а. На рис.5а показаны два этапа заполнения первой магистрали: резервация и укладка. Вначале осуществляется резервация терминала 33 , лежащего на 1-й магистрали. Для этого от терминала 33 проводится горизонтальный фрагмент до ближайшего свободного столбца. Терминал 33 резервируется терминалом 3¢3 , а ДС32=(32 ,33 ) трансформируется в ДС32¢=(32 ,3¢3 ). Затем проводится укладка ДС в первую магистраль. Просматривается матрица Vk и первым выбирается ДС31=(31 ,32 ). ДС31 укладывается частично, при этом трансформируясь в ДС31¢=(31 ,3¢2 ). Следующим из Vk выбирается ДС32¢, которое полностью помещается в первую магистраль и удаляется из Vk . Процесс заполнения завершается и Vk сжимается. На рис.5б заполняется вторая магистраль. Вначале резервируются терминалы 21 и 42 , ДС21=(21 ,22 ) и ДС4=(41 ,42 ) трансформируются в ДС21¢=(2¢1 ,22 ) и ДС4¢=(41 ,4¢2 ).
Затем просматривается матрица Vk . ДС31¢ не помещается, ДС4¢ помещается полностью и удаляется из Vk , которое потом сжимается. На рис.5в,г,д, показан процесс укладки 3, 4, и 5-й магистралей.