Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

ОПТИМИЗАЦИЯ ЗАДАЧИ КАНАЛЬНОЙ ТРАССИРОВКИ НА ОСНОВЕ ГЕНЕТИЧЕСКИХ ЭВОЛЮЦИОННЫХ ПРОЦЕДУР

Чернышев Ю.О. Апаева Л.Р.

Основной задачей науки и техники является поиск оптимальных решений, т. е. оптимизация задачи. Большинство задач оптимизации относит­ся к классу комбинаторных и, как правило, имеют множество решений различного качества [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.10.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074