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

Посмотреть архив целиком

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

Б. К. Лебедев

Введение

Ввиду грандиозной сложности трассировка СБИС разбивается на два этапа: глобальная и детальная. При глобальной трассировке решается две задачи: разбиение коммутационного поля на области и распределение соединений по областям. Детальная трассировка заключается в проектировании топологии соединений внутри областей. Традиционно коммутационное поле разбивается на два типа областей: канал и коммутационный блок (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, S1S, и пусть S2 множество ДС, которые не могут быть реализованы без нарушений в ОТ, заполненной S1, S2S, S1S2=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=<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 двухтерминальных соединений, но отличаются порядком расположения элементов.

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

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

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

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

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

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


Случайные файлы

Файл
102810.rtf
176401.rtf
123183.rtf
59607.rtf
37832.doc




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.