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

Страницы:
1  2 

УДК 681.518

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ПОСТРОЕНИЯ ИДЕНТИФИЦИРУЩИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ ЦИФРОВЫХ СХЕМ С ПАМЯТЬЮ

Иванов Д.Е., к.т.н., с.н.с., доцент Институт Прикладной Математики и Механики НАН Украины E-mail: ivanov@iamm.ac.donetsk.ua

Abstract

In the life cycle of development of digital circuits developer need to solve the several problems of building of input sequences: test, initializing and verifying of equivalence. In this paper a generalized approach to solving this problem is presented. It based on the genetic algorithm and avoids some problems that are intrinsic to the traditional deterministic methods.

1. Введение.

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

Для всех указанных выше задач построения входных последовательностей в своё время зарубежными и отечественными авторами были предложены детерминированные и псевдослучайные алгоритмы их решения. Для задачи построения тестовых последовательностей разработаны структурные методы, являющиеся расширением для последовательностных схем метода ветвей и границ [1], методы, основанные на символьном моделировании [2], а также псевдослучайные методы [3].

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

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

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

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

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

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

памяти

Рис.1. Модель синхронной последовательностной схемы.

2. Формальная модель и постановка задач.

В качестве модели в данной работе используются синхронные последовательностные схемы (рис.1). В данной модели схема представляется в виде комбинационного блока (в свою очередь состоящего из нескольких функциональных комбинационных блоков, КФБ) и блока памяти, который состоит из D-триггеров. Далее также будем использовать следующие обозначения: #Вх - число внешних входов схемы, размерность вектора v; #Вых - число внешних выходов схемы, размерность вектора Y; #Тр -число элементов состояния (D-триггеров) схемы, размерность вектора T .

Вектор   v   -   упорядоченное множество двоичных значений, которое подаётся на вход цифровой схемы в определённый такт времени. Последовательность si заданной длины li - упорядоченное множество из li

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

j ( j = 0,...,l -1).

При моделировании используется преобразование синхронной последовательностной схемы в псевдокомбинационный эквивалент с дальнейшим его итеративным моделированием в последовательные такты времени. Для такого преобразования удаляют элементы состояний. Входы элементов состояний (вектор Ti на рис.1) при этом называются

псевдовыходами, а их выходы (вектор Ti-1 на рис.1) - псевдовыходами.

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

момента времени i , на псевдовходы подаются значения псевдовыходов схемы в предыдущий такт времени Ti-1 , после чего путём моделирования комбинационной части

схемы для такта времени  i   формируются выходные сигналы схемы  Yi   и сигналы

псевдовыходов Ti .

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

1) Построение тестовых последовательностей.

Пусть задано исправное устройство A0 и конечное множество его неисправных

модификаций A = {A1, A2,..., An}, и A0 Ф Ai для i є 1,n . Тестом, проверяющим заданную неисправность, назовём такую входную последовательность s, выходные реакции на которую устройств A0 и Ai различны. Тестом, проверяющим все неисправности множества A, называется такая входная последовательность, которая является проверяющей для всех Ai є A. Отметим, что для проверки того факта, что последовательность s является проверяющей, необходимо моделирование работы n + 1-й схемы: одна исправная схема и n схем с неисправностями. Для моделирования работы неисправных схем из множества A необходимо выбрать класс модельных неисправностей. Традиционно мы используем класс одиночных константных Fconst (const0 и const1 ) неисправностей для всех линий схемы. Также для уменьшения времени работы алгоритмов класс неисправностей сжимается с учётом их эквивалентности [11] с получением сжатого класса неисправностей Fconst. Тогда

A

Отметим   здесь   также,   что   в   рассматриваемой   постановке внутреннее

представление устройства A0 и всех элементов множества A в виде логической сети одинаково.

В качестве меры качества тестовой последовательности выбирается полнота теста: отношение числа проверенных неисправностей m к общему числу неисправностей n = |A|:

P = m -100% (1) n

2) Построение инициализирующих последовательностей

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

Дадим более формальное определение. Пусть  Q  - множество всех состояний

последовательностной схемы, тогда Q = {0,1, X}#Тр (0,1,X - элементы трёхзначного алфавита моделирования схемы). Пусть S - множество всех возможных определённых состояний схемы, состоящей из #Тр триггеров: S = {0,1}#Тр. Пусть также £ - множество всех возможных входных последовательностей si. Очевидно также, что для выбранного трёхзначного моделирования S d £ . Пусть x є Q начальное неопределённое состояние. Функция F : Q х £ — Q обозначает все состояния, достижимые схемой при поступлении на её вход последовательностей из £ при использовании трёхзначного алфавита моделирования. Тогда, некоторая последовательность s є £ называется инициализирующей для заданной схемы, если в финальном состоянии q = F (x, s) все состояния определены, т.е. q є S.

