Бионический подход к решению задачи расслоения соединений

Размещено на http://www.allbest.ru/

бионический подход к решению задачи расслоения соединений^{**Работа выполнена при поддержке РФФИ, грант № 07 - 01 - 00174 и программы развития научного потенциала высшей школы 2006-2008 гг. (РНП.2.1.2. 3193)}

Щеглов С.Н., к.т.н., доцент

Технологический Институт Южного

Федерального Университета

тел.: (8634)37-16-25, e-mail: leo@tsure.ru

ВВЕДЕНИЕ

бионический расслоение декодирование

Автоматизация проектирования - это многоаспектная, многоуровневая проблема, охватывающая исследование, разработку, производство и эксплуатацию технических, математических, программных и информационных средств [1].

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

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

Одной из важнейших задач конструкторского проектирования является задача размещения фрагментов цепей СБИС по слоям.

С ростом степени интеграции СБИС трудоемкость разработки и конструирования узлов резко возрастает. Проектирование электронных устройств с использованием БИС выдвинуло на передний край проблему эффективной реализации меж соединений на всех конструктивных уровнях.

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

Одним из подходов такой модернизации является моделирование эволюции, аппаратная поддержка баз знаний, интеллектуальный интерфейс и др. Интеллектуальные САПР должны адаптироваться к внешней среде и объекту проектирования, настраиваться на решаемую проблему и технологический процесс изготовления объекта с возможностью гибкой перестройки на другие объекты, методы проектирования, новые и смешанные технологии изготовления СБИС [2]. Именно такие принципы были использованы в данной работе при реализации алгоритма разнесения по слоям фрагментов цепей СБИС на основе моделирования эволюции.

1. ПОСТАНОВКА ЗАДАЧИ

Физическое проектирование, например мультикристальных модулей (МСМ), состоит из нескольких этапов. В данном случае рассматривается этап назначения слоев для последующей прокладки в них соответствующих соединений. Этот шаг определяет число пара-плоскостей необходимых для допустимой прокладки в них трассируемых соединений.

Как уже отмечалось, проблема назначения слоев имеет сложный комбинаторный характер (NP-complete), поэтому для ее решения требуются «хорошие» эвристики [3].

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

Определим структуру поставленной задачи в виде кортежа:

<X, D, Q>,

где

X = ?х₁, х₂, х₃,…?- пространство решений.

Причем х_i=?e₁, e₂, e₃,…e_m??

где e_i - множество цепей, расположенных в одном слое; m - количество слоев. D - ограничения, выделяющие в Х области, допустимые решения S Н X. В данном случае ограничением расположения цепей в одном слое является их пересечение. Определяется граф пересечений (несовместимости) Gp = (E, U), где множеству вершин E соответствует множество цепей, и две вершины из E соединяются ребром U только в том случае, если соответствующие им цепи пересекаются. Q:S®R+ - критерий оптимизации, где R+ - множество неотрицательных вещественных чисел. В рассматриваемой задаче критерием оптимизации является минимальное количество слоев L, необходимых для распределения заданных цепей. Тогда Q(x*)®min, где x*ОS.

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

На основе данной постановки задачи далее рассмотрим модифицированные генетические операторы решения задачи расслоения топологии.

2. СХЕМА БИОНИЧЕСКОГО ПОИСКА РЕШЕНИЯ ЗАДАЧИ РАССЛОЕНИЯ

Укрупненная схема бионического поиска задачи расслоения представлена на рисунке 1. Процесс расслоения соединений может происходить до, во время и после процесса трассировки соединений. Поэтому целесообразно произвести предварительный анализ исходных данных. Исходными данными являются список цепей, параметры конструкции элементов и коммутационного поля, либо совмещенная топология схемы. Поскольку список цепей определяет лишь группы эквипотенциальных выводов, основной задачей данного этапа является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочивание осуществляется с помощью алгоритмов построения минимально связывающих деревьев. Цель данного анализа получения графа пересечений (несовместимости), определение структуры хромосомы.

Далее строится текущая (начальная) популяция решений, т.е. определяется заданное подмножество х1, х2, х3,….,хm. Такое подмножество решений может быть получено случайным, направленным или случайно-направленным методами. При наличии большого количества соединений предпочтительными будут конструктивные и случайные алгоритмы для получения текущей популяции.

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

Сортировка популяции осуществляется следующим образом. Сначала расставляются элементы с наименьшим значением ЦФ и т.д. по возрастанию.

Рис. 1. Укрупненная схема бионического поиска задачи расслоения

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

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

Далее происходит построение новой популяции решений. Для каждой индивидуальности из новой популяции вычисляется ЦФ и выживают те элементы из старой и новой популяции, у которых ЦФ больше либо равно среднему значению, так чтобы количество элементов в новой популяции не превышало числа элементов в старой популяции.

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

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

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

Работа оператора кроссинговера основана на принципе обмена информацией между «родителями». У каждого родителя определяется слой, содержащий максимальное количество цепей. Затем происходит обмен данными между родителями, - выбранные слои переносятся от одного родителя к другому и наоборот. Цепи, перенесенные при переписывании слоев, исключаются из остальных слоев новой хромосомы.

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

Работа одноточечного оператора кроссинговера осуществляется следующим алгоритмом. Пусть S-длина хромосомы, Р(А), Р(В) - родительские хромосомы.

1. Получить случайным образом число К от 0 до S.

2. Определить в каком слое находится цепь гена К хромосомы Р(А).

3. Перейти в конец данного слоя.

4. Объявить ген конца слоя точкой кроссинговера.

5. Остаток хромосомы Р(В) перенести в хромосому Р(А).

6. Добавить недостающие и удалить дублирующиеся гены.

7. Получить хромосому Потомок 1

8. Повторить п.1-6 для хромосомы Р(В).

9. Полученная хромосома Потомок 2

10. Конец работы.

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

Операция мутации применяется к одной хромосоме и незначительно преобразует ее путем локальных случайных перемещений. Применение различных операторов мутации вносит существенные изменения в работу алгоритма распределения соединений по слоям, что в свою очередь сказывается на времени получения приемлемого решения задачи. Экспериментальные исследования показали, что удовлетворительные результаты дает применение оператора мутации известного в литературе как «Золотое сечение» [4].

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

Цель использования этих операторов - предотвращение единообразия во множестве решений. Сознательное ухудшение некоторых решений вносит новую информацию и является механизмом выхода из «локальных» ям [5].

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

ЗАКЛЮЧЕНИЕ

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

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

Временная сложность разработанного алгоритма в среднем составляет O(N2).

ЛИТЕРАТУРА

1. Норенков И.П. Основы автоматизированного проектирования. -М.: МГТУ имени Н.Э.Баумана, 2006.

2. Курейчик В.М. Методы генетического поиска. Под редакцией Курейчика В.М. - Таганрог: ТРТУ, 2002.

3. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. -М.: Физматлит, 2003.

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит, 2006.

5. Щеглов С.Н. Применение генетического поиска для решения задач расслоения // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008). Научное издание в 4-х томах. - М.: Физматлит, 2008. -Т.1. -С.67-73

Размещено на Allbest.ru