Основной задачей науки и техники является поиск оптимальных решений, т. е. оптимизация задачи. Большинство задач оптимизации относится к классу комбинаторных и, как правило, имеют множество решений различного качества [3]. В настоящее время созданы алгоритмы и описаны методы для решения различных оптимизационных задач, как для конкретных случаев, так и в общем виде. Эффективным методом решения оптимизационных задач являются генетические алгоритмы. При проектировании СБИС обычно решается стандартная задача. Элементы (вентили) расположены в рядах. Области между рядами (канал) используются для прокладки связей между элементами [2]. Отдельные элементы (вентили) и выводы в пределах элементов могут быть взаимно заменены без изменения функции элементов. Взаимно замена (перераспределение) вентилей и выводов может уменьшить общую длину цепей, число пересечений, конфликтов и т.п., что создает условия для получения лучших результатов при канальной трассировке [2,3,4]. Задача минимизации внутрисхемных пересечений фактически представляет собой задачу линейного размещения, и заключается в таком линейном расположении элементов дискретных устройств, при котором достигается требуемая характеристика устройства [1,2]. Под характеристикой можно понимать суммарную длину электрических цепей, соединяющих элементы, число пересечений электрических соединений, число электрических соединений, проходящих в каком-либо месте схемы, величину наиболее длинного соединения, суммарное время задержек электрических сигналов и т.п. [2,3,4].
Алгоритм перераспределения выводов построен на основе генетических эволюционных процедур. Для реализации этих процедур прежде всего нужно представить решение в закодированном виде, в виде хромосомы. При разработке структуры хромосомы необходимо учесть специфику задачи перераспределения выводов. Хромосома должна нести информацию об эквивалентных контактах, группах выводов, их взаимном расположении и взаимном расположении групп друг относительно друга. С другой стороны при разработке структуры хромосомы, необходимо учесть возможность применения к ним стандартных генетических операторов, а также возможность быстрого и эффективного декодирования, то есть построения по хромосоме решения [1].
В начале строится дерево И-ИЛИ на основе которого формируется базовый набор векторов (БНВ), включающий d*ij, cij, R и W. После этого, случайным образом формируется исходная популяция Пи размером М. Затем, на каждой из Т генераций выполняются следующие действия. Выбирается на основе селекции nk родительских пар хромосом и на каждой паре реализуется оператор кроссинговера. Полученная популяция Пк объединяется с Пи: Пт = Пи + Пк.
Затем на генах хромосом текущей популяции Пт реализуется оператор мутации. Полученное множество Пм новых индивидуальностей включается в Пт: Пт = Пи + Пк + Пм.
Для всех новых индивидуальностей Пк и Пм рассчитывается значение целевой функции.
На основании значений целевой функции осуществляется селекция и уменьшение популяции Пт до размеров исходной популяции Пи. Далее с вероятностью Рср осуществляется смена базового набора D , т.е. фактически смена популяции. Фиксируется лучшая индивидуальность.
Параметры Пк, Пм, М и Т являются управляющими и определяющими в некоторой степени эффективность генетического алгоритма. Хотя с другой стороны, их значения ограничиваются вычислительными ресурсами. Поскольку оценки временной сложности отдельных генетических процедур имеют вид О(NxM), то и общая оценка временной сложности алгоритма на одной генерации имеет вид О(N×М), а при выполнении Т генераций О(N×M×T). Если оставить один показатель N, то в зависимости от соотношения значений М и Т по отношению к N (М и Т как правило меньше N) оценка временной сложности колеблется в пределах О(N2) - O(N3) [1,2].
СПИСОК ЛИТЕРАТУРЫ: 1. Норенков И.П. Основы автоматизированного проектирования [Текст] / Норенков И.П - Москва: Изд-во МГТУ им. Баумана, 2000. -348 с.
2. Емельянов В.В. Теория и практика эволюционного моделирования [Текст] / Емельянов В.В., Курейчик В.М., Курейчик В.В. - М.: Физматлит, 2003. -412 с.
3. Лебедев Б. К. Интеллектуальные процедуры синтеза топологии СБИС [Текст] / Лебедев Б.К.Таганрог: Изд-во ТТИ ЮФУ, 2003. -108 с. Курейчик В.М., Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О.Адаптация на основе самообучения. Монография.[Текст] -Ростов-на-Дону: Изд-во РГАСХМ ГОУ, 2004-146с.
Библиографическая ссылка
Чернышев Ю.О., Апаева Л.Р. ОПТИМИЗАЦИЯ ЗАДАЧИ КАНАЛЬНОЙ ТРАССИРОВКИ НА ОСНОВЕ ГЕНЕТИЧЕСКИХ ЭВОЛЮЦИОННЫХ ПРОЦЕДУР // Современные наукоемкие технологии. – 2009. – № 6. – С. 22-23;URL: https://top-technologies.ru/ru/article/view?id=26461 (дата обращения: 23.11.2024).