<<
>>

Поиск на основе коллективной адаптации при планировании СБИС с изменяющимися размерами модулей

Рассмотрим второй подход к построению плана, связанный с возможностью изменения размеров модулей в соответствии с ограничениями (6.1)-(6.3).

При втором подходе решение полностью определяется де­ревом разрезов Dи массивом размеров областей G = {gi | i = = 1,2,...,n}, где gi = (Xi,yi).

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

Объект адаптации и среда — те же самые, что и при первом подходе.

Параметры и методика оценки состояния объекта адаптации аналогичны рассмотренным выше, т. е. состояние объекта адап­тации в среде определяется парой

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

Поведение объекта адаптации в среде регламентируется тре­мя альтернативами:

При задании альтернативы Ai1у модуля miуменьшается hiи соответственно увеличивается wi,при этом должны соблюдаться ограниченияЗадается пара­

метр δ изменения размера модуля. Новые значения h* и w* при реализации альтернативы Ai1, определяются следующим образом:

В соответствии с заданными ограничениями необходимо, чтобы

После подстановки

≤ ti. Следовательно, параметр δ должен удовлетворять неравен- с

В этом случае параметр δ должен удовлетворять неравенству

Это делается для того, чтобы изменения габа­ритных размеров модуля (увеличение или уменьшение) было не более, чем на величину δ.

При задании альтернативы A3у модуля miувеличивается hi и соответственно уменьшается wi:

При задании альтернативы A2размеры модуля остаются неизменными.

Для реализации механизма адаптации каждому модулю mi ставится в соответствие автомат адаптации AAiс тремя группа­ми состояний {C1, C2, C3},соответствующих трем альтернати­вам Ai1, A2, A3(рис. 6.8).

Рис. 6.8. Автомат адаптации с тремя группами состояний

Механизм выработки управляющего сигнала («поощрение» или «наказание») основан на следующих соображениях.

Если один из параметров пары (Pχ, Py)равен единице, то целесообразно уменьшить либо wi(для случая (1,0)), либо hi (для случая (0, 1)). Если AAiнаходятся в той группе состо­яний, которой соответствует альтернатива, предусматривающая подобное уменьшение, то вырабатывается сигнал «поощрение», в противном случае — сигнал «наказание».

Если пара имеет вид (1,1), то независимо от того, в какой группе состояний находится AAi, вырабатывается с вероятно­стью P = 0 ÷ 0,2 сигнал «наказание». Параметр P является из­меняемым и может быть подобран в результате эксперименталь­ных исследований. Вероятностная выработка сигнала «наказа­ние» для случая, когда пара имеет вид (1, 1), предназначена для выхода из локального оптимума.

Если пара имеет вид (0,0) и AAiнаходится в группе Ci2, то вырабатывается сигнал «поощрение», в противном случае — сигнал «наказание».

Переходы AAiиз группы Ci2в группу Ci1или Ci3осуществля­ются следующим образом. Сначала при выходе из группы состоя­ний Ci2автомат адаптации переходит в промежуточное состояние Zi. За время нахождения AAiв группе C2подсчитывается число наказаний αi,полученных приа также общее число

наказаний βi.

Тогда после перехода иг i_ сразу же с вероятностью осуществляется переход вас вероятностью 1 — P — переход в Ci3.

В табл. 6.2 приведены правила выработки управляющих сиг­налов.

Таблица 6.2

Локальная цель объекта адаптации (модуля mi)— достичь состояния, при котором оценивающая двойка имеет вид (1,1), т. е. такого состояния, когда размеры (wi, hi) модуля miсовпада­ют с размерами (xi, yi)области ri,в которую помещен mi.

Глобальная цель коллектива — достичь состояния с мини­мальным значением критерия F.

Работа адаптивной системы на каждой итерации осуществ­ляется за четыре такта.

На первом такте для каждого объекта определяются значения двойки (Pχ, Py).

На втором такте вырабатываются управляющие сигналы («поощрение», «наказание»).

На третьем такте осуществляются переходы в автоматах адаптации под действием управляющих сигналов.

На четвертом такте реализуются альтернативы, соответству­ющие состояниям автоматов адаптации. Изменяются размеры отдельных модулей. Далее с помощью свертки строится план.

