<<
>>

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

Множество модулей M = {mi| i = 1,2,...,n} с фиксирован­ными размерами, дерево разрезов D = {dj∙ | j = 1,2,... ,2n — 1} и ориентации модулей O = {oi|i = 1,2,...,n} однозначно опреде­ляют план, который строится с помощью процедуры свертки.

Пространство решений составляют решения, отличающиеся друг от друга значениями элементов множества O, задающими ориентацию модулей.

Процесс поиска в пространстве ре­шений представим в виде адаптив­ной системы, работающей в условиях неопределенности.

На каждом шаге работы адаптив­ной системы под действием адаптиру­

ющего воздействия осуществляется переход от одной вершины пространства к другой, т. е. выбор альтернативных значений эле­ментов множества O.

В качестве объектов адаптации будем рассматривать моду­ли mi. Каждый объект может быть только в одном из двух альтернативных состоянийСостояние объекта

адаптации соответствует выбранной альтернативе (ориентации): Ai1соответствует первой ориентации

Пусть для множества модулей M с фиксированными разме­рами задан некоторый первоначальный план, т. е. задано дерево разрезов, ориентация модулей; в соответствии с выбранными альтернативами произведена свертка областей и сформированы выражения для определения значений параметров ho и wo пря­моугольника R.

Для каждого miсредой будет множество взаимодействующих друг с другом и с miмодулей Mi= M∖mi. Состояние сре­ды определяется выбранными для всех модулей ориентациями. Оценка состояний объекта адаптации зависит как от состояния среды, так и от состояния объекта адаптации в среде.

Локальная цель объекта адаптации — принять такую ори­ентацию, при которой в состав расчетных выражений входит размер меньшей стороны модуля.

Глобальная цель коллектива объектов адаптации, т. е. мно­жества модулей M, — достичь такого состояния, при котором значение критерия F имеет минимальное значение.

Введем для оценки состояния объекта адаптации (т. е. моду­ля mi) в среде два параметра: (PJ, Py). Определим возможные значения этих параметров:

При значениях Py = 1 или Py = 1 предпочтительными будут те же альтернативы, что и при первом способе, так как их реа­лизация приводит или может привести к минимизации размеров области, а следовательно, и всего плана в целом.

Для реализации механизма адаптации каждому модулю mi ставится в соответствие автомат адаптации AAiс двумя груп­пами состояний {Ci1, C2}, соответствующих двум альтернативам Ai1и A2. Число состояний в группе задается параметром Qi, называемым глубиной памяти. На вход автомата адаптации AAi подается сигнал «поощрение» или «наказание» в зависимости от состояния объекта адаптации (модуля mi) в среде.

На рис. 6.7 показана граф-схема переходов автомата адаптации. Знаком (+) помечены переходы под действием сигнала «поощрение», знаком (—) помечены переходы под действием сигнала «наказание».

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

Рис.6.7. Граф-схема переходов автомата адаптации

Если предпочтительная альтернатива в соответствии со зна­чениями пары параметров (PXx, Py),совпадает с реализованной в данный момент альтернативой, то вырабатывается сигнал по­ощрения, в противном случае — сигнал наказания. Отметим, что в случае, когда пара параметров (Pχ, Py) имеет значение (0,0) или (1,1), предпочтительной альтернативы нет. Поэтому в случае (0,0) управляющий сигнал не вырабатывается вообще. А в случае (1,1) с вероятностью P вырабатывается сигнал нака­зания. Выработка сигнала наказания в такой ситуации способ­ствует выходу из локального оптимума. Конкретное значение P можно подобрать в результате экспериментальных исследований.

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

Таблица 6.1

Локальная цель каждого объекта адаптации (модуля mi) — достичь такого состояния, при котором предпочтительная аль­тернатива совпадает с реализованной.

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

На первом такте в соответствии с расчетными выражениями для определения размеров сторон woи hoпрямоугольника R,

для каждого модуля miопределяются значения пары параметров

На втором такте для каждого автомата адаптации в соот­ветствии со значениями пары параметров (P%., Py) и состоянием автомата адаптации (Ci2или Ci1), вырабатываются управляющие сигналы («поощрение» или «наказание»).

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

На четвертом такте в соответствии с состояниями автома­тов адаптации реализуются альтернативы для модулей mi,т. е. выбираются их соответствующие ориентации. Затем с помощью процедуры свертки строится план, определяются выражения для определения размеров параметров W0 и h0 и размеры всех обла­стей.

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

Algorithm ПЛАНИРОВАНИЕ КРИСТАЛЛА СБИС C МЕНЯЮЩЕЙСЯ ОРИЕНТАЦИЕЙ МОДУЛЯ

begin

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

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

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

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

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

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

};

end

В массиве параметры хранятся исходные данные, это опи­сание модулей (число, размеры и т.п.).

С помощью процедуры ГЕНЕРАЦИЯ (параметры) генериру­ется дерево разрезов D, информация о нем хранится в массиве дерево. Способы генерации дерева разрезов могут быть различ­ны. Это и случайная генерация, и генерация на основе анализа соотношения размеров модулей и т. п.

С помощью процедуры ВЫБОР_НАЧ_СОСТОЯН (парамет­ры) синтезируются автоматы адаптации и выбираются (как пра­

вило случайным образом) начальные состояния автоматов адап­тации. Результат работы процедуры заносится в массив состо- ян_аа.

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

Далее процедурой СВЕРТКА (дерево, ориент, па­раметры) строится план, формируются выражения для определения размеров параметров W0 и h0 и рассчитываются размеры всех областей. Этой же процедурой рассчитывается значение критерия оптимизации F. План с лучшим значением критерия Fзапоминается.

Параметру итерация присваивается значение числа итера­ций, которые будет выполнять алгоритм. Далее на каждой ите­рации реализуются четыре такта адаптивной системы.

Ha первом такте процедурой ОЦЕНКА (план, параметры) для каждого модуля miрассчитываются значения пары парамет­ров {Pχ, Py), которые заносятся в массив состоян_объект.

На втором такте процедурой УПАРВЛ (состоян_объект, ориент) вырабатываются управляющие сигналы («поощрение», «наказание»), которые заносятся в массив управл_сигнал.

На третьем такте процедурой ПЕРЕХОД (состоян_аа, управл_сигнал) осуществляются переходы в автоматах адаптации под действием управляющих сигналов.

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

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

6.5.

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

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

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