3) Построение последовательностей, верифицирующих эквивалентность схем.

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

Формально постановка задачи выглядит следующим образом. Заданы две цифровые схемы A0 и A1. Необходимо построить такую входную последовательность s є £, выходные

реакции на которую схем A0 и A1 различны.

Отметим разницу с постановкой задачи в случае 1). При построении тестовых последовательностей предполагается, что логическая сеть, представляющая внутреннююструктуру A0 и элементов из A идентичны. В данной же постановке задачи схема A1

получена результате некоторой оптимизации внутренней структуры схемы A0 , т.е. вообще

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

3. Общая схема генетического алгоритма.

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

Общим для всех трёх задач является поиск некоторой входной последовательности, обладающей заданным свойством. Исходя из этого, выбирается следующее кодирование особей и популяций (рис.2). Число бит в каждом двоичном наборе (ширина последовательности) соответствует числу входов схемы (#Вх) и является неизменной величиной в алгоритме. Каждый входной набор соответствует одному такту работы схемы, а число таких наборов, входящих в последовательность, определяет длину особи. Эта величина может изменяться в процессе работы алгоритма под воздействием генетических операторов. В качестве популяции выступает набор особей (входных последовательностей). В нашем алгоритме число особей в популяции (её размер) является величиной неизменной.

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

разрезание особей идёт по входам схемы. Для каждого столбца входной последовательности особи-потомка случайным образом определяется столбец, какого из родителей необходимо скопировать. При горизонтальном скрещивании, которое выполняется по входным наборам (тактам времени) в каждой особи-родителе выбирается одна точка скрещивания. Особь-потомок формируется из начала последовательности одного родителя и конца последовательности второго родителя.

Рис.2. Кодирование особей и популяций.

Рис.3. Операции скрещивания над двоичными последовательностями.

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

применяется три стандартных для данного типа алгоритмов вида мутации, выбор между которыми происходит случайно: а) мутация одиночного бита (каждый бит в последовательностях-потомках может изменить своё значение с вероятностью 0.5%); б) добавление вектора (в случайную позицию в последовательности вставляется случайным образом сгенерированный вектор, что позволяет вводить и рассматривать тестовые последовательности с большей длиной); в) удаление вектора (из случайно выбранной позиции удаляется вектор, если он был несущественным, то оценочная функция всей последовательности не должна уменьшится).

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

4. Построение фитнесс-функций.

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

Генетический_алгоритм(Схема(ы),РазмерПопуляции,Число итераций) {

// подготовка начальной популяции ПостроитьНачальнуюПопуляцию(); ОценитьОсобей(НачальнаяПопуляция); НомерПопуляции=0;

Пока( не_достигнут_критерий_остановки ) {

НоваяПозиция=0;

Для(  i=0  ;  і<РазмерПопуляции ; {

ОперацияВыбора(РодительА,   РодительБ); Если (  rand()   < Pc )

ОперацияСкрещивания(РодительА,   РодительБ, Потомок); Если (  rand()   < Pm )

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

}

ОценитьОсобей( ПромежуточнаяПопуляция); ПостроитьНовуюПопуляцию( РазмерПопуляции); НомерПопуляции++;

}

СоздатьОтчёт();

}

Рис.4. Псевдокод основного цикл генетического алгоритма.

функции и способе её вычисления. В статье не рассматриваются алгоритмы моделирования работы цифровых схем, поскольку они являются отдельной большой отраслью научных исследования. Отметим, однако, что авторы ранее также проводили исследования в данном направлении [13].

Рассмотрим построение фитнесс-функций, основанных на моделировании для каждой постановки задачи.

1) Построение тестовых последовательностей.

Фитнесс-функция в данном случае имеет вид:

i=dnuna

H (s, f) = £ H * h(vl, f) (2)

i=1

где    s-анализируемая    последовательность;     vi     -    вектор    из рассматриваемой

последовательности, i - позиция вектора в последовательности, f є Fconst - заданная

неисправность, H - предварительно заданная константа в диапазоне 0 < H <= 1, благодаря которой предпочтение отдаётся более коротким последовательностям.

Функция h(v, f) в свою очередь определяет качество отдельного входного вектора v при моделировании в присутствии неисправности f:

h(v, f) = f (v, f) + c1 * f (v, f) = n1 + c1 - n2 (3) где v - текущий входной набор, c1 - константа нормирования, равная отношению числа вентилей   схемы   к  числу   триггеров;   f1(v, f)   и   f2(v, f)   эвристические функции, определяющие:

Страницы:
1  2 


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

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

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

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

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

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