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

Страницы:
1  2 

УДК 681.518

Д.Е. Иванов, Р. Зуауи

АЛГОРИТМ СИМУЛЯЦИИ ОТЖИГА ПОСТРОЕНИЯ ТЕСТОВ ЦИФРОВЫХ УСТРОЙСТВ

Введение и постановка задачи. Тестирование цифровых схем на различных этапах жизненного цикла их проектирования остаётся одной из центральных задач в технической диагностике. Это связано с непрекращающимся ростом размерности современных схем. Тестирование состоит в подаче входных воздействий на внешние входы схемы и наблюдении внешних выходов. Различие в поведении эталонной схемы с текущей проверяемой, которое наблюдается как несовпадение сигналов на внешних выходах, показывает неисправность схемы. Трудность задачи связана с тем, что число схем, которые должны сравниваться с эталонной очень велико. Например, для обычно используемой модели одиночных константных неисправностей число таких схем будет 2 * N, где N - число линий в схеме. Существующие структурные алгоритмы [1] не дают приемлемых результатов для схем с числом вентилей более десяти тысяч и числом триггеров более тысячи.

Для поиска решений в сложных задачах поиска решений в последнее десятилетие стали применять недетеменированные алгоритмы, которые ищут субоптимальные решения. Одним из примеров такого подхода являются генетические алгоритмы [2]. Парадигма впервые предложена в [3]. Наиболее широко её применение в автоматизированном проектировании цифровых схем разрабатывается в политехническом университете г.Турина, Италия [4]. Генетические алгоритмы относятся к направленным случайным методам поиска. Преимущество их применения состоит как в прозрачности стратегии, так и в возможности работать со схемами большой размерности, для которых структурные методы не дают результата. Эта возможность появляется в связи с тем, что необходимая для построения тестов информация получается на основе моделирования поведения схем. Здесь применяется как моделирование работы исправных схем, так и схем с неисправностями. К недостаткам такого подхода можно отнести достаточно продолжительное время работы, что связанно именно с оценкой качества входных последовательностей, которая выполняется на основе моделирования.

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

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

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

Стратегия симуляции отжига. Стратегия симуляции отжига впервые была предложена Метрополисом в [7] для нахождения состояний группы молекул в остывающем слитке. Из данной статьи заимствованы все основные термины стратегии: начальная и конечная температура, скорость остывания, конфигурация и т.д. Только в 1983 году Кирпатриком в [5] было показано, что описанный подход может быть с успехом применён к задачам оптимизации в широком смысле. В частности, автор описывает примеры решения следующих задач автоматизированного проектирования: разбиения схемы на подсхемы, размещения чипов на плате, трассировка соединительных линий.

Таким образом, стратегия симуляции отжига является ещё более «молодой», чем генетические алгоритмы. Исследования в этой области ещё только начинаются и разработано относительно небольшое число приложений к практическим задачам. В основном это классические задачи комбинаторной оптимизации, которые носят иллюстративный характер, показывая саму возможность применения стратегии на практике. К ним относятся как упомянутые выше задачи, так и задача построения расписаний [8], задача коммивояжёра [9] и т.д..

Кратко опишем общий алгоритм стратегии симуляции отжига. Как и в генетических алгоритмах, применяется кодирование потенциальных решений в пространстве поиска. Закодированное решениеназывается конфигурацией K . Для оценки качества решения задачи в точке K задаётся функция оценки C(K). Математически задача формулируется как поиск оптимума функции оценки:

C(K) -- max. (1)

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

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

о( k )={k1, k 2,..., kot}.

Размер m окружения O(Kt) задаётся как параметр алгоритма. Каждая точка окружения K является небольшой модификацией текущей конфигурации K . Смысловая нагрузка оператора возмущения задаётся исходя из самой задачи. Далее необходимо вычислить оценку для каждой конфигурации из окружения O(K), i = 1, m . Если оценка конфигурации улучшилась C(K) > C(Ki), то происходит

замена текущей конфигурации на лучшую: Ki = Kt. Если же оценка ухудшилась, то принимать или не

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

P = exp(-(C(Ki) - C(Ki))/kTi), (2)

где k - константа Больцмана, Ti - текущая температура итерации. Алгоритм строится таким образом, чтобы с увеличением номера итерации вероятность P приёма ухудшенных конфигураций уменьшалась со временем. Для этого задаётся распределение температур по итерациям {Ti} , которое обычно заключается в постепенном уменьшении температуры. Таким образом, при большей температуре вероятность P будет больше, чем при низкой. Этот момент позволяет алгоритму СО избегать локальных максимумов и является аналогом мутации в генетических алгоритмах. Скорость уменьшения температуры также ключевой момент алгоритма и существенно влияет на поиск оптимума.

Общая схема алгоритма построения тестов. В качестве модели в алгоритме используется модель синхронных последовательностных схем [10]. В данной модели происходит преобразование схемы в комбинационный эквивалент путём удаления линий обратной связи. При этом входы элементов состояний, которые представлены D -триггерами, становятся псевдовыходами схемы, а их выходы -псевдовходами. Моделирование поведения такой схемы происходит итеративно по тактам модельного времени. Причём значения сигналов, которые сформировались на линиях внешних псевдовыходов, попадают на псевдовходы одновременно с подачей следующего входного набора (по тактам синхронизации).

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

- заранее не известна длина требуемой последовательности;

