Д Е Иванов, Р Зуауи - Алгоритм симуляции отжига оптимизации рассеивания тепла диагностических тестов - страница 1

Страницы:
1  2 

УДК 681.518

1Д.Е. ИВАНОВ, 2Р. ЗУАУИ

1 Институт прикладной математики и механики НАН Украины, Донецк Донецкий национальный технический университет, Донецк

АЛГОРИТМ СИМУЛЯЦИИ ОТЖИГА ОПТИМИЗАЦИИ РАССЕИВАНИЯ ТЕПЛА ДИАГНОСТИЧЕСКИХ ТЕСТОВ

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

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

Введение

Требования рынка электроники заставляют производителей выпускать продукцию с минималь­ным потреблением электрической энергии, что впи­сывается в современную тенденцию к снижению потребления человечеством любого вида энергии. Для цифровой техники известно [1], что пиковое потребление происходит во время стартового тести­рования, поскольку в этот момент задействована максимальная часть логики устройства. Наряду с полнотой теста и его длиной параметр рассеивания тепловой энергии является одной из наиболее часто применяемых метрик при оценке качества входных диагностических последовательностей.

Для решения задачи построения тестов с ми­нимальным рассеиванием тепла было предложено несколько подходов. Один из них - адаптация из­вестных алгоритмов, в которые включены дополни­тельные ограничения. Например, в [2] предложен такой генератор тестов на основе алгоритма PODEM: при этом присвоение значений на неопре­делённых линиях происходит таким образом, чтобы минимизировать число событий. В работе [3] те же цели достигаются за счёт упорядочивания входных векторов в заранее построенном тесте.

В последнее время для решения многих задач технической диагностики широкое применение на­шли недетерминированные методы, в частности, генетические алгоритмы [4-5]. Это связано с недос­татками классических методов, основанных на пре­образовании булевого представления схемы [6] или построения дерева решения [7], в которых происхо­дит переполнение памяти, что делает их практиче­ски неприменимыми к реальному размеру совре­менных цифровых устройств.

Авторами в последнее время активно изучается новая оптимизационная стратегия «симуляция от­жига» (СО). Будучи заимствованной из области ме­таллургии [8], она сохранила первоначальные тер­мины, однако была развита как оптимизационный подход в работе [9]. Сама стратегии является кон­цептуально более прозрачной и более простой в реализации в сравнении с генетическими алгорит­мами. Это связано с тем, что в ней эволюция (улуч­шение свойств по решению целевой задачи) проис­ходит для отдельно взятого потенциального реше­ния. Это избавляет алгоритм от громоздких проце­дур обработки и построения популяций. В качестве апробации оптимизационных свойств данной стра­тегии авторы уже построили на её основе одноуров­невый алгоритм для генерации инициализирующих последовательностей [10] и показали его эффектив­ность.

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

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

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

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

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

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

1. Генерация избыточных по покрытию неисправ­ностей входных последовательностей.

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

3. Поиск оптимального  подмножества входных последовательностей.

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

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

Определение. Неисправность f є Fconst обна­руживается (проверяется) заданной последователь­ностью S = {s\,52г",si} с избыточностью r, если существует не менее чем r подпоследовательностей S1,*2,---,sn є S, где 11 > r, таких, что каждая из них проверяет неисправность f . При этом r называет­ся фактором избыточности. Здесь Fconst - сжатое по

эквивалентности множество одиночных констант­ных неисправностей.

Определение. Входная тестовая последователь­ность і'вх обладает полной избыточностью r, если

каждая неисправность класса Fconst проверяется

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

Определение. Избыточная полнота последова­тельности і'вх при избыточности r равна

Pr (5вх) :

const

где mr

Fconst (sвх)

(1)

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

множества Fc

Этап 1 решения задачи заключается в по­строении входной последовательности (набора под­последовательностей) S = {sbS2,...,si}, которая об­ладает требуемой избыточной полнотой при фикси­рованной избыточности r .   При этом для каждой

фиксированной неисправности из FConst (s^) гаран­тируется существование не менее r входных под­последовательностей, принадлежащих S таких, что каждая из них обнаруживает данную неисправность. Гарантирование избыточности для некоторой неис­правности позволяет в дальнейшем в зависимости от целей задачи выбирать ту или иную из последова­тельностей.

Этап 2 заключается в вычислении оценки рас­сеивания тепла E(si) для каждой подпоследова­тельности s'j є S . Задача фактически заключается в

моделировании работы схемы на заданной входной последовательности и получении на его основании необходимых данных.

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

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

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

на заданной входной последовательности.

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

представление:

A(sex) = £ X 4 (3)

i=1

которые проверяются не менее r

раз заданной входной последовательностью.

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

4 =\0 (4)

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

2. Алгоритм симуляции отжига выбора множест­ва подпоследовательностей

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

P(S') = P(S), (5) E(S') min. (6) Рассмотрим пример, который раскрывает суть этапа. Пусть для некоторой схемы множество про­веряемых   неисправностей   Fconst = {fb /2,..., fw }, тестовая последовательность S = {f,S2,...,S6}, где

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

s1: E(s1) = 45, F1(s1) = {l,3,5,7,9,10}; S2: E(s2) = 15, F 1(s2) = {1,3,5,10}; s3 : E(s3) = 13, F1(s3) = {2,4,6}; s4 : E(s4) = 30 , F 1(s4) = {1,2,5,7,8,10}; s5: E(s5) = 10 , F 1(s5) = {6,7,8,10};

S6: E (s6) = 15, F 1(s6) = {1,2,8,9,10}.

Пусть в качестве возможных решений высту­пают следующие подмножества S : S1 =     S3,S5} с S , S2 =     S3,S6} с S ,

S3 = {S2,S3,S5} с S и S4 = {S1,S3,S4,с S. Рас­считаем характеристики данных последовательно­стей:

S1: E(S1)=68, P(S1)=100%; S2: E(S2) =73, P(S2)=100%; S3: E(S3)=38, P(S3)=90%; S4: E(S4)=103, P(S1)=100%.

Из расчётов видно, что из множества потенци­альных решений сразу необходимо исключить на­бор S3 , поскольку он обладает худшими тестовыми

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

Введём некоторые базовые понятия, которые необходимы для описания стратегии (алгоритма) симуляции отжига. Данная стратегия представляет собой итеративный алгоритм улучшения свойств некоторого потенциального решения - конфигура­ции, которое для шага алгоритма обозначается Ki.  С каждой конфигурацией  Кі соотносится

функция, которая показывает качество данной кон­фигурации с точки зрения решения задачи, и назы­вается функцией оценки: Сі = С(Кі). Также допол­нительно вводятся модифицирующие операции, которые позволяют для точки Кі строить окруже­ние - некоторое множество точек с изменёнными характеристиками. Вычисление функций оценки для точек из окружения может показать, что их качество ухудшилось по сравнению с исходной точкой. При­нимать такие ухудшения или отклонять показывает распределение температур {Ті}. Смысл построения данного распределения заключается в том, что при больших температурах вероятность принять худшие решения выше, чем при более низких. Выбор рас­пределения температур {Ті} задаёт скорость осты­вания субстанции и, таким образом, существенно влияет результаты поиска.

На основе этого дадим краткое описание алго­ритма симуляции отжига.

1. Алгоритм начинает работу с построения на­чальной   конфигурации   Кі = К1   и   её оценке

С = С(К1). Также для выбранного распределения температур выбирается начальная температура Ti = T. Следующие шаги алгоритма повторяются итеративно вплоть до нахождения решения на од­ном из них, либо до достижения верхней границы числа итераций.

2. Для текущей температуры Ti путём применения модифицирующих операций к текущёй конфигура­ции Кі строится её окружение, состоящее из N

конфигураций: ON = 0(Кі) = {К1, К2,..., }

3. Для каждой конфигурации К- из окружения ON вычисляется её оценка С- = С (К- ), а также параметр улучшения оценки АС- = С- - Сі, на ос­новании которого происходит/не происходит заме­щение текущёй конфигурации К :

К+1

К/ , если АС/ < 0;

К

с вероятностью (7) P = ехр(-АС/ / Щ), если АС/ > 0;

где k - константа Больцмана.

4. Изменяется счётчик итераций і = і +1, а также в соответствии с выбранным распределением темпе­ратур изменяется текущая температура:

T+1 = обновить(Т)

5. Переход к шагу 2.

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

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

Алгоритм делится на две фазы, в каждой из ко­торых применяется свой вид функции оценки. В первой фазе из множества S выбираются такие подмножества, для каждого из которых выполнено условие P(S') = P(S) , т.е. подпоследовательности, входящие в множество S' обнаруживают все те не­исправности, которые обнаруживают последова­тельности из S. Функция оценки при этом имеет вид:

Страницы:
1  2 


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

Д Е Иванов, Р Зуауи - Алгоритм симуляции отжига оптимизации рассеивания тепла диагностических тестов

Д Е Иванов, Р Зуауи - Алгоритм симуляции отжига построения тестов цифровых устройств

д Е Иванов, Р Зуауи - Верификация эквивалентности цифровых схем с использованием стратегии симуляции отжига

Д Е Иванов, Р Зуауи - Применение стратегии симуляции отжига для построения инициализирующих последовательностей цифровых схем

Д Е Иванов, Р Зуауи - Построение идентифицирующих последовательностей цифровых схем с использованием стратеги симуляции отжига