Д Е Иванов - Генетический алгоритм оптимизации рассеивания тепловой энергии входных тестовых последовательностей - страница 1

Страницы:
1  2 

УДК 681.518

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

Иванов Д.Е., к.т.н., с.н.с., доцент, Институт Прикладной Математики и

Механики НАН Украины, E-mail: ivanov@iamm.ac.donetsk.ua

Abstract

In this paper a new approach for solving the problem of the optimization of the power dissipation under test sequence application is proposed. This approach is based on the redundancy of the test sequences and consists of the steps: redundant test generation, evaluating power dissipation for generated test sequences and construction of the subset of sequences with optimal parameters. The last stage is based on the genetic algorithm. Also we give the results of the computer experiments on the ISCAS-89 benchmark circuits that show the effectiveness of the proposed approach.

1. Введение

Широкое распространение для решения различных задач технической диагностики получили генетические алгоритмы (ГА) [1-2]. Это связано с тем фактом, что классические детерминированные методы решения оказываются неэффективными в условиях продолжающегося роста размерности дизайна цифровых схем. В частности, ГА эффективно применяются при решении задача построения входных идентифицирующих последовательностей цифровых устройств (ЦУ): тестовых [3-4], инициализирующих [5] и последовательностей, проверяющих эквивалентность [6].

Основным недостатком классических методов, которые основаны на преобразовании булевого представления схемы [7] или построения дерева решения [8], является переполнение памяти, что делает их практически неприменимыми к реальному размеру современных цифровых устройств. Это связано с тем, что полное представление решения в памяти инструментальной ЭВМ невозможно из-за размера дерева решений, которое в свою очередь определяется числом элементов состояний в ЦУ. ГА сумели обойти данное ограничение благодаря тому, что они не строят решение в явном виде. Эта задача, фактически, заменена на две другие: моделирование и основанная на нём оценка качества потенциального решения. При этом для задач построения входных последовательностей ГА представляются как направленные стохастические методы поиска решений, основанные на моделировании. Для оценки потенциальных решений используются как алгоритмы исправного моделирования, так и алгоритмы моделирования с неисправностями. Задача моделирования считается решённой для последовательностных схем. Классическим инструментом, применяемым для этих целей, является алгоритм моделирования, предложенный в [9], а также его различные модификации [10-11].

Недостатком алгоритмов построения входных последовательностей, которые основаны на ГА, является существенно большая длина получаемых решений в сравнении с детерминированными подходами [12].

Применение ГА не ограничивается лишь только построением входных идентифицирующих последовательностей. Большое количество задач технической диагностики могут быть решены с помощью комбинаторного перебора. Размерность такихзадач велика, поэтому эффективно решать их могут генетические алгоритмы, поскольку они обладают наилучшими нелокальными поисковыми свойствами [2].

В последнее время актуальность приобретает цифровая техника, которая обладает минимальным потреблением электрической энергии. Данное требование обусловлено как потребительскими предпочтениями рынка электроники, так и общими усилиями человечества к снижению потребления любого вида энергии. С другой стороны, потребление энергии во время тестирования существенно выше, чем при обычной работе ЦУ [13], поэтому режим тестирования является критическим с этой точки зрения.

Для решения задачи минимизации потребления энергии во время приложения теста предложено несколько подходов. Например, в [14] для этих целей адаптируется известный алгоритм PODEM. При этом присвоение значений на неопределённых линиях происходит таким образом, чтобы минимизировать число событий. В работе [15] предложен метод минимизации рассевания тепла для заданного теста, что достигается упорядочиванием входных наборов.

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

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

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

2. Общий подход решения задачи

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

Целью работы является разработка алгоритма, который строит входные тестовые последовательности с минимальным рассеиванием тепла.

Решение указанной задачи осуществляется в три этапа:

- генерация избыточных по покрытию неисправностей входных последовательностей;

- оценка качества решения задачи для каждой из таких последовательностей;

- поиск оптимального в смысле целей задачи подмножества входных последовательностей.

Первые два этапа являются подготовительными, а третий является задачей комбинаторной оптимизации и решается в нашем подходе с помощью ГА.

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

Определение 1. Неисправность f є Fconst обнаруживается (проверяется) заданной последовательностью S = {s1,s2r..,sl} с избыточностью r, если существует не менее чем r подпоследовательностей s1,s2,...,sl1 є S, где l1 > r, таких, что каждая из них проверяет неисправность f . При этом r называется фактором избыточности. Здесь Fconst - сжатое по эквивалентности множество одиночных константных неисправностей.

Определение 2. Входная тестовая последовательность sex обладает полной избыточностью r , если каждая неисправность класса Fconst проверяется данной последовательностью не менее r раз.

Определение 3. Избыточная полнота последовательности sex   при избыточности r

равна

Pr (sex) = i~mr і ,   где mr F

r const]

Fconst (sex)

число неисправностей из множества Fc

const

которые проверяются не менее r раз заданной входной последовательностью.

Этап 1 решения задачи заключается в построении входной последовательности (набора подпоследовательностей) S = {s1,s2,...,sl}, которая обладает требуемой избыточной полнотой при фиксированной избыточности r . При этом для каждой фиксированной неисправности из F~cronst(sex) гарантируется существование не менее r входных подпоследовательностей, принадлежащих S таких, что каждая из них обнаруживает данную неисправность. Гарантирование избыточности для некоторой неисправности позволяет в дальнейшем в зависимости от целей задачи выбирать в качестве окончательного решения ту или иную из последовательностей.

Решение задачи построения избыточной тестовой последовательности возможно путём адаптации практически любого генератора тестов для последовательностных схем. Мы адаптировали для этих целей генетический алгоритм построения тестов, разработанный ранее авторами [4]. В начальном варианте алгоритма неисправность удаляется из общего списка непроверенных неисправностей сразу, когда будет обнаружена очередной строящейся последовательностью. В модифицированном варианте алгоритма неисправность будет вычеркнута из списка целевых неисправностей в том случае, если уже обнаружена r раз, где r - фактор избыточности.

Этап 2 заключается в предварительной оценке подпоследовательностей, которые входят в S : для каждой подпоследовательности si є S вычисляется числовая оценка E(si), которая показывает рассеивание тепловой энергии при моделировании работы схемы на заданной входной последовательности. Задача фактически заключается в моделировании работы схемы на заданной входной последовательности и получении на его основании необходимых данных.

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

Известно [16], что для КМОП технологии рассеиваемая мощность для заданной входной последовательности sex определяется выражением

E(sex) = 0,5 • V2 C f A(sex) (1) где: V - напряжение работы схемы, C - физическая ёмкость на выходе вентиля, f -частота работы схемы, A(sex) - число событий при моделировании на заданной входной последовательности.

Таким образом, для оценки рассеиваемой тепловой мощности с точностью до постоянного коэффициента нам необходимо вычислить параметр E(sex) , который в свою очередь имеет следующее представление:

A(sex) = Z Z

, (2)

i=1 g

где:

L - длина входной последовательности (число входных наборов), а активность вентиля определяется выражением

Ag     1% еслиeыxод єєншшія g изменился при моделироeании на наборе с номером i; (3) g    [0, e проттном случае.

Видно, что рассеиваемая мощность прямо пропорциональна числу событий, причём все остальные переменные являются фиксированными для заданного режима работы схемы. Произвести вычисление параметра A(sex) позволяет сделать любой алгоритм событийного моделирования работы неисправных схем. Авторами для данной задачи описанный ранее алгоритм [11] с нулевыми задержками распространения сигнала.

3. Генетический алгоритм выбора множества подпоследовательностей.

В данном разделе мы подробно опишем алгоритм решения задачи третьего этапа. Он основан на генетическом алгоритме как средстве комбинаторной оптимизации.

Этап 3 заключается в выборе подмножества последовательностей S' с S такого, что выполняются два следующих условия:

P(S') = P(S), (4)

и

E(S') ч min. (5) Рассмотрим   пример.   Пусть   для   некоторой   схемы   множество поверяемых

неисправностей     Fconst ={f1, f2,..., f10},     тестовая     последовательность     S = {s1, s2,..., s6}.

Подпоследовательности si, i = 1,6 имеют следующие характеристики:

s1 : рассеиваемая тепловая мощность 45, проверяемые неисправности: 1, 3, 5, 7, 9, 10;

s2 : рассеиваемая тепловая мощность 15, проверяемые неисправности: 1, 3, 5, 10;

s3 : рассеиваемая тепловая мощность 13, проверяемые неисправности: 2, 4, 6;

s4 : рассеиваемая тепловая мощность 30, проверяемые неисправности: 1, 2, 5, 7, 8, 10;

s5 : рассеиваемая тепловая мощность 10, проверяемые неисправности: 6, 7, 8, 10;

S6 : рассеиваемая тепловая мощность 15, проверяемые неисправности: 1, 2, 8, 9, 10;

Пусть в качестве возможных решений выступают следующие подмножества S :

51 = {s1,s3,s5} с S, S2 = {s1,s3,s6} с S, S3 = {s2,s3,s5} с S и S4 = {s1,s3,s4,s6} с S. Рассчитаем характеристики данных последовательностей:

S1: рассеиваемая тепловая мощность 68, полнота теста P(S1) = 100%;

52 : рассеиваемая тепловая мощность 73, полнота теста P(S2) = 100%; S3: рассеиваемая тепловая мощность 38, полнота теста P(S3) = 90%; S4 : рассеиваемая тепловая мощность 103, полнота теста P(S1) = 100%;

Из расчётов видно, что из множества потенциальных решений сразу необходимо исключить набор S3 , поскольку он обладает худшими тестовыми свойствами относительно других наборов и не обеспечивает выполнения первого из условий. Из наборов с наилучшими тестовыми свойствами необходимо выбрать тот, который обладает наименьшим параметром рассеивания, т.е. S1. Также из примера видно, что набор S4 является избыточным, и из него без потери полноты можно исключить либо последовательность s4 (рассеивание тепла = 73), либо последовательность s6 (рассеивание тепла = 88). Хотя в этих случаях полнота теста останется равной 100%, параметррассеивания мощности окажется больше, чем у других наборов, и данное множество также не будет выбрано в качестве оптимального.

Оценим практическую сложность задачи. Если входная последовательность S состоит из n подпоследовательностей, то число возможных подмножеств 2n . Например для контрольной схемы средней размерности s1488 из каталога ISCAS-89 на этапе 1 сгенерирована последовательность S , которая состоит из 356 подпоследовательностей, т.е. n=356. В этом случае число возможных множеств подпоследовательностей будет 2n = 2356 ~ 1,47e107. Перебор такого числа вариантов является нереальным для современных рабочих станций. Поэтому для решения данной задачи предлагается использовать генетический алгоритм.

Известно [2], что для построения генетического алгоритма необходимо задать его компоненты: вид особей и популяций, оценочную функцию, генетические операции. Авторы неоднократно описывали сам генетический алгоритм и его применение к решению задач диагностики [4-6], поэтому здесь для краткости изложения его описание опущено. Ограничимся только описанием компонент, которые необходимы для понимания сути описываемого здесь алгоритма.

В качестве особи в предлагаемом алгоритме выступает множество номеров подпоследовательностей из S . Номера в разных особях изменяются в ходе эволюции, также как и их число в различных особях. Мы не учитываем порядок номеров в особи.

Операция скрещивания выполняется над двумя родителями и порождает одного потомка. При этом число номеров подпоследовательностей в нём будет равно n/2, где n -длина первого родителя. В список потока включаются следующие номера подпоследовательностей: первый n/2 случайно копируются из первого родителя, оставшиеся - из второго.

Используются три «классические» операции мутации для множеств: обмен элементами, удаление элемента и добавление случайного элемента. При этом выбор между типами операций мутации происходит также случайно.

Вид оценочной функции существенно влияет на поисковые свойства всего алгоритма, а также на скорость его работы. Работа ГА по выбору оптимального подмножества последовательностей состоит из двух фаз, каждой из которых соответствует своя оценочная функция.

В первой фазе из множества S выбираются такие подмножества, для каждого из которых выполнено условие P(S') = P(S), т.е. подпоследовательности, входящие в множество S' должны обнаруживать все те неисправности, которые обнаруживают последовательности из S . Таким образом цель первой фазы ГА - увеличение показателя полноты теста для всех особей в популяции до уровня P(S) . Для особи с номером i оценочная функция будет иметь

вид:

Fi = P(Si) - P(S). (6) После того как будет выполнено условие (4) для всех особей в популяции, ГА переходит в фазу 2, целью которой является уменьшение рассеивания тепла для каждого подмножества, но без потери тестовых свойств. При этом, если в результате генетических операций (скрещивание и мутация) будут построены особи, которые не удовлетворяют условию (4), то они не рассматриваются далее. Таким образом, для фазы 2 ГА в качестве оценочной функции выступает выражение:

Fi = Emax Ei . (7)

где Emax - показатель рассеивания тепла для множества S .

При построении новой популяции используется стратегия элитизма.

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

Страницы:
1  2 


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

Д Е Иванов - Взаимодействие компонент в распределённых генетических алгоритмах генерации тестов

Д Е Иванов - Генетические алгоритмы построения идентифицирущих последовательностей для цифровых схем с памятью

Д Е Иванов - Генетический алгоритм оптимизации рассеивания тепловой энергии входных тестовых последовательностей

Д Е Иванов - Генетический алгоритм построения диагностических последовательностей цифровых устройств

Д Е Иванов - Генетический подход проверки эквивалентности последовательностных схем