Д Е Иванов, Т А Васяева - Генетический алгоритм оценки пикового рассеивания тепла для больших интегральных схем - страница 1

Страницы:
1  2 

УДК 681.518

Иванов Д.Е., Васяева Т.А.

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ОЦЕНКИ ПИКОВОГО РАССЕИВАНИЯ ТЕПЛА ДЛЯ БОЛЬШИХ ИНТЕГРАЛЬНЫХ СХЕМ

Рассматривается задача оценки пикового рассеивания тепловой энергии для больших и сверхбольших интегральных схем, построенных по КМОП технологии. Задача сводится к построению двухтактной входной последова­тельности. Предложен генетический алгоритм решения задачи. Приводятся результаты машинных экспериментов на схемах международного каталога ISCAS-89.

Ключевые слова: цифровая схема, рассеивание тепла, генетический алго­ритм.

Введение.

Стремительное развитие КМОП-технологии существенно уменьшает нормы технологического процесс производства больших интегральных схем. При этом размеры транзисторов становятся всё меньше, позволяя размещать на одном кристалле сверхбольших интегральных схем (СБИС) всё большее их число. Современные СБИС часто используются в портативных устройствах: карманные калькуляторы, электронные часы, мпЗ-плэйеры и т.п. При разработ­ке таких устройств большое значение имеет параметр потребляемой энергии, что заставляет разрабатывать новые подходы в их проектировании [1].

При возникновении задачи уменьшения потребления энергии цифровы­ми схемами вначале были разработаны методы оценки рассеиваемой тепло­вой энергии для ЦУ при работе на заданной входной последовательности [Najm-Goel, Tsui-Monterio]. В основном эти методы для оценки данного пара­метра используют показатель активности вентилей при моделировании. Далее были разработаны методы, которые оценивают пиковое возможное потребле­ние заданного устройства [Devadas-Keutzer]. В работе проблема определения пикового рассеивания тепла в схеме сведена к задаче максимального покры­тия для многовыходной булевой функции, которая строится из логического описания схемы. Показано, что задача относится к NP-полным, для её решения предложен метод ветвей и границ. Метод работает для небольших схем: наи­большая представленная схема имела 733 логических элемента, а для реше­ния задачи потребовалось несколько часов машинного времени. Также данную задачу для комбинационных схем рассматривали в [Kriplani-Najm]. В работе [Manne-Prado] авторы исследовали данную задачу для последовательностных схем. Для устройства восстанавливался граф переходов и для каждого из них оценивался параметр рассеивания тепла. Задача в такой постановке оказа­лась чрезвычайно ресурсоёмкой. Например, для небольшой схемы s208 в гра­фе было около 71 миллиона переходов. Поэтому метод оказался неприемле­мым для обработки схем с большим числом элементов состояний. Наконец, метод, основанный на генерации тестов, предложен в [Wang-Roy]. Идея рабо­ты заключалась в попытке активировать те элементы схемы, которые имеют наибольшее количество последователей.

Постановка задачи.

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

Показатель рассеиваемой тепловой энергии при моделировании задан­ной входной последовательности sex существенно зависит от технологии фи-

X1

комбинационный блок

X2

Z2

комбинационный блок

Z1

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

Известно [Shen-Ghosh-92], что при реализации ЦУ по технологии КМОП рассеивание тепловой энергии делится на статическое и динамическое.

Статическое рассеивание энергии возникает вследствие токов утечки либо других паразитных токов и происходит постоянно во время работы уст­ройства. Уменьшение потери энергии вследствие статического рассеивания достигается усовершенствованием технологического процесс производства чипов. Однако непосредственно переключательная активность на статическое рассеивание не влияет.

Динамическое рассеивание тепла является следствием утечки токов при зарядке и разрядке конденсаторов во время переключения состояний логиче­ских вентилей.

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

В последовательностной схеме переключательная активность зависит как от начального её состояния, так и от прилагаемого в текущий момент вре­мени входного набора [Hsiao99]. При этом такая активность зависит от состоя­ния схемы в большей степени, поскольку число триггеров в схеме обычно су­щественно больше, чем число внешних входов. Математически такая зависи­мость выглядит как P(Z,X), где Z - начальное состояние схемы, X - текущий входной набор.