Определяются выражения для размеров wo и ho и размеры всех областей. Рассчитывается значение Fдля нового решения.

Приведем псевдокод алгоритма работы адаптивной системы планирования кристалла СБИС с изменяющимися размерами модулей.

Algorithm планирование_кристалла сбис

с изменяющимися размерами модулей begin

параметры = ИСХОДНЫЕ_ДАННЫЕ;

дерево = ГЕНЕРАЦИЯ (парметры); размеры = 0ПРЕДЕЛ_НАЧ_ЗНАЧЕН (параметры);

план = СВЕРТКА (дерево, размеры, параметры); состоян_аа = ВЫБОР_НАЧ_СОСТОЯН (параметры); итерация = ЧИСЛО_ИТЕРАЦИЙ;

while (итерация > 0) do

{ состоян_объект = ОЦЕНКА (план, параметры); управл_сигнал = УПРАВЛ (состоян_объект, ориент); состоян_аа = ПЕРЕХОД (состоян_аа, управл_сигнал); размер = РЕАЛ_АЛЬТЕРНАТИВ (состоян_аа);

план =СВЕРТКА (дерево, размеры, параметры); итерация = итерация_1;

};

end

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

C помощью процедуры ОПРЕДЕЛ_НАЧ_ЗНАЧ (параметры) определяются начальные значения размеров модулей, которые заносятся в массив размеры.

Возможны два режима. Либо размеры всех модулей выбира­ются случайно с соблюдением всех ограничений из (1-3), либо размеры у всех модулей выбираются так, чтобы wi= hi.

Процедурой ВЫБОР_НАЧ_СОСТОЯН (параметры) синтези­руются автоматы адаптации, затем каждый из них приводится в начальное состояние.

Возможны два режима. При первом режиме автоматы при­водятся в первое состояние группы Ci2. При втором режиме — в первое состояние любой из групп Ci1, Ci2, Ci3.

Процедура РЕАЛ_АЛЬТЕРНАТИВ (состоян_аа) реализует альтернативы, соответствующие состояниям автоматов адапта­ции и заносит скорректированные размеры модулей в массив размеры.

Остальные процедуры функционально не отличаются от одно­именных процедур, рассмотренных в псевдокоде алгоритма пла­нирования кристалла СБИС с меняющейся ориентацией модулей.

Экспериментальные исследования приведенного алгоритма показали, что качество решения зависит от параметра δ. Целесо­образно использовать переменное значение δ(t), уменьшающееся в процессе работы адаптивной системы.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Поиск на основе коллективной адаптации при планировании СБИС с изменяющимися размерами модулей:

  1. Определение секущих модулей и коэффициентов поперечных деформаций при отсутствии трещин
  2. § 3. Обеспечение законности при выборе вида и размера административного наказания как способ защиты прав граждан
  3. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  4. 1. Коллективные субъекты административного права: понятие и виды
  5. ПЛИТЫ С РАЗМЕРАМИ В ПЛАНЕ 800X600 ММ
  6. Тема 6. Коллективные субъектыадминистративного права
  7. 2.2 Технология получения КМ на основе алюминия (Al-3масс.%Ni- 1масс.%Cu)
  8. 1. Правовые основы системы образования
  9. 3. Основы административно-правового статуса граждан
  10. Тема 18. Правовые основы управления образованием
  11. II ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДА ИНТЕРПОЛЯЦИИ ПО КОЭФФИЦИЕНТУ ФОРМЫ
  12. ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ РАЗВИТИЯ ПЕРСОНАЛЬНЫХ ФИНАНСОВ
  13. 1.7. Влияние OA на характеристики оптических, оптоэлектронных и лазерных устройств на основе кристаллов.
  14. 34. Наем жилого помещения на коммерческой основе: юридическая характеристика, элементы, срок, отличие от договора социального найма.
  15. Глава I. ТЕОРЕТИЧЕСКИЕ И ЭМПИРИЧЕСКИЕ ОСНОВЫ ВКЛЮЧЕНИЯ ЛИЧНОСТНЫХ РЕЗУЛЬТАТОВ ОБУЧЕНИЯ В СОСТАВЕ СОДЕРЖАНИЯ ОБРАЗОВАНИЯ