8769-1 (662916)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

Б. К. Лебедев

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. , (ij) [ _{i j} =0]

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

(ij _{i k} & _{j k}) [(O(l_j) O(l_i) O(r_j))((O(l_j) O(r_i) O(r_j))].

Подмножество _k пронумерованы и сформированы так, что все левые концы участков _k расположены левее левых концов участков _k+1, т.е. (ij _{i k} & _{j k+1}) [(O(l_i) < O(l_j) )].

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

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

S₁={21,31,11} ,S₂={32,4,12,22,5};

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

S₁={11,21,4,31}, S₂={22,32}, S₃={12,5}.

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

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

Для ОТ1: V₁=; V₂=.

Для ОТ2: V₁=; V₂=; V₃=.

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов реферата