Б. К. Лебедев
Введение
Ввиду грандиозной сложности трассировка СБИС разбивается на два этапа: глобальная и детальная. При глобальной трассировке решается две задачи: разбиение коммутационного поля на области и распределение соединений по областям. Детальная трассировка заключается в проектировании топологии соединений внутри областей. Традиционно коммутационное поле разбивается на два типа областей: канал и коммутационный блок (switchbox).
В классической постановке коммутационный блок - это прямоугольная область на всех четырех сторонах которой размещены в фиксированных позициях терминалы (выводы). Терминалы помечены цифрами - номерами подключенных к ним цепей. Задача состоит в том чтобы сделать терминалы каждой цепи электрически связными так, чтобы цепи и переходные отверстия, реализующие связи, вписывались в область трассировки и удовлетворяли конструктивным ограничениям.
Обычно проблема решается с дополнительно наложенными ограничениями, одним из которых является число слоев. В работе рассматривается двухслойная трассировка.
Задача трассировки в ограниченной прямоугольной области является 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 число нереализованных ДС.
Очень интересно - Доклад: Размер имеет значение или история форм-факторов HDD
В случае полной реализации цепей, т.е. при 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.