Содержание к диссертации
Введение
1. Сравнительный анализ алгоритмов решения задачи анальной трассировки цепей различной ширины в сбис 12
1.1. Постановка задачи канальной трассировки цепей в сбис 12
1.2. Исследование бессеточного алгоритма канальной трассировки сбис 23
1.3. Анализ генетических методов 26
1.4. Применение алгоритмов адаптации в методах генетического поиска 36
1.5. Выводы 48
2. Разработка генетического алгоритма канальной рассировки цепей различной ширины в сбис 49
2.1. Постановка задачи 49
2.2. Целевая функция 51
2.3. Принципы кодирования и декодирования хромосом 53
2.4. Принцип создания массивов горизонтальных и вертикальных максимумов 57 2.5 оздание начальной популяции 59
2.6. Структурная схема генетического алгоритма 63
2.7. Модифицированные генетические операторы 67
2.8. Теоретические оценки алгоритм а 81
2.9. Выводы 83
3. Разработка генетического оператора на основе процедур даптации 84
3.1. Генетический оператор адаптации 84
3.2. Структурная схема алгоритма адаптации 86
3.3. Формирование объекта адаптации 88
3.4. Целевая функция 89
3.5. Модель объекта адаптации 91
3.6. Методика выработки управляющих сигналов 95
3.7. Пример работы оператора адаптации 99
3.8. Теоретические оценки оператора адаптации 104
3.9. Выводы 106
4. Разработка программной реализации и экспериментальное сследование разработанных алгоритмов 107
4.1. Цель экспериментального исследования 107
4.2. Описание работы с программой 108
4.3. Формат входного и выходного файла канала сбис 114
4.4. Этапы проведения экспериментальных исследований 117
4.5. Результаты экспериментальных исследований 119
4.6. Сравнение результатов исследования разработанных алгоритмов с результатами налогов 129
4.7. Выводы и рекомендации 130
Заключение 131
Литература 133
- Исследование бессеточного алгоритма канальной трассировки сбис
- Принцип создания массивов горизонтальных и вертикальных максимумов 57 2.5 оздание начальной популяции
- Методика выработки управляющих сигналов
- Сравнение результатов исследования разработанных алгоритмов с результатами налогов
Введение к работе
На сегодняшний день в мире производится огромное число электронных устройств, в которых задействованы различные микропроцессоры, память, преобразователи сигналов и т.д. Увеличивается тенденция к внедрению сложной техники в быт человека. Поэтому необходимо использовать различные комплексы и системы для автоматической разработки и производства этих устройств. Одной из основных единиц в производстве электронных устройств является сверхбольшая интегральная микросхема (СБИС). Современная САПР СБИС должна учитывать ряд критериев: увеличение производительности при возрастающих ограничениях при разработке и производства СБИС, время разработки СБИС, стоимость разработки. Такая система обеспечивает разработку мелкосерийных, «заказных» СБИС. Полученная интегральная схема может использовать биполярную технологию (более 500 элементов) или МДП-технологию (более 1000 элементов).
Важным этапом в САПР СБИС является конструкторское проектирование. Этот этап преобразует схемное представление СБИС в ее геометрическое представление. Каждой логической функции ставится в соответствие множество геометрических образов. Между некоторыми геометрическими образами могут быть проведены соединения. Соединение также представляют собой набор геометрических образов. Процесс проведения соединений между различными компонентами схемы называется трассировкой. Выделяют два основных уровня трассировки СБИС: глобальная и детальная. Глобальная трассировка занимается проведением соединений между отдельными областями СБИС. Детальная трассировка располагает соединения внутри каждой области СБИС. Области трассировки
СБИС делятся на область коммутационных блоков (от англ. switchbox) и область каналов.
Основная задача канальной трассировки формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости кристалла ограниченной верхней и нижней границе канала. Требуется реализовать заданные технические соединения с учетом заранее заданных ограничений. Основными являются ограничения на ширину проводников и минимальные расстояния между ними.
С наступлением эры субмикронных и нанометровых технологий (0,18 микрон и ниже) интегральные схемы стали работать на высоких частотах и потреблять больший ток и мощность при меньших напряжениях питания. Это привело к более яркому проявлению эффекта паразитной емкостной связи. Кроме того, масса других паразитных эффектов, которые можно было не учитывать в проектах предыдущего поколения, стали ключевыми факторами для обеспечения правильного функционирования и высокой производительности новых микросхем повышенной плотности. В современных условиях проблема взаимосвязи таких параметров, как скорость, потребляемая мощность, целостность сигналов и надёжность, стала столь же актуальной, как и проблема снижения площади кристалла для устройств предыдущего поколения.
Наиболее заметным из них является эффект паразитной емкостной связи между проводниками, приводящий к возникновению в них перекрёстных искажений. Кроме него, на целостность сигналов влияют:
шумы и задержки как следствие перекрёстных искажений;
падение напряжения на внутреннем активном сопротивлении;
электромиграция и плотность тока; индуктивность.
Перекрёстные искажения возникают из-за взаимной емкостной связи между проводниками микросхемы, в результате чего при изменении уровня
сигнала в проводнике форма сигнала в соседних проводниках также изменяется. Эти эффекты почти не проявлялись при использовании технологии с шириной проводников 0,5 мкм и больше. По мере повышения плотности схем и перехода к 0,25-мкм и меньше технологии, емкостная связь начинает расти вследствие сближения проводников и роста их относительной толщины.
Когда слишком высокая плотность тока воздействует на проводники в течение длительного времени, металл разрушается, что приводит к появлению обрывов и коротких замыканий и, как следствие, к отказу всего устройства. В результате, это может закончиться забракованием всей партии дорогостоящих микросхем. Разрушение проводника происходит в результате проявления электромиграции.
Индуктивные эффекты критичны для цепей с высокоскоростными или высокочастотными сигналами. Для длинных проводников, современные инструменты проектирования автоматически добавляют инверторы, чем достигается подавление этих эффектов. Лучший же способ заключается в том, чтобы осуществить такую стратегию канальной трассировки, которая устраняет потребность в подробном моделировании и анализе индуктивных эффектов.
Алгоритм канальной трассировки должен по возможности решить перечисленные выше проблемы. Дня этого используются различные методы моделирования, выявление несовместимых цепей на ранних стадиях проектирования, проведение цепей питания и заземления на небольшое количество сигнальных цепей. Канальный трассировщик представляет собой бессеточную (основанную на точных геометрических формах) систему автоматической трассировки, позволяющую изменять ширины проводников и зазоры между ними с целью подавления перекрёстных искажений. Он включает механизмы, позволяющие напрямую связать ограничения, направленные на снижение перекрёстных искажений, с весовыми оценками
качества трассировки и избежать влияния искажений на длительность фронтов и задержки в цепях.
Проблема канальной трассировки является NP-полной [1] и в настоящее время не существует радикального метода, гарантирующего нахождение глобально оптимального решения. Существующие детерминированные алгоритмы хоть и обеспечивают высокую точность получаемых решений, однако для получения этого результата необходимо очень много времени. Такие алгоритмы используются при небольшой размерности задачи.
Одним из новых направлений поисковых методов являются методы генетического поиска. Они базируются на моделировании естественного процесса эволюции для поиска оптимального решения [2]. Существуют четыре основных модели эволюционных алгоритмов: генетические алгоритмы (Holland, 1975), генетическое программирование, эволюционное программирование (Fogel, 1966) и эволюционные стратегии (Rechenberg, 1973). В генетическом алгоритме (ГА) решению соответствует хромосома. Она оценивается целевой функцией (fitness). Важное значение придается кодированию решения в хромосому и разработке целевой функции. Основными механизмами трансформации решения являются операторы кроссинговера и мутации. Существует множество различных операторов как стандартных (побитовое скрещивание, изменение одного гена), так и специальных, созданных только для конкретного алгоритма, и только для конкретной структуры хромосомы. В кроссинговере новое решение образуется из нескольких старых. В мутации существующее решение может случайно преобразовано. Таким образом, из полученной новой популяции решений на основе селекции могут быть отобраны лучшие решения в следующее поколение. Весь метод моделирует естественный процесс эволюции в достижения оптимума.
Основное отличие ГА от других оптимизационных методов состоит в том, что они оперируют целым множеством решений. Используется целевая функция, а не детерминированная оценка решения. Для модификаций решений и последующей селекции используются вероятностные модели.
Разработан генетический оператор адаптации, использующий методы адаптации. Оператор адаптации использует способность технических систем изменять свое состояние в зависимости от изменений внешней среды, путем накопление информации о ней. В результате его работы, в хромосому помещаются только те варианты размещения цепей, ЦФ которых была оптимальная, в течении нескольких итераций. Оператор адаптации использует методы альтернативной адаптации. Объектом адаптации является цепь в канале СБИС.
Таким образом, учитывая все вышеизложенное, тема диссертационного исследования, связанная с разработкой новых алгоритмов решения задачи канальной трассировки цепей различной ширины в СБИС, является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является разработка комплекса алгоритмов канальной трассировки цепей различной ширины, позволяющего получить решение канала с наименее возможной длиной цепей и минимизированной площадью канала.
Для достижения поставленной цели были поставлены и решены следующие задачи:
Разработка комплекса алгоритмов для решения задачи канальной трассировки.
Создание модифицированных генетических операторов и процедур (кроссинговер, мутация, селекция, сегрегация).
Построение алгоритма формирования начальной популяции.
Разработка и исследование нового генетического оператора на основе процедур адаптации.
Создание структуры и принципов кодирования и декодирования хромосомы.
Разработка процедуры оценки и качества (целевой функции).
Для решения поставленных задач используют следующие МЕТОДЫ ИССЛЕДОВАНИЙ; элементы теории множеств, элементы теории алгоритмов, элементы теории эволюционного моделирования.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
Разработке комплекса алгоритмов решения задачи канальной трассировки цепей различной ширины в СБИС, использующего методы эволюционного моделирования.
Создании новых структур и принципов кодирования и декодирования решений для задачи канальной трассировки.
Создании модифицированного алгоритма формирования начальной популяции.
Разработке нового генетического оператора на основе процедур адаптации.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
1. Структура и принцип представления информации для генетического
алгоритма канальной трассировки СБИС.
2. Алгоритмы и программное обеспечение для решения задачи
канальной трассировки СБИС, которые позволяют уменьшить длину
соединительных проводников в канале и площадь канала СБИС.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.
Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».
Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
Результаты работы внедрены в НИИ ТКБ ТРТУ по научно-исследовательской работе №710/98-16002-7 «Участие в разработке технических предложений по созданию РИС и алгоритмов ее функционирования».
АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международной научно-технической конференции «Интеллектуальные САПР — 98», (г. Геленджик, 1998г,) Сорок шестой студенческой научной конференции (г. Таганрог, 1999г.), Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 2000г.), Четвертой всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2001г.)
ПУБЛИКАЦИИ. Результаты диссертации отражены в 7 печатных работах. Запатентовано 1 авторское свидетельство для программ ЭВМ «Программа генетической трассировки цепей в канальной области СБИС (ПГТК)»
СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 стр., включая 60 рис., 13 таб., список литературы из 105 наименований, 5 стр. приложений и актов об использовании.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ приведена постановка задачи канальной трассировки цепей различной ширины. Рассмотрены основные алгоритмы решения задачи канальной трассировки в СБИС. Выявлены их достоинства и недостатки. Описаны методы генетического поиска, основные генетические операторы, их отличие от других оптимизационных и поисковых методов. Рассмотрен эволюционный алгоритм адаптации.
ВО ВТОРОЙ ГЛАВЕ описан комплекс алгоритмов для решения задачи канальной трассировки СБИС. Приведена структурная схема генетического алгоритма. Показана структура и принципы представления информации для генетического алгоритма. Разработаны алгоритм формирования начальной популяции, целевая функция качества получаемых решений, модифицированные генетические операторы, теоретическая оценка алгоритма.
В ТРЕТЬЕЙ ГЛАВЕ приведена реализация алгоритма адаптации в общей схеме генетического поиска. Описаны структура и назначения автоматов адаптации, методика выработки управляющих сигналов. Показана структурная схема генетического алгоритма с алгоритмом адаптации в качестве одного из генетических операторов.
В ЧЕТВЕРТОЙ ГЛАВЕ описаны основные функции программы генетического алгоритма канальной трассировки. Поставлены цели экспериментального исследования. Определены оптимальные параметры, управляющие генетическим поиском. Произведена экспериментальная оценка пространственной и временной сложности алгоритма. Полученные оценки позволили подтвердить полученные ранее теоретические оценки ВСА и ПСА. Выполнено сравнение результатов работы разработанного алгоритма канальной трассировки СБИС с известными аналогами. Приведено описание
программного обеспечения для создания, решения и исследования различных каналов СБИС.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложении даны копии свидетельства о регистрации программы, актов об использовании, графический интерфейс программного обеспечения, примеры решения задачи канальной трассировки цепей с одинаковой и разной шириной цепи.
Исследование бессеточного алгоритма канальной трассировки сбис
Алгоритм бессеточной канальной трассировки СБИС [5] основан на двух методах - графовый алгоритм и алгоритм расширения по блокам. Графовый алгоритм для двух слоев уже были разработаны [6]. Существуют разнообразные его модификации [13, 14, 28]. Представлен эффективный, комбинированный, графовый алгоритм для нескольких слоев и также рабочий алгоритм разрыва и перетрассировки. Этот алгоритм позволяет улучшать результаты существующих решений трассировки [5].
Графовый алгоритм использует простой граф ограничений для промежутков между компонентами слоев, но его применение не дает эффективную информацию о свободном пространстве на горизонтальном или вертикальном слоях. Тем не менее, эта информация необходима для генерации полезных зигзагов (dogleg) и ответвлений (overshoots). Для очень плотных каналов, замечено, что ответвления, зигзаги и неограниченное число слоев проводников в схеме дают полезные решения. Многие алгоритмы эффективно используют dogled bi, такие как символьный трассировщик YACR2 [27,41], лабиринтный алгоритм разрыва и перетрассировки MIGHTY [44], Mulch [45], Chameleon [54], и жадные трассировщики [55]. Тем не менее, эти трассировщики также не могут оперировать с произвольным числом слоев или не могут изменять ширину проводников.
Двухслойный трассировщик [56] использует один блок размещения для представления двухслойной схемы. Лабиринтный алгоритм использует зарезервированную модель проведения проводников в слоях, и только допускает расширение в ортогональных направлениях.
Тем не менее, это осуществляет А алгоритм [6]. Он является поисковым лабиринтным алгоритмом эффективным во времени и гарантирует нахождение оптимального решения в соответствии с весовой функцией [57]. Далее осуществляется многослойное расширение по блокам в канале, основанное на А алгоритме.
Бессеточный алгоритм использует неограниченное количество слоев. В каждом слое проводники распространяются в ортогональном направлении в соответствии с назначением слоя (вертикальное или горизонтальное распространение проводников). Алгоритм использует специальную технологию называемой двойные блоки размещения (dual tile plane). ДБР, которая конструирует простые изменения координат горизонтальных полос, имеет преимущество в быстроте и симметричности горизонтальных и вертикальных расширений. Также используется модель перекрытий блоков расширений, которая позволяет пути расширения перекрывать существующие цепи. Эффективный многослойный алгоритм разрыва и перетрассировки является основой модели расширения. Предварительная топология берется из решения полученного графовым алгоритмом, и затем оптимизируется алгоритмом разрыва и перетрассировки. Далее метод расширения по блокам генерирует необходимые зигзаги во второй части алгоритма трассировки.
Метод расширения по блокам эффективно осуществляет одноразмерное сжатие, минимизируя число переходов и смещений проводников [75]. Накладывание штрафов на создание переходов, в лабиринтной трассировки, позволяет значительно уменьшить количество переходов. Угловые стяжки блоков позволяют эффективно манипулировать фрагментами компонентов в схеме поисковым алгоритмом. Таким образом быстрый алгоритм смещения проводников осуществлен в алгоритме расширения по блокам.
В итоге, бессеточный алгоритм, предложенный в [5], условно можно разбить на несколько этапов. Первый этап: графовый метод, управляет назначением межслойных переходов и горизонтальных проводников в слои. Во второй части, алгоритм назначения ребер, применяется для минимизации самого длинного пути в графе ограничений. На третьем этапе, графовый алгоритм разрыва и перетрассировки проводников используется для уменьшения самого длинного пути в графе.
Достоинство алгоритма заключается в использовании многослойной модели трассировки проводников разной ширины в канальной области СБИС. Недостаток алгоритма заключается в повышенной пространственной и временной сложности: бессеточный алгоритм, разработанный Hsiao-Ping Tseng и Carl Sechen, является совокупностью нескольких алгоритмов (графовый, лабиринтный, разрыва и перетрассировки). Временная сложность бессеточного алгоритма определяется как сумма составляющих ВСА. Пространственная сложность алгоритма пропорциональна числу цепей в канале О(п). Временная сложность бессеточного алгоритма 0(п3).
Принцип создания массивов горизонтальных и вертикальных максимумов 57 2.5 оздание начальной популяции
Начальная популяция формируется из хромосом, созданных на основе волнового алгоритма Ли [3], адаптированного к рассматриваемой проблеме. Модификация этого алгоритма представляет собой развитие алгоритмов построения кратчайших путей в сети и позволяет находить маршруты соединений, оптимальные по ряду параметров [4,7].
Модифицированный волновой алгоритм, примененный в данной работе, позволяет сгенерировать множество разнообразных решений. Обладает высокой степенью общности, прост в реализации и имеет широкий спектр применимости для трассировки двухслойных, многослойных печатных плат, БИС и т.д. Он основан на "просмотре" возможных вариантов решений и выборе из них одного, удовлетворяющего требованиям поставленной задачи.
Решение задачи с использованием волнового алгоритма предполагает два этапа: на первом осуществляется поиск возможных решений -распространение волны, на втором выбирается решение, удовлетворяющее условиям поставленной задачи - построение обратного следа.
Модель поля платы для трассировки представляется совокупностью ячеек. Все множество ячеек модели D разделяются на два подмножества D и D". Подмножество D объединяет в себе те ячейки модели, которые допустимо использовать для прокладки через них печатных проводников. Подмножество D" состоит из ячеек, через которые недопустима прокладка трасс.
Описание модифицированного волнового алгоритма для решения задачи канальной трассировки. 1. Пусть S= {$1,52,.-,5 } будет множество несоединенных выводов канала, a T = {tj, tj,..-,t\}- множество всех выводов, имеющих, по крайней мере, одну связь с другим одноименным выводом. На первом шаге работы алгоритма Т[=0. Вывод S; є S выбирается случайно среди всех элементов из S (в данном случае элемент s; является источником, a t j - приемником). Если Т содержит выводы {tu,..., tj,..-, tv) той же цепи, тогда вывод t: среди них выбирается также случайным образом. В противном случае второй вывод той же цепи произвольно выбирается из S и передается в Т. Задача проведения трасс сводится к получению последовательностисоответствуют выводам одной цепи. 2. Модель рабочего дискретного поля преобразованного из хромосомы имеет вид двух матрицы (рис. 2.7). Ячейки, помеченные знаком "х" относятся к подмножеству D" и запрещены для распространения волны. Ячейки, помеченные знаком "О " относятся к подмножеству D и разрешены для распространения волны. На начальном этапе количество магистралей (строк в матрице), полагается равным количеству цепей. Далее алгоритм может удалять магистрали, если они не содержат горизонтальных участков. Алгоритм добавляет магистрали, если фронт волны распространять дальше уже нельзя, а ячейка-приемник не встретился (т.е. цепь осталась не оттрассированной). 3. В модели рабочего поля моделируется распространение волны из "источника" Sj, до тех пор, пока фронт волны не достигнет "приемника" tj или пока на шаге к фронт волны не сможет включить ни одной незанятой ячейки. Отметим, что волна распространяется по свободным ячейкам. При распространении волны алгоритм последовательно шаг за шагом строит 1-й фронт, 2-й фронт,..., k-Vi фронт источника. Шаг распространения волны равен единице. При переходе на другой слой фронт также увеличивается на единицу. м\ = Рис. 2.9. Решение канала а) до распространения волны и б) после распространения волны и проведения проводника для цепи №2
Процесс построения нового фронта начинается с присваивания ячейке, соседней с ячейками предыдущего фронта, номера фронта на единицу больший. На рисунке 2.8. показано распространение волны для цепи №2. Таким образом, четвертый фронт волны встретил приемник t j.
Для варианта VH-топологии, с учетом введенных ограничений на расположение горизонтальных отрезков цепей в нижнем слое, а вертикальных - в верхнем. В каждом слое задается приоритетное направление проведения пути из приемника к источнику. В нижнем слое: влево, вправо; в верхнем слое: вверх, вниз. Таким образом, в матрице Ml волна будет распространяться только в горизонтальном направлении, а в М2 только в вертикальном.
В случае если невозможно провести к+1 фронт волны и к фронт волны не достиг ячейки приемника, то тогда модель рабочего дискретного поля увеличивается на одну строку произвольной строке yadd при условии: I yadd Уы (yind - число строк в матрице М1,М2). Далее происходит обнуление фронта волны и переход к пункту 3.
Если же 10 расширений канала также не обеспечивают соединения, то модель трассировочного поля обнуляется и процесс продолжается снова с выбора случайным образом трассируемых выводов, т.е. переход к пункту 1. 4. Далее происходит построение обратного следа от приемника tj к источнику Sj. Затем Sj передается в Т. Процесс продолжается со следующим произвольным выбором sj є S, пока S не окажется пустым (S = 0). Рассмотрим пример распространения волны для двух выводов цепи №2. На рисунке 2.9(a) изображена топология канала до трассировки цепи №2. Модель дискретного рабочего поля представлена на рисунке 2.7. Необходимо соединить источник s и приемник t. В хромосоме источнику S соответствует ген сізо, а приемнику t соответствует ген 6 60.
Методика выработки управляющих сигналов
Этими группами состояний определяется действие алгоритма по отношению к цепи. Совокупность всех состояний автоматов определяет действие алгоритма на данной итерации.
С3 - промежуточное состояние Sj=0, алгоритм подкидывает монету чтобы определить в каком из состояний он сейчас окажется, причем эта вероятность зависит от целевой функции цепи gj. Ниже описан подробный механизм перехода из состояния С .
Глубина автомата. Определяет количество состояний автомата. Глубина автомата имеет большое значение. Для цепей большой размерности (многотерминальных), необходимо быть твердо уверенным, прежде чем проводить какие-либо манипуляции с ней. Может сложиться такая ситуация, что на первых итерациях алгоритма цепь будет иметь неустойчивое состояние, а на следующей сделает минимальный скачок к улучшению. Но при этом глобального оптимума не достигнет. В этом случае автомат с малой инерционностью оставит ее неизменной на следующих итерациях, тогда как необходимо новое размещение этой цепи. Но всегда существует противоположная опасность: как только найдется оптимальное решение, на следующей итерации алгоритм уничтожит его, создав новое в соответствии с состоянием АА.
Опытным путем была определена оптимальная глубина автомата, формула (3.4). Чем больше Q, тем сильнее инерционность автомата, ибо тем более последовательность действий вынуждает его к смене действий. Глубина автомата напрямую зависит от размерности самой. Для нашего примера (рис. 3.3), АА цепи №1 имеет глубину 5, а автоматы для цепей №2 и №3 имею глубину 4, рисунок 3.4. Если имеется цепь с большим количеством выводов, то и соответствующая глубина автомата будет большой, для того чтобы эта цепь, выбрав наилучшее размещение в канале, могла оставаться в нем как можно дольше. Для усиления способности выхода из локальных оптимумов при работе адаптивной системы автомат адаптации модернизирован введением вероятностных механизмов перехода из одной группы состояний в другую. На рисунке 3.5 представлен граф-схема такого автомата адаптации.
Если АА очутится в неопределенном состоянии С3, то выйти из него он может в соответствии с параметром Р. Таким образом, в автомате адаптации при переходе из групп С вС и из С вС используются детерминированные переходы, а из С3 в С2 и С1 - вероятностные. При выходе из С АА попадет в группу С с вероятностью Р, а в группу С с вероятностью (1-Р). Метод определения параметра Р заключатся в следующем: Пусть а — число негативных изменений ЦФ цепи (случаи когда AF =0), а /3 - число положительных изменений (AF 0), тогда: ф Следовательно, при случае, когда OF=1 и /3=9, р-0,1 и автомат а; будет иметь больше шансов оставить цепь g; в таком же нетронутом виде. При переходе из С в С2 или С1, счетчики а и /3 не обнуляются. При случайном единичном переходе алгоритм будет иметь шанс вернуться к наилучшему варианту
Процесс выработки управляющих сигналов выглядит следующим образом. Для каждой итерации рассматривается предыдущее состояние автоматов S. Если итерация первая, то предыдущим будет начальное состояние, которое определяется произвольным образом. Далее берется по порядку цепи, начиная с первой, и для нее алгоритм пытается найти лучшее расположение с учетом удаления тех цепей gj, у которые состояние S; 0 (т.е. у них невыгодная топология). И фиксирование тех цепей у которых S-, 0. lit При этом учитываются глубина автомата Q;, предыдущая целевая функция цепи FBAK, и случайная величина є (необходимая для перехода из промежуточного состояния, для перехода в другую группу состояний). На рисунке 3.7 показан псевдокод методики формирования управляющих сигналов и вычисление новых состояний автоматов, для одной итерации алгоритма адаптации. Изображенный на рисунке 3.7 алгоритм расчета управляющих сигналов работает на каждой итерации поочередно для каждой цепи gj. V Текущая рассматриваемая цепь обозначается как gcUr, и соответствующий ей автомат Seur. Обозначим через FBAKi целевую функцию каждой цепи автомата адаптации на текущем этапе. Далее производится попытка найти лучшее решение для этой цепи посредством удаления цепи gcUr, а также удаление всех цепей, у которых Si 0, и фиксирование остальных цепей для которых S; 0. Псевдокод этого процесса: удалить (gj : {S; 0}, i=l,2...n, i cur); фиксировать (gj: {Sj 0}, i=l,2.. лі, i cur) ; Далее в частично заполненном канале, находится новое размещение цепи gcur и дотрассировка остальных цепей: новое_размещеные( тУг дотрассировка_цепей(,\: i=l,2...n, i cur); i=l; // счетчик автоматов
Если AF 0, т.е. целевая функция улучшилась (найдено более лучшее размещение для цепи), то тогда управл_сигнал-{+1}; Эта процедура повторяется для всех автоматов в адаптивной системе. В связи с этим состояние автомата может перейти из какой-либо группы состояний (С, С ) в промежуточное состояние, когда Scur—0. Т.к. автомат не может находиться в этом состоянии (для этого состояния не определено соответствующее действие алгоритма), то алгоритм должен сделать выбор в сторону одной из групп. Разумно сделать этот выбор на основании полученной информации о сделанных изменениях в топологии канала, а конкретно на изменении целевой функции AF (1), текущей цепи gcur. Это изменение фактически является математическим ожиданием ЦФ. И оно показывает в процентном отношении количественное изменение ЦФ. Для того чтобы исключить f однообразные варианты размещения цепи, приводящие к локальному оптимуму, применим вероятностную схему для выхода из промежуточного состояния. Для этого введем равновероятную величину є, в пределах от 0 до 1. Параметр є в программе можно устанавливать от 0 до любой нужной
Сравнение результатов исследования разработанных алгоритмов с результатами налогов
Производительность алгоритма была проверена на различных тестовых ь каналах. Полученные результаты представлены в таблице 4.7. Сравнение проводились для тестовых каналов Burshtein [26, 68] и Joobl6 [6, 7]. Видно, что результаты рассмотренного алгоритма (GA_ROUTV) либо такие же, либо лучше известных результатов популярных алгоритмов канальной трассировки: волновой алгоритм, алгоритм Mighty и другие [5, 27, 42,44],
Программа формирует файл, содержащий накопительную информацию о решаемых каналах. В ходе работы алгоритма включается таймер, который засекает время работы. Полученные таким образом, данные позволяют 4f определить время работы алгоритма для различных типов каналов. Приведем время выполнения некоторых тестовых каналов при этих параметрах:
Были проведены экспериментальные исследования для генетического алгоритма канальной трассировки. Как видно из графиков (рисунки 12-14), комплекс алгоритмов имеет квадратичную зависимость 0(N) времени решения от числа выводов в канале СБИС. Несмотря на то, что эксперименты проводились в одних и тех же неизменяемых условиях (параметры генетических операторов, число итераций, размер популяции), время решения задачи получались, на канале с одинаковым числом цепей и числом выводов, весьма далекие друг от друга. Это объясняется различной сложностью самого эскиза топологии канала (рис. 4.8). Поэтому график - строится исходя из среднего арифметического значения времени затраченного на трассировку канала. Получить более правдоподобные результаты позволяет увеличение числа экспериментов. 1. "
Сформулированы цели выполнения экспериментальных исследований предложенного комплекса алгоритмов. Определены параметры алгоритмов и этапы проведения экспериментов. Собранные данные позволили определить временную сложность для каждого из алгоритмов. Проведенные исследования показали пригодность к прикладному применению алгоритма и программы канальной трассировки цепей различной ширины в СБИС. 2.
Разработанная программа канальной трассировки цепей различной ширины в СБИС позволяет исследовать эффективность предложенного комплекса алгоритмов. Модифицированный волновой алгоритм Ли позволяет быстро сгенерировать начальную популяцию разнообразных решений. Оператор адаптации дает оптимальные решения на основе процедур адаптации. Алгоритм имеет квадратичную зависимость 0(N) времени решения от числа выводов канала. 3. Экспериментальное исследование стандартных каналов показывает, что результаты данного алгоритма в некоторых случаях равны или лучше опубликованных результатов других популярных алгоритмов. В ходе выполнения диссертационной работе были осуществлены ряд научных и практических приложений:
1. Представлен анализ существующих алгоритмов решения задачи канальной трассировки цепей различной ширины в СБИС. Выявлены основные достоинства и недостатки существующих алгоритмов. Отмечены перспективные для исследований методы и алгоритмы эволюционного моделирования, в частности методы генетического поиска. На основе проведенного анализа предложен и обоснован поиск на основе генетических алгоритмов и эволюционной адаптации для решения задачи канальной V трассировки СБИС. 2. Разработан комплекс алгоритмов канальной трассировки, на основе применения методов генетического поиска и алгоритмов адаптации. Генетический алгоритм основан на проблемно-специфическом представлении схемы и проблемно-ориентированных генетических операторах. Создан генетический оператор на основе процедур адаптации. Он использует несколько видов автоматов адаптации, такие как автомат с линейной тактикой, «осторожный» и «доверчивый» автоматы. Оператор Т создает решения по отличной от других генетических операторов схеме, тем самым, увеличивая разнообразие генотипа в генетическом алгоритме. 3. Создана новая методика кодирования решений. Она учитывает специфику решаемой задачи, и позволяет отбросить большое количество "нереальных" решений. Применение новых принципов кодирования позволяет улучшить качество получаемых решений и уменьшить время 4t работы алгоритма. Определены генетические операторы, схема генетического алгоритма. 4. Применение волнового алгоритма при формировании начальных популяций позволило получить множество разнообразных решений.
Определена теоретическая и экспериментальная оценки временной сложности алгоритма формирования начальной популяции. Она составляет 0(N2), где N - число выводов в канале. Разработана целевая функция для оценки пригодности решения. Она учитывает длину проводников цепей, количество межслойных переходов, габаритные размеры канала СБИС. Созданы модифицированные генетические операторы, позволяющие улучшить решения на 10-30% по сравнению с начальными решениями, формируемыми волновым алгоритмом. Определены ВС А каждого генетического оператора, они пропорциональны 0(N2). 5. Использование параллельных стратегий выполнения генетического алгоритма с применением оператора миграции позволило: усовершенствовать качество решения, уменьшить вероятность попадания в локальный оптимум, сократить время решения задачи. 6. Для реализации предложенного комплекса алгоритмов было разработано программное обеспечение. При разработке программы канальной трассировки СБИС
