<<
>>

Стохастическое планирование СБИС

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

Планирование с учетом неопределенности — это проблема получения хорошей топологии, когда информация о размерах модулей не является полной. В этом разделе рассматривается подход к планированию с учетом неопределенности.

В традиционной проблеме планирования входными данными является набор модулей (блоков), их ширин и высот и информа­ция о соединениях. Строится такой топологический план, чтобы общая площадь или задержка или мощность или комбинация этих параметров была минимизирована [6.1]. Рассмотрим осо­бенности планирования с нечеткими данными.

Данные с нечеткостью состоят из списков распределения ширины Wi (1 ≤ i ≤ n) и списков распределения высоты Hi(1 ≤ i ≤ n), где n — число модулей. Необходимо построить план, причем такой, чтобы математическое ожидание площади описывающего прямоугольника (площади плана) было мини­мальным. Каждый список распределений содержит пары чисел: ширина (или высота) модуля и ее вероятность [6.15]:

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

В традиционном планировании, когда два блока с размерами (wi,hi) и (w2,h2) группируются по горизонтали в общий блок, размеры блока могут быть рассчитаны по следующим уравнени­ям:

Когда те же блоки (куски) группируются по вертикали, получаем Различная группировка модулей приводит к различным тополо­гическим планам.

Учет неопределенности при группировке по горизонтали мо­дуля 1, определяемого распределениями Hj и Hi, с модулем 2, определяемым распределениями W2 и H2, дает следующее рас­пределение ширины и высоты для модуля (1,2):

При группировке по вертикали:

Операцииназываемые соответственно сложени­

ем распределений и максимумом распределений, определяются следующим образом [6.15]:

В соответствии с уравнением (6.4) для того, чтобы найти сумму двух случайных переменных с распределениями Hj и W2, мы должны создать новое распределениеэлементы ко­

торого образуются в результате попарного «сложение» элементов из двух списков распределения.

«Сложение» двух элементов из

распределений W-и W2 выполняется посредством сложения их значений ширины (высоты) и перемножения их вероятностей. Если окажется, что некоторые элементы списков распределения W- ф W2 имеют одинаковое значение ширины (высоты), то они заменяются одним элементом с этим значением ширины (высоты) и с вероятностью, равной сумме вероятностей объединяемых элементов.

В качестве примера возьмем

W- = {(5,0.3), (7,0.5), (8,0.2)} и W2 = {(2,0.9), (3,0.1)}.

Когда мы объединяем их по горизонтали, результирующим распределением будет

W-,2 = {(5 + 2,0.3 • 0.9), (5 + 3,0.3 • 0.1), (7 + 3,0.5 • 0.1),

(7 + 2,0.5 • 0.9), (8 + 2,0.2 • 0.9), (8 + 3,0.2 • 0.1)} =

= {(7,0.27), (8,0.03), (9,0.45), {(10,0.05),

{(10,0.18), {(11,0.02)} =

= {(7,0.27), (8,0.03), (9,0.45), {(10,0.23), {(11,0.02)}.

Список распределений H- ф H2 состоит из элементов, кото­рые являются «максимумом» пар элементов двух списков распре­делений H- и H2. Значения ширина (высота) для «максимума» двух элементов — это максимум их значений. Вероятность «мак­симума» двух элементов вычисляется таким же способом, как и при выполнении операции сложение распределений. Уравнение (6.5) является формальном описанием операции максимума рас­пределений.

В качестве примера возьмем

H- = {(1,0.1), (2,0.2), (7,0.7)} и H2 = {(4,0.4), (6,0.6)}.

Если мы объединим их вертикально, результирующим рас­пределением будет

H-,2 = {(7,0.7 • 0.4), (7,0.7 • 0.6),

(4,0.4 • 0.1), (4,0.4 • 0.2), (6,0.6 • 0.1), (6,0.6 • 0.2)} =

= {(7, (0.28 + 0.42), (4, (0.04 + 0.08)), (6, (0.06 + 0.12))} =

= {(7, (0.7), (4, (0.12)), (6, (0.18))}.

С помощью этих выражений путем последовательной свертки блоков рассчитываются списки распределений ширины

и высоты

плана и их математическое ожидание MWo и MHo .

Если для построения плана используется n-арное дерево раз­резов, то при свертке производится группирование нескольких блоков вертикально или горизонтально в общий блок. Расчет распределений ширины и высоты общего блока производится путем последовательного выполнения операций сложения рас­пределений и максимума распределений.

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

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

Для оценки решения задачи планирования используются три оценки: минимальная, максимальная и ожидаемая.

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

При расчете максимальной оценки в качестве фиксированных значений ширины и высоты модуля выбирается максимальное значение ширины из списка ширин и максимальное значение высоты из списка высот.

5 В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев

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

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

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

Цель оптимизации при решении задачи нечеткого планиро­вания заключается в минимизации математического ожидания площади описывающего прямоугольного плана S = MWo * MHo. Критерий оптимизации F = S.

При планировании с учетом неопределенности распределения ширины и высоты модулей фиксированы. Можно изменять ори­ентацию модулей. В этом случае для заданного дерева разрезов отыскиваются ориентации модулей, обеспечивающие при свертке минимальные значения показателя F

6.4.

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

Еще по теме Стохастическое планирование СБИС:

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