Однако такая оценка не является сколь-нибудь приемлемой, поскольку в ней совсем не учитывается значения сигналов (состояния) на внутренних ли­ниях в комбинационном блоке. Для того чтобы учесть данный фактор необхо­димо сначала произвести инициализацию схемы. Таким образом, мы приходимк необходимости при оценке рассеивания тепла за один такт учитывать два последовательных входных набора. При этом первый входной набор Xj необ­ходим для инициализации схемы, а второй набор X2 для получения переклю­чательной активности схемы. Учитывая, что применяется модель синхронных последовательностных схем, это приведёт к использованию двух копий комби­национного эквивалента схемы, как это показано на рис 1. При этом выходные реакции схемы нас, вообще говоря, не интересуют. Поясним работу схемы, изображённую на данном рисунке. Первоначально схема находится в полно­стью неопределённом состоянии, что при моделировании в трёхзначном ал­фавите соответствует наличию на всех линиях схемы значения u из алфавита E3. После записи начального состояния Zj и подачи первого входного набора Xj выполняется моделирование комбинационной части. При этом в соответст­вии с логикой схемы будут получены выходной набор Yj (для оценки рассеива­ния тепла не учитывается и не приведён на рисунке) и новое состояние схемы Z2 . Комбинационная часть при этом перейдёт в полностью определённое со­стояние, т.е. на её линиях будут присутствовать значения 0 и 1 из алфавита моделирования E3. Данное утверждение будет верно только для «правильно»

спроектированных схем, в которых отсутствует избыточная логика. Мы будем рассматривать только такой случай. Далее на следующем такте времени схема начинает работу из некоторого состояния Z2, получает на вход набор X2, вы­полняется моделирование комбинационной части и потребляемой энергии. Заметим, что выход Y2 , генерируемый схемой на данном такте, также не учи­тывается. В предлагаемой модели видно, что оценка потребления энергии происходит только для второго такта модельного времени. Это связано с тем, что первый такт необходим только для инициализации всех внутренних линий схемы. Также нет необходимости в параметры работы данной модели вклю­чать состояние Z2 , которое сформируется на триггерах после первого такта времени.

Таким образом, мы приходим к тому, что для оценки рассеивания тепла за один такт времени, необходимо учитывать тройку параметров P(Z1,X1,X2).

Такая модель служит для оценки рассеивания тепла на одном такте времени.

Для оценки пикового потребления за один такт времени необходимо мак­симизировать данный функционал:

Рассеивание тепла за один такт модельного времени при заданных па­раметрах схемы [Shen-Ghosh-92] и приложении входной последовательности

X определяется выражением:

P(Z1,X1,X2) -> max

(1)

P(X) = 0,5 • V2 C f A(X)

(2)

где:

V - напряжение работы схемы;

C - физическая ёмкость выхода вентиля;

f - частота работы схемы;

A(X) - переключательная активность схемы, т.е. число событий при модели­ровании на заданном входном наборе или последовательности.

Анализируя данное выражение видно, что первые три параметра зависят от технологических характеристик ЦУ. Более того, для реализованного по оп­ределённой технологии ЦУ вклад данных параметров в динамическое рассеи­вание тепла будет определяться некоторой константой. Только параметр A(X) определяется входной последовательностью, на которой работает ЦУ.

Таким образом, для оценки рассеиваемой тепловой мощности P(X) с точностью до постоянного коэффициента нам необходимо вычислить парамет­ра переключательной активности схемы A(X). Математически он задаётся следующим выражением:

A(X) = £ х 4, (3)

i=1 g

где: _

l - длина входной последовательности X (число входных наборов); Ag - активность вентиля g при работе на входном наборе с номером i. Активность вентиля определяется следующим образом:

i    fl, если выход вентиля g изменился;

Ag =\0 . (4)

[0, в противном случае.

Видно, что для вычисления параметра переключательной активности схемы A(X), необходимо выполнить моделирование работы ЦУ на заданной входной последовательности. В нашем случае для вычисления P(Z1,X1,X2) необходимо записать начальное состояние схемы Z1 , выполнить моделирова­ние на наборе X1 без подсчёта переключательной активности, после чего по­дать набор X2 и выполнить моделирование с оценкой параметра A(X2) . По­лученное значение с точностью до константы будет оценивать P(Z1,X1,X2).

Генетический алгоритм.

Для оценки пикового потребления энергии в схеме необходимо найти та­кую тройку объектов (Z1,X1,X2), которая максимизирует функционал (1). В об­щем случае данная задача носит переборный характер и является NP-полной. В последнее время широкое распространение для решения задач подобного рода получили генетические алгоритмы [Скобцов, Ивнов2008]. Мы также пред­лагаем для решения рассматриваемой задачи использовать ГА.

Будем строить ГА конструктивно, задавая его компоненты.

В качестве особи будем использовать двоичную последовательность. Одна такая последовательность кодирует сразу тройку объектов (Z1,X1,X2) (рис.2).

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

(3). Произвести вычисление параметра A(X) позволяет любой алгоритм собы­тийного моделирования работы цифровых схем. Для решения данной задачи использовался описанный ранее алгоритм [Иванов-Скобцов-Параллельное моделирование] с нулевыми задержками распространения сигнала.

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

ГА оценка пикового потребления(схема, параметры) {

ВводОписанияСхемы();

Популяция=ПостроениеНачальнойПопуляции();

ОценитьПопуляцию(Популяция);

пока( НеДостигнутКритерийОстановки() )

{

Позиция=0;

для(  i=0  ;  і<ЧислоОсобей ;  i++ ) {

Родитель1=ВыбратьОсобь(Популяция); Родитель2=ВыбратьОсобь(Популяция); Потомок=Скрещивание(Родитель 1,Родитель2); Потомок=Мутация(Потомок);

ДобавитьВПромежуточнуюПопуляцию(Потомок,Позиция); Позиция++;

}

Популяция=ПостроитьНовуюПопуляцию( Популяция, ПромежуточнаяПопуляция);

}

Решение=ВыборЛучшейОсоби(Популяция);

}

Экспериментальные данные.

При разработке генетических алгоритмов решения конкретной задачи важным является этап подбора эвристических констант. Это осуществляется на основании предварительных экспериментов. Мы не будем полностью опи­сывать данную фазу исследования, поскольку она является достаточно «тра­диционной». Для примера покажем выбор вероятности операции мутации. На рис.2 приведён график зависимости достигнутой оценки наилучшей особи от значения параметра вероятности мутации. Эксперименты проводились со схе­мой s1269, усреднение проводилось по 100 экспериментам. Видно, что в каче-стве параметра следует выбрать Рмут = 0,05 , поскольку экстремум функции со­ответствует данному значению. Другие значения эвристических констант со­ставили: Рскр = 0,99 , число особей в популяции = 100 , максимальное число по­колений = 100 , число поколений без улучшения оценки = 20 , замене новыми особями на одной итерации подвергается 80% популяции.

В качестве апробации эффективности предложенного алгоритма исполь­зовались схемы из международного каталога ISCAS-89 [ISCAS]. Численные результаты экспериментов приведены в табл.1. В колонке «генетический алго­ритм» приведены результаты работы предложенного алгоритма. Для сравне­ния его эффективности в колонке «случайный метод» даны результаты оценки при случайной генерации тройки 500 000 объектов (Z1,X1,X2). Результаты

обеих серий экспериментов содержат три колонки: «число событий» - параметр рассеивания тепла, который соответствует формуле (3); «вентильная актив­ность » - показывает среднее число переключений вентиля при приложении входного набора X2 , численно равен отношению параметра «число событий»

к числу элементов в схеме; «время работы» - показывает время выполнения соответствующего алгоритма.

Выводы

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

Страницы:
1  2 


Похожие статьи

Д Е Иванов, Т А Васяева - Генетический алгоритм оценки пикового рассеивания тепла для больших интегральных схем