close

Вход

Забыли?

вход по аккаунту

?

Алгоритм адаптивного размещения фрагментов топологии СБИС.

код для вставкиСкачать
Известия ТРТУ
Тематический выпуск
Для полученной математической формулировки задачи при m ≥ 3 не существует точных алгоритмов решения, а имеющиеся приближенные алгоритмы либо
осуществляют полный перебор всех возможных вариантов, либо с их помощью не
удается получить близкого к оптимальному решения.
Предлагается алгоритм получения субоптимальных расписаний, основанный
на субградиентной процедуре решения двойственной задачи. В основу которого
положена идея алгоритма Удзавы [1]. Предлагаемый алгоритм не гарантирует получение точного решения исходной задачи, так как в силу её целочисленности может иметь место “скачок двойственности”. Однако, получаемые субоптимальные
решения являются приемлемыми.
Созданный на основе предложенного алгоритма программный продукт использован в лаборатории ВГАУ.
ЛИТЕРАТУРА
1. 1. Uzawa H. Iterative methods for concave programming // Studies in linear and nonlinear
programming (Arrow, Hurvies, Uzawa etc.). - Stanford University Press, 1958.
УДК 681.1
А.В. Мухлаев
АЛГОРИТМ АДАПТИВНОГО РАЗМЕЩЕНИЯ ФРАГМЕНТОВ
ТОПОЛОГИИ СБИС
Целесообразным представляется некоторая оптимизация начального размещения для ячеек, содержащих ограниченное число подъячеек (до 1000) с помощью
итерационных алгоритмов переразмещения. При этом время работы САПР в расчете на одну такую ячейку увеличивается на 20%, а в общем объеме не более, чем
на 10%.
Во всех промышленно эксплуатируемых САПР используются итерационные
алгоритмы размещения, основанные на парных перестановках элементов. Однако,
λ-перестановочные алгоритмы дают более качественные результаты.
Отметим, что под λ-перестановочным алгоритмом будем понимать итерационный алгоритм, организующий одновременно перестановку λ-элементов с целью
повышения значения некоторого критерия. 3-перестановочные алгоритмы дают
хотя и лучшие, но близкие результаты к результатам 2-перестановочных алгоритмов. Однако, для реальных задач большой размерности λ>4 дает наилучший результат. Оптимальное значение λ лежит в пределах 3÷5. Очевидно, что наиболее
целесообразным было бы динамическое отслеживание величины. Такое отслеживание возможно путем применения методов альтернативной адаптации. Постановка задачи в этом случае будет следующей Пусть имеется 4 альтернативных алгоритма улучшения начального размещения Ai (λ=2, λ=3, λ=4, λ=5). Необходимо для
решения потока задач размещения Xl ,..., Xk динамически выбирать один из алгоритмов
Ai, чтобы обеспечить экстремизацию
m
∑F
k =1
k
→ max ,
m →∞
343
Материалы Международной конференции
Интеллектуальные САПР”
“
где Fk – показатель качества решения задачи.
Для решения поставленной задачи применим АА, описанный в разделе 2.1. так
же, как и там, АА представляет собой четверку A={A, S, B, F}.
Только множество действий АА будет моделировать в данном случае все четыре
λ-перестановочных алгоритма (λ = 2, 3, 4, 5).
Структуру алгоритма оптимизации результата размещения, рассчитанного на метод сечений, можно представить следующим образом:
1.
Формирование линий сечения.
2.
Счетчик итераций I=1.
3.
λ-перестановки элементов через линии сечений.
4.
Если цена сечений не уменьшается, то к п.5, иначе фиксация перестановки.
5.
Если I<N, то I=I+1 и к п.3.
Оценка АА результатов работы λ-перестановочного алгоритма и принятие ре6.
комендаций по величине λ на следующем шаге.
Как отмечалось выше, достоверное определение удачного (выигрыш) либо неудачного (проигрыш) применения текущей альтернативы – центральная проблема при
использовании предложенной методики взаимовлиянию задач друг на друга.
УДК 681.3.001
Э.Э. Малютина
ПОСТРОЕНИЕ АДАПТИВНЫХ СЕТОК С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО
АЛГОРИТМА
Работа посвящена разработке методов, основанных на использовании генетического алгоритма, для создания адаптивных сеток. Адаптивные сетки наиболее эффективно используются при исследовании задач, имеющих большие градиенты в узких
зонах: пограничных и внутренних слоях. Для решения таких задач необходимы методы
построения адаптивных сеток со сгущающимися узлами в зонах больших градиентов,
которые позволяют уменьшить осцилляции и погрешность численного алгоритма. При
решении нестационарных задач узлы сетки могут перемещаться с учетом движения
среды, позволяя таким образом получать более точные численные решения за счет более рационального распределения узлов сетки. В работе предложен генетический алгоритм, который, являясь эволюционным процессом, может быть использован для динамической адаптации сетки при решении нестационарных задач.
Рассматривается задача аппроксимации функции f(x), заданной на некотором
множестве D. На D задается разностная сетка {xi} i=0…N-1. Требуется найти расположение точек сетки {xi} при фиксированном N, наилучшим образом аппроксимирующих
функцию f(x) в смысле нормы
e =
где




∫(f
− f ) dx
2
D




∫
D
f 2 dx




1




1
2
2
~
f –кусочно-линейная аппроксимация f(x), заданная на сетке {xi}.
В качестве тестовой функции рассматривается функция вида
344
Документ
Категория
Без категории
Просмотров
3
Размер файла
80 Кб
Теги
сбис, размещения, алгоритм, адаптивного, фрагменты, топология
1/--страниц
Пожаловаться на содержимое документа