- влияние неисправности на поведение схемы сначала необходимо распространить на внешние псевдовыходы схемы;

- после этого влияние неисправности следует распространить на внешние выходы.

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

- в списке больше нет непроверенных неисправностей;

- время работы алгоритма превысило предварительно заданное значение;

- достигнуто заданное предельное число итераций алгоритма.

В начале очередной итерации алгоритм выбирает некоторую ещё не проверенную тестом неисправность - фаза 1 алгоритма. Данная неисправность будет служить в качестве целевой неисправности в фазе 2 алгоритма, в которой происходит вызов непосредственно процедуры симуляции отжига построения теста. Если неисправность обнаружена в фазе 2 некоторой последовательностью, то для данной последовательности выполняется дополнительное моделирование (фаза 3), цель которого заключается в проверке: обнаруживает ли данная последовательность ещё некоторые неисправностикроме целевой. После этого последовательность добавляется в тест. Если же в фазе 2 не удалось построить тестовую последовательность для неисправности /цел, то данная неисправность отмечается

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

СО построения тестов(схема) {

чтение описания схемы();

построение полного списка неисправностей  F (); while(  не достигнут критерий остановки() ) {

// псевдослучайная генерация - Фаза 1 алгоритма /цел =выбрать целевую неисправность из списка ( F );

if(   Un==NULL )   {  возврат };

иначе

{

// применение алгоритма СО - Фаза 2 алгоритма

smecm =вызов_СО_построения_теста (схема, /цеЛ , sакт );

if(   /цел   проверена последовательностью smecm ) {

// дополнительное моделирование - Фаза 3

моделирование с неисправностями (схема, smecm , F );

добавить_в_тест ( smecm ); }// конец if - вызов Фазы 3 алгоритма else {

отметить неисправность как непроверяемую ( /цел );

}// конец else - тест не построен }     // конец if - выбрана целевая неисправность }        // конец while - не достигнут критерий остановки } // конец алгоритма

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

Остановимся подробнее на описании фаз 1 и 3, представляющие верхний уровень алгоритма, а в следующем разделе мы опишем второй уровень (фаза 2), который является центральным.

В фазе 1 алгоритма выбирается некоторая неисправность-цель /цел.   Для этого происходит

итеративная случайная генерация входных последовательностей (конфигураций) Свп/тек с длиной L . Для каждой последовательности выполняется моделирование с неисправностями на полном списке ещё непроверенных неисправностей F. Если для некоторой последовательности Свп/тек в результате такого

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

становится основной для второго уровня алгоритма. Если же после просмотра всего списка неисправностей не обнаружено активных неисправностей, то длина последовательности L увеличивается и происходит переход к следующей итерации. Процедура возвратит признак невозможности найти целевую неисправность в том случае, когда счётчик итераций ЧислоПопыток достигнет максимального значения МАХЧислоПопыток, которое задаётся предварительно. Псевдокод данного фрагмента алгоритма приведён ниже.

Выбрать целевую неисправность из списка(F)

{

While( ЧислоПопыток < MAX ЧислоПопыток )

{

L=ОбновитьДлину();

Confm(!K =ПостроитьНачальнуюКонфигурацию ( L ); моделирование с неисправностями ( схема,   Confm(!K , F ); if(  обнаружены новые неисправности ) {

добавить_в_тест ( ConfmeK );

}

else {

if(  в   F  есть активизированная неисправность   fi ) {

return( = fi );

}     // конец if - есть активизированные неисправности }        // конец else - обнаружены новые неисправности } // конец while - по числу попыток

return NULL;   //целевая неисправность не выбрана } // конец процедуры

Заметим, что такое построение процедуры поиска целевой неисправности является очень эффективным в связке со вторым уровнем. Большая часть всех неисправностей обнаруживается именно в фазе 1.

Алгоритм симуляции отжига построения теста одной неисправности. Фаза 2 является основной в описываемом алгоритме. Именно здесь используется алгоритм симуляции отжига. Чтобы применить общую схему алгоритма СО для решения конкретной задачи необходимо дополнительно задать функцию оценки, операцию возмущения и расписание температур.

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

Как было сказано выше, оценка качества конфигурации основана на моделировании с неисправностями. Для некоторой входной последовательности s и фиксированной неисправности f4ejl

она имеет вид:

i=dnuHa

Cost(s, f4en) =  £ И * h(Vi, fm„), (3)

i=1

где И - предварительно заданная константа в диапазоне 0 < LH <= 1, благодаря которой предпочтение отдаётся более коротким последовательностям. Функция h(vi, f4ejl) определяет качество i -го вектора в

последовательности и использует информацию о различии поведения исправной и неисправной функций. Из-за краткости изложения мы не будем останавливаться на данном моменте. Подробно вычисление функций такого вида описано в [10].

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

Применяется линейное изменение температуры от Тнач до Ткон с шагом 1.

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

проверяющую последовательность smecm), а также активизирующая последовательность saKm. Получив

исходные данные, процедура в соответствии с алгоритмом СО итеративно для заданного ряда температур производит построение окружения с оценкой всех конфигураций, которые в него попадают. Псевдокод процедуры построения теста для одной неисправности представлен ниже.

СО_генерация_теста (схема, f4ejl , sat.m )

{

ConfmeK ~-

Т    =Т ;

Страницы:
1  2 


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

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

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

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

